### Oleg Kryzhanovsky’s Problem - Coin Sequence

**Source:**http://blog.tanyakhovanova.com/

**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?**

Problem:

Problem:

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