https://math.stackexchange.com/questions/2375327/coin-weighing-to-find-similar-weight-sets#2375327 If you only care about asymptotic time, then you can assume you have a three-way weighing machine that takes three piles and tells you how they all compare to each other. (A single balance can simulate a three-way weighing machine with only constant overhead; just use it three times.) The following algorithm uses a number of operations **logarithmic** in the number of coins, but perhaps there's an even more efficient algorithm. 1. Split the coins into three stacks of approximately equal size. 2. Use the balance to determine the relative weights of the stacks; label the stacks $P_1, P_2, P_3$ such that $P_1$ is the lightest and $P_3$ is the heaviest. If they all weigh the same, we're done. 3. Otherwise, use binary search to find how many coins you have to take off the top of $P_3$ before it weighs less than $P_1$. In detail, this means that you initialize a pointer to the middle of stack $P_3$. At the start of the loop, check whether $P_3$ weighs no more than than $P_1$; if so, finish. Otherwise, take off all coins above the pointer. If the resulting pile weighs less than $P_1$, put the coins back and move the pointer halfway between its current position and the top of the stack. Otherwise, the resulting $P_3$ still weighs more than $P_1$; leave the coins off and move the pointer halfway between its current position and the bottom of the stack. 4. Now you have a nonempty stack $P_4$ consisting of coins removed from $P_3$. The previous step terminated by removing a single coin from $P_3$ which makes the difference between it weighing more than $P_1$, and no more than $P_1$. Transfer this coin from $P_4$ back to $P_3$. 5. Repeat the process in step (3) with $P_1$ and $P_2$, creating a stack of coins $P_5$ which were removed from the top of $P_2$ so as to make it weigh no more than $P_1$. Because $P_1$ and $P_2$ might weigh the same initially, this stack $P_5$ might be empty. 6. Now $P_1$, $P_2$, and $P_3$ have the desired property that we can remove a specific coin from any stack and make it weigh less than the other two stacks — but we haven't used up all of our coins yet. 7. ** Here is a partial answer, containing an idea for algorithm to run in a logarithmic number of weighing operations. The starting point is to consider a simpler problem: making /two/ piles 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 the details. 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 regions $P_1$ and $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 believe (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 be able to use the idea of a "binary search" subroutine in another way. For example, a different approach 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 pile before it is no heavier than the lightest pile. [*] **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. 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. what I call an "encroach" subroutine. The encroach subroutine is to progressively move the boundary between two of the subdivisions so that the lighter subdivision acquires more and more coins. We are looking for the spot where if we take one more coin, the lighter subdivision becomes the (weakly) heavier one. Evidently, such a spot must exist. 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 can use binary search, taking a logarithmic number of weighings. To do so, let's call the lighter region "A" and the heavier region "B". We initialize a pointer to the middle of the heavier region B. At the beginning of the loop, we check whether B is no heavier than A---if so, we are finished. Otherwise, we move the A/B boundary to where the pointer is. Now we weigh groups A and B with this new boundary to see if A is still strictly lighter than B. If it is, we move the pointer to the middle of the new B region and continue the loop. If it isn't, we revert the A/B boundary to where it just was, and move the pointer to the midpoint between the A/B boundary and its current position. Then we repeat the loop. (A picture helps.) This algorithm will terminate when we find a single coin that makes a difference between A being strictly lighter than B or not.