3
$\begingroup$

In the "guess-my-number" game, one player (player A) makes guesses at another player's (player B) secret number. All games would follow the following procedure:

  • Player B decides on a number between a known, set limit (for example, he/she may only choose a number between 1 and 100), this will become the player's "secret number" (the secret number must be an integer)

  • Player A then guesses an initial number

  • Player B responds by (honestly) declaring Player A's response to be either too high, too low, or correct

  • The process repeats, Player A guesses a number based on previous feedback, and Player B responds, until Player A guesses correctly

Anyways, I've heard that the most efficient method for Player A to guess player B's number would be the binary search, as it takes logarithmic time. First of all, I want to confirm that this is true, but I have another part to my question...

What if the game was modified so that Player B lied on occasion, under the following, known circumstances:

  • Player B only lies one-third of the time

  • Player B does not lie twice in a row

  • Player B only lies when the guess is too high, if the guess is too low or correct, Player B will not lie

  • When Player B lies, the lie is guaranteed to be that the guess is too low

Would it still be most efficient to perform a binary search, and if so, how would I modify it to fit this situation more precisely? Alternatively, what other algorithm would be most efficient?


edit: related: Twenty questions against a liar

  • 1
    The numbers are required to be integers, I hope.2012-01-12
  • 0
    @HenningMakholm Yes, the numbers must be integers2012-01-12
  • 1
    The question you linked to in your edit has the same problem that it never says what the objectives of A and B are. It does say "at most" several times, which seems to imply that A is trying to minimize the number of guesses in the worst case (so we don't need to know anything about how B acts). It would help if you could clarify whether this is also the case for your game, and if not, what the objectives are. As I stated in my answer, it's based on the premise that A is trying to minimize the number of guesses and B is trying to maximize it.2012-01-12

2 Answers 2