2

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?

Taner
  • 247
  • 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
  • No, this would say you need at least 6. It doesn't guarantee that 6 are enough-you may not be able to keep finding weighings that bring you enough information. For example, if I start with 1234 vs 5678 I get 1 bit of info. But if I then weigh 1235 vs 4678 I probably get less, as the probability is the result will be the same. Early on, you can avoid the problem-your second should probably be 1256 vs 3478. But later, it may not work. – Ross Millikan Sep 19 '13 at 22:36
  • I see. So there isn't a mathematical solution which gives the answer for sure. But it gives the idea that I'm not far from the correct answer. I should keep trying. Thanks a lot again=) – Taner Sep 19 '13 at 22:44
  • I've been trying and trying to find the solution, it's not working. I only noticed that my previous solution which was 7 is wrong. If you can think of anything please let me know. – Taner Sep 20 '13 at 01:04
  • @Ross, the way I read the problem, we know box 1 is lighter than box 2, which is lighter than box 3, and so on. Weighing 1234 vs 5678 gives us 0 bits of information --- we already know 1234 is lighter. The number of non-silly ways to split the boxes into two groups is less than 35 (though I haven't worked out just how much less). – Gerry Myerson Sep 20 '13 at 13:32
  • @GerryMyerson: Thinking about it, I believe you are correct. Without that assumption I think you have to try them all. – Ross Millikan Sep 20 '13 at 16:36
  • 1
    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
  • I get 21 valid combinations. If you try 1458 first, if it's too light, you can rule out 1238, 1248, 1258, 1348, 1358, 1456, and 1457. If it's too heavy, you can rule out 1468, 1478, 1568, 1578, and 1678. – Gerry Myerson Sep 21 '13 at 01:34
  • The question is also posted at http://www.puzzleup.com/2013/ – Gerry Myerson Sep 21 '13 at 23:44
  • @GerryMyerson I couldn't find the solution or the answer on the site you mentioned – Taner Sep 22 '13 at 00:32
  • It's not there. I thought that might have been where you originally found the question. But you can see that it's an ongoing competition, so it's not clear to me whether we should be discussing the question here. – Gerry Myerson Sep 22 '13 at 01:41
  • Oh I didn't know that I'm sorry. If that's the case, you might be right. I think I can't delete the question now, but an administrator can I suppose. – Taner Sep 22 '13 at 01:48
  • You can flag your question for moderator attention, and ask the moderator for advice. – Gerry Myerson Sep 22 '13 at 06:08
  • @Ross Millikan: a weighing has 3 possible outcomes and 5 weighings give a tree with 63 leafs and not $2^5$ – miracle173 Oct 26 '13 at 14:56
  • Once a weighing is in balance, you are done, so I was ignoring that possibility. It seems from the problem statement that only one split will balance. – Ross Millikan Oct 26 '13 at 18:24
  • @Ross Millikan: I already took into account that the weighing stops when the scale is balanced (therefore there are 63 different outcomes after 5 weighings and not $3^5$). Also I think that the fact that the result of the 1st, 2nd, 3rd, 4th or 5th weighing can be equality does not mean that there are 5 different possible splits that will balance (nor $2^0+2^1+2^2+2^3+2^4$) but only that the split you did for the 1st,2nd,... weighing is the unique solution. If you add my name preceded by a '@' to your answer I will get a notification. – miracle173 Oct 28 '13 at 15:10

2 Answers2

1

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.

mjqxxxx
  • 41,358
0

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

Ross Millikan
  • 374,822
  • 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 ? – Taner Sep 21 '13 at 22:23
  • @Taner: oversight. Updated and it cost me one. Now I think one can do better. – Ross Millikan Sep 21 '13 at 23:01
  • 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? – Taner Sep 22 '13 at 02:46
  • @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. – Ross Millikan Sep 22 '13 at 05:16