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 checkout 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
dogeared 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?”
While Heathcliff was looking for his limerickwriting 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.
ReplyDeleteWhat 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)
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.
ReplyDeleteThe 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.