Oleg Kryzhanovsky’s Problem - Coin Sequence
Source: http://blog.tanyakhovanova.com/
Problem: You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice?
Disclaimer: It is a difficult problem
Hint: (Highlight from * to * to see the hint) *
Problem: You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice?
Disclaimer: It is a difficult problem
Hint: (Highlight from * to * to see the hint) *
Some people post wrong solutions and believe they have solved it. For example, they would start by putting the coins labeled 1 and 2 on the left cup of the scale and 3 on the right cup. If these coins balanced, the person assumes that the coins on the left weighed 1 and 2 grams and that the coin on the right weighed 3 grams. But they’d get the same result if they had 1 and 4 on the left, for example, and 5 on the right.
I propose the following sequence a(n). Suppose we have a set of n coins of different weights weighing exactly an integer number of grams from 1 to n. The coins are labeled from 1 to n. The sequence a(n) is the minimum number of weighings we need on a balance scale to confirm that the labels are correct. The original Oleg Kryzhanovsky’s problem asks to prove that a(6)=2. It is easy to see that a(1)=0, a(2)=1, a(3)=2. Its fun proving that a(4) = a(5) =2.
*
A(4)
ReplyDeleteIn the set (1,2,3,4) a solution for
x+y < z .... (x,y,z) ∈ (1,2,3,4)
x ≠ y ≠z≠x.
is (x,y) ∈ (1,2) .....z = 4
So first step we take coins labelled 1,2 put them on left balance......coin labelled 4 on right balance.
If right is heavier.......then left = (1,2) .....right {labelled coin(4) } = 4....coin not included in the balance {labelled coin(3)} = 3.
now if coined labelled 2 is heavier than coin labelled 1....then coin(2) = 2; coin (1) = 1
A(5)
Take coins labelled(1)...labelled(2) put them in left pan.....coined labelled(4) in right pan.....
now if right pan is heavier than left pan...then possible solutions for
x+y < z .... (x,y,z) ∈ (1,2,3,4,5)
x ≠ y ≠z≠x.
is
case 1 : (x,y) ∈ (1,2) z = 4
case 2 : (x,y) ∈ (1,2) z = 5
case 3 : (x,y) ∈ (1,3) z = 5
if right pan > left pan =>
coin labelled(4) weighs either 4 or 5 gms
coin labelled (1) and coin labelled(2) weigh 1/2/3 gms (any two)
now take coin labelled(1) and coin labelled(4) put them in left pan...coin labelled(5) in right pan.
a+b = c; a<b (a from left pan of first weighing and b from right pan)
case 1 : a ∈ (1,2) b =4 c ∈ (3,5)
case 2 : a ∈ (1,2) b = 5 c ∈ (3,4)
case 3 : a ∈ (1,3) b = 5 c ∈ (2,4)
is a = 1...b =4 ... c=5
so if we take coin labelled(1) and coin labelled(2) and weigh against coin labelled(4) and coin labelled(4) weighs more than the other two coins combined.
In second weighing we take coin labelled(1) and coin labelled(4) and weigh against coin labelled(5) to find them match we say the coins are rightly labelled.
Will try A(6) later at night.
Couldnt wait till night...had to try now
ReplyDeleteHow to approach : Split the coins in groups such that no group contains more than 3 elements....because in a 4 element group, it is not possible to decide the coin labels and weighs in one balance
However with 3 coins, we can leave out a coin, put one coin in left balance and one in right.
and put rest of the coins from other sets in such a way so as to have a unique solution.
1+2+3+4 < 5+6
and this is the only solution where combined weighs of 4 coins < combined weigh of 2.
but because of above suggested approach we try to have a 3 element set.
"Coin labelled x" .....hence referred to as "(x)"
Balance 1 :
(6) on left pan (1), (2) and (3) on right pan.
if it balances =>
the only possible solution is
set A : (6) = 6........................................left pan
set B : {(1), (2), (3)} = {1,2,3}..............right pan
set C : {(4), (5)} = {4,5}........................left out coins
Balance 2 :
(6) and (2) on right pan.... (5) and (3) on left pan
if it balances => all are correct
proof ....after first balance it is obvious the split groups that have been declared above are correct.
one coin each from set C and set B...the maximum weight can be 8...and there is only one way to achieve it 5 and 3.
the weight 8 from set A and set B taking one each can be achieved by only one way 6 and 2
left out coin from set C = 4 ...left coin from set B = 1.
coin from set C on left pan = 5
coin from set B on left pan = 3
coin from set B on right pan = 2
I think this is correct..i hope so
solution for a(6) is wrong
ReplyDelete6+2 = 5 +3
can be 6+1 and 5+2
sorry guys
How to approach : Split the coins in groups such that no group contains more than 3 elements....because in a 4 element group, it is not possible to decide the coin labels and weighs in one balance
ReplyDeleteHowever with 3 coins, we can leave out a coin, put one coin in left balance and one in right.
and put rest of the coins from other sets in such a way so as to have a unique solution.
1+2+3+4 < 5+6
and this is the only solution where combined weighs of 4 coins < combined weigh of 2.
but because of above suggested approach we try to have a 3 element set.
"Coin labelled x" .....hence referred to as "(x)"
Balance 1 :
(6) on left pan (1), (2) and (3) on right pan.
if it balances =>
the only possible solution is
set A : (6) = 6.............................
...........left pan
set B : {(1), (2), (3)} = {1,2,3}..............right pan
set C : {(4), (5)} = {4,5}........................left out coins
Balance 2 :
take out
(4) and (2)
on left pan put (6) and (1)
on right pan put (5) and (3)
if right pan > left pan then the weights are correct
because
one element from set B and 6 weighs less than one element form set B and one from set C combined.
the only possible solution is
left pan set B element = 1
right pan set C element = 5
right pan set B element = 3
left out coin set B = 2
left out coin set C = 4
put
ReplyDelete1) 1, 2, 3 and 6 on scale
no other such combination possible
if true we have pair of 1, 2, 3 and 4 ,5
now put 1, 2, 4 and 5, 3 on scale
no other such combination there between two pairs
if true
oops we still have confusion between 1 and 2 :(
For a(4), I came up with conditions:
ReplyDeletet1: 1+2=3
t2: 1+3=4
If confusions raised during t1 cud be cleared by t2, then our plan is right.
x~y : means coin labeled x is originally y grams.
Doubts in 1st weighing, if t1 scale is equal:
1~2 and 2~1 and 3~3
1~1 and 2~3 and 3~4
1~3 and 2~1 and 4~4
Putting above 3 doubts to satisfy t2:
2+3 != 4
1+4 != 4 (which is originally 3)
3+2 (wrongly labeled 3) != 4
Hence, a(4) = 2
For a(5), working out if:
t1: 1+2 = 3
t2: 2+4 = 5+1
will post results later.
1)Put 1,2,3 on one side and 6 on other side. If both sides are not equal, it proves that the numbrs are not correct
ReplyDeleteIf they are equal (in the above weighing):
2) put 6,1 on one side and 5,3 on other side. if (5,3) is heavier than (6,1), then you can say that the numbers of correct. If (5,3) is lighter than or equal to (6,1), then you can say numbers are not correct.
This seems to be a correct but Iam not very sure.
A detailed analysis of the problem and similar problems can be found here
ReplyDelete