Good luck, Simon :)
Printable View
Good luck, Simon :)
Hum, nobody else has tried the 12 coin riddle ?
No time, seems impossible anyway.
Plus I got hit by a car which may have damaged my brain. Have I mentioned yet I like gurls and chicken chop?
Hum... even if you'vew got hit by a car, you could still be considerate with other members of the board ;)Quote:
Originally posted by Simon666
Plus I got hit by a car which may have damaged my brain. Have I mentioned yet I like gurls and chicken chop?
Will you finally post the answer to that 12 coins / dwarfs / dragons / jokers / gems / gold / washing machine... huh anyway :D :D :D
JeffB
Ok, if you want me to spoil the riddle then I'll do it ;) The solution is not simple by any means though.
Actually, here is the reason it's feasible :
You have to find one false coin in twelve (12) and it can be lighter or heavier (2), so you have to distinguish between 12*2 = 24 states. With one weighing you can distinguish three states : lighter, heavier or equal. With three weighings, you can distinguish 3^3 = 27 states. So since 24 < 27 you can actually solve the riddle theoretically. Now all you have to do is find an algorithm ;)
And this approach is guaranteed to return the result in three comparisons?
I would be interested in seeing a working algorithm.
There is an approach that will get the result in no more than four tries...
Divide the coins into two piles of six and weigh them.
Take the lighter pile, divide it into two piles of three
and weigh them.
if these piles weigh the same, the false coin is heavier;
divide the heavier pile of six in two piles of three and weigh them.
Select two coins from the heavier pile of three. If they weigh the same, the false coin is the one not weighed; otherwise the false coin is the heavier one.
On the other hand, if one of the two piles of three is lighter, the false coin is lighter. Select two coins from the lighter pile and weigh them. If they are equal, the false coin is the one not weighed; otherwise, it is the lighter one.
:D
As I said in the post before, it it feasible, since we can differentiate between 27 possibilities and there are only 24.
Here is a hint:
Each coin can have four different states in the process :
- You don't know anything about it. It could be the false coin (lighter or heavier) or a correct coin
- It's either the false coin and lighter or a correct coin.
- It's either the false coin and heavier or a correct coin.
- It's a correct coin.
I've left the state out when you have identified the false coin, since that's only at the end. Counting possibilities, 1) adds two possibilities, 2) and 3) add 1 possibility and 4) doesn't add any (it's certain)
In the first weighing you have 24 possibilities to start with. With one weighing you can divide that by three and remain with 8 possibilities for each outcome (pile 1 is heavier / lighter / same as pile 2).
So... The first weighing has to be four coins (pile A) versus four other coins (pile B). If A is lighter then all coins in A will be in state 2), all coins in pile B in state 3) and all coins of the remaining four will be in state 4). So we have 4 + 4 + 0 = 8 possibilities left.
If A were the same weight as B then we would know that A and B are in state 4 and the remaing 4 are in state 1), so we have 0 + 0 + 2*4 = 8 possibilities.
The rest is similar ;)
Since any one coin can be A)lighter, B)heaver, or C)equal in weight to a good coin, are there not in fact 12*3 (36)
possibilities to resolve?
No, because only one coin is false. So the correct way of calculating the possibilities is :
- choose 1 coin out of 12 to be the false coin (12 possibilities)
- choose whether it's lighter or heavier (2 possibilities)
which makes 12 * 2 = 24.
Then they are triellists, not duellists.Quote:
Originally posted by dimm_coderThere are 3 duellists:
...
They are all stand face to face ( like in triangle ).
His story checks out.Quote:
Originally posted by Simon666
I got hit by a car which may have damaged my brain. Have I mentioned yet I like [chicken chop]?
Yves,
Consider this scenario:
Pile1 and Pile2 weigh the same; this tells us that the false coin is in Pile3.
Take two coins from Pile3 and weigh them with two coins from Pile1 (Pile1 contains all good coins)
If these two coins weigh the same, you could weigh one of the untested coins from Pile 3 against a known good coin.
If the third comparison is also even, you have found the bad coin (the one not weighed from Pile3),
but you still don't know if it is heavier or lighter; you have to do a fourth comparison to find out! :(
(if you know a more efficient way to resolve this scenario, please let me know)
It's not as easy as that ;)
If you have 4 coins which you know nothing about (pile C), then you have to split the possibilities into three again. But, unluckily, 8 is not divisible by 3, so we divide the possibilities into 3, 3 and 2.
So you will weigh A1C1 (pile 1) versus C2C3 (pile 2) and leave C4 aside. If pile 1 is lighter then either C1 is false and lighter or C2 or C3 is false and heavier (3 possibilities). The same if pile 1 is heavier. If they are equal, then C4 is the false coin (2 possibilities).