Question 45
Isaac and Jeremy play a game. Isaac tells Jeremy that he is thinking of some $2^n$ integers $k_1, \dots, k_{2^n}$, where $n$ is a positive integer. Jeremy asks questions of the form "is $k_i \lt k_j$?", to which Isaac answers truthfully. After $n2^{n-1}$ questions, Jeremy must state whether or not Isaac's numbers are all distinct. Show that Jeremy has no way of ensuring that his statement is correct. Jeremy's questions may depend on the answers he has already received, and are exactly determined by them.
[Slightly harder formulation: instead ask "Can Jeremy ensure that his statement is correct?"]
[Slightly harder formulation: instead ask "Can Jeremy ensure that his statement is correct?"]