Coin weighing to find similar-weight sets

Question

There are $n$ coins. You have a scale that, between two sets of coins, tells you which set is heavier, or if they are equal. What is the worst-case minimum number of weighings after which you can divide the coins into three sets with the property that between any two sets $A,B$, there exists a coin in $B$ that if you remove it, then $A$ weights at least as much as $B$?

This is possible using $O(n)$ weighings in the following way. Start with three empty sets. For each coin, put it into the set that is currently the lightest. After putting in each coin, use the scale twice to determine which set is now the lightest. We can check that the property is satisfied for any pair of set: If it is not satisfied for some pair $A,B$, then the last coin put in $B$ should have been put in $A$.

I suspect finding an exact bound will be difficult, so an asymptotic bound is good enough. For example, can we do better than $O(n)$ weighings?

Answer 1

Edit: I haven't found a solution yet, but here is another way of looking at the problem:

1. Suppose we have $n$ coins, numbered $1\ldots n$. The possible weights of the coins form a convex cone $\mathcal{C}=(0,\infty)^n$, which means that any positive linear combinations of points is in the space.

2. Let $P_n$ be the set of all ways of partitioning $\{1,\ldots,n\}$ into 3 sets. For any given assignment of weights $w\in\mathcal{C}$, some of these partitions will be the kind we are looking for (where each pile is either empty or has a single coin you can remove, etc. etc.). Let us define $$f(w) = \{p\in P_n : p \text{ partitions }w\text{ in the desired way.}\}$$ (And we know because of the $O(n)$ algorithm that $f(w)$ is always nonempty.)

3. Consider how $f$ labels the space of possible weighings $\mathcal{C}$. Note that $f$ behaves nicely under certain transformations:

   • Multiplying all the weights by a positive amount doesn't change the set of partition solutions. That is, if $\alpha >0$ is any constant and $w$ is any weight assignment, then $f(w) = f(\alpha\cdot w)$.

   • If two weightings $w_1, w_2$ have a solution in common, then $w_1 + w_2$ has it, too. Formally, this means that $f(w_1)\cap f(w_2) \subseteq f(w_1+w_2)$.

   • By symmetry, the best case scenario is when all weights are equal— for all $w$, $f(w) \subseteq f([1,1,1,\ldots,1])$.

   • Combining the previous two properties, increasing the weight of each coin by the same amount not affect the set of solutions.

4. In this setup, weighing a particular set of coins means drawing a linear boundary $$[a_1, a_2, \ldots, a_n]\cdot \vec{w} = 0$$ in $\mathcal{C}$, where each $a_i \in \{1,0,-1\}$. Depending on which way the balance tips, you are either on one side of the boundary or the other (or exactly on the boundary in the case of a tie.)

   The boundary splits the space; subsequent boundaries subdivide these spaces.

5. A deterministic solution to this problem amounts to a choice of subdivisions of this kind such that the resulting regions each have a partition in common.

This suggests that an optimal algorithm might be found using a decision tree or branch-and-bound search procedure: given a collection of weighings from the $n$-dimensional unit sphere, find the collection of planes that most efficiently subdivides the sphere into regions that have at least one successful partition in common.

---

Here is a partial answer, containing the start of an idea for an algorithm to run in a logarithmic number of weighing operations.

The starting point is to consider a simpler problem: making two sets instead of three. Here, there's a straightforward algorithm to do so with a number of weighings which is logarithmic in the number of coins:

1. Arrange all the coins in a row so that each coin has a left and right neighbor (except the first and last coin).
2. Place a divider somewhere in the middle of this row, roughly forming two subdivisions of coins.
3. Weigh the two subdivisions to see which is lighter. If they are equal, we are done— these are our two subdivisions.
4. Otherwise, we will use an "encroach" strategy: The encroach strategy is to progressively move the boundary between the two subdivisions so that the lighter subdivision acquires more and more coins from the heavier region. We are looking for the spot where if we take one more coin, the lighter subdivision becomes the (weakly) heavier one. (And such a coin is guaranteed to exist.)

5. We could use a linear algorithm— that is, move the boundary one coin at a time, weighing both subdivisions after each movement. However, this takes a linear number of weighings. Instead, we will use binary search, taking a logarithmic number of weighings.

   To do binary search, call the lighter region A and the heavier region B. Initialize a pointer halfway into region B. At the start of the loop, check whether B has become no heavier than A. If so, we are finished. Otherwise, move the A/B boundary to where the pointer is. Weigh the two regions with their new boundary. If B is still strictly heavier than A, move the pointer halfway into the new region B and continue the loop. Otherwise, revert the A/B boundary to where it just was, and move the pointer midway between its current position and the A/B boundary. Then continue the loop. (A picture helps.)

   This algorithm only terminates when we find a single coin that makes the difference between A being strictly lighter than B, versus being no heavier than B.

6. Remove that decisive coin from the lineup so that it's not included in A's weight or B's weight. We need to decide whether it should belong to A or to B. If, without the decisive coin, A is strictly lighter than B, we add the decisive coin to A (making it heavier than B). Otherwise, we add it to B (making B heavier than A). This guarantees that our two regions have the desired property: if we remove the decisive coin from the heavier region, it becomes the lighter region. If we remove any coin from the lighter region, it remains the lighter region.

This is the two-pile algorithm. The trick is to adapt it, if we can, to make three piles in logarithmic time. Here is the initial attempt to do so; I am still figuring out whether it is fully possible in detail.

1. Arrange the coins in a circular formation so that each coin has a clockwise and counterclockwise neighbor.
2. Place three dividers in the circle (somewhere between adjacent coins), roughly forming three subdivisions of coins.
3. Use three weighings to label the subdivisions $P_1$, $P_2$, and $P_3$ in nondecreasing order of weight. If they are all equal, we are done.
4. Otherwise, we will need to use our "encroach" subroutine from the two-pile problem. The encroach subroutine works the same way as before: we specify two of the regions, and move the boundary between the two regions from the lighter region into the heavier region until we find the decisive coin that would tip the balance. This takes a logarithmic number of weighings.

5. First, we apply the encroach subroutine to $P_1 \leftarrow P_3$.

   In the three-pile version of the problem, it turns out that the decisive coin can cause any of the possible reorderings to happen: by gaining the decisive coin, the lightest pile can become the heaviest or the second-heaviest; the heaviest pile can become the lightest or the second lightest; and the middle pile can remain the middle or become the lighest or heaviest. (See note [*] for examples of each.)

6. Let us consider the easiest possible case. In the easiest possible case, the following happens: the decisive coin we find has the property that when it is transferred from $P_3$ to $P_1$, $P_1$ becomes the heaviest pile and $P_3$ becomes the lightest; and if the decisive coin is removed altogether (excluded from the weight calculations of both $P_1$ and $P_3$), $P_3$ is the lightest pile and $P_1$ is the heaviest pile. In this easy case, the subroutine tells us to put the decisive coin into pile $P_3$. Afterwards, we apply the encroach subroutine to $P_1\leftarrow P_2$. If the decisive coin again should be allocated to the heavier region (here, $P_2$), we are done: all three of the regions have the property that removal of a single coin makes it lighter than the other two regions.

I hope (but have not proven!) that this algorithm can be extended to handle the less-easy cases as well. However, even if this is not possible, we may still be able to borrow the idea of a "binary search" subroutine in another way. For example, a different approach entirely would be to form three arbitrary stacks of coins, then use binary search to find the minimum number of coins you can remove from the top of the heaviest stack before it is no heavier than the lightest stack. Leave the decisive coin on top (the coin that, if removed, makes the heavest pile lighter than the lightest pile). Similarly use binary search on the middle stack to make it just a single coin heavier than the lightest stack. The result will be three piles with the desired property property, though some coins may be left over. There may be an efficient way to "merge" these leftover coins into the three piles so as to preserve the desired property.

---

[*] Examples of reorderings. Here are concrete numerical examples that show that a single decisive coin can result in any possible reordering of the piles' relative weights.

In each case, we have three piles arranged in increasing order of weight, and a single decisive coin of a particular weight will be transferred from the heaviest pile to the lightest.

1. The piles have weight 2, 3, 101, and the decisive coin has weight 100.
2. The piles have weight 1, 2, 8 and the decisive coin has weight 5.
3. The piles have weight 3, 8, 10, and the decisive coin has weight 4.
4. The piles have weight 1, 2, 10, and the decisive coin has weight 3.

In these examples, the effect of transferring the decisive coin is that:

1. The lighest and heaviest piles trade ranks.
2. The lighest pile becomes the heaviest, and the middle one becomes lightest.
3. The heaviest pile becomes lightest, the middle pile becomes heaviest, and the lighest pile becomes the middle.
4. The lightest and middle piles trade ranks.

These are the four possibilities for a decisive coin $P_1 \leftarrow P_3$.

It also matters, but I do not consider, what the effect is of removing the decisive coin altogether.

Answer 2

There are $\Theta(\log n)$ upper and lower bounds.

Lower bound

Run the algorithm adversially, pretending all the weight is in a set $S_t$ starting with the whole set. Each time the algorithm tries to compare sets $A$ and $B,$ take $S_{t+1}$ to be the largest of the sets $(A\setminus B)\cap S_t,$ $(B\setminus A)\cap S_t,$ and $S_t\setminus (A\cup B).$ This gives $|S_{t+1}|\geq \tfrac 13|S_t|.$ After $t=\lfloor \log_3(n/4)\rfloor$ weighings we have $|S_t|\geq 4,$ which means if the algorithm chooses three sets at this point, one of them contains two from $S_t.$ Put weight $1$ on two of these coins, and $\epsilon$ on all the others. These weights are consistent with all the results reported to the algorithm, but the algorithm has produced an incorrect result.

Upper bound

Order the coins so they are labelled $1,\dots,n.$ The algorithm will find a partition of the form $A=\{1,\dots,i\},$ $B=\{i+1,\dots,j-1\},$ $C=\{j,\dots,n\},$ and such that the coin to be removed can be taken from the end of each interval.

As a general simplification we can break ties by pretending $X$ has larger weight than $Y$ if they really have the same weight but $\max(X\setminus Y)>\max(Y\setminus X).$ So we can assume distinct sets have distinct weights.

If we partition the coins into sets of the form $A,B,C$ as above, one of these sets will have minimum weight and one will have maximum weight. This means one of the end sets $A$ or $C$ is either a minimum or a maximum. This gives us one bit of information, which we can use to do a binary chop. In effect we do two binary chops in parallel, for $i$ and $j.$ If $A$ is a minimum that tells us $A$ has less than a third of the total weight, and if it's a maximum it has at least a third of the total weight, and similarly for $C.$ One these binary chops eventually terminates, giving us either an $i_0$ such that $\{1,\dots,i_0\}$ is a minimum in some partition and $\{1,\dots,i_0+1\}$ is a maximum in some partition, or similarly for $j$ and $C.$ Without loss of generality (using reversal symmetry) we can assume it's $A.$ This step takes $O(\log n)$ weighings.

Now there are two strategies we try:

• "$\geq \{1,\dots,i_0\}$ greedy algorithm from the right": binary chop to find the largest $j$ such that $\{j,\dots,n\}$ is heavier than $\{1,\dots,i_0\},$ and set $i=i_0.$
• "bisecting $\{i_0+2,\dots,n\}$": binary chop to find a $j$ such that $\{i_0+2,\dots,j-1\}$ and $\{j,\dots,n\}$ have as equal weight as possible (just solving the two-set problem), and set $i=i_0+1.$

These each take $O(\log n)$ steps, and one of them will successfully find a valid partition. We can check for a valid partition in a constant number of weighings (since coins are always taken from one end).

For the first strategy the following condition is sufficient: $\{i_0+2,\dots,j-1\}$ is lighter than $\{1,\dots,i_0\}.$ Note the first strategy's $B$ must be heavier than $A$ because $A$ was minimal in some partition and $C$ is chosen minimally subject to being heavier than $A.$ This condition ensures each of $A,B,C$ is at least as heavy as $\{1,\dots,i_0\}$ but can be made at least as light as $\{1,\dots,i_0\}$ by removing an element from one end.

The second strategy succeeds if $\{i_0+2,\dots,n\}$ can be split into two sets heavier than $\{1,\dots,i_0\}.$ The second strategy's $A$ weighs more than one-third of the total weight, and $B$ minus its rightmost coin weighs less than half the remaining weight hence less than $A,$ and similarly $C$ minus its leftmost coin weighs less than $A.$ So it remains to check that we can remove a coin from $A$ to make it lighter than $B$ and $C,$ but that follows if $B$ and $C$ are heavier than $\{1,\dots,i_0\}.$ And if there is any (linear) partition of $\{i_0+2,\dots,n\}$ into two sets heavier than $A,$ then the bisection strategy will choose a partition with this property.