2

I heard this puzzle from a friend, haven't heard back with the answer and it's driving me nuts! It seems like a variation of the counterfeit coin problem.

You have twelve boxes, each containing 1 to 6 marbles. The marbles inside the boxes are bound in place, so they won't roll around if you shake the box. Each marble weighs the same, 1 gram.

You have a simple balance scale.

Finally, you have a reference weight of your choosing.

Using the 12 boxes, the scale, and the reference weight, your task is to determine how many marbles are in each box. What reference weight do you choose?

C.K.
  • 21
  • Are we guaranteed that there are two of each weight, or could each one be anywhere from $1$ to $6$ independently? Are we supposed to find a weight that lets us determine the individual box weights at all, or do we have to minimize the number of weighings? – Ross Millikan Sep 27 '17 at 02:55
  • One challenging case is where all the boxes have the same weight. After a number of weighings you can determine that. If the reference weight is greater than $24$ grams you won't be able to distinguish all $1$s from all $2$s, so the reference must be $24$ or less. I am assuming the boxes are weightless. – Ross Millikan Sep 27 '17 at 03:00
  • does the box itself weigh something? – Dan Uznanski Sep 27 '17 at 03:01
  • 6188 layouts, 462 of which can be uniquely identified by single-box comparisons; these single-box comparisons give 562 bins with more than one layout each, covering 5,726 such layouts total. ...then there's seeing if we can figure out the weight of each size. Many of the layouts should be distinguishable with simple multiple-box weighings, but I haven't written the script to handle it yet. Then once that's done we can look at what remains and what we'd need the reference weight to be. – Dan Uznanski Sep 27 '17 at 04:49
  • The reference weight clearly must be 12. All marble weights divide 12 except 5. Now we just need to work out the details... :) – Jens Sep 27 '17 at 17:01
  • To be serious for a moment, as @Ross explained above, the reference weight must be between 1 and 24 grams. We then only need to show that at each weight in this interval, there is a failure scenario. – Jens Sep 27 '17 at 18:07

2 Answers2

3

A partial answer.

As Ross Millikan pointed out, the reference weight must be $24$ or less, otherwise it will not be possible distinguish between having all $1$s and all $2$s. I therefore tried all reference weights between $1$ and $24$ to see if I could find a failure scenario for each weight and therefore show that no single reference weight could handle all scenarios. The result is below:

enter image description here

As you can see, I did not immediately find a failure scenario for the reference weight $22$. Let me know if you find any mistakes and especially let me know if you find a failure scenario for $22$.

Jens
  • 5,686
  • 2
  • 20
  • 38
3

22

There are $6^{12} = 2\,176\,782\,336$ possible layouts in total, but we can reduce this to a mere $\binom{17}{5} = 6\,188$ possibilities by sorting the items by weight; this can be done on the unknown weights as well, to put the objects into $\sum_{k=0}^5\binom{11}{k}=1\,024$ bins based on their signature of number of items of identical weight: $(2,4,6)$ is the signature of both 112222333333 and 223333444444, and another 18 layouts. Some $\binom{11}{5} = 462$ of these cover all six weights, so have no need for further measurements to figure out what we're looking at - $(1,3,1,2,3,2)$ is always 122234455566. This leaves $562$ signatures with 6-20 layouts each, which we must distinguish via weighings with multiple objects on each side.

I will not attempt to give instructions for actually doing this.

Since we haven't included a reference weight yet, we cannot reliably distinguish between all possible different layouts; many can be, but some have difficulties:

  1. Sometimes one layout simply has its weights as some multiple of another layout's. This can happen for layouts with 1, 2, or 3 items in the signature: 123 and 246 are indistinguishable without some external reference, for instance, as are 12 24 and 36, 13 and 26, and 23 and 46, and of course any single-weight layout.
  2. Some layouts don't have enough light objects to measure heavy objects: the signature $(2,10)$ does not have the ability to distinguish between 113333333333 and 114444444444 for instance because the two 1s aren't enough to tell whether the heavier object is 3, 4, 5, or 6.
  3. Some layouts have light objects that are too heavy to tell the difference between possible heavy objects: you cannot distinguish between 333333333334 and 333333333335 because 3 < 4 and 5, and 33 > 4 and 5.

There are 132 total groups of indistinguishable layouts, and 50 of them are interesting in that they involve something other than mere multiples. I have assembled these in the appendix.

Having found these layouts that are indistinguishable without a reference weight, we must now attempt to use various reference weights to determine whether there are any indistinguishable layouts it cannot help with. Here is a chart of the simplest entries that cannot be distinguished using given reference weights. It is mostly identical to the chart in @Jens's answer, though my script found a few simpler ones.

  1. all 2s, 3s, 4s, 5s, or 6s
  2. all 3s, 4s, 5s, or 6s
  3. all 4s, 5s, or 6s
  4. all 5s or 6s
  5. all 3s or 4s
  6. all 4s or 5s
  7. all 4s, 5s, or 6s
  8. all 5s or 6s
  9. all 5s or 6s
  10. a single 1, 2, 3, or 4 and 11 5s
  11. all 4s or 5s
  12. a single 1, 2, or 3 and 11 4s
  13. all 5s or 6s
  14. all 5s or 6s
  15. a single 1 or 2 and 11 3s
  16. a single 2 or 3 and 11 5s
  17. a single 2, 3, or 4 and 11 6s
  18. a single 1 or 2 and 11 3s
  19. all 5s or 6s
  20. a single 1, 2, or 3 and 11 4s
  21. a single 2 or 3 and 11 5s
  22. No Problems
  23. a single 2, 3, or 4 and 11 6s
  24. a single 1, 2, or 3 and 11 4s

22 manages to successfully distinguish between all possible layouts. It is interesting how all the others fail even on relatively simple things: None of the failed reference weights has to get past "a single (something) and 11 (something else)" to find something it doesn't work for.

Appendix

The following are descriptions of layouts and signatures that cannot be distinguished without a reference weight. Some of these have multiple signatures; in this case, layouts with different signatures can be distinguished from each other, but layouts with the same signature cannot.

  • Any $(12)$.
  • Any $(11, 1)$.
  • Any $(x, 12-x)$ with weights 1,2, 2,4 or 3,6.
  • Any $(x, 12-x)$ with weights 1,3 or 2,6.
  • Any $(x, 12-x)$ with weights 2,3 or 4,6.
  • Any $(x, y, 12-x-y)$ with weights 1,2,3 or 2,4,6.
  • Any $(1, x, 11-x)$ with weights 1,3,6 or 2,3,6.
  • Any $(x, 1, 11-x)$ with weights 2,3,4, 3,4,6, or 3,5,6.
  • $(2,10)$ with weights 1,3, 1,4, 1,5, 1,6, 2,5, or 2,6.
  • $(2,10)$ with weights 2,3, 3,4, 3,5, 4,5, 4,6, or 5,6.
  • $(3,9)$ with weights 1,4, 1,5, or 1,6.
  • $(3,9)$ with weights 3,4, 4,5, or 5,6.
  • $(4,8)$ with weights 1,5 or 1,6.
  • $(4,8)$ with weights 4,5 or 5,6.
  • $(9,3)$ with weights 4,5 or 5,6.
  • $(10,2)$ with weights 3,4, 4,5, or 5,6.
  • $(11,1)$ with weights 2,3, 3,4, 3,5, 4,5, 4,6, or 5,6.
  • $(1,1,10)$ with weights 1,2,3, 1,3,4, 1,4,5, 1,5,6, 2,3,5, or 2,4,6.
  • $(1,1,10)$ with weights 1,2,4, 1,2,5, 1,2,6, 1,3,5, 1,3,6, 1,4,6, or 2,3,6.
  • $(1,1,10)$ with weights 2,3,4, 2,4,5, 2,5,6, 3,4,5, 3,4,6, 3,5,6, or 4,5,6.
  • $(1,2,9)$ with weights 1,3,4, 1,4,5, or 1,5,6.
  • $(1,2,9)$ with weights 2,4,5 or 2,5,6.
  • $(1,2,9)$ with weights 3,4,5 or 4,5,6.
  • $(1,3,8)$ with weights 1,4,5 or 1,5,6.
  • $(1,9,2)$ with weights 1,4,5 or 1,5,6.
  • $(1,9,2)$ with weights 3,4,5 or 4,5,6.
  • $(1,10,1)$ with weights 1,3,4, 1,4,5, or 1,5,6.
  • $(1,10,1)$ with weights 2,3,4, 3,4,5, or 4,5,6.
  • $(1,10,1)$ with weights 2,4,5, 2,5,6, or 3,5,6.
  • $(2,1,9)$ with weights 1,2,5 or 1,2,6.
  • $(2,1,9)$ with weights 1,3,4, 1,4,5, or 1,5,6.
  • $(2,1,9)$ with weights 1,3,5 or 1,4,6.
  • $(2,2,8)$ with weights 1,4,5 or 1,5,6.
  • $(2,9,1)$ with weights 1,4,5 or 1,5,6.
  • $(2,9,1)$ with weights 3,4,5 or 4,5,6.
  • $(3,1,8)$ with weights 1,4,5 or 1,5,6.
  • $(1,1,1,9)$ with weights 1,2,4,5 or 1,2,5,6.
  • $(1,1,1,9)$ with weights 1,3,4,5 or 1,4,5,6.
  • $(1,1,9,1)$ with weights 1,3,4,5 or 1,4,5,6.

Source code

Dan Uznanski
  • 11,025
  • It is indeed odd how $22$ manages to hit such a sweet spot when all others fail so easily. It is not easy to see a deeper reason for this. – Jens Oct 02 '17 at 16:23