3
$\begingroup$

A coin weighing problem is a problem that looks something like this:

You have twelve coins. Eleven of them weigh the same; one of them is either heavier or lighter than the other eleven. You want to figure out which one is the counterfeit, and whether it is heavier or lighter. The only way you can measure the difference between coins is by using a balance, putting some number of coins on one side, and some on the other. What is the minimal number of weighings you need, and what strategy achieves this minimal number?

For this puzzle, it turns out that only three weighings suffice! I won't reproduce the strategy here. Proving that three weighings is also optimal is then easy: there are 24 possible configurations (each of the 12 coins could be the odd one out, and it could be lighter or heavier), and a single weighing only has three possible outcomes: left is heavier, right is heavier, or the scale is balanced. This means that with two weighings you can only distinguish $3^2 = 9$ configurations.

There are many, many variations of coin weighing puzzles all over the internet. Very often, optimality of a strategy is proved by an argument like I gave above: showing that $$ \lceil \log_3(\text{number of configurations}) \rceil = \text{number of moves}. $$ I am wondering if it is possible to create coin puzzles that are deceptively hard by that measure: where there are relatively few configurations, and yet solving the puzzle requires relatively many moves.

For the purposes of giving this question some scope, I want to define a "coin weighing problem" as follows, although I am definitely also interested if it turns out a slight generalization gives a more interesting answer.

A coin weighing problem consists of and integer $n \in \mathbb N$, and a set $P \subseteq \mathbb N \times \mathbb N$ such that for all $(l, h) \in P$ we have $l + h < n$. An $m$-move solution to a coin weighing problem $(n, P)$ consists of a strategy for identifying the light, normal and heavy coins out of an $n$-coin configuration, under the additional assumption that if $l, h$ are the number of light and heavy coins in our set, then $(l, h) \in P$, such that in the worst case it requires at most $m$ weighings. We assume that a heavy and a light coin together weigh as much as two normal coins.

In this formulation, our coin weighing problem above corresponds to $n = 12$, $P = \{(0, 1), (1, 0)\}$.

My question:

How big can we make the gap between the $3$-log of the number of possible configurations of the coin problem and the optimal strategy?


Edit: I realize now that, as formulated, there are unsolvable coin puzzles, such as $n = 2, P = \{(0,1), (1, 0)\}$. Let me add the additional assumption that there are no indistinguishable configurations like the one I just wrote, and I will ponder on what a natural condition is to avoid indistinguishable configurations.

$\endgroup$
  • 1
    $\begingroup$ If you have $13$ coins including one counterfeit that may be lighter or heavier, that's only $26$ possible configurations, all distinguishable, and $log_3(26) < 3,$ but you can't uniquely determine the configuration in three weighings. $\endgroup$ – David K Jun 28 at 23:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.