"Balls in Boxes in a Sack" Weighing Problem

Question

_{This puzzle is based on a competitive programming problem in SG NOI 2019.}

---

Let's assume there are $100$ balls with some labels (e.g. with $100$ different marks on them) having different weights of integers $1$ to $100$. You don't know which ball has which weight. You want to know them by using a unique weighing machine as few as possible times.

This machine needs a sack as an input. This sack must contain exactly $50$ boxes. Each box must contain exactly $2$ balls. Thus, all balls will be inserted to the machine but "separated" in boxes. The machine will then report all weights of all balls and return the sack back to you.

The tricky part is that: when the machine scans the input, the boxes may be shuffled inside the sack and the balls inside each boxes may be shuffled as well. After the scanning, they may be shuffled again before retrieved by you.

For example, let's say you only have $6$ balls from $A$ to $F$. Their weights are $1$ to $6$ respectively but you don't know yet about this. When you insert a sack with $3$ boxes each containing $(A,B) - (C,D) - (E,F)$ to the machine, it may be shuffled to $(D,C) - (A,B) - (F,E)$ when scanned. Therefore, the machine will report $(4,3) - (1,2) - (6,5)$. After that, the sack may be shuffled again, for example to $(F,E) - (B,A) - (C,D)$, as you retrieved it.

So, for $100$ balls, what is the minimum number of times to use the machine to know which ball has which weight?

Answer 1

If the machine returned the boxes/balls in a random order after each weighing, then the problem is impossible. Even if you knew all the individual ball weights, if the machine returns them in a random order, you would no longer know which is which, so without some sort of continuity, it would be impossible to solve.

I am therefore going to assume that either the machine returns them in the same order, or that when you say the balls are indistinguishable, they are only indistinguishable with regards to their weight number. You can label them in order to track which ball is which from one weighing to the next.

In this case I can solve it using

$3$

weighings.

The first two steps of this solution are a little bit like one of the solutions to the classic wiring problem.
Label the balls $b_1$ to $b_{100}$.

First pair the balls as:
$b_1b_2$, $b_3b_4$, ..., $b_{2k-1}b_{2k}$, ..., $b_{99}b_{100}$.

For the second weighing, pair them up like this:
$b_2b_3$, $b_4b_5$, ..., $b_{2k}b_{2k+1}$, ... , $b_{98}b_{99}$, $b_{100}b_1$

The results of the weighings will tell you for any weight number what the weight numbers are of the two neighbouring balls (w.r.t your labelling). So we now know the cyclic ordering of the weight numbers, but we just don't know where the cycle starts, nor in which direction. This is a huge improvement, as there are now only $200$ possibilities left instead of $100!$.

With one more weighing you should be able to pin this down. You could for example repeat the first weighing, except that you swap $b_1$ and $b_3$, and also swap $b_5$ and $b_9$. The first swap is between adjacent boxes, the second between non-adjacent boxes. Comparing the result of this weighing with the result of the first weighing will uniquely determine the swapped balls, and therefore the sequence of all the weights.

It thought that there might be a better solution, using only $2$ weighings, but couldn't find one. See noedne's answer for a proof why no such solution exists.

Answer 2

The minimum is

$3$

weighings.

Graph theory is a good setting for this problem. We start with an empty graph $G$ with one vertex for each ball and an empty graph $H$ with one vertex for each weight. Each box in the input of a weighing corresponds to an edge between two corresponding vertices of $G$, so the input of a weighing is a perfect matching of the vertices of $G$. Similarly, each pair of weights in the output of a weighing corresponds to an edge between two corresponding vertices of $H$, so the output of a weighing is a perfect matching of the vertices of $H$.

After each weighing, we add the input and output edges to our graphs $G$ and $H$. (Technically they are multigraphs because we could weigh the same box twice and have two edges between a pair of vertices.) Our goal of determining the weight of each ball corresponds to determining a one-to-one mapping between the vertices of $G$ and $H$ that preserves their edge relationships. In graph theory, this is called an isomorphism. The only way to determine this with certainty is if there is only one isomorphism between $G$ and $H$.

Every isomorphism between $G$ and $H$ can also be viewed as an automorphism of $G$, i.e., an isomorphism of $G$ to itself. Think of automorphisms as symmetries of a graph; visually, they are ways of moving the vertices around so that the graph looks the same, e.g., by rotating or reflecting the graph. For example, a circular graph with $n$ vertices and $n$ edges (an $n$-cycle) has $2n$ automorphisms because we can rotate it $n$ different ways or reflect and rotate it $n$ different ways. In the weighing problem, our goal is to add edges to $G$ until it has a unique automorphism: the trivial identity automorphism that maps the vertices of $G$ to themselves. This is called an asymmetric graph.

After two weighings, every vertex in $G$ is connected to two edges. Such a graph must consist of non-intersecting cycles. (You can convince yourself of this by repeatedly performing a depth-first search from unvisited vertices.) We saw earlier that cycles are not asymmetric, so we cannot yet know which ball has which weight. With the third weighing, it is easy to find a way to orient the cycles, provided they are large enough. For example, Jaap Scherphuis' method produces one large cycle in the first two weighings and adds three edges (ignoring doubled edges) in the third weighing to produce a graph that is clearly asymmetric (only 20 vertices are depicted):