12 boxes reference weight

Question

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?

Answer 1

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:

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

Answer 2

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