wu :: forums « wu :: forums - A question from the Russian MO » Welcome, Guest. Please Login or Register. Jun 9th, 2023, 10:00am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Eigenray, SMQ, william wu, Icarus, Grimbal, ThudnBlunder, towr)    A question from the Russian MO « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: A question from the Russian MO  (Read 2618 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
 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 »