Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Apr 25, 2010

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

8 comments:

  1. A(4)
    In 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.

    ReplyDelete
  2. Couldnt wait till night...had to try now

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

    ReplyDelete
  3. solution for a(6) is wrong
    6+2 = 5 +3
    can be 6+1 and 5+2
    sorry guys

    ReplyDelete
  4. 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
    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 :
    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

    ReplyDelete
  5. put
    1) 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 :(

    ReplyDelete
  6. For a(4), I came up with conditions:

    t1: 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.

    ReplyDelete
  7. 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

    If 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.

    ReplyDelete
  8. A detailed analysis of the problem and similar problems can be found here

    ReplyDelete