Author |
Topic: A question from the Russian MO (Read 2658 times) |
|
wonderful
Full Member
Posts: 203
|
 |
A question from the Russian MO
« on: May 15th, 2008, 2:04pm » |
 Quote  Modify
|
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!
|
| « Last Edit: May 15th, 2008, 2:39pm by wonderful » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: A question from the Russian MO
« Reply #1 on: May 15th, 2008, 3:10pm » |
Quote Modify
|
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)?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: A question from the Russian MO
« Reply #2 on: May 15th, 2008, 4:17pm » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: A question from the Russian MO
« Reply #3 on: May 19th, 2008, 10:13am » |
Quote Modify
|
So noone answers ... 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.
on May 19th, 2008, 6:19pm, 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.
|
| « Last Edit: May 20th, 2008, 1:59am by Hippo » |
IP Logged |
|
|
|
wonderful
Full Member
Posts: 203
|
|
Re: A question from the Russian MO
« Reply #4 on: May 19th, 2008, 6:19pm » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
Captain_Doubtful
Newbie
Posts: 1
|
|
Re: A question from the Russian MO
« Reply #5 on: Mar 31st, 2009, 2:04pm » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
Vondell
Junior Member
Gender:
Posts: 78
|
|
Re: A question from the Russian MO
« Reply #6 on: Apr 1st, 2009, 9:24am » |
Quote Modify
|
Here is a more workable solution.
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.
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.
|
|
IP Logged |
Why is it that people ask for my two cents worth, and then only offer me a penny for my thoughts?
That deal sucks!
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: A question from the Russian MO
« Reply #7 on: Apr 1st, 2009, 9:48am » |
Quote Modify
|
Vondell: Even defected scale can return correct results so it can past the tests and later give wrong results.
on Mar 31st, 2009, 2:04pm, Captain_Doubtful wrote: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! |
|
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.
|
| « Last Edit: Apr 1st, 2009, 10:11am by Hippo » |
IP Logged |
|
|
|
Vondell
Junior Member
Gender:
Posts: 78
|
|
Re: A question from the Russian MO
« Reply #8 on: Apr 1st, 2009, 11:36am » |
Quote Modify
|
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. 
|
|
IP Logged |
Why is it that people ask for my two cents worth, and then only offer me a penny for my thoughts?
That deal sucks!
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: A question from the Russian MO
« Reply #9 on: Apr 1st, 2009, 11:46am » |
Quote Modify
|
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 ...
|
| « Last Edit: Apr 1st, 2009, 1:35pm by Hippo » |
IP Logged |
|
|
|
Immanuel_Bonfils
Junior Member
Posts: 114
|
|
Re: A question from the Russian MO
« Reply #10 on: Apr 1st, 2009, 6:37pm » |
Quote Modify
|
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.
1st 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.
2ndexample:
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.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: A question from the Russian MO
« Reply #11 on: Apr 2nd, 2009, 12:21am » |
Quote Modify
|
on Apr 1st, 2009, 6:37pm, 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 Apr 1st, 2009, 6:37pm, Immanuel_Bonfils wrote:
2ndexample:
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 Apr 1st, 2009, 6:37pm, 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.
|
| « Last Edit: Apr 2nd, 2009, 12:22am by Hippo » |
IP Logged |
|
|
|
Immanuel_Bonfils
Junior Member
Posts: 114
|
|
Re: A question from the Russian MO
« Reply #12 on: Apr 2nd, 2009, 6:04am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print