# Coin Weighing Game

Instruction

The purpose of this game is to find out a fake coin by using a scale. There's is only one fake coin in the pile of coins and the fake coins is either heavier or lighter than the real ones but you do not know whether it is heavier or lighter. You can use the scale only a few times depending on the number of coins in the scale. In the end you have to tell which coin is fake and whether it is lighter or heavier than the real ones.

Description

Play the role of an ancient wise man finding the fake coin for the kings.

Coin Weighing Tips
Solution to a 12 Coin Game

The point is that you need to arrive at a situation where "either the fake coin is lighter and is one of these coins; or the fake coin is heavier and is one of those coins".

The first weigh is: 4 vs 4

We will consider 2 cases:

A) the left side is heavier than the right side
B) the two sides are of the same weight

for A) the fake coin is on the scale, that means the remaining coins are all real, for ease of explanation we name the coins as follows:

H1, H2, H3, H4, L1, L2, L3, L4, R1, R2, R3, R4

where H1, H2, H3, H4 are the coins on the heavier side; L1, L2, L3, L4 are the coins on the lighter side; and R1, R2, R3, R4 are the remaining real coins. In this situation, we know that the fake coin is either heavier and is one of H1, H2, H3, H4; or lighter and is one of L1, L2, L3, L4.

We do the second weigh as follows:

H1,H2,L1,L2 vs H3,L3,R1,R2

we have 3 cases:

C) the left side is heavier
D) the right side is heavier
E) the two sides weighs the same

for C) the fake coin is either H1, H2 or L3 (can you figure out why?) the final weigh will be H1 vs H2 and you can get the answer

for D) the fake coin is either L1, L2 or H3, the final weigh will be L1 vs L2 and you can get the answer

for E) the fake coin is either H4 or L4, the final weigh will be H4 vs R1 and you can get the answer

Hence case A) is complete, we now deal with case B), in this case the coins on the scale are real, and one of the remaining coins is fake, we name the coins as follows:

R1, R2, R3, R4, R5, R6, R7, R8, U1, U2, U3, U4

where the R's are the real coins and the U's are the remaining coins.

We do the second weigh as follows:

R1, R2, R3 vs U1, U2, U3

we have 2 cases:

F) the left side is heavier (that the right side is heavier is similar)
G) the two sides weights the same

for F) the fake coin is lighter and is one of U1, U2, U3. We weigh U1 vs U2 and we can get the answer

for G) the fake coin is U4, but we don't know whether it it is lighter or heavier than the real ones, we can find this out by weighing this against one of the real coins.

This is the solution for a 12 coin problem, the second weigh of case A) is the tricky weigh.

In general, if you are allowed to weigh n times, then the maximum number of coins that you can play with is ((3 ^ (n - 1)) - 1) * 3 / 2