Minimum number of weighings necessary

Question

8 boxes each having different weights are numbered from 1 to 8 (the lightest 1, the heaviest 8). The total weight of 4 boxes are equal to the other 4’s total, and your task is to identify these two groups. You have a balance scale with two pans on which you can compare the weight of two groups each having exactly 4 boxes. What is the minimum number of weighings necessary to guarantee to accomplish this task?

Answer 1

I would start with $1278$. If heavy, it allows you to knot that $7$ and $8$ are in different groups, if light, you know $1$ and $2$ are in different groups. Let us assume it is heavy, otherwise subtract all numbers below from $9$.

The remaining combinations that are possible are $$\begin {array} \\1268&1368&1468&1568\\ 1258&1358&1458\\1248&1348\\1238\\ \\2368\\2358&2458\\2348\\ \\3458\end{array}$$ where combinations above, north or east are known to be heavier. The line breaks represent layers in a 3D matrix. If we try $1358$ next, then either $1468$ or $2358$, we might need as many as four more. This gives $7$ weighings. I haven't proven that you can't do it in $6$.

Answer 2

Knowing that the weights increase monotonically from box $1$ to box $8$ allows several options to be discarded out of hand. In particular, if the groups are $A=\{a_1,a_2,a_3,a_4\}$ and $B=\{b_1,b_2,b_3,b_4\}$, with $a_1<a_2<a_3<a_4$ and $b_1<b_2<b_3<b_4$ and $a_1<b_1$, then we already know the $A$'s are lighter if $a_i<b_i$ for each $i$. These ignorable configurations correspond to walks by $\pm 1$ from $0$ to $0$ that are always non-negative: $$ 010101010 \\ 010101210 \\ 010121010 \\ 012101010 \\ 012121010 \\ 012101210 \\ 010121210 \\ 012321010 \\ 012121210 \\ 010123210 \\ 012123210 \\ 012321210 \\ 012323210 \\ 012343210 $$ (fourteen, or the Catalan number $C_4$) where the $A$'s are definitely lighter. (The last in this list corresponds to $A=\{1,2,3,4\}$ and $B=\{5,6,7,8\}$, for instance.) This leaves only $\frac{1}{2}{{8}\choose{4}}-14=21$ partitions to choose from. So it's quite possible that $5$ weightings are enough.

Indeed, even $4$ may be enough, since a weighing may be balanced (that is, there are three possible outcomes, one of which consists of only one possibility). So ideally the first weighing would either balance or reduce us to $10$ possibilities; the second would either balance or reduce us to $5$ possibilities; the third would either balance or reduce us to $2$ possibilities; and the fourth would determine the answer.