July 2013 POM - The King's coins

[bonanova]

This puzzle begins with a familiar ring: you have a bag of visually indistinguishable, but not identical, coins. They are variously gold, silver and bronze, and therefore they are of three distinct weights. The King asks you to give him a gold coin.

You consider just drawing a coin at random, but you fear (correctly) that you will lose your head if the coin you give to the King is not gold. Being of above average intelligence, you cast about for a better approach.

You search the BrainDen archives for a balance scale. Luckily, you find one. Unluckily, it's damaged: Instead of giving the usual three outcomes, { <, +, > } it can discern only whether the two sides of the scale are in balance, or not. Whatever you place in the two pans can only be determined to have equal weight, or not.

But weight, there's more. The scale has a further idiosyncrasy. It will allow an object to be weighed only two times. If an object is weighed for a third time, the scale will magically cause the object to disappear.

That's it. The King is tapping his fingers impatiently on the table. There is no time to find another scale. If it heldps, I just looked in the bag and counted 1521 coins. I threw them all into a mass spectrometer that I just happened to have with me and determined that 827 of the coins are gold.

It's algorithm time. Can you fulfill the king's wishes using this really weird scale?

[Rainman]

No need to throw odd coins away...

1. If there are less than two coins in the bag, go to step 6.

2. Take two coins from the bag and weigh them against each other.

3. Throw them away if unbalanced, else stack them.

4. If there are two stacks of equal size, take one coin from each stack and weigh them against each other. Else go to step 1.

5. Throw the stacks away if unbalanced, else stack them together. Go to step 4.

6. Take a coin from the largest stack and give it to the King.

- All coins in a stack will be of the same kind.

- A stack will always have exactly two coins which can still be used for weighing.

- I will never throw away more gold coins than non-gold coins.

- I will always have more gold coins than non-gold coins left.

- There will not be any stacks of equal size at the end of the algorithm.

- Every stack contains a number of coins that is a power of 2.

- The largest stack contains more coins than all other stacks combined.

- The largest stack contains only gold coins.

Edited July 23, 2013 by Rainman

[superprismatic]

This algorithm will sort the coins into 3 different piles with

each pile containing coins which all have the same weight.
Now, as soon as any pile has more than 694 coins in it, we will
know that all of the coins in this pile are gold. We know this
because there are only 694 (=1521-827) non-gold coins.

For ease of reference, number the coins from 1 to 1521.

step 01: let N=1 and put coin 1 into pile A and make piles B and C empty
step 02: re-order the piles so that A and B have the most recent & next most recent additions, respectively; increment N by 1
step 03: weigh coin N against the highest numbered coin in pile A
step 04: if the result is not equal, go to step 08
step 05: add coin N to pile A
step 06: if pile A has 695 coins, stop. This is the pile of gold coins
step 07: go to step 02
step 08: if pile B is empty, put coin N into pile B and go to step 02
step 09: weigh coin N against the highest numbered coin in pile B
step 10: if the result is not equal, go to step 14
step 11: add coin N to pile B
step 12: if pile B has 695 coins, stop. This is the pile of gold coins
step 13: go to step 02
step 14: add coin N to pile C
step 15: if pile C has 695 coins, stop. This is the pile of gold coins
step 16: go to step 02

Edited July 22, 2013 by superprismatic
added the first clause in step 02 to to fix algorithm bug

[Anza Power]

Ok well let's look at this differently, make it a graph, each coin is a node and there is an edge between two nodes if and only if they are equal in weight.

So the graph we have is actually 3 cliques, and we must find the clique of size 827, we have a machine that can tell us if two nodes are connected or not but it can only do each node once.

My solution isn't guarenteed but I think it will work very well in most cases:

Take the first coin, call it stack0, now each time you take another new coin and compare it with the latest coin in stack0, if it is equal we add it to stack0, if not then we start a new stack called stack1 with that coin and continue what we do with stack1 (forget about stack0 for now)

As you can see each coin (beside the very first) in each stack is put on the scale exactly twice, once when it first enters the stack (be it an existing stack or new stack created because it was not equal to the old stack) and again when another coin gets compared with that stack, all except the very first and the very last coins which each have been compared once, so we can compare them, if equal we join the last stack to stack0.

Now what we have is N stacks of different sizes, and we only know that each stack contains the same type of coins and every two neighboring stacks are different, now you simply run an algorithm for the subset-sum problem, and ask it to find all subsets of the sizes you have that sum up to 827, you remove any option that contains two neighboring stacks (also the last stack and stack0 are considered neighbors), if you are lucky you will end up with one option and you know exactly which are the gold coins, if not you try to find a stack which appears in all options and then you can be sure that that too is a gold stack (the king only wants one coin), but if you can't find that then alas you have to take your chances, maybe take one from a stack that appears in most options or the largest stack

Edited July 22, 2013 by Anza Power

[Anza Power]

This algorithm will sort the coins into 3 different piles with

each pile containing coins which all have the same weight.

Now, as soon as any pile has more than 694 coins in it, we will

know that all of the coins in this pile are gold. We know this

because there are only 694 (=1521-827) non-gold coins.

For ease of reference, number the coins from 1 to 1521.

step 01: let N=1 and put coin 1 into pile A and make piles B and C empty

step 02: increment N by 1

step 03: weigh coin N against the highest numbered coin in pile A

step 04: if the result is not equal, go to step 08

step 05: add coin N to pile A

step 06: if pile A has 695 coins, stop. This is the pile of gold coins

step 07: go to step 02

step 08: if pile B is empty, put coin N into pile B and go to step 02

step 09: weigh coin N against the highest numbered coin in pile B

step 10: if the result is not equal, go to step 14

step 11: add coin N to pile B

step 12: if pile B has 695 coins, stop. This is the pile of gold coins

step 13: go to step 02

step 14: add coin N to pile C

step 15: if pile C has 695 coins, stop. This is the pile of gold coins

step 16: go to step 02

I think you have a problem, say the coin types were as follows:

0 1 2 3

A B C A

Coin 0 will go to pile A, coin 1 to B and 2 to C, but in the process you have compared coin 0 with 2 coins so you can't compare it against coin 3.

[Rainman]

I separate the coins into 760 pairs and throw the odd one away. I weigh each coin against its paired coin and throw both away if they aren't balanced. Thus for each gold coin I throw away, I also throw away a non-gold coin, except possibly the odd coin I threw away at the start.

Now all remaining pairs are balanced. I separate the pairs into pairs of pairs and throw the odd pair away if necessary. I weigh one coin from each pair against one coin from its paired pair. If they are unbalanced I throw away all four coins. Thus for each gold coin I throw away, I also throw away a non-gold coin, except possibly the odd pair I threw away at first.

Now I have a number of balanced quartets. Two coins from each quartet can still be used for weighing, while the other two have already been weighed twice. I separate them into pairs of quartets and throw away the odd quartet if necessary. I weigh one weighable coin from each quartet against one from its paired quartet. I throw all eight coins away if they are not balanced, and so on...

Can I run out of gold coins before I run out of non-gold coins? It is possible, but extremely unlikely. I start with 827 gold coins and 694 non-gold coins, i.e. 133 more gold than non-gold. The only way to throw away a gold coin without also throwing away a non-gold coin is when I throw away odd ones. Even if I threw away an odd single, an odd pair, an odd quartet, an odd 8, an odd 16, an odd 32, and an odd 64, I have still only thrown away 127 gold coins without a corresponding non-gold coin. So I would need to throw away an odd stack of 128 gold coins! Not only is it near impossible to get to this point due to the laws of probability, but once I have acquired a stack of 128 coins I would be able to feel which stack is heavier since gold is considerably heavier than silver or bronze. Unless the coins are very small

[superprismatic]

This algorithm will sort the coins into 3 different piles with

each pile containing coins which all have the same weight.

Now, as soon as any pile has more than 694 coins in it, we will

know that all of the coins in this pile are gold. We know this

because there are only 694 (=1521-827) non-gold coins.

For ease of reference, number the coins from 1 to 1521.

step 01: let N=1 and put coin 1 into pile A and make piles B and C empty

step 02: increment N by 1

step 03: weigh coin N against the highest numbered coin in pile A

step 04: if the result is not equal, go to step 08

step 05: add coin N to pile A

step 06: if pile A has 695 coins, stop. This is the pile of gold coins

step 07: go to step 02

step 08: if pile B is empty, put coin N into pile B and go to step 02

step 09: weigh coin N against the highest numbered coin in pile B

step 10: if the result is not equal, go to step 14

step 11: add coin N to pile B

step 12: if pile B has 695 coins, stop. This is the pile of gold coins

step 13: go to step 02

step 14: add coin N to pile C

step 15: if pile C has 695 coins, stop. This is the pile of gold coins

step 16: go to step 02

I think you have a problem, say the coin types were as follows:

0 1 2 3

A B C A

Coin 0 will go to pile A, coin 1 to B and 2 to C, but in the process you have compared coin 0 with 2 coins so you can't compare it against coin 3.

You're right. I had to modify step 2 in my post to fix that problem.

[Rainman]

This algorithm will sort the coins into 3 different piles with

each pile containing coins which all have the same weight.

Now, as soon as any pile has more than 694 coins in it, we will

know that all of the coins in this pile are gold. We know this

because there are only 694 (=1521-827) non-gold coins.

For ease of reference, number the coins from 1 to 1521.

step 01: let N=1 and put coin 1 into pile A and make piles B and C empty

step 02: re-order the piles so that A has the highest number coin in it; increment N by 1

step 03: weigh coin N against the highest numbered coin in pile A

step 04: if the result is not equal, go to step 08

step 05: add coin N to pile A

step 06: if pile A has 695 coins, stop. This is the pile of gold coins

step 07: go to step 02

step 08: if pile B is empty, put coin N into pile B and go to step 02

step 09: weigh coin N against the highest numbered coin in pile B

step 10: if the result is not equal, go to step 14

step 11: add coin N to pile B

step 12: if pile B has 695 coins, stop. This is the pile of gold coins

step 13: go to step 02

step 14: add coin N to pile C

step 15: if pile C has 695 coins, stop. This is the pile of gold coins

step 16: go to step 02

Suppose coins 1,2, and 3 are gold, silver, and bronze respectively.

- Put coin 1 in pile A.

- Weigh coin 2 against coin 1, not equal. (Both coins have been weighed once)

- Put coin 2 in pile B.

- Re-order piles so coin 2 is in pile A, coin 1 in pile B.

- Weigh coin 3 against coin 2, not equal.

- Weigh coin 3 against coin 1, not equal. (All coins have been weighed twice)

I think this will only work if you can see the result of the third weighing of a coin before the coin magically disappears.

[superprismatic]

This algorithm will sort the coins into 3 different piles with

each pile containing coins which all have the same weight.

Now, as soon as any pile has more than 694 coins in it, we will

know that all of the coins in this pile are gold. We know this

because there are only 694 (=1521-827) non-gold coins.

For ease of reference, number the coins from 1 to 1521.

step 01: let N=1 and put coin 1 into pile A and make piles B and C empty

step 02: re-order the piles so that A has the highest number coin in it; increment N by 1

step 03: weigh coin N against the highest numbered coin in pile A

step 04: if the result is not equal, go to step 08

step 05: add coin N to pile A

step 06: if pile A has 695 coins, stop. This is the pile of gold coins

step 07: go to step 02

step 08: if pile B is empty, put coin N into pile B and go to step 02

step 09: weigh coin N against the highest numbered coin in pile B

step 10: if the result is not equal, go to step 14

step 11: add coin N to pile B

step 12: if pile B has 695 coins, stop. This is the pile of gold coins

step 13: go to step 02

step 14: add coin N to pile C

step 15: if pile C has 695 coins, stop. This is the pile of gold coins

step 16: go to step 02

Suppose coins 1,2, and 3 are gold, silver, and bronze respectively.

- Put coin 1 in pile A.

- Weigh coin 2 against coin 1, not equal. (Both coins have been weighed once)

- Put coin 2 in pile B.

- Re-order piles so coin 2 is in pile A, coin 1 in pile B.

- Weigh coin 3 against coin 2, not equal.

- Weigh coin 3 against coin 1, not equal. (All coins have been weighed twice)

I think this will only work if you can see the result of the third weighing of a coin before the coin magically disappears.

I now see that I have much more of a problem with the algorithm than can be fixed in the simple way I've tried. I must be getting tired.

[BMAD]

3 steps.

1. Hand the king all of the coins.

2. Before he raises alarm and calls for the gallows, remind him that with the whole bag of coins, he surely has 1 gold coin.

3. Then run.

[BMAD]

i don't see the flaw in my solution

Nice job rainman