Tuesday 30 April 2013

Counterfeit Coins


Counterfeit Coins

C
atherine and Heathcliff were spending a quiet evening at home. Catherine was absorbed in a detective novel and Heathcliff was thumbing his way through a check-out stand magazine.
“Cath,” Heathcliff said, interrupting her reading. “Why don’t you put your book down for a minute? I’ve just solved a puzzle and I’d like to share it with you.” Heathcliff paused while Catherine dog-eared the paperback. “Let me read you the ‘Back Page Puzzler’ from this magazine.”He continued, “It says, imagine you have nine coins. One is slightly heavier than the others. Can you identify the heavy coin, using a two pan balance scale only twice?”
---
Heathcliff smiled with pride as he explained his solution, “For the first weighing,” he said, “I thought I would put four coins in each pan, leaving one on the table.  But, no matter how I tried, I couldn’t solve it that way.” “So,” He continued, “I decided to put three coins in each pan and leave the remaining three coins on the table. That way, after the first weighing I’d know which group of three contained the heavy coin. Once I knew that, I could put one coin in each pan and leave one on the table. If the scale balanced,” he concluded, “The heavy coin would be on the table. Otherwise, it would be in the lower pan.
“That’s great Heath,” Catherine said, reaching for her novel. “Now, can I get back to my mystery?” “Not just yet Cath,” Heathcliff replied with a grin. “Now, I’ve got a puzzle for you”
Catherine listened as Heathcliff began. “The puzzle I solved was just a warm up for this one” Heathcliff continued. “This time, you have 12 coins. One is counterfeit. It’s either slightly heavier or slightly lighter, than the rest. The challenge is to identify the odd coin using the same kind of two pan balance scale no more than three times.” “Remember,” Heathcliff coached her, “In this puzzle, you don’t know if the odd coin is heavier or lighter than the others.”
---
Catherine set her book aside and considered Heathcliff’s puzzle. She could already sense this was going to be difficult.
Thinking back to Heathcliff’s earlier puzzle, she decided to begin with 3 even groups of coins. Catherine imagined putting four coins in one pan of the scale, four in the other pan, and the remaining four coins on the table. If the scale balanced, the odd coin would be among those on the table. She paused, “This would be easier if I knew whether the odd coin was heavy or light”. “In that case,” she thought, “I would just put two coins in each pan. Then I’d know which group of two contained the odd coin. Finally, I would weigh those two coins against each other”. “Unfortunately,” she reminded herself, “I don’t know if the coin I’m looking for is heavy or light.”
Catherine thought back to the previous puzzle, “Was there anything she could learn from it,” she wondered. “Well,” she thought, “Heathcliff was able to find an odd coin in a group of three, in one weighing.” “But,” she reflected, “He knew the odd coin was heavy.”  Catherine paused in thought for a moment. Then she got an idea.
“If the scale balanced after the first weighing, the odd coin would be in the group of four coins on the table. After clearing the scale, she would put two of the suspect coins in the pan on one side of the scale and another one of them in the pan on the other side.   Finally, she would add one of the coins she knew was genuine to the second pan.”
“Now,” she thought. If the scale balances the bad coin will be the one I left on the table. And if it doesn’t balance,” she went on, “I still have one weighing to find it.” “Let’s imagine the lower pan of the scale contains the two coins from my group of four suspects” “I’ll know that either one of those coins is heavy or the single suspect coin in the other pan is light”. “I can clear the scale and weigh the two coins from the lower pan against each other. If the scale balances, the odd coin is the light one I took off the scale. If the scale doesn’t balance, the odd coin is in the lower pan.
“Well,” thought Catherine. “That’s reassuring. If the scale balances after the first weighing, I know how to find the counterfeit coin” “But,” She wondered. “What if the scale doesn’t balance?”
Catherine pictured the unbalanced scale. She envisioned four coins in the lower pan and four coins in the upper pan. She wondered, “What would happen if I removed two coins from each pan?” After considering this for a moment, Catherine could see that whether the scale balanced or not, she would be left trying to find the odd coin out of a group of four coins with only one use of the scale remaining. She was pretty sure that was impossible.
“This is a tough puzzle,” Catherine muttered. “I thought it might be.” Heathcliff responded.
Catherine took stock. There were eight suspect coins after the first weighing. She realized the second weighing would have to reduce that number down to three.  To start, she decided to remove three coins from the lower pan. If the scale ended up balancing after the second weighing, she’d be able to find the heavy coin in that group. To replace those three coins, she would put three coins from the table into the lower pan. She did some calculating “Everything would be fine if the scale changed orientation after the second weighing.”  But she realized there would still be too many suspect coins if the same pan was low.  In that case, not only would there be the one remaining coin suspected of being heavy in the low pan. But, there would also be four coins suspected of being light in the higher pan.
Catherine mentally swapped one of the good coins she had put in the lower pan with a suspect coin from the higher pan. However, she quickly realized she would still have four suspect coins, if the scale didn’t change orientation after the second weighing. So, she repeated the procedure and swapped anther coin. This left two good coins and two coins suspected of being light in one pan. The other pan contained one good coin, one coin suspected of being heavy, and two coins suspected of being light.
Catherine slowly grinned. The puzzle was solved. If the scale’s orientation remained unchanged after the second weighing, there would be one coin suspected of being heavy and two coins suspected of being light. She could use the scale a third time to weigh the two coins suspected of being light against each other. This would identify the bad coin.
If the pans reversed orientation, there would be two coins suspected of being light. Finding the light one would be easy. Finally, if the scale balanced, she would know that one of the three coins she removed after the first weighing was heavy. She could find that one easy enough as well.
“I solved your puzzle Heath,” Catherine announced. “You are amazing, Cath!” Heathcliff said, standing up from his chair. “Why don’t I leave you alone for a while now?”

2 comments:

  1. While Heathcliff was looking for his limerick-writing scratch pad, Catherine did some more thinking. Her solution had been arrived at after a good deal of trial and error, but what made it work was that, in the second weighing, there were *not* two coins suspected of being heavy in one pan opposite two suspected of being light in the other, in other words not four doubtful coins.
    What if she had started afresh at the second weighing, set aside the four coins known to be good, and simply placed two suspected of being heavy coins and one suspected of being light in each pan, leaving two suspected of being light on the table. Then, if the scales balanced, one of the two coins on the table was the light one, to be identified in a third weighing. And if the scales didn't balance, the two suspected heavy ones on the lower pan and the one suspected light one on the upper pan were the new suspects.
    "Heathcliff, I think I've improved on my solution", she ventured, "but you are the smart one. It seems so simple now, but perhaps I'm missing something?"

    (From Sue)

    ReplyDelete
  2. Thanks Sue, your solution does seem more straightforward than Catherine’s. One of the goals of Catherine’s Pastimes is to explain the process Catherine follows to solve each puzzle. This is a very difficult puzzle and I am not happy with her explanation. I will revise it before publication.

    The difficult part of this problem is the choice and orientation of coins for the second weighing, if the first weighing doesn’t balance. Thanks to google, I am now aware of a 3rd solution, so the 3 options for the second weighing are:
    Catherine’s (HLLn) --- (LLnn)
    Yours (HHL ) --- (HHL )
    Google's (HLLL) --- (Lnnn)

    After some consideration, I think the 3rd one may be easier for Catherine to explain.

    ReplyDelete