Question

Combinatorics:

6. A mathematician picks and integer i from the set {1,2,3,...,15} and a computer scientist tries to find the number by asking questions of the form: Is i<x, i>x, or i=x? Show that the number can always be found using three questions

Answer 1

Suppose the integer picked is denoted by i

Here follows the 3 questions :

Question 1. Is, i < 8 or i > 8 or i = 8

Now, if i = 8, we find the number as 8 only in the first question.

If i > 8, proceed as follows :

Question 2. Is, i < 12 or i > 12 or i = 12

If, i = 12, we find the number as 12 only in the second question.

Subcase 1 : if i > 12

Question 3. Is, i > 14 or i < 14 or i = 14

If i < 14 & already i > 12, so, i = 13

If, i = 14 then we find i.

If, i > 14, then i = 15

So, we find i in 3 questions.

Subcase 2 : if i < 12

Question 3. Is, i > 10 or i = 10 or i < 10

If, i > 10 & also, i < 12, so, i = 11

If, i = 10, then we find i

If, i < 10 & also, i > 8 then we find i as 9

So, we find i in 3 questions.

Now, we left another case : what if i < 8 right after the first question ?

Break it into subcases. Try with the middle numbers respectively as, i > 4 , or i = r or i < 4

& For the subcase, i > 4, try with i > 5 or i = 5 or i < 5

& For the subcase, i < 4, try with i > 2 or i = 2 or i < 2