This description is quite long. If you are interested only in the algorithm for solving the problem, you can jump right to the last couple of paragraphs.
The original game "Guess the number" is a classical example of a problem which is usually solved by binary search. Our problem is quite similar to this game, so one might be tempted to try some variation of binary search.
The easiest approach would work by using questions 1, 3, 5, ... (in easy case) or 1, 4, 7, ... (in hard case) for the actual binary search and ignore all the other questions. For example, if the interval of valid numbers was <1,15>, the exchange might look this:
Submit 1: 8 Answer: <nothing useful> Submit 2: <some pad> Answer: 8 is GREATER than my number Submit 3: 4 Answer: <nothing useful> Submit 4: <some pad> Answer: 4 is SMALLER than my number Submit 5: 6 Answer: <nothing useful> Submit 6: <some pad> Answer: 6 is SMALLER than my number Submit 7: 7 Answer: <nothing useful> Submit 8: <some pad> Answer: You're RIGHT, it's 7!
This approach would, however, double/triple the number of needed questions, so it might not be feasible (in easy case it might need 20 submissions, in hard case 27, which is more than you're allowed). Therefore, we'll need to find a better algorithm. First we'll describe how will it work in the easy case and prove its optimality. Then we briefly sketch its generalization to the hard case.
Our first improvement is simple – after each submit, we'll guess what the answer will be and generate further question(s) accordingly. If the guess was correct, we will save some questions, otherwise we are in the same position as above. The communication using this strategy might look like this (using the same interval as in the example above):
Submit 1: 8 Answer: <nothing useful> Submit 2: 12 (guess: 8 < his number) Answer: 8 is GREATER than my number [Oh, our guess was wrong...] Submit 3: 4 Answer: <nothing useful> [We already knew that 12 is GREATER.] Submit 4: 6 (guess: 4 < his number) Answer: 4 is SMALLER than my number [And we were right this time!] Submit 5: 7 (guess: 6 < his number) Answer: 6 is SMALLER than my number [And again!] Submit 6: <some pad> Answer: You're RIGHT, it's 7!
In our example we have saved two questions. It can easily be seen that the average case of this strategy is better, but the worst case is the same as when using the trivial approach. Even this simple strategy was sufficient to solve the easy task, but probably with an unnecessary large number of questions.
Now we will improve our strategy to an (worst-case) optimal one. Look at the example above and suppose that we could ask only X questions. Our first submit in the example was the number 8. If our first guess (which we made when we were deciding about the number in our second submit) was correct, we would have (X-1) questions left to find the correct number among 7 numbers (9-15). If, however, our guess was wrong, we would have only (X-2) questions left and again 7 possible answers (1-7). The second case is obviously worse than the first one. But – we can improve it. Suppose that the first submit would not be the number in the center of the current interval. Thus we divided our interval into two new ones with different lengths. Our guess will (naturally) be that the number we seek is in the longer one. If we are correct, we still profit from our guess. If we are wrong, we are left with a shorter interval than with the strategy above. What remains is to formalize this approach and to find the best place to divide the interval.
Let's try to formally solve a dual problem we already sketched above – if we have X questions, how big can be N (the length of the interval of valid numbers)? We'll denote this number B(X). Clearly, if X=1, we aren't able to do anything useful because after our first submit, we won't get any answer from TM. So, B(1)=0. If X=2, the best we can do is to submit one number (for example, "1") in our first question and hope it's right (again, the last (=second) submit would be irrelevant). Therefore, B(2)=1. Now, let's have X>2 questions, the correct answer is C and let's say we submitted P in the first question. and Q in second (we'll assume that P and Q are distinct; it would make no sense to ask the same thing twice). There are three possibilities – P can be the right answer or Q and C can both lie on the both side from P (i.e. both are smaller or both are greater) or they can lie on opposite sides (one is smaller than P, one is greater).
In the first case, we can celebrate. In the second, we were also quite lucky, our guess was correct and we haven't lost any questions. So, in this case, after the first question, we are left with (X-1) questions. In the last case, we weren't lucky and we have lost one question. In other words, we are left with (X-2) questions (just like we described in the example above). In (X-1) questions we are able to find the right answer among at most B(X-1) numbers – therefore the length of the longer interval may be at most B(X-1). Similarly, the length of the shorter interval may be at most B(X-2). It follows that B(X)=B(X-1)+B(X-2)+1 (the +1 comes from the lucky case).
Naturally, we also have to choose P and Q carefully. The choice of P is easy – just choose it such that it splits the interval of length B(X) into two intervals of lengths B(X-1) and B(X-2). We'll choose Q from the longer of these two intervals. Thus if C fell into it, we would have (X-1) questions (including Q) left. Still, there is a little catch – we have to submit Q before we find out whether C fell into this interval or not. Fortunately, this problem can be resolved easily – the length of the interval is B(X-1), also if we want to find the right answer with (X-1) questions, we have to choose Q in the same way as we did choose P, but for an interval of length B(X-1).
The hard version of the problem is very similar. Again, it'll be useful to know the maximal length A(X) of an interval we are able to solve with X questions. Clearly, A(1)=0, A(2)=0, A(3)=1. In this case, we have to think two steps ahead – so we have to find three questions P, Q, and R and consider all their relative positions (like, C<P<Q<R, etc.). Surprisingly, the recurrence in this case is also very simple, namely A(X)=A(X-1)+A(X-3)+1. The method of choosing P will be almost the same as in easy case – just choose it such that it splits the interval into subintervals of length A(X-1) and A(X-3). Q and R will be chosen from their respective subintervals using the same method (i.e. Q will split the subinterval of length A(X-1) into A(X-2) and (A-4) and R will split the first of them into A(X-3) and A(X-5)).
The algorithm for the easy version of the problem:
The algorithm for the hard version of the problem is very similar: