2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Ross Millikan Sep 19 '13 at 22:05
  • $\begingroup$ 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. $\endgroup$ – Taner Sep 19 '13 at 22:15
  • $\begingroup$ 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$. $\endgroup$ – Ross Millikan Sep 19 '13 at 22:20
  • $\begingroup$ 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. $\endgroup$ – Taner Sep 19 '13 at 22:32
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Sep 20 '13 at 18:46
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ There is something I dont understand. There are 6 combinations(considering 21 valid) which has 7 and 8 on the same side. There should be 15 left. How did you narrow it down to ten? What happened to 2368, 3458, 2458, 2358 and 2348 ? $\endgroup$ – Taner Sep 21 '13 at 22:23
  • $\begingroup$ @Taner: oversight. Updated and it cost me one. Now I think one can do better. $\endgroup$ – Ross Millikan Sep 21 '13 at 23:01
  • $\begingroup$ Maybe I'm asking too many questions, but I also couldnt entirely understand why did we assume 1278 would be heavier and not lighter? How does 1278 being lighter be an easier way to find the equality? $\endgroup$ – Taner Sep 22 '13 at 2:46
  • $\begingroup$ @Taner: there is a symmetry in the problem that is broken when we get that result. Any strategy that applies if 1278 is heavy is mirrored by one where 1278 is light, with all the numbers subtracted from 9. So instead of trying 1358 next, we would try 1468, then 1358 or 1467. $\endgroup$ – Ross Millikan Sep 22 '13 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.