Computer Science Canada Balances and coin problems |
| Author: | PaulButler [ Sat Feb 23, 2008 2:12 pm ] |
| Post subject: | Balances and coin problems |
Suppose you have 9 coins and a balance. You know that one is fake, and is heavier than the others. The others are all the same weight. Using the balance only twice, how would you find out which coin is the fake? If you've done balance problems before, that was too easy for you. Here is another: Suppose you have 8 coins and a balance. This time you know there is exactly one fake, and that it has a unique weight, but this time you don't know if it is heavier or lighter. The others are all the same weight. Using the balance three times, how do you find the fake? |
|
| Author: | md [ Sat Feb 23, 2008 2:49 pm ] |
| Post subject: | RE:Balances and coin problems |
This was posted not very long ago at all... |
|
| Author: | PaulButler [ Sat Feb 23, 2008 4:05 pm ] |
| Post subject: | RE:Balances and coin problems |
Oops, I suppose I should read off-topic more before posting. I found the post you are talking about though, and it has the first question but not the second. In retrospect I should have posted the second question as a follow-up in the original thread, but I didn't know it existed at the time. |
|
| Author: | OneOffDriveByPoster [ Sat Feb 23, 2008 5:08 pm ] |
| Post subject: | Re: Balances and coin problems |
PaulButler @ Sat Feb 23, 2008 2:12 pm wrote: Suppose you have 8 coins and a balance. This time you know there is exactly one fake, and that it has a unique weight, but this time you don't know if it is heavier or lighter. The others are all the same weight. Using the balance three times, how do you find the fake? We have 8 coins with one fake.
Place two sets of two coins in the balance (leaving 4). If equal weight, then these coins are non-fake; otherwise, these four coins contain the fake. We now have 4 non-fake coins and 4 coins with one fake. Place 2 non-fake coins and 2 of the other coins in the balance (leaving 2 of the other coins). If equal weight, then the 2 other coins in the balance are also non-fake; otherwise, those two coins contain the fake. We now have 6 non-fake coins and 2 coins with one fake. Place 1 non-fake coin and 1 of the other coins in the balance (leaving 1 other coin). If equal weight, then the other coin in the balance is also non-fake; otherwise, that coin is the fake. We now have 7 non-fake coins and the fake coin. |
|