12 coins, 11 gold

The Problem:


You have 12 gold coins — or so you think! One is fake and is known to have a different weight than the others. It could be heavier or lighter; you only know it’s wrong. Using the same simple balance scale, how do you determine the incorrect coin, and whether it is heavier or lighter, in only three weighings?

400px-The_Coin_full.jpg

Problem from Ollie’s The Riddler

The Logic:


The criteria for the unique coin’s identity to be known is

  • It must be weighed at least once
  • If put on the scale with an equal number of coins on each side it cannot be evenly balanced
  • If put on the scale more than once with an even number of coins on each side it must weight consistently more or consistently less than the other side

This is the framework for finding the solution — just find a weighing scheme that lets you remove 11 of the coins from this criteria with one that satisfies it. There is some branching allowed, depending on the result of the previous weighing you can alter which coins you put on each side of the scale. I call these Scale Configs and there are two per branch:

Untitled Diagram (1).png

For example, putting coins 0,1,2,3 on one side of the scale and 4,5,6,7 on the other is Scale Config 1

The Solution:


My configurations are as follows:

WithConfigsUntitled Diagram (1).png

For example, if coin 8 is made of a heavier material than metal our path would go:

  1. Weigh [0,1,2,3] against [4,5,6,7]. They are evenly balanced (go to Config 3)
  2. Weigh [5,6,7] (known non-unique coins) against [8,9,10]. [8,9,10] is heavier meaning the coin is among those three and heavier
  3. Weigh [8] against [9]. 8 is heavier and therefore the unique coin

Code:


Making this in Python helped me understand the problem and the decisions I actually got to make. I was fairly confident in my Configurations 1,3,6,7 because I could logic though them — but 2, 4 and 5 were all dependent on one another and therefore annoying. It ended up saving time just writing a way to brute force different configurations for those three — yielding the solution above.

The code can be found here 

 

The code creates configurations for both sides of C2, C4, C5 then tests every coin as being both heavier and lighter. If it can deduce each one then it is a pass. It took about 20,000 iterations to get to the working solution, above.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s