Another variant: this weekend I (foolishly) tried to impress my son by guessing his number from 1..100 in <=7 queries. After "50?-Less", "25?-Less" he said "This is boring. If I give you the same answer 3 times in a row you lose."
Now what's the best strategy?
An infinite version of the game is easy to analyse. Here, one picks a real number in some interval; the guesser tries to shrink the interval containing the number as quickly as possible, but mustn't allow three consecutive same answers. So, if the last two answers were the same, the guesser must waste a guess, to ensure the opposite answer. If the last two answers were different, he splits the interval according to the golden ratio (GR), so that the new answer is more likely to be different from the last answer. If he gets the different answer, he has reduced the interval by GR; if he gets the same answer, he has reduced by GR^2, but must waste a guess. Either way, he reduces by GR per guess. In the finite game (1..N), you never quite waste a guess, so you should converge faster. The roundoff errors likely have a lesser effect. Furthermore, you can start right in the middle. Anyway, 1+ceil(log_GR(N/2)) guesses should be enough. For N=100, that's 1+ceil(8.13)=10. For the 1..100 game, a quick computation shows that if one - starts with 50, - guesses the safe extremum when necessary, and otherwise - rounds the GR split to the nearest integer, then one always wins within eight guesses, and the average (over all 100 games) is 6.49 guesses. I don't mean to say that that's optimal, but it might be close.
(Perhaps posed as casino games: ante $1, the house pays $100 for a hit on the first guess, then reduces the payoff by half (rounded down) each time it answers...) I'd average $5.06 payoff ($4.06 profit) per game.
Given an optimal Guesser, what numbers are the Hider's best choices? That makes a difficult game-theory problem. If I knew that Hider would pick one of my 8-guess numbers (according to the strategy above), I'd shift to a slightly different strategy which gets those numbers sooner. But he knows I'd do that, and so... There are _so_ many Guesser strategies: the payoff matrix might be practically unconstructable, never mind solvable.
-- Don Reble djr@nk.ca