After someone posed yet another cannonball weighing problem at work, and having been through this several times, but not remembering the details, I decided it was time to kill this problem once and for all.
Spoiler Alert! If you just can't get enough of these puzzles and you want to do it for yourself, close your browser now.
Why are there always a dozen cannonballs? And three weighings? Three is sensible enough from a mystico-numerological point of view. I suppose 12's tidy factoring into small numbers makes more wrong paths possible. Anyway, if you know the "bad" ball is light, the problem is simpler, and the limit's not 12, but 27 (or 33). I'll let you work that one out, and just hint that symmetry runs rampant. What follows is for the case where the bad ball may be light, or it may be heavy, you don't know.
Since one always wants to start at the beginning and work to the end, and since the end is inevitably where things don't work out, turn the problem around, and start at the end.
What's the most information you can get from a single weighing on a balance?
First, let's make some labels. Completely unknown balls are blank. Known good balls are marked with an X. Balls that might be good or might be light are marked L? and similarly, H? for might-be heavy cannonballs.
One weighing can sort out a L? and a H? ball, if you have a known good one to work with. If all the balls are of one of the semi-known types, comparing two will show you which of the three is the bad one, the same as if you're given the "bad = light" (or "bad = heavy") information up front. This works for any of L?/L?/L?, H?/L?/L?, H?/H?/L?, or H?/H?/H?.
I wish I could say I worked out some elegant mathematics to go from there to the 2nd of three weighings. But it was a bunch of pencil scratching and head scratching (otherwise known as "trial and error") that led me to conclude that 4 ea. of L?s and H?s could be sorted out, as long as you have one ball that's known good. What if the balls are completely unknown, though?
After figuring it out from trial and error, I can picture an induction path: 3 balls if the defect is known (light vs. heavy) plus 2 balls if it isn't in the last weighing suggest that five unknowns should be distinguishable in two weighings.
The following chart lays it all out, along with the conclusion that a baker's dozen can be sorted out with three weighings.
|Last weighing, all one flavor||Balance => 3rd ball is off
Unbalance => Heavy's heavy
|Last weighing, 3 mixed||Balance => 3rd ball is light
Unbalance => Heavy's heavy
|Last weighing, 1 each||Balance => 3rd ball is heavy
Unbalance => 1st one's light
|2nd weighing, (4+4)Unk||Balance => 3 heavies left
Unbalance => (2+1)Unk or 2 lights left
|2nd weighing, 5 Unknowns||Balance => 2 left, L/H unknown
Unbalance => 3 left, L/H known
|1st weighing, 13 balls||Balance => 5 Unknowns
Unbalance => (4+4)Unk
Of course, there are plenty more puzzles to make up. What if there's more than one bad ball?
Tom von Alten tva_∂t_fortboise_⋅_org