11
$\begingroup$

To allow new users to solve this puzzle and earn reputation points, I encourage all users whose reputation is 200 or more to not post an answer until 48 hours after this question is posted. Thank you!

Among 101 coins, 100 are genuine and have the same weight. The weight of the counterfeit coin is different from that of a genuine coin. Determine whether the counterfeit coin is heavier or lighter in two weighings on a standard balance. The identification of the counterfeit coin is not required.

Clarification: The goal is to determine if the counterfeit coin is heavier or lighter than a genuine coin. But you aren’t required to determine which coin is the counterfeit coin.

This puzzle is from a Leningrad Mathematical Olympiad.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ @PDT Since you currently have reputation of about 10,000 here on PSE, I would say you are not new to puzzling. Please wait the 48 hours to give newbies a chance. Thanks for asking. $\endgroup$
    – Will.Octagon.Gibson
    Commented Mar 3 at 19:16
  • 10
    $\begingroup$ @PDT that would be sockpuppeting and is generally frowned upon. $\endgroup$
    – 2012rcampion
    Commented Mar 4 at 1:42
  • $\begingroup$ @2012rcampion sockpuppeting is absolutely fine. Many of us, including most mods, have multiple accounts for testing things and the like. What is frowned upon is using your second account to let you do something you could not do with a single account (such as upvoting your main account's posts). If your two accounts never interact with each other's posts (including not commenting unless you make it clear you are the same person), there is nothing wrong with having multiple accounts. $\endgroup$
    – terdon
    Commented Mar 4 at 16:31
  • 2
    $\begingroup$ @terdon Yep, that's exactly what's explained in the post I linked. Multiple accounts are OK, using multiple accounts abusively, a.k.a. sockpuppeting, is not OK. $\endgroup$
    – 2012rcampion
    Commented Mar 4 at 18:55

3 Answers 3

Reset to default
19
$\begingroup$

1) Balance 30 vs. 30. If they balance, you know the counterfeit is in the remaining 41. If not, it's in one of the groups of 30, and the remaining 41 are all genuine. Could use anywhere from 26 to 33 for this step and adjust next steps accordingly.

2) If the 30 v 30 balanced, weigh the remaining 41 (that must have the counterfeit coin) against any 41 of the first 60 to see if they are heavier or lighter (because of the counterfeit coin).

3) If the initial 30 v 30 didn't balance, weigh one group of 30 against any 30 of the remaining (genuine) 41.

4) If this first set of 30 are lighter/heavier with the 30 genuine coins, you know the counterfeit coin from the first 30 is lighter/heavier than a genuine coin.

5) If the second weighing balances, then you know that the remaining group of 30 from the first comparison has a heavier/lighter coin, and you know if it's heavier or lighter based on the initial 30 v 30 comparison.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ how important are the numbers here? If I replaced 30 with 35, say, would it not work? Why? $\endgroup$
    – Kate Gregory
    Commented Mar 3 at 15:15
  • 2
    $\begingroup$ Sorry. I thought about adding more detail here then then got lazy. No wait, I was trying to keep it short & sweet - yeah, that's it. ;) $\endgroup$
    – NoeS
    Commented Mar 3 at 16:07
  • 3
    $\begingroup$ You could use anywhere from 26 to 33 in the first step. Less than 26 and you wouldn't have enough left to compare to the remaining qty in step 2. More than 33 and you wouldn't have enough for the compare in step 3. $\endgroup$
    – NoeS
    Commented Mar 3 at 16:15
  • $\begingroup$ Are the numbers in the first step "largest amount that's less than a third of the total (33.6666)" and "smallest that's more than a quarter of the total (25.25)"? If so how do 1/3 and 1/4 come about? $\endgroup$
    – Sam Dean
    Commented Mar 4 at 15:16
  • 2
    $\begingroup$ @SamDean - The first samples need to be at least ¼ of the total in order to ensure you have enough coins to weight against “the remaining 41” if you do step 2. If you only had 24 v 24 (48 total), then you can’t compare to the full remaining qty of 53 – some of the 53 coins would be un-weighed (and one of those might be the counterfeit one). The first samples can’t be more than 1/3 each since you may need an equal size sample for Step 3. If you did 34 v 34 and they didn’t balance, you only have 33 “known genuine coins” left, so you can’t compare to one to the sets of 34. $\endgroup$
    – NoeS
    Commented Mar 5 at 3:37
13
$\begingroup$

Weigh 50 against 50. If they balance, the one remaining coin is counterfeit and you can weigh it against any of the 100 with your second weigh.

In the likely event that they don't balance, take the 50 coins that were light overall and weigh 25 of them against the other 25. If they don't balance, the counterfeit coin is in here and was making the group light in the first weigh. If they do balance, the counterfeit coin is in the other 50 and was making that group heavy.

Improve this answer
$\endgroup$
2
  • $\begingroup$ How important are the numbers here? If I replaced 50 with 49 or 48, say, would it not work? Why? $\endgroup$
    – codewarrior0
    Commented Mar 4 at 1:30
  • 2
    $\begingroup$ @codewarrior0: You need an even number, to be able to split one of the groups in half. The "if they balance" case can be adjusted to handle having more than 1 coin left, though, as long as you have at least as many known-good coins as possibly-counterfeit coins. $\endgroup$
    – user2357112
    Commented Mar 4 at 4:20
5
$\begingroup$

Here's a complete set of solutions for arbitrarily many coins to a more restrictive version of the problem, where the second weighing is not allowed to depend on the result of the first.

Any solution is a partition of the N coins into nine groups according to where they appear in each weighing: left, right, or neither. Call the groups LL, LR, LX, RL, RR, RX, XL, XR, XX.

It's clear that XX = 0. Moreover, either LL or RR must be zero since a heavier coin in one group would mimic a lighter coin in the other, and likewise, LR or RL, LX or RX, and XL or XR must be zero. Since they're all nonnegative, we can represent a solution unambiguously by four integers: LL−RR, LR−RL, LX−RX, XL−XR.

The problem is symmetric under interchange of the pans in either weighing or swapping the weighings. We may as well fix the pan order by saying LX = XL = 0 and the weighing order by saying LR = 0, so the solution becomes LL−RR, RL, RX, XR.

There are three (almost-)linear constraints on the four variables: the total number of coins is N and the number of coins on each side in each weighing must be equal: $$\begin{eqnarray} |\mathrm{LL} - \mathrm{RR}| + \mathrm{RL} + \mathrm{RX} + \mathrm{XR} &=& N \\ \mathrm{LL} &=& \mathrm{RR} + \mathrm{RL} + \mathrm{RX} \\ \mathrm{LL} + \mathrm{RL} &=& \mathrm{RR} + \mathrm{XR} \end{eqnarray}$$ Note the second one implies $\mathrm{LL}-\mathrm{RR} \ge 0$, so $\mathrm{RR} = 0$. The constraints can be solved to give $$\begin{eqnarray} \mathrm{RL} = N - 3\,\mathrm{LL} \\ \mathrm{RX} = 4\,\mathrm{LL} - N \\ \mathrm{XR} = N - 2\,\mathrm{LL} \end{eqnarray}$$ The resulting values are in range iff $\mathrm{LL} \in \left[ \frac N 4, \frac N 3 \right] \cap \mathbb Z$. I believe all of those are solutions as there is nothing else that would stop them from being solutions.

This gives no solutions for 1, 2, or 5 coins. There are obviously no solutions to the original problem for 1 or 2 coins, but Goldstein's solution works for 5, so apparently result-dependent weighing is necessary in that single case.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.