Sometimes arguments like that which appear in the puzzle can be useful in proofs. In their paper, An optimal strategy for a conflict resolution problem, (Venkat Anantharam and Pravin Varayia, Systems and Control Letters, 1986, pp. 329 -332), the authors consider a problem in which each of $n$ people has a number in $[0,1]$. The aim is to find out who has the greatest number, using the minimum expected number of yes/no questions, which are to be asked in sequence to everyone simultaneously.
Questions can be of the form "Whose number in subset $A$ of $[0,1]$?", for any subset $A$. They prove that it is optimal to restrict questions to the simplest form of "Whose number is bigger than $x$?" To prove this they use an argument like this:
We postulate the following genie:
The genie tells us which of the sets $A$ and $A^c$ ...
I omit the detail (see their paper if you like). I focus here on the idea that the genie is providing extra information that can make the optimal policy easier to figure out. The authors continue:
By postulating a genie we mean that we permit ourselves to use different strategies on events on which the genie gives us different answers. Clearly we can do no better without the genie than we can with it.
They then show that given the information provided by the genie, the optimal policy is one that could have been implemented without having that information, and which takes a special form. So they can conclude the optimal policy (without the genie) must also take this special form (i.e. that it suffices to ask questions of the simple form "Whose number is bigger than $x$?").
We see, however, that one has to be careful with this type of proof. In the puzzle we are drawn into thinking about a genie who tells us whether A is true or false. At issue is the fact that the policy which is optimal, given what the genie tells us about A, may have identical $u_0$, whatever the genie says, but this is only because we can act differently for $u_1, u_2, \dotsc$.
Questions can be of the form "Whose number in subset $A$ of $[0,1]$?", for any subset $A$. They prove that it is optimal to restrict questions to the simplest form of "Whose number is bigger than $x$?" To prove this they use an argument like this:
We postulate the following genie:
The genie tells us which of the sets $A$ and $A^c$ ...
I omit the detail (see their paper if you like). I focus here on the idea that the genie is providing extra information that can make the optimal policy easier to figure out. The authors continue:
By postulating a genie we mean that we permit ourselves to use different strategies on events on which the genie gives us different answers. Clearly we can do no better without the genie than we can with it.
They then show that given the information provided by the genie, the optimal policy is one that could have been implemented without having that information, and which takes a special form. So they can conclude the optimal policy (without the genie) must also take this special form (i.e. that it suffices to ask questions of the simple form "Whose number is bigger than $x$?").
We see, however, that one has to be careful with this type of proof. In the puzzle we are drawn into thinking about a genie who tells us whether A is true or false. At issue is the fact that the policy which is optimal, given what the genie tells us about A, may have identical $u_0$, whatever the genie says, but this is only because we can act differently for $u_1, u_2, \dotsc$.
