The optimal strategy for $n=13$ (and similarly for any odd value of $n$) is to try $2,3,\ldots,n-1=12$ first, which will catch the opponent if and only if she started on an even number; if the opponent is still not caught, one is sure she started on an odd number. In that case one is now (after $n-2=11$ moves) on an even number (in particular not on $n=13$), and trying $12,11,\ldots2$ is sure to catch her, for a total of $2*11=2n-4=22$ tries.
The same scheme works for $n=12$ (and similarly for any even value of $n$): try $2,\ldots,n-1=11$ first, which will catch the opponent if and only if she started on an even number; if she still not caught, one is sure she is now (after $n-2$ moves) again an odd number (in particular not on $n=12$), and trying $n-1=11,\ldots2$ is sure to catch the opponent, for a total of $2*10=2n-4=20$ tries.
Added: Here is the full analysis of the game. It clearly splits into two parallel games, one where the opponent starts odd and another where she starts even. The opponent chooses a game at the start and has to stick to it, but we don't know which it is, so we need to reduce to number of remaining potential positions in both games to $0$. On each move we remove one of the potential positions, but then the remaining possible positions are replaced by the set of all their neighbours; this also happens in the game we didn't play in. If one switches back-and-forth between games (playing game $A$, then at leat once game $B$ then again game $A$), then the before the second move in game $A$ the number of potential positions in game $A$ (if the first move didn't reduce it to $0$) has again grown to at least the same number it was before the previous move in $A$, so this gains nothing; an optimal strategy therefore should avoid such switching. We must therefore choose a game to play in first, terminate that game entirely, and then start playing in the other game.
Now focussing on one game (so the parity of the possibilities at each point in time is known), one may verify that the only type of move that actually reduces the number of remaining possibilities is where those possibilities form an "interval" (in the sense of the numbers of a given parity in a given interval) containing one of the extremities of the total set: by playing the other end of the interval, the possibilities are reduced to those of the opposite parity between the ends of the original interval. (The claim "only" is not entirely true: (1) whenever the possibilities have been reduced to a singleton, one can play that to reduce it to $0$, and (2) if $n$ is odd and all odd numbers remain possible, their number is bound to decrease regardless of our move. However these possibilities are marginal and do not affect our analysis.) After such a move one cannot reuse the number again on the next move, but by playing again on the same end of the (new) interval one can at least prepare do decrease it on the move after that.
There are four types of games, according to the parity of $n$ and of the initial possibilities. The two variants with $n$ even are left-right mirror images, and the "initial even" one can be won in $n-2$ moves by playing $2,3,\ldots,n-1$. So can the "initial even" game with $n$ odd. The game with $n$ odd and initial possibilities odd however needs $n-1$ moves: the very first move makes no difference whatsoever, and then the "initial even" game remains. Since we have the choice which game to play in first, and since for $n$ odd the "initial even" game requires an odd number of moves, we can play that first and have transformed the other game into another "initial even" game, so in the end we can still win in $2(n-2)$ moves, regardless of the parity of $n$.
Your strategy is completely defined by specifying, for each number in $\mathbb R$ that you might see, the probability that you guess that it's the higher one. You can only guarantee a winning percentage $\gt\frac12$ if this probability strictly monotonically increases. (Otherwise I can pick a pair where it hasn't increased.) So this probability that defines your strategy is a strictly increasing function $f:\mathbb R\to[0,1]$.
For any $\epsilon\gt0$, I can find $n\in\mathbb N$ such that $f(n+1)-f(n)\lt\epsilon$ and write down $n$ and $n+1$. For if not, the function would increase by at least $\epsilon$ in each integer step, and thus would increase beyond any bound, in contradiction to it being bounded to $[0,1]$. But your winning percentage above $\frac12$ is proportional to this difference. Thus no matter how you choose $f$, I can make your winning percentage as close to $\frac12$ as I want.
Best Answer
The winning result sequences need to be mapped in lexicographical order (with “lower” $\lt$ “correct” $\lt$ “higher”) to the possible numbers. To solve a smaller example first: If you have four guesses and no two consecutive guesses may be the same, the winning result sequences are, in order:
LC,LHLC,LHC,C,HLC,HLHC,HC. So you can differentiate between the numbers from $1$ to $7$, and you can read off the required guesses from the sequence by always guessing the number that hasCin the current position: The first guess is $4$, and then for “lower” you need to guess $1$, then $3$ and then $2$ (and symmetrically opposite for “higher”).In part a, the numbers $1$ to $19$ remain, and the winning sequences (without the inital “lower”)
LC,LHLLC,LHLC,LHLHC,LHC,LHHLC,LHHC,C,HLLC,HLLHC,HLC,HLHLC,HLHC,HLHHC,HC,HHLLC,HHLC,HHLHC,HHCremain, in that order. So we have exactly the right number of sequences left to differentiate between the numbers left, and reading off the required guesses yields the decision tree linked to in Daniel Mathias’s comment under the question. This also yields the answers to parts b and c.For part d, it would be rather cumbersome to list all the sequences by hand, so we can ask more generally: How many sequences of at most $n$ letters in {
L,C,H} are there that contain a singleCat the end and don’t contain three consecutiveLs orHs? We can just drop the finalCand equivalently ask for the number of strings with at most $n-1$ letters in {L,H} that don’t contain three consecutiveLs orHs.Let $a_n$ denote the number of such strings, and $b_n$ the number of them that don’t end in
L. Then $a_n=2b_n-1$ (since the empty string ends in neither letter), and $b_n=b_{n-2}+b_{n-1}+1$ (since an admissible string not ending inLis either the empty string or can be produced by appendingHorHHto a string not ending inH). Thus $b_n+1$ satisfies the recurrence of the Fibonacci numbers, and since $b_1=1$ and $b_2=2$, it follows that $b_n=F_{n+2}-1$ and thus $a_n=2F_{n+2}-3$.So we have $a_6=2F_8-3=39$, in agreement with the fact that you were able to distinguish $39$ numbers with $6$ guesses (if the answer to your initial guess of $20$ had been “higher”, you would only have been able to distinguish $19$ of the $20$ remaining numbers from $21$ to $40$); and for $n=8$, we find that with $8$ guesses you could distinguish between $a_8=2F_{10}-3=107$ numbers.
While each unrestricted question allows you to distinguish twice as many numbers, each of these restricted questions only increases the number of distinguishable numbers by about a factor of $\phi=\frac{\sqrt5+1}2\approx1.618$, the golden ratio, so instead of one bit per unrestricted question you only gain about $\log_2\phi\approx0.694$ bits of information per restricted question.