Minimum weighings for dividing two real coins

Question

There are $n$ coins, two real (with equal positive weight) and the rest fake (with zero weight). You have a scale that, between two sets of coins, tells you which set is heavier (or if they are equal). What is the minimum number of weighings that you must use in order to divide the coins into two sets so that each set contains one real coin?

We can do this with $\lceil \log n\rceil$ weighings by lining up the coins and binary searching for a point between the two real coins. (Even this more general problem can be done with $\lceil \log n\rceil$ weighings.) How can we show that this is optimal?

One argument might be that on the line, we must search all $n$ points because they are all possible points between the two real coins, and if the two real coins are adjacent, each point could be a unique such point. This requires $\log n$ weighings. However, this argument does not work because there could be other ways to divide the coins into two sets other than cutting somewhere on this particular line.

Answer 1

Suppose we split the set into three piles: A, B and C. We weigh A & B.

1. If they weigh equal, then either both contain one tc (true coin) each or none of them. So we compare A against C.
   1. If A is heavier then (A, B) is the solution.
   2. In the opposite case C is heavier and it contains both tc, so we proceed with C.
2. If in the first comparision A appears heavier than B, then A contains at least one tc and B does not – so either A contains both tc or A and C contain one tc each. We compare A against C then.
   1. If A is heavier than C, A contains both true coins, and we proceed with A.
   2. Or they weigh equal and (A, C) is the solution.
3. If B is heavier than A, we have the case symmetric to 2.

If C is $1/5\,n$ coins and A & B are $2/5\,n$ each then we have $1/5$ of initial set in case 1.2 or $2/5$ in case 2.1 (or 3.1). So we drop at least $3/5$ of $n$ in two comparisions, hence the asymptotic maximum number of comparisions is approximately $2\log_{5/2}n$.

One can also consider the expected number of comparisions. The probability of case 1.2 (both true coins in set C) is about $(1/5)^2$, and probability of 2.1 plus 3.1 (both tc either in A or in B) is about $2\cdot(2/5)^2$. So the expected number of comparisions necessary to solve the problem is $$T(n) = 2 + 1/25\cdot T(n/5) + 8/25\cdot T(2n/5)$$ Alas solving this recurrence is high above my skills, not to mention optimizing the result by changing the coefficient $1/5$ to some other values.
However, it certainly can be bound with $$T(n) < 2+9/25\cdot T(2n/5)$$

Splitting into three equally sized subsets leads to a maximum number of comparisions $\approx 2\log_{3/2}n$

Answer 2

Let $T(n)$ be the number of weighings needed. Clearly it is optimal to have half the coins on each side of the scale. If the scale balances we are done, but if one side is heavy we know both real coins are on that side. Throw away the light half and we have the same problem with $n/2$ coins having used one weighing. This gives the recurrence $$T(n)=1+T(n/2)\\T(2)=0$$ which we can solve to find $T(n)=\log_2 n-1$

Answer 3

$\lfloor\log_3(n)\rfloor$ weighings are necessary, and $\lceil\log_3(n-1)\rceil$ weighings are sufficient. These bounds are equal for numbers of the form $3^d$ or $3^d+1,$ and otherwise differ by $1.$

To get the lower bound, when the weigher compares disjoint sets $A$ and $B$ out of the total set $S,$ we switch the real coins to be in the largest of $A,$ $B,$ and $S\setminus(A\cup B),$ and ignore the rest from then on. This ignores at most two-thirds of the coins, so we end up with at least three after $\lfloor\log_3(n)\rfloor-1$ weighings. If a set of the original coins is chosen at this point, either it or its complement contains two of the remaining coins, so we can switch the two real coins to be in that set, and all the previous weighings will be consistent with this.

For the upper bound, embed the $n$ coins in $\{-1,0,1\}^d$ where $d=\lceil\log_3(n-1)\rceil,$ placing two at co-ordinate $(0,0,\dots,0)$ to handle the case $n=3^d+1.$ Let $S_0$ be the set of coins. For the $i$'th weighing, $1\leq i\leq d,$ compare the coins in $S_{i-1}$ that have $i$ co-ordinate $-1$ to those with $i$ co-ordinate $1.$ If the former set is heavier, set $t_i=-1$; if the latter set is heavier set $t_i=1$; otherwise set $t_i=0.$ Take $S_i$ to be the set of coins in $S_{i-1}$ whose co-ordinates $x$ satisfy $x_i=t_i$ if $t_i\neq 0.$ (So if $t_i=0$ then $S_i=S_{i-1}.$)

Let $S$ be the set of coins whose co-ordinates $x$ satisfy:

• if $x_i\neq t_i$ for some $i,$ then for the least such $i$ we have $(x_i,t_i)=(1,0).$
• in the special case $x=(0,0,\dots,0)$ and $n=3^d+1,$ the coin is a fixed arbitrary choice of the two coins with this co-ordinate.

Note each $S_i$ is determined by the observations $t_1,\dots,t_i,$ and $S$ is determined by all the observations. I claim $S$ and its complement each contain exactly one real coin. These sets therefore meet the requirement for the division.

There is at least one real coin whose co-ordinates $x$ satisfy $x_i=t_i$ whenever $t_i\neq 0$ (i.e. it's in $S_d$) - pick one. Let $x'$ be the co-ordinates of the other real coin. If $x=x'=t$ then we are in the special case $n=3^d+1$ and $x=x'=t=(0,0,\dots,0),$ where $S$ contains exactly one of the coins with co-ordinates $(0,0,\dots,0).$ Otherwise, consider the first index $i$ such that $x_i=x'_i=t_i$ is not satisfied. If $t_i\neq 0$ then $x_i=t_i\neq x'_i,$ which implies $|S_i|=1$ giving $x_j=t_j$ for all $j>i,$ so $x\in S$ and $x'\not\in S$ as required. If $t_i=0$ then $x_i=-x'_i$ and again we have that exactly one of the real coins is in $S.$