Minimum number of weighings necessary8 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?

Question

Baluttor7 · Accepted Answer

Step 1I 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.Step 2The remaining combinations that are possible are                    1268                    1368                    1468                    1568                            1258                    1358                    1458                            1248                    1348                            1238                                          2368                            2358                    2458                            2348                                          3458            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&#039;t proven that you can&#039;t do it in 6.

spremani0r · Accepted Answer

Step 1Knowing 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    &amp;lt;      a    2    &amp;lt;      a    3    &amp;lt;      a    4   and       b    1    &amp;lt;      b    2    &amp;lt;      b    3    &amp;lt;      b    4   and       a    1    &amp;lt;      b    1  , then we already know the A&#039;s are lighter if       a    i    &amp;lt;      b    i   for each i. These ignorable configurations correspond to walks by   ±  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&#039;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       1    2                                (                                      8                          4                                      )                      −  14  =  21 partitions to choose from. So it&#039;s quite possible that 5 weightings are enough.Step 2Indeed, 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.

Answered question

Answer & Explanation

New Questions in College Statistics