Question

Two persons (A & B) play guess the number game. First person choses an integer in the
range [1,10] and second person has to guess it by asking questions that the first person can only
answer in yes or no.
a) Person B asks questions in the sequence, “is it x?” where x=1, 2, …, 10 e.g. first question would
be, is it number 1. If no, 2nd question would be, is it number 2, etc. Find the expected number
of questions person B asks to guess the number.
b) Person A asks questions such that to eliminate half of possibilities. For example, is the number
greater than 5, if no, 2nd question: is the number greater than 2 etc. Find the expected number
of questions person A asks to guess the number.

Answer 1

a) Probability that B gets it right first time is 1/10, and he asked 1 question

Probability that B gets it right second time with 9 numbers remaining is 1/9, and he asked 2 questions. But B should have failed in the first question, so we need to multiply by 9/10. Thus overall, probability that he needs to ask the second question is still 1/10. That is,

In short, the probability that B gets it right on each of the 10 questions is the same, 1/10.

Hence, expected no of questions asked,

Note that we do not add the 10th question, because B won't ask this question. In 9th question itself, he would know the answer

b) In terms of total questions asked, A has only two choices

First of all, note that the data (number of questions) is not symmetric w.r.t. the division of subparts into equal halves.

Note that in this strategy, A cannot get a definite answer in the first, and not even in the second question, because his strategy is to divide the range and not hit the number directly. For ex, say B responds "No" to first Q is it greater than 5? Then A knows numbers are 1 to 5. So he asks "Is to greater than 2" , and again B will either say Ye or No. In either case, A can never have the answer to what is the number, he only has possibilities.

Now we need to do some critical analysis. After A has asked the second question, note that there are two numbers on one side (ex. 1, 2, call this Group1) and 3 numbers on the other side (ex. 3, 4, 5, call this Group2). The probability that we land up to choose from Group1 is 2/5 (because there were 5 numbers in the lot initially) and the probability that we land up in Group2 is 3/5.

If we have Group1, then we only need to ask one more question: our third question, and we are done for sure. That is, A asks "Is it 1?" - answer could be yes: number is 1, or answer is No: number is 2.

If we have Group2, we may need to ask either 1 or 2 more questions, depending on our luck. Note that we are left with 3, 4, 5. A would ask "Is it greater than 4", if answer is Yes (for which the probability is 1/3) we are done after having asked 3 questions. But if answer is No (for which the probability is 2/3) we have both 3, 4 remaining and A shall ask the final 4th question.

So A will need to ask just 3 questions if either he was in Group1, or if he was in Group2 and the answer to the question was Yes

But A will need to ask 4 questions if he was in Group2, and answer to the question was No

Thus, the expected number of questions that A asks are