Playing Guess Game Using Recurrence Relation

In a TV game show in 2002, there was a guess game. It is easy to play and excited. That’s why the game is played in many situations. Let’s think of a question: If there are only 2 people playing the guess game, how should we choose the number to maximise the winning probability? Which player, the first one or the second one, is of greater advantage?

Let’s explain the instruction of game before the discussion:

1. A interval of integers is chosen, say 1 to 100. A judge then selects one of the numbers in the interval to be the “bad number” without letting the players know;

2. Two players choose a number from the range in turn. If anyone chooses the bad number, the game ends and his opponent wins. Otherwise, the chosen number should split the interval into two while the bad number is contained in one of them. His opponent then chooses a number from the interval with the bad number.

Here is an example:

Suppose the bad number is 45. If the first player (denoted by X) chooses 25, then the second player (denoted by Y) should choose his number among the integers from 26 to 100. If Y chooses 90, then the interval that X should choose his number is from 26 to 89. The game ends when someone chooses 45.

The interval of 1 to 100 is too large to handle. Let’s discuss smaller ones first. (Note: In the following discussion, we assume the judge chooses the bad number randomly, so the probability for each number to be the bad number is equal.)

1. If the interval has 1 number, say 1, then 1 is the bad number obviously. Therefore, the probability that X wins is 0.

2. If the interval has 2 numbers, say 1 and 2, the the probability that X chooses the bad number is . If he does not choose the bad number, then Y has only one choice, so he definitely loses. Therefore, the probability that X wins is .

3. If the interval has 3 numbers, say 1, 2 and 3, the the probability that X chooses the bad number is no matter which number is bad. If he chooses 1 and does not lose, then Y returns to case B (an interval with 2 numbers). In this case, Y has a winning probability of . Therefore, the probability that X chooses 1 and win is . If he chooses 2 and does not lose, then the bad number is either 1 or 3. If 1 is bad, Y returns to case A and has a zero winning probability. If 3 is bad, Y returns to case A and has a zero winning probability. Therefore, the probability that X chooses 2 and wins is . Obviously, the case where X chooses 3 is similar to that he chooses 1, the winning probability of X is . Hence, the best strategy for X is to choose 2, he has a winning probability of .

In the discussion, we see that we need to adopt the results in smaller cases (i.e. cases A and B) when we discuss the case with an interval of 3 numbers. Therefore, we can imagine that it should be done similarly when we seek the best strategy for larger and larger intervals. It is the recurrence relation in mathematics.

Let’s have several definitions first:

When an interval has n numbers, say 1, 2, …, n, the probability that X chooses k and wins eventually is defined as P(n, k). We also define . It is the maximum winning probability that X can attain.

For example, here is a table about the results above:

Table 1: Some preliminary results

We want to compute all relationships among each P(n, k) and P_m(m < n).

Let the interval have n numbers, say 1, 2, …, n. If X chooses k, then the probability that he loses immediately is . If he does not lose immediately, then there is a probability of that Y chooses the his number from k – 1 numbers namely 1, 2, 3, …, k – 1; and a probability of that Y chooses his number from n – k numbers, namely k + 1, k + 2, k + 3, …, n. If the former case occurs, the winning probability of Y is P(k – 1), i.e. the winning probability of X is 1 – P(k – 1). Therefore, the winning probability of X in this case is .

Similarly, the winning probability of X in the latter case is  . Therefore, we have [2]. From the results in Table 1, we can compute Table 2:

		Pn

Table 2: The values of P (n, k) and P_n

Although Table 2 lists out the cases for n not greater than 13, we can observe the pattern in the table which repeats every 4 rows.

The proof of the pattern is not difficult, so it is omitted here. From Table 2, we have:

• When n º 0 (mod 4), k º 2 or 3 (mod 4) maximises the value of P(n, k). In this case, ;
• When n º 1 (mod 4), all values of P (n, k) are identical. In this case, ;
• When n º 2 (mod 4), k º 1 or 2 (mod 4) maximises the value of P(n, k). In this case, ;
• When n º 3 (mod 4), k º 2 (mod 4) maximises the value of P(n, k). In this case, .

Therefore, if we can choose to be the first or second player, we should choose:

• When n º 1 (mod 4), the second player;
• When n º 3 (mod 4), the first player;
• When n is even, there is no difference between two choices.

Suppose the length of the remaining interval is n.

• When n º 0 (mod 4), choose (4t +2)th or (4t +3)th number;
• When n º 1 (mod 4), any choice will do;
• When n º 2 (mod 4), choose (4t +1)th or (4t +2)th number;
• When n º 3 (mod 4), choose (4t +2)th number.

(t is any non-negative integer)

We can have an interesting fact from the tabulated results. Unless there is only one number left (If so, we definitely loses), we can always choose the second number to attain the maximum winning probability.