# Minimum number of weighings necessary

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?

• As there are $\frac 12 {8 \choose 4}=35 \gt 2^5$ (barely) ways to split the eight boxes into fours, one would guess $6$. – Ross Millikan Sep 19 '13 at 22:05
• Thank you very much. I was trying to solve it by choosing the most useful 4's every time. But it's hard to be sure that way=) thanks again. – Taner Sep 19 '13 at 22:15
• I didn't post that as an answer, as I am not convinced. But it gives an idea where to look. In puzzles like this, there may be a trick that gets you down to $5$. – Ross Millikan Sep 19 '13 at 22:20
• But you're saying it shouldn't be more than 6 right? Because I could guarantee it with 7 weighings, which should be wrong if that's what you mean. – Taner Sep 19 '13 at 22:32
• Some of the valid combinations are 1238, 1248,1258,1268, 1278. If you weigh 1258 first you can eliminate two of the others by noting which way the balance tilts. I believe this is the kind of thinking needed. – Ross Millikan Sep 20 '13 at 18:46

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