In the book (available online for free) "Information Theory, Inference, and Learning Algorithms" by David J.C. MacKay, on pages 68f, and in this recorded lecture of his (Youtube), the "Weighing Problem" (an example of combinatorial group testing) is described and solved by what could be called a "greedy information content strategy". It is mentioned at the end of the Youtube lecture (around 45:45) that there are problems where this strategy would fail (or be sub-optimal). My question is: What is an example puzzle/problem where such a "greedy information content strategy" fails? In general, in what kinds of problems (puzzles?) does it fail?
I will now outline what I mean by "greedy information content strategy". The "Weighing Problem" involves having some number of balls, all equal in weight except for one that is either heavier or lighter. One may weigh any two subsets of the balls against each other in a scale. The task is to find the odd ball with as few uses of the scale as possible. In each weighing, one makes a partition of the balls into the three subsets (weigh left, weigh right, don't weigh). Starting with a uniform prior probability distribution, one updates it after each weighing according to the result. The optimal solution strategy, as presented by MacKay, dictates to make partitions which maximize the expected information content of the next weighing outcome. This is what I call "greedy information content strategy".
Noticing the (well known) fact that building a prefix-free binary code (with minimum average length) is equivalent to devising an strategy for finding an item with yes-no questions... it's quite evident that the greedy strategy (maximize the information content gained in each step) can be suboptimal. Because, in that scenario, the greedy strategy would correspond to the Shannon-Fano coding. And this code is suboptimal. In that page an example is provided in which the Huffman code (non greedy) performs better.