489,231 views
37 votes
37 votes
The king receives 64 gold coins in taxes but has reason to believe that one is counterfeit. he summons you to identify the fake coin. you have a balance that can hold coins on each side. how many times do you need to use the balance to find the lighter, fake coin

User ShoeMaker
by
3.6k points

1 Answer

6 votes
6 votes
The simplest way is to split the 64 coins into two lots of 32 and compare them.
Then take the lighter pile, halve it and compare again.
Halving each time will find the fake coin in 6 weighings.
64 —> 32 —> 16 —> 8 —> 4 —> 2 —> 1

You can find the light fake coin in only 4 weighings on a balance scale.
Split the 64 coins into two piles of 21 coins and a pile of 22
Compare the 21 piles. If one is lighter again split them into three piles of 7.
Compare two of the 7 piles
If one is lighter split it into two 2 piles and a 3 pile
Compare the two 2 piles.
If one is lighter compare the two coins to find the fake.
If the two 2 piles are equal then the the fake in in the 3 pile.
Compare two of the coins to find the fake (if equal it must be the other one)

If the 21 piles are equal choose the 22 pile and split it into two piles of 7 and 8 left out
Compare two of the 7 piles. If one is lighter follow the instructions above.
To test the 8 pile split it into two 3 piles and a 2 pile and follow the previous instructions.
This sounds very complicated but does take less time
User Jashim
by
2.3k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.