wu :: forums - Print Page


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

        riddles >> hard >> A question from the Russian MO
        
(Message started by: wonderful on May 15^th, 2008, 2:04pm)

Title: A question from the Russian MO
Post by wonderful on May 15^th, 2008, 2:04pm

This question is from the Russial Math Olympia (2006-2007):

There are 9 identical looking coins. One of them is lighter. Also, there are 3 standard two-arm balances. One of them doesn't work properly; the other two work perfectly. It is unknown which balance works properly.

Can you find out the counterfeit coins in 4 weightings?

Have A Great Day!

Title: Re: A question from the Russian MO
Post by towr on May 15^th, 2008, 3:10pm

The balance that doesn't work properly, does it not do so in an expected way? I might buy that it give A=B when it's A>B or A<B; but should I also worry it may give A>B when it's A<B (or vice versa)?

Title: Re: A question from the Russian MO
Post by wonderful on May 15^th, 2008, 4:17pm

The broken balance works in unexpected (random) manner. It might give A>B, A<B, or A=B regardless of the true status of A & B.

Have A Great Day!

Title: Re: A question from the Russian MO
Post by Hippo on May 19^th, 2008, 10:13am

So noone answers ... [hide]number the coins 00 to 22 in ternary and measure on balance i coins with i-th digit 1 on the 1st(left) pan against coins with i-th digit 2 on the 2nd(right) pan. If you know the balances are OK the lighter coin is identified by the results. (i-th balance sets i-th digit to 0,1,2 for =,<,> results). Let such coin has number ab. Put a* on left pan of third balance and *b on right side of the balance (ab cannot be on both ... so put it nowhere).
Now
= means ab is the lighter coin (The digit in which the coin differs identifies the wrong balance and if it differs third balance is OK).
In other cases one of the balances gave wrong result.
< *b cannot be lighter means 2nd balance is OK and repeat the 1st weighting on it.
> a* cannot be lighter means 1st balance is OK and repeat the 2nd weighting on it.
[/hide]

on 05/19/08 at 18:19:53, wonderful wrote:

It is mentioned that only 2 people who participated in the Russian Math Olyimpia that year could solve this question.

I am surprised ... it seamed to me I must be much worse than in the age of 18, but some problems which looked unsolvable in that time are easier for me now. Russians had always very strong teams in IMO's. May be the math is not so interesting now for young students.
At least here in Czech the number of strong students in math decreases.

Title: Re: A question from the Russian MO
Post by wonderful on May 19^th, 2008, 6:19pm

Brillian Hippo! I like your solution which is very elegant. It is mentioned that only 2 people who participated in the Russian Math Olyimpia that year could solve this question.

Have A Great Day!

Title: Re: A question from the Russian MO
Post by Captain_Doubtful on Mar 31^st, 2009, 2:04pm

Hippo or wonderful:

Could you please explain the "elegant solution" a bit more? Perhaps it's the way it is worded, I didn't really understand the answer. This puzzle has been bothering me for ages. Thank you very much!

Title: Re: A question from the Russian MO
Post by Vondell on Apr 1^st, 2009, 9:24am

Here is a more workable solution.

[hide]1: Take 2 coins. It does not matter which 2.
Place them on either side of one of the scales. Once again, it does not matter which scale.
2: Put each coin on the other side of the same scale.
If it tips once and then balances, you have the broken scale.
If it tips twice in the same direction, you have the broken scale.
If it tips in each direction, you have a working scale and the lighter coin.
If it balances twice, you have a working scale and 2 equal coins.

Since you now know that if you were using the broken scale then you need to move to one of the others. Likewise, if you were using a working scale, then you don't need to move at all.[/hide]
To save myself from typing too much, I am going to assume that the rest of this answer is known from the classic riddle. If you do not, just post and someone, I'm sure, will post the rest.

Title: Re: A question from the Russian MO
Post by Hippo on Apr 1^st, 2009, 9:48am

Vondell: Even defected scale can return correct results so it can past the tests and later give wrong results.

on 03/31/09 at 14:04:46, Captain_Doubtful wrote:

I am sorry, I did best what I can. I hope someone else can translate it to better english.

Just some comments to the solution: First two measurements does not say anything individually as the scale can be broken. But as we know one of the two scales is OK the coins which were twice detected as OK must be OK. So only 5 coins are suspicious. One of them among wrong twice and 4 detected among wrong once (2 of them in first, 2 of them on second measurement).
Compare the pairs on third scale.
If equal, the 4 were detected OK by 2 diferent scales so the remaining one is defected.

If some pair seems to be lighter, we know the other pair was detected OK by 2 diferent scales so only 3 coins are suspected.
If we ignore coins we know are OK:
One scale said nothing, other said one coin is suspected, last said two other coins are suspected. Clearly one of the last two scales is broken.
Use the first one to detect the defected coin.

Title: Re: A question from the Russian MO
Post by Vondell on Apr 1^st, 2009, 11:36am

Without trying to argue, could you then put your solution in the 4 step process?

EX :Step 1:weigh coins a,b against c,d on scale 1
(explain results)
2:weigh coins...........

and so forth...

I still do not see how this solution works. At least
my brain refuses to recognize it, anyway. :P

Title: Re: A question from the Russian MO
Post by Hippo on Apr 1^st, 2009, 11:46am

I am lazy.

Put 10,11,12 on the left pan and 20,21,22 on the right pan of first scale. Remember result.

Put 01,11,21 on the left pan and 02,12,22 on the right pan of second scale. Remember result.

Now there are 9 possible results ... and I am lazy to continue with each of them as separate branch ...

Title: Re: A question from the Russian MO
Post by Immanuel_Bonfils on Apr 1^st, 2009, 6:37pm

Maybe a couple of resultant examples, from Hyppo's last post experiment, will help:

Symbolism: S1,S2,S3 = scales or balances;
= , < , > seems to balance, right pan heavier, left pan heavier, respectively.

1^st example:
S1< says that either 10,11,12 should be the counterfeit one and S2 = says that 11 and 12 wouldn't be, so the pair of measures would say that the fake should be 10.
Let's test it with a third experiment on S3, with (11, 12) on left and (00,20) on right pan.
S3 = says 10 is the fake an that agrees with S1 and S2 ,and we are done: 10 is the chosen one (since in the first version Hyppo put it as a kind of matrix), and all the three scales worked well (even the broken one).

S3 > says either 00 or 20 is the lighter coin, in contradiction with S1, so one of them is the broken scale and S2 works Ok. So test on it, 00 X 20.

S3 < gives equivalent argument with 11 and 12, but S2 is the bad scale and we can conclude using either S1 or S3.

2^ndexample:
S1 < and S2 < says that 11 is the coin we want. Let's se wat says S3, putting there (10,12) left and (01,21) right.
S3 = says , as the other two, that 11 is the coin, and finish.
S3 > says 01 or 21 is the lighter coin so S1 is the bad scale and S2 or S3 will do it Ok.
S3 < says 10 or 12 is the fake and S2 is the broken scale,leaving either S1 or S3 to test
10 X 12.

Title: Re: A question from the Russian MO
Post by Hippo on Apr 2^nd, 2009, 12:21am

on 04/01/09 at 18:37:57, Immanuel_Bonfils wrote:

S3 < gives equivalent argument with 11 and 12, but S2 is the bad scale and we can conclude using either S1 or S3.

Not exactly ... one of the S3 or S2 is the bad scale so use S1.

on 04/01/09 at 18:37:57, Immanuel_Bonfils wrote:

2^ndexample:

S3 > says 01 or 21 is the lighter coin so S1 is the bad scale and S2 or S3 will do it Ok.

Not exactly ... one of the S3 or S1 is the bad scale so use S2.

on 04/01/09 at 18:37:57, Immanuel_Bonfils wrote:

S3 < says 10 or 12 is the fake and S2 is the broken scale,leaving either S1 or S3 to test
10 X 12.

Not exactly ... one of the S3 or S2 is the bad scale so use S1.

Title: Re: A question from the Russian MO
Post by Immanuel_Bonfils on Apr 2^nd, 2009, 6:04am

Of course !
At the time of my post, I had already made an arrangement of the coins for S1 and S2 slighty different, and speaking of laziness... I've adapted... this generate those mistakes. Sorry and thanks.