## Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-) |

# July 2013 POM - The King's coins

### #1

Posted 22 July 2013 - 06:44 PM

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?

*Vidi vici veni.*

### #2

Posted 22 July 2013 - 08:31 PM

**Edited by superprismatic, 22 July 2013 - 10:57 PM.**

added the first clause in step 02 to to fix algorithm bug

### #3

Posted 22 July 2013 - 08:54 PM

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 by Anza Power, 22 July 2013 - 08:56 PM.**

### #4

Posted 22 July 2013 - 08:59 PM

Spoiler for my algorithm

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.

### #5

Posted 22 July 2013 - 09:53 PM

### #6

Posted 22 July 2013 - 10:10 PM

Spoiler for my algorithm

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.

### #7

Posted 22 July 2013 - 10:40 PM

Spoiler for my algorithm

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.

### #8

Posted 22 July 2013 - 11:21 PM

Spoiler for my algorithmSuppose 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.

### #9

Posted 23 July 2013 - 01:28 AM Best Answer

**Edited by Rainman, 23 July 2013 - 01:31 AM.**

### #10

Posted 23 July 2013 - 02:05 AM

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users