• Coding

  • [Exercise] An Interview Question

My professor gave us this problem to solve:
You are given 12 coins. One of them is lighter or heavier than the others. You can use three weightings. You have to identify the different coin.
It took me more than 3 hours to solve it, I would like to share it with you.
Do you have to identify if it's heavier or lighter? Or simply different?
I think it's warranted in "lighter or heavier" that both possibilities are valid and that you are not required to specify in the solution.
I solved this problem in the past, when I was back in highschool, so I'll just google it to reaffirm :)
rahmu wroteDo you have to identify if it's heavier or lighter? Or simply different?
You only have to find the different coin.
What do you mean by weightings? You mean you are limited to weigh any 2 coins for a total of 3 times?
it's a typical math professors question:P
Last year (grade 11) my math professor asked us this question. I have written it somewhere.
Tomorrow i'll edit this post and post the solution.
I almost found the answer (if only allowed 3 weightings), stuck with 3 coins with only 1 comparison left. Hmm.
MrClass wroteWhat do you mean by weightings? You mean you are limited to weigh any 2 coins for a total of 3 times?
You may use a 2 plate balance and put any amount of coins in each plate, it will give you which plate is heavier. 3 times.
Yup I figured that out. Stuck with last 3 coins and 1 more comparison try
MrClass wroteYup I figured that out. Stuck with last 3 coins and 1 more comparison try
Yes the 3 coins that are left you way 2 of them see if they are equal the third coin will be the needed, and if they aren't equal well we still couldn't identify which one of these 2 is the one we need.
Hint: You start by weighing 4 coins against 4 other coins
I came up with something, I know it's a mess but I am too tired to write it properly and explain it. The one who solve it should know if my steps are correct... maybe later ill write a better paper if I have time

LINK
Lets say that there's 1 heavier coin.

You pick 4 random coins and weight them to 4 other coins. If a side is heavier than the other, you choose this side else if both are equal then the heavier coin is in the other 4 coins.

After the first weight, you split the 4 coins and weight 2 by 2. One side will be heavier than the other. You choose the heavier side and finally you weight the last 2 coins. The heavier will be the different coin.
@moei
One of them is lighter or heavier than the others
Just a test of this solution because it's a neat way (sorting network style) of picking the odd ball out: 
f[s_] := StringJoin[{
  Order[s[[{1, 2, 3, 4}]], s[[{5, 6, 7, 8}]]],
  Order[s[[{1, 2, 5, 9}]], s[[{3, 4, 10, 11}]]],
  Order[s[[{3, 7, 9, 10}]], s[[{1, 4, 6, 12}]]]
} /. {-1 -> "L", 0 -> "B", 1 -> "R"}];

g[r_] := r /. {
  "BBB" -> {0, 0},
  "BBL" -> {12, -1},
  "BBR" -> {12, +1},
  "BLB" -> {11, -1},
  "BLL" -> {9, +1},
  "BLR" -> {10, -1},
  "BRB" -> {11, +1},
  "BRL" -> {10, +1},
  "BRR" -> {9, -1},
  "LBB" -> {8, -1},
  "LBL" -> {6, -1},
  "LBR" -> {7, -1},
  "LLL" -> {0, 0},
  "LLB" -> {2, +1},
  "LLR" -> {1, +1},
  "LRB" -> {5, -1},
  "LRL" -> {3, +1},
  "LRR" -> {4, +1},
  "RBB" -> {8, +1},
  "RBL" -> {7, +1},
  "RBR" -> {6, +1},
  "RLB" -> {5, +1},
  "RLL" -> {4, -1},
  "RLR" -> {3, -1},
  "RRB" -> {2, -1},
  "RRL" -> {1, -1},
  "RRR" -> {0, 0}
};

s = ConstantArray[0, 12];
b = True;
Do[
  s[[i]] += j;
  b = b && g[f[s]] == {i, j};
  s[[i]] -= j;
  , {i, 12}, {j, {-1, 1}}
];

b
> True
scorz wroteI came up with something, I know it's a mess but I am too tired to write it properly and explain it. The one who solve it should know if my steps are correct... maybe later ill write a better paper if I have time

LINK
I think your solution is correct. I did it in a slightly different way.
Ra8 wrote
scorz wroteI came up with something, I know it's a mess but I am too tired to write it properly and explain it. The one who solve it should know if my steps are correct... maybe later ill write a better paper if I have time

LINK
I think your solution is correct. I did it in a slightly different way.
Not true, scorz's solution also assumes that the different coin is heavier. In case the different coin is lighter, then the conclusions stated at the final stage of each branch in his analysis "tree" when the first comparison stage yields different weights are false. For example, one branch compares coins 5, 1 and 2 versus 6, 3 and 4 in stage 2. If these coins don't balance out, the tree analyzes only the side with heavier coins. If indeed set 5/1/2 of coins is heavier than set 6/3/4, and coins 1 and 2 have the same weight, it does not mean that coin 5 is different. In fact, coins 5, 1 and 2 might be of the same weight, and the lighter coin is in set 6/3/4.
The correct way is to start comparing 3 coins versus 3 coins. Also, the weight is a factor which will help you determine which is the different coin. It can't be solved without identifying if the different coin is heavier or lighter than the rest. I'll post my solution tree when I finish work.
yes there is a solution (even if you don't know if its heavier or lighter)

Define:
good coin --> a coin with normal weigh
bad coin --> either a heavy or a light coin
uncertain coin --> a coin that you don't know if it's a good coin or a bad coin

you start by weighing 4 coins against other 4 coins

1- if the weight is the same then you got 8 good coins and 4 uncertain coins
you then weigh 3 good coins against 3 uncertain coins
1a - if the weight is the same, then you are left with 1 bad coin. you weigh the bad coin with a good coin to determine if its heavier or lighter
1b - if the weight is not the same, then now you know if the coin is heavier or lighter and you are left with 3 uncertain coins.
so now weigh one uncertain coin with another uncertain coin to determine which of the three uncertain coins is the bad coin.

2- if the weight is not the same --> i'll leave this for someone else (i know the answer)
scatman wrote 1b - if the weight is not the same, then now you know if the coin is heavier or lighter and you are left with 3 uncertain coins.
No, you are left with 4 uncertain coins.