Jump to content


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 :-)
Guest Message by DevFuse
 

Photo
* * * * * 1 votes

July 2013 POM - The King's coins


Best Answer Rainman, 23 July 2013 - 01:28 AM

Spoiler for perfecting my solution

Go to the full post


  • Please log in to reply
10 replies to this topic

#1 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5312 posts
  • Gender:Male
  • Location:New York

Posted 22 July 2013 - 06:44 PM

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?
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#2 superprismatic

superprismatic

    Not just Prismatic

  • Moderator
  • PipPipPipPip
  • 1281 posts
  • Gender:Male

Posted 22 July 2013 - 08:31 PM

Spoiler for my algorithm


Edited by superprismatic, 22 July 2013 - 10:57 PM.
added the first clause in step 02 to to fix algorithm bug

  • 0

#3 Anza Power

Anza Power

    Junior Member

  • Members
  • PipPip
  • 80 posts

Posted 22 July 2013 - 08:54 PM

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

  • 0

#4 Anza Power

Anza Power

    Junior Member

  • Members
  • PipPip
  • 80 posts

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.
  • 0

#5 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 139 posts

Posted 22 July 2013 - 09:53 PM

Spoiler for very small risk of failure


  • 0

#6 superprismatic

superprismatic

    Not just Prismatic

  • Moderator
  • PipPipPipPip
  • 1281 posts
  • Gender:Male

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.


  • 0

#7 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 139 posts

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.


  • 0

#8 superprismatic

superprismatic

    Not just Prismatic

  • Moderator
  • PipPipPipPip
  • 1281 posts
  • Gender:Male

Posted 22 July 2013 - 11:21 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.

 

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.


  • 0

#9 Rainman

Rainman

    Advanced Member

  • Members
  • PipPipPip
  • 139 posts

Posted 23 July 2013 - 01:28 AM   Best Answer

Spoiler for perfecting my solution


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

  • 0

#10 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1586 posts
  • Gender:Female

Posted 23 July 2013 - 02:05 AM

Spoiler for all or nothing algorithm

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users