strategy - Are there basic weighing puzzles requiring adaptive strategies?

Let us define a basic weighing puzzle as such:

• There are identical balls, except one weighs


• A balance scale may be used to weigh two subsets of the balls, giving


• The goal is to determine which ball weighs a different weight in weighings

For example, one such puzzle is:

• There are 12 identical balls, except one weighs a different amount than the others


• A balance scale may be used to weigh two subsets of the balls, giving either which subset is heavier or that both subsets weigh the same amount


• The goal is to determine which ball weighs a different weight in 3 weighings and whether it weighs more or less

Now, the first answer gives a strategy conditional on what each weighing comes out as. The second answer, however, gives a strategy without branching: before knowing the results of any weighing we can determine what all (three) weighings will be.

In my limited experience with 'basic' weighing puzzles, I've never come across one where branching is necessary. So my question is:

Does there exist a basic weighing puzzle which requires some sort of branching: where a fixed strategy of weighings cannot be determined in advance?

Secondary questions (not necessary to answer but I would be curious to know if it's easy to prove):

• If so, what are some necessary / sufficient conditions?


• If not, what generalisations of a basic weighing puzzle make branching necessary / also do not require branching?

Answer

No, there should always be a pre-planned approach that will work just as well as an adaptive strategy. The way in which I solve for the pre-planned approach might best express why that is:

Each ball, during each weighing, can be in one of three locations: pan "A", pan "B", and "C" can just refer to when it was left off the scale. So if I say a given ball is [A,B,C] that means it was on pan "A" in the first weighing, pan "B" in the second weighing, and left off the scale in the third.

We know that if two balls were in the same location during each of the weighings, then we would be in trouble because we could never distinguish between them. So how many unique combinations of locations can we make over three weighings? Should be 27 total, from [A,A,A], [A,A,B], [A,A,C] ... [C,C,C].

That's not the end of the story, of course, because we don't know if the counterfeit is heavy or light. That means if there are two balls always opposite each other, they will also be indistinguishable. So [A,B,A] and [B,A,B] are "mirrors" of eachother and we couldn't know if one ball was light or one was heavy should one of them be the counterfeit. Location "C" has no opposite, so [A,C,C] would mirror [B,C,C]. Aside from the [C,C,C] combination, the remaining 26 combinations can be thought of as 13 viable combinations, each with a mirrored combination that we can't use. So our list of useable combinations is now 14.

The last task you need to perform is to ensure that the number of balls is equal in pan "A" and "B". You get to pick which of the mirrored combinations you want to use, so while it may seem possible at first, you cannot use all 14. You always have to drop one of them to make it work. Now we are down to 13 combinations.

That [C,C,C] combination may or may not be allowable based on how the puzzle was phrased, because if you must say whether or not the counterfeit was heavy or light, you do need to weigh it at least one time. In the example stated, we have 12 distinguishable combinations to fit our 12 total balls and that's the pre-planned answer.

So that's the process, but why can't a branching strategy be better? At the end of a theoretical trial of this puzzle, no matter your strategy, each ball can still be described using the same coding system (ex: [B,C,B]). A branching strategy still must follow those above rules, it just becomes easy to not notice it when you are able to say certain balls are neutral early and not bother using them later (unless you have to).

That's my answer to the specific question you asked, but there are other balance puzzles for which a branching strategy is absolutely superior. Basically anytime the number of counterfeits is more than one, pre-planned methods fall behind. I couldn't find a puzzle to link to, but for three weighings and two identical counterfeits, you can manage 5 total balls with a branching strategy. That's compared to a lousy 3 balls if you had to pre-plan it, which means that there is a single correct ball. Why does that happen? In short, making each ball discernible isn't good enough when you need to make every possible pair of balls discernible (and that's also why I prefer to use coins instead of balls so I don't say sentences like that one!)