wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 5 coins and 5 weighings
        
(Message started by: Altamira_64 on Jan 13^th, 2012, 12:51pm)

Title: 5 coins and 5 weighings
Post by Altamira_64 on Jan 13^th, 2012, 12:51pm

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.

Title: Re: 5 coins and 5 weighings
Post by towr on Jan 14^th, 2012, 5:28am

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.

Title: Re: 5 coins and 5 weighings
Post by SWF on Jan 14^th, 2012, 7:35am

on 01/13/12 at 12:51:25, 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.

Title: Re: 5 coins and 5 weighings
Post by Grimbal on Jan 16^th, 2012, 8:19am

I think I wouldn't even need a scale to order the coins/balls by weight.

Title: Re: 5 coins and 5 weighings
Post by Altamira_64 on Jan 17^th, 2012, 12:50pm

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.

Title: Re: 5 coins and 5 weighings
Post by Altamira_64 on Jan 19^th, 2012, 11:14am

How come?

on 01/16/12 at 08:19:11, Grimbal wrote:

I think I wouldn't even need a scale to order the coins/balls by weight.

Title: Re: 5 coins and 5 weighings
Post by towr on Jan 19^th, 2012, 11:35am

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..

Title: Re: 5 coins and 5 weighings
Post by aicoped on Jan 21^st, 2012, 8:00am

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.

Title: Re: 5 coins and 5 weighings
Post by towr on Jan 21^st, 2012, 10:45am

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.)

[edit]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]

Title: Re: 5 coins and 5 weighings
Post by aicoped on Jan 21^st, 2012, 3:23pm

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.

Title: Re: 5 coins and 5 weighings
Post by Altamira_64 on Jan 22^nd, 2012, 1:09am

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?

Title: Re: 5 coins and 5 weighings
Post by towr on Jan 22^nd, 2012, 1:59am

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.)

[edit]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]

Title: Re: 5 coins and 5 weighings
Post by Altamira_64 on Jan 29^th, 2012, 2:56am

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 01/22/12 at 01:59:21, 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.)

[edit]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]

Title: Re: 5 coins and 5 weighings
Post by towr on Jan 29^th, 2012, 7:38am

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.

Title: Re: 5 coins and 5 weighings
Post by towr on Jan 29^th, 2012, 11:04am

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.

Title: Re: 5 coins and 5 weighings
Post by rmsgrey on Jan 30^th, 2012, 9:24am

on 01/22/12 at 01:59:21, 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?

Title: Re: 5 coins and 5 weighings
Post by towr on Jan 30^th, 2012, 10:08am

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.

Title: Re: 5 coins and 5 weighings
Post by Altamira_64 on Jan 30^th, 2012, 12:44pm

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.

Title: Re: 5 coins and 5 weighings
Post by towr on Jan 30^th, 2012, 1:20pm

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.

Title: Re: 5 coins and 5 weighings
Post by Altamira_64 on Feb 1^st, 2012, 9:28am

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

Thanks!

Title: Re: 5 coins and 5 weighings
Post by Grimbal on Feb 2^nd, 2012, 9:10am

Computers are very patient.

Title: Re: 5 coins and 5 weighings
Post by brac37 on Apr 20^th, 2012, 1:36pm

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.

Title: Re: 5 coins and 5 weighings
Post by towr on May 26^th, 2012, 3:32am

on 04/20/12 at 13:36:35, brac37 wrote:

Six doesn't seem to be enough, you need seven.

Title: Re: 5 coins and 5 weighings
Post by jousha22 on Oct 20^th, 2013, 11:42pm

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?