Fog Creek Software
Discussion Board




even harder coin problem 


Did anyone submit a soln to this one (3 independent weighings to find out if a coin is heavier or lighter)?

I have an idea, not sure if it is correct. Basically in each of the 3 weighings have 4 balls on the left pan 4 on the right and 4 outside (i.e. not part of the group).

I came to this conclusion because each of the 3 weighings has 3 possible results (The 2 pans can be equal, left one can be greater or left one can be less than the right).
So 3 weighings can result in 27 different combinations, depending on what is on the pan.

Since we need to find out whether a coin is heavier or lighter, each coin has to be part of the weighing at least once.

This means that the cases of all 3 weghings returing equal is eliminated (Call it EEE). Instictively I think the combination of LLL, GGG (the same side being greater or less) can also be eliminated, I am not able to explain why.

That leaves us with 24 possibilities, that is 12 each if the coin is heavier or lighter.

We can assign the serial # of a coin to each combination of weighings (of E, L and G), depnding on whether the coin is on the left right or outside.

Hence the combination is :


First                                Second                  Third

Left  Right Outside  Left  Right Outside  Left  Right  Outside
1        5          9        5      4          1        3      2        1
2        6          10        6      7        2        5      6        4
3        7          11        9      8        3        8    10        7
4        8          12      10      11      12      9      12      11

Now depending on how the weighings turn out we can determine the different coin is. For example combinations GEE and LEE are assigned to coin 1. So in the first weighing the left is either heavier or lighter (since coin 1 is there) and in the other 2 the 2 are equal (since 1 is outside). Similarly for other coins.

Any thoughts, corrections, better ideas ?

Thanks
Krish

Krish
Saturday, September 25, 2004

"Instictively I think the combination of LLL, GGG (the same side being greater or less) can also be eliminated, I am not able to explain why."

That statement is not right.

You can rule out EEE for sure, but you cannot rule out LLL or GGG.

For example, if LLL means coin #10 is light, then GGG would mean coin #10 is heavy.

JHY
Saturday, September 25, 2004

To be more concrete, in the solution that you gave, GGG would indicate coin #6 is light, and LLL would indicate coin #6 is heavy.  G stands for left pan down, L stands for left pan up.

I think that LGG and GLL can be eliminated, but I am not able to explain why either.

JHY
Saturday, September 25, 2004

Placing of coins for testing :

Test 1 :
Left pan 1 2 3 4
Right Pan 5 6 7 8


Test 2:
Left Pan : 5 6 9 10
Right Pan : 4 7 8 11


Test 3:
Left Pan : 3 5 8 9
Right Pan : 2 6 10 12

=========


Careful observation of the way coins are placed in the pan u can come to the following conclusion:

Either the coin is placed in 1 or 2 pans at most
which means that if one of those coins are faulty then u should be having a result of E in the other pan (given the fact that only one coin is faulty)

or

since a coin is placed for testing in 3 pans in different locations(left pan and sometimes right pan) which means that if that coin is faulty then u cannot get combination such as GGG and LLL in the result.
(since a coin cant be heavy and light at the same time. All other coins weigh the same)

Another observation can be easily made :
(Grouping result can help understanding)

G means left pan going down
L means left pan goign up

Results          Faulty Coin      Heavy/ Light
(Coin placed for testing  only once)

GEE                  1                    H
LEE                    1                    L
====
EGE                  11                  L
ELE                  11                  H
====
and

EEG                  12                L
EEL                    12                H

(Coins placed for testing twice)
======
GEL                    2                H
LEG                    2                L

GEG                    3                H 
LEL                    3                  L

=====
GGE                  7                  L
LLE                    7                  H


GLE                  4                  H
LGE                  4                  L
====
EGL                    10              H
ELG                    10              L

EGG                    9                H
ELL                      9              L
====
(Careful observation can help u see that coins 9,10 are placed on the same side once and in the opposite pans for testing second time. Same is true for other testing pairs)

(Coins placed for testing 3 times)

GLL                      5                L
LGG                      5                H

GLG                    6                  L
LGL                    6                  H

GGL                    8                L
LLG                    8                H

======
there are 24 possible combinations

Samir Mehta
Saturday, September 25, 2004

Thanks for the timely correction, Samir Mehta.  This is embarrassing for me.

I devised the following weighing solution, which, if I am not mistaken, should match what I wrote in my last post.


Test 1 :
Left pan : 3 4 9 12
Right Pan : 6 7 10 11


Test 2:
Left Pan : 1 5 9 11
Right Pan : 4 6 7 8


Test 3:
Left Pan :  2 3 7 10
Right Pan :  5 6 8 11


I think EEE can be eliminated in all the solutions.  But you cannot eliminate GGG and LLL before you come up with a particular solution.

JHY
Sunday, September 26, 2004

I am sorry if I hurt you
I didnt mean to embarase you.

But yes as u said ; the conditions eliminated depends on the way u select the problem to solve

Samir Mehta
Monday, September 27, 2004

If you have 12 coins, and one weighs different, here's what I would do (coin 9 is heavy one):

Weighing 1:
Scale A: 1234
Scale B: 5678
Results: Both sets of coins weigh the same.  Set of coins 9-12 contains the heavy one.

Weighing 2:
Scale A: 9 10
Scale B: 11 12
Result: Scale A is heavier than B, so heavy coin is either 9 or 10.

Weighing 3:
Scale A: 9
Scale B: 10
Result: A is heavier, therefore coin 9 is heavier.

nathan
Wednesday, October 06, 2004

There are two different versions of the problem.  One is adaptive and the other non-adaptive.

We are discussing the non-adaptive version.  Your solution is to the adaptive version.

Here are the links to the problem statements, read them to see what I mean.

Adaptive version:
http://www.techinterview.org/Puzzles/fog0000000046.html

Non-adaptive version:
http://www.techinterview.org/Puzzles/fog0000000090.html

JHY
Wednesday, October 06, 2004

How about this:

number your coins,
1st weigh even vs odd
Then weigh 1,2,3,4 vs 7,8,9,10
Then weigh 3,4,5,6 vs 9,10,11,12

Outcome of the 1st will tell you if your fake is even or odd and if it is heavier or lighter than the norm.

The second two will allow you to pinpoint the exact coin.

Alex.
Wednesday, October 13, 2004

By "1st weigh even vs odd," I assume you mean weigh
2,4,6,8,10,12 vs 1,3,5,7,9,11.  If that is the case, then we have the following three weighings.


weigh 1:    2,4,6,8,10,12 vs 1,3,5,7,9,11
weigh 2:    1,2,3,4 vs 7,8,9,10
weigh 3:    3,4,5,6 vs 9,10,11,12


Assume coin #4 is heavy, then we will get GGG, where G stands for left pan down, L stands for left pan up, and E stands for equal.

Now assume coin #9 is light, then we will get GGG, too.

Therefore, in general, if one uses this method and get the weighing result GGG, one cannot conclude which coin is counterfeit (could be #4 or #9).

JHY
Wednesday, October 13, 2004

Due to symmetry this mapping should provide a solution:

  Less/More
1: EEL/EEG
2: ELE/EGE
3: ELL/EGG
4: ELG/EGL

  More/Less
5: GEE/LEE
6: GEG/LEL
7: GEL/LEG
8: GGE/LLE

  Less/More
9: LLG/GGL
A: LGE/GLE
B: LGL/GLG
C: LGG/GLL

where 1..C stand for the 12 coins. As a matter of fact, this mapping to the individual coins is completely arbitrary. The trick lies in the even distribuition of the E, L and G for each turn. That is: for each turn you have exactly 4E, 4L and 4G coins. For this we don't use the EEE, LLL and GGG constellations.

To group the coins, for each coin take the left mapping column (6 = GEG) and according to the letter found:

L : place it on the left side,
G : place it on the right side,
E : dont use this coin in this turn.

For example coin 6 (= GEG) should be placed on the right for the first and third turn and ignored for the second.

This comes out to the follwing:

Turn1:  (9, A, B, C)  (5, 6, 7, 8)
Turn2:  (2, 3, 4, 9)  (8, A, B, C)
Turn3:  (1, 3, 7, B)  (4, 6, 9, C)

The result has to be looked up in the map above. Depending on the column we find out if the coin is less or more.

Uwe Raabe
Tuesday, October 19, 2004

After rereading my last comment I realized that I missed to clarify the mapping thing. It was just because my mind was captured by the problem, I forgot to explain the idea behind.

Easy to see that the three turns make up to 27 possible combinations. Being one of 12 coins with the additional freedom of being more or less counts up to 24 possibilities.

Now I simply map the 24 possibilities to 24 of the 27 combinations with the restriction that each turn shall compare exactly 4 coins with another 4 ones.

The symmetry eas clear as if the coin is less and maps for example to ELE it has to map to EGE if it were more.

Uwe Raabe
Wednesday, October 20, 2004

Well, a quick recap:

1) There are 3^3 = 27 possible results, and only 24 possible answers, so this should be soluble.

2) Each coin will have to be weighed twice (the second time to show it is the anomaly, not any of the coins it was weighed with, or against, the first time).  With 12 coins each weighed twice, we have 24 total coin-weighings.  We have six trays (3 weighings of Tray A vs. Tray B), so four coins a side seems right.  We will therefore need to specify six 'four-coin' subsets of the twelve coins.

3) THIS IS WHAT PEOPLE SEEM TO BE MISSING: If two coins are weighed twice, both times either with or opposite to one another, they are indistinguishable, for example you won't be able to tell the difference between "1 is light/heavy" and "10 is heavy/light," if 1 and 10 are weighed on opposite sides of the scale both times they are weighed.

4) So, you need six subsets of the numbers one to twelve, each with four unique numbers, such that: (i) each number from 1 to 12 is used exactly twice; (ii) no number is in a set with another number more than once; (iii) of the four sets that do not contain a given number, at least two must not intersect (i.e. have any numbers in common).

5) According to my above argument, there will always be one balanced measurement: since each coin is weighed only twice, the odd coin will not be included in one weighing, which will therefore be balanced.  How many possible results are there when exactly one weighing must be balanced?  Exactly twelve.  The direction of imbalance for the imbalanced weighings tells you whether the counterfeit is heavier or lighter.

6) Can anyone prove that the sets I describe in 4) exist?  Or that they might exist?  If you can prove they can't exist then 1) or 2) must be wrong...

Alec Campbell
Friday, October 22, 2004

Please nobody respond to my above posting.  I know its wrong.  I guess I should stop trying to do this stuff at work...

Alec Campbell
Friday, October 22, 2004

Just found out that my solution allows to expand the question:

"you have 12 coins.  one of them MAY BE counterfeit..."

So the outcome of EEE corresponds to "all coins are good".

If anyone has difficulties to understand my approach, I will be glad to clarify it.

Uwe Raabe
Saturday, October 23, 2004

Let's try to generalize the problem a little bit, for a set of 2^n + n + 1 coins and n weighs.  Let the coins be numbered starting with 0 (zero) up to 2^n + n.

First consider that we only had to deal with 2^n coins, from 0 to 2^n - 1. For the i'th comparison, simply put on one side of the balance all the coins with the i'th bit set to 1, and on the other side the coins with the i'th bit set to 0. After the comparison try to find the coin(s) that always have been on the lighter side, and separately the coins that have always been in the heavier side of the balance. Because there is no other coin that the counterfeit always meets on the other side, or always meets on the same side, no other coin than the counterfeit one will get selected by this process. It is also easy to infer if the counterfeit coin is lighter or heavier than the normal coins.

Now suppose that we have 2^n + n + 1 coins (that is, additional n + 1 coins). In this case, on the i'th weigh simply add to the left side coin # 2^n + i, and on the right side add coin # 2^n + i + 1, with 0 <= i < n. If the counterfeit coin index is greater than or equal to 2^n, n - 1 or n - 2 comparison will yield equal, and it is easy to determine which coin is counterfeit, and how it stands compared to the normal coins. Otherwise, none of the comparisons will yield equal and the previous description applies.

For instance, for 12 coins, one could compare:

1.    0, 2, 4, 6; 8 / 1, 3, 5, 7; 9
2.    0, 1, 4, 5; 9 / 2, 3, 6, 7; 10
3.    0, 1, 2, 3; 10 / 4, 5, 6, 7; 11

The only requirement for the “additional” coins (separated by a semicolon above) is to be able to find the counterfeit one amongst them, but with the additional restriction that every such additional coin must not appear in at least one of the comparisons. That is to allow us to recognize that the counterfeit coin is “additional” when at least one comparison yield equal. The n + 1 additional coin count is easily solved by the described approach, but probably a bigger number of coins can be compared with a better algorithm for the additional coins.

Daniel Aioanei
Wednesday, October 27, 2004

Sorry, but this doesn't work!

Suppose Coin 0 is lighter - the balance will go down to the right in all three weighs. Now suppose coin 7 is heavier and you will have the same result.

Uwe Raabe
Thursday, October 28, 2004

It seems you are right. It doesn't work for pairs of coins with negated bit patterns (such as 0 and 7). Thanks for your good point.

Daniel Aioanei
Thursday, October 28, 2004

this is fairly easy to solve.  the hard part is the terminology to describe it.  i'm beginning with a specific solution, and then i follow that up with a generic solution.

let's start with 3 groups of four coins, labelled ABCD, JKLM, & WXYZ.  if i say "ABCD is light", i mean "one of the coins A, B, C or D is light."

Note that all weighings must be 4 coins versus 4 coins!

ONE OF SEVERAL POSSIBLE SOLUTIONS:

FIRST WEIGHING = ABCD vs. JKLM (WXYZ not weighed)
SECOND WEIGHING = ABJW vs. CKXY (DLMZ not weighed)
THIRD WEIGHING = ACLX vs. BMYZ (DJKW not weighed)

a detailed analysis follows in a funky outline form:

(1a) ABCD < JKLM ... either ABCD light or JKLM heavy
(1a)(2a) ABJW < CKXY ... either AB light or K heavy
(1a)(2a)(3a) ACLX < BMYZ ... A is light
(1a)(2a)(3b) ACLX = BMYZ ... K is heavy
(1a)(2a)(3c) ACLX > BMYZ ... B is light
...
(1a)(2b) ABJW = CKXY ... either D light or LM heavy
(1a)(2b)(3a) ACLX < BMYZ ... M is heavy
(1a)(2b)(3b) ACLX = BMYZ ... D is light
(1a)(2b)(3c) ACLX > BMYZ ... L is heavy
...
(1a)(2c) ABJW > CKXY ... either C light or J heavy
(1a)(2c)(3a) ACLX < BMYZ ... C is light
(1a)(2c)(3b) ACLX = BMYZ ... J is heavy
(1a)(2c)(3c) ACLX > BMYZ ... ERROR!!!

(1b) ABCD = JKLM ... either WXYZ light or WXYZ heavy
(1b)(2a) ABJW < CKXY ... either W light or XY heavy
(1b)(2a)(3a) ACLX < BMYZ ... Y is heavy
(1b)(2a)(3b) ACLX = BMYZ ... W is light
(1b)(2a)(3c) ACLX > BMYZ ... X is heavy
...
(1b)(2b) ABJW = CKXY ... either Z light or Z heavy
(1b)(2b)(3a) ACLX < BMYZ ... Z is heavy
(1b)(2b)(3b) ACLX = BMYZ ... ERROR (all coins equal?)
(1b)(2b)(3c) ACLX > BMYZ ... Z is light
...
(1b)(2c) ABJW > CKXY ... either XY light or W heavy
(1b)(2c)(3a) ACLX < BMYZ ... X is light
(1b)(2c)(3b) ACLX = BMYZ ... W is heavy
(1b)(2c)(3c) ACLX > BMYZ ... Y is light

(1c) ABCD > JKLM ... either JKLM light or ABCD heavy
(1c)(2a) ABJW < CKXY ... either J light or C heavy
(1c)(2a)(3a) ACLX < BMYZ ... ERROR!!!
(1c)(2a)(3b) ACLX = BMYZ ... J is light
(1c)(2a)(3c) ACLX > BMYZ ... C is heavy
...
(1c)(2b) ABJW = CKXY ... either LM light or D heavy
(1c)(2b)(3a) ACLX < BMYZ ... L is light
(1c)(2b)(3b) ACLX = BMYZ ... D is heavy
(1c)(2b)(3c) ACLX > BMYZ ... M is light
...
(1c)(2c) ABJW > CKXY ... either K light or AB heavy
(1c)(2c)(3a) ACLX < BMYZ ... B is heavy
(1c)(2c)(3b) ACLX = BMYZ ... K is light
(1c)(2c)(3c) ACLX > BMYZ ... A is heavy

And these results are symmetrical, of course -- (1a)(2a) is the opposite of (1c)(2c), for example.

***

Note that this is one of several solutions.  for example, it would still work if the third weighing was AMXZ vs BJLY with CDKW left out, although the arrangement of the final solutions would differ.

A more generic solution would be something like this:

First Weighing: group A (4 coins) versus group B (4 coins) leaving group C (4 coins) out.

Second Weighing: put 2 coins of either Group A or B on one side and one coin of that same group on the other, leaving one out.  then put one coin of either Group B or A (whichever hasn't been placed yet) on EACH side, leaving 2 coins out.  Then fill each side with one or two coins from Group C, leaving one out.

Third Weighing:  Do a quick analysis based on which coins you picked above to determine which pairs should be broken and which coins can be left out.  an example from the initial solution follows:

(1a)(2a) ABJW < CKXY ... either AB light or K heavy
so A is put on one side, B on the other, K left out.
(1a)(2b) ABJW = CKXY ... either D light or LM heavy
so L is put on one side, M on the other, D left out.
(1a)(2c) ABJW > CKXY ... either C light or J heavy
so either C or J is put on one side, the other left out.
(1b)(2a) ABJW < CKXY ... either W light or XY heavy
so X is put on one side, Y on the other, and W left out.
(1b)(2b) ABJW = CKXY ... either Z light or Z heavy
so Z is put on the final open space.

whew!

Pan Walker
Wednesday, December 08, 2004

*  Recent Topics

*  Fog Creek Home