wu :: forums « wu :: forums - 5 coins and 5 weighings » Welcome, Guest. Please Login or Register. Dec 16th, 2018, 8:42pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Icarus, towr, SMQ, Grimbal, ThudnBlunder, Eigenray, william wu)    5 coins and 5 weighings « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: 5 coins and 5 weighings  (Read 13506 times)
Altamira_64
Junior Member

Posts: 116
 5 coins and 5 weighings   « on: Jan 13th, 2012, 12:51pm » Quote Modify

We have 5 coins of identical shape and volume, but with different weights, 10, 20, 30 40 and 50 grams.
How can we determine the weight of each coin by using a balance scale and only in 5 weighings?
Just to clarify that we are not looking for the exact weight of each, but want to sort them by order of weight.
 « Last Edit: Jan 17th, 2012, 12:48pm by Altamira_64 » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13651
 Re: 5 coins and 5 weighings   « Reply #1 on: Jan 14th, 2012, 5:28am » Quote Modify

I could do it in seven, I think. But that's with limiting weighing to one coin/ball against another. I don't readily see how to improve that by weighing more of them at the same time.
If push came to shove, it'd be easy enough to have a computer do a brute force search for the answer, though. But 5 weighings is not a lot; there are 120 different orders for 5 coins, and distinguishing between them requires 7 bits of information; that's close to the maximum you can get from 5 weighings.
 « Last Edit: Jan 14th, 2012, 5:29am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
SWF
Uberpuzzler

Posts: 879
 Re: 5 coins and 5 weighings   « Reply #2 on: Jan 14th, 2012, 7:35am » Quote Modify

on Jan 13th, 2012, 12:51pm, Altamira_64 wrote:
 We have 5 coins of identical shape and volume, but with different weights, 10, 20, 30 40 and 50 grams. How can we determine the weight of each ball by using a balance scale and only in 5 weighings?

You ask to determine the weight of balls, but only give information pertaining to coins.

I would try starting with 2 vs. 2.  That way there are 3 possible results for the first weighing.
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7433
 Re: 5 coins and 5 weighings   « Reply #3 on: Jan 16th, 2012, 8:19am » Quote Modify

I think I wouldn't even need a scale to order the coins/balls by weight.
 IP Logged
Altamira_64
Junior Member

Posts: 116
 Re: 5 coins and 5 weighings   « Reply #4 on: Jan 17th, 2012, 12:50pm » Quote Modify

First of all, I made a mistake and was referring to balls instead of coins. I also changed the wording to make a clarification. See above.
 IP Logged
Altamira_64
Junior Member

Posts: 116
 Re: 5 coins and 5 weighings   « Reply #5 on: Jan 19th, 2012, 11:14am » Quote Modify

How come?
on Jan 16th, 2012, 8:19am, Grimbal wrote:
 I think I wouldn't even need a scale to order the coins/balls by weight.

 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13651
 Re: 5 coins and 5 weighings   « Reply #6 on: Jan 19th, 2012, 11:35am » Quote Modify

Drop them in water. The faster they sink, the heavier (higher density) they must be.
But that's not in the spirit of the problem..
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
aicoped
Junior Member

Gender:
Posts: 57
 Re: 5 coins and 5 weighings   « Reply #7 on: Jan 21st, 2012, 8:00am » Quote Modify

I don't see an elegant way to solve it, but I brute force was able to prove it possible if the first weighing of 2v2 was equal. I imagine similar logic could be used if side a weighed more or less than b but I ran out of time.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13651
 Re: 5 coins and 5 weighings   « Reply #8 on: Jan 21st, 2012, 10:45am » Quote Modify

So far I know that you can't do it with five pre-picked weighings; if it's possible at all, you'll need to make different choices depending on the results of earlier weighings. (Perhaps not surprising; but it is the easiest case to test.)

I've found a solution, but it's not pretty. I've also ruled out solutions starting with something other than starting with 2vs2 [/edit]
 « Last Edit: Jan 21st, 2012, 2:23pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
aicoped
Junior Member

Gender:
Posts: 57
 Re: 5 coins and 5 weighings   « Reply #9 on: Jan 21st, 2012, 3:23pm » Quote Modify

yes I agree. I was forced to do a ton of if then in my one case i solved for, and I stopped figuring the rest could be solved as well.
 IP Logged
Altamira_64
Junior Member

Posts: 116
 Re: 5 coins and 5 weighings   « Reply #10 on: Jan 22nd, 2012, 1:09am » Quote Modify

I started by weighing 2 vs 2, but we have 15 different possibilities:
1st plate     2nd plate
10+20=30,  30+40=70
10+20=30,  30+50=80
10+20=30,  40+50=90
10+30=40,  20+40=60
10+30=40,  20+50=70
10+30=40,  40+50=90
10+40=50,  20+30=50
10+40=50,  20+50=70
10+40=50,  30+50=80
20+30=50,  10+50=60
20+30=50,  40+50=90
10+50=60,  20+40=60
10+50=60,  30+40=70
20+40=60,  30+50=80
30+40=70,  20+50=70

In cases 7, 12 and 15 the scale balances,
but then what?
 « Last Edit: Jan 22nd, 2012, 1:15am by Altamira_64 » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13651
 Re: 5 coins and 5 weighings   output.txt « Reply #11 on: Jan 22nd, 2012, 1:59am » Quote Modify

If the a,b equal c,d, then in my solution the next weighing is a,b,c against c,d a,b,c against d,e, if they're not equal I weigh a,c against b,d.

(Note that if they're not equal, you can transform the < case to the > case by swapping the names for a,b and c,d; so there are ways to simplify the solution. I haven't really explored that yet, because my solution is not in a very useful format.)

Attached somewhat cleaned up solution.
Read "00112=" as first two balls in left pan (0), next two in right pan (1), last ball not on the scales (2), result of weighing: equal.[/edit]
 « Last Edit: Jan 30th, 2012, 10:15am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Altamira_64
Junior Member

Posts: 116
 Re: 5 coins and 5 weighings   « Reply #12 on: Jan 29th, 2012, 2:56am » Quote Modify

I don't quite understand your solution, although I trust it is correct!
In some cases (the "=" cases), you have 3 zeroes or 3 aces. How is this possible?

on Jan 22nd, 2012, 1:59am, towr wrote:
 If the a,b equal c,d, then in my solution the next weighing is a,b,c against c,d, if they're not equal I weigh a,c against b,d.   (Note that if they're not equal, you can transform the < case to the > case by swapping the names for a,b and c,d; so there are ways to simplify the solution. I haven't really explored that yet, because my solution is not in a very useful format.)   Attached somewhat cleaned up solution.   Read "00112=" as first two balls in left pan (0), next two in right pan (1), last ball not on the scales (2), result of weighing: equal.[/edit]

 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13651
 Re: 5 coins and 5 weighings   « Reply #13 on: Jan 29th, 2012, 7:38am » Quote Modify

I don't see any cases with three 0's or three 1's that have = as a result; that would have been a problem if it occurred since it's impossible.
Maybe it'll be clearer if I translate the solution to a more legible format, but that's a lot of work, so it may take a while.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13651
 Re: 5 coins and 5 weighings   5weighings1.pdf « Reply #14 on: Jan 29th, 2012, 11:04am » Quote Modify

I've attached a cleanup version of the solution I found. I also put in a few simplifications.

There are probably simpler solutions, because my program simply stopped at the first one, rather than looking for the simplest one.
Starting with AB vs CD followed by AC vs BD allows a bit more simplification, for starters.
 « Last Edit: Jan 30th, 2012, 1:25pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
rmsgrey
Uberpuzzler

Gender:
Posts: 2818
 Re: 5 coins and 5 weighings   « Reply #15 on: Jan 30th, 2012, 9:24am » Quote Modify

on Jan 22nd, 2012, 1:59am, towr wrote:
 If the a,b equal c,d, then in my solution the next weighing is a,b,c against c,d,

How do you weigh c on both sides at once? And how do you get any useful information out of proving that c has a positive weight? Or is this an obvious typo?
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13651
 Re: 5 coins and 5 weighings   « Reply #16 on: Jan 30th, 2012, 10:08am » Quote Modify

It's an obvious typo. Should be a,b,c vs d,e.
And I see I made a similar mistake in my last attachment.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Altamira_64
Junior Member

Posts: 116
 Re: 5 coins and 5 weighings   « Reply #17 on: Jan 30th, 2012, 12:44pm » Quote Modify

Great job towr!
However, I have a question:
As far as I can tell, all possible combinations of 3 coins vs 2 are 10 (10 20 30 vs 40 50 etc).
In all of these cases, we can have either < or >. We cannot have "=" with the given numbers 10, 20, 30, 40 and 50.
In your solution, you have two cases where you consider the "=" result.
One of them results to 43125 (which does not correspond to the A+C+D vs B+E)
and the other is the "=" after the 4th weighing (A+B+D vs C+E), which results to either "=" or "<", and the "=" then results to A+C+E vs B+D, giving us either 34521 or 25341.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13651
 Re: 5 coins and 5 weighings   « Reply #18 on: Jan 30th, 2012, 1:20pm » Quote Modify

Yup, those are another two errors that snuck in when I translated the output of my program into a more readable format. I've fixed them in the pdf now. There might be more errors in that image, though; so when in doubt check the original list.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Altamira_64
Junior Member

Posts: 116
 Re: 5 coins and 5 weighings   « Reply #19 on: Feb 1st, 2012, 9:28am » Quote Modify

Nice solution! I wish I had your patience! I gave up after the first weighing!

Thanks!
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7433
 Re: 5 coins and 5 weighings   « Reply #20 on: Feb 2nd, 2012, 9:10am » Quote Modify

Computers are very patient.
 IP Logged
brac37
Newbie

Gender:
Posts: 23
 Re: 5 coins and 5 weighings   « Reply #21 on: Apr 20th, 2012, 1:36pm » Quote Modify

Just a stupid question. If the weights are 10, 20, 30,40, 50, then you do not need a balance scale to order them. Can you also order them in five weightings if you only know that the weights are an arithmetical progression. In that case, each weighting must have the same number of coins on each scale. Probably not, but maybe it can be done in six weightings.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13651
 Re: 5 coins and 5 weighings   « Reply #22 on: May 26th, 2012, 3:32am » Quote Modify

on Apr 20th, 2012, 1:36pm, brac37 wrote:
 Just a stupid question. If the weights are 10, 20, 30,40, 50, then you do not need a balance scale to order them. Can you also order them in five weightings if you only know that the weights are an arithmetical progression. In that case, each weighting must have the same number of coins on each scale. Probably not, but maybe it can be done in six weightings.
Six doesn't seem to be enough, you need seven.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
jousha22
Newbie

Gender:
Posts: 1
 Re: 5 coins and 5 weighings   « Reply #23 on: Oct 20th, 2013, 11:42pm » Quote Modify

While you have a balance scale and 16 coins, 2 of which are counterfeit. The counterfeits weigh the same as each other, but this time you don't know whether they're light or heavy. Can you determine the counterfeits (as well as their comparative weight) in 5 weighings?
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board