# The other side of the moon /bb|[^b]{2}/
Never stop Grokking

## Sunday, November 21, 2010

### Counterfeit coins solution

This is a solution to the Weighing piles of coins problem listed on Microsoft Research. It was fun solving it, and the basic idea of the solution could be applied to many other kinds of elimination problems.

Here's my algorithm. If you don't understand it, well, spend some time figuring it out.
Pile#:    1 2 3 4 5 6 7 8 9 0 1 2 3
Selected: 4 4 4 3 3 3 2 2 2 1 1 1 0 => 30 coins
// This is the first weighing

expected weight = 30X
actual weight = W

X1 = W div 30
D1 = W mod 30    // D1 <= 20 since |D| <= 5 and counterfeit coins in pile <= 4

if D1 == 0 then
weigh all 52 coins (W)    // this is the second weighing
X = W div 52
D = (W mod 52) / 4
pile = 13
else if D1 <= 5 then
possible piles = 1-12
else if D1 >= 25 then
X1 = X1 + 1,
D1 = 30 - D1
possible piles = 1-12
else if 5 < D1 < 10 then
possible piles = 1-9
else if 10 <= D1 <= 20
X11 = X1 + 1,
D11 = 30 - D1
possible piles = 1-6
end if

if 0 < D1 < 10 then

Pile#:    1 2 3 4 5 6 7 8 9 0 1 2 3
Selected: 1 3 4 1 2 4 0 1 3 2 3 4 4 => 32 coins
// This is the second weighing

expected weight = 32X
actual weight = W

X2 = W div 32
D2 = W mod 32    // D2 <= 20 since |D| <= 5 and counterfeit coins in pile <= 4

if 12 <= D2 <= 20 and X1 != X2 then
X2 = X2 + 1
D2 = 32 - D2
end if

X = X2

if      D2 == D1*0 then
pile = 7
D = D1/2
else if D2 == D1*1 then
pile = 3
D = D1/4
else if D2 == D1*2 then
pile = 10
D = D1
else if D2 == D1*3 then
pile = 11
D = D1
else if D2 == D1*4 then
pile = 12
D = D1
else if D2 == D1*1/2 then
pile = 8
D = D1/2
else if D2 == D1*3/2 then
pile = 9
D = D1/2
else if D2 == D1*1/3 then
pile = 4
D = D1/3
else if D2 == D1*2/3 then
pile = 5
D = D1/3
else if D2 == D1*4/3 then
pile = 6
D = D1/3
else if D2 == D1*1/4 then
pile = 1
D = D1/4
else if D2 == D1*3/4 then
pile = 2
D = D1/4
end if
else

Pile#:    1 2 3 4 5 6 7 8 9 0 1 2 3
Selected: 1 2 3 0 1 2 4 4 4 4 4 4 4 => 37 coins
// This is the second weighing

expected weight = 37X
actual weight = W

X2 = W div 37
D2 = W mod 37    // D2 <= 15 since |D| <= 5 and counterfeit coins in pile <= 3

X = X2

if X11 == X2 then
D1 = D11
end if

if      D2 == D1*1/4 then
pile = 1
D = D1/4
else if D2 == D1*2/4 then
pile = 2
D = D1/4
else if D2 == D1*3/4 then
pile = 3
D = D1/4
else if D2 == D1*0/3 then
pile = 4
D = D1/3
else if D2 == D1*1/3 then
pile = 5
D = D1/3
else if D2 == D1*2/3 then
pile = 6
D = D1/3
end if
end if