1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
  • 2
    $\begingroup$ I am not sure it is optimal to have half the coins on each side. You could split the coins into three piles and measure two of them, leading to a more optimized strategy (I don't know which strategy is this, just pointing out that there could be one). $\endgroup$ – Ricbit Jul 25 '17 at 15:09
  • $\begingroup$ (In fact I'm thinking that splitting into three piles is worse on the worst-case case, but better on the average-case.) $\endgroup$ – Ricbit Jul 25 '17 at 15:16
  • $\begingroup$ @Ricbit If two of three piles weigh equal, you can't know if they contain one real coin each or both coins are in the third pile. You need at least one additional weighing to decide. So in two comparisions you drop $1/3$ or $2/3$ of coins, compared to dropping $3/4$ of coins when dividing in halves each time... $\endgroup$ – CiaPan Jul 25 '17 at 15:16
  • $\begingroup$ @Ricbit: splitting in half lets you rule out half the coins. Any other split leaves you with more the coins possible at the next step. The classic one bad in twelve coins works with thirds because you get useful information about the ones not on the scale. That is not the case here. $\endgroup$ – Ross Millikan Jul 25 '17 at 15:18
  • 1
    $\begingroup$ @RossMillikan If you split in thirds and find that piles 1 and 2 are equal, then while it's true that you can't rule out any pile, you do learn that either the two real coins are in piles 1 and 2, or both are in pile 3. As Ricbit said, it is conceivable that using this information can lead to a better strategy - I don't think it does, but your proof doesn't rule this out. $\endgroup$ – pi66 Jul 25 '17 at 17:51
0
$\begingroup$

$\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.$

$\endgroup$

Your Answer

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

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