# Failure of Maximum Information Content Strategy for Puzzle Solving

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

• This Vsauce 2 video provides an example (at least one where a greedy algorithm fails - I'm not sure about a "greedy information content strategy"). May 27 '20 at 0:33