Guess the number

2021-12-15

python

The computer thinks a number x from 1 to N and the human tries to guess it.

That random number x in the range from 1 to n is generated by the function draw_lots(n). We keep guessing that number as long as the condition guess != x is true. In our program we assign 100 to N.

The question is how many iteration do we need to guess the nunber x.

#Guss the number
import random
N = 100
counter = 0 #counts number of guesses

def draw_lots(n):
    r = int(n*random.random()) + 1
    return r
    
a = 1   # left edge of range
b = N   # right edge of range
x = draw_lots(N)  # computer draws a random numbenr 
print("C: I thought a number. Guess it!\n")
guess = 0 # initianate our gues with 0 to enter the loop
while (guess != x):
    guess = int(input("C: put a number from " +  str(a) + " to " + str(b) +": " ))
    counter += 1
    if(guess < x):
        print("C: too small")
        a = guess
    elif(guess > x):       
        print ("C: two big")
        b = guess
    else:
        print ("C: you guessed my number. It was " + str(x))

print("\nC: you needed " + str(counter) + " moves.")

We need around $\log_{2}N$ moves to guess the computer number, so in our case it is $\log_{2}100$. It is around 7 times.

In python we can calculate it like this:

import math
value = math.log(100, 2)
print(value)

It gives us 6.643856189774725. The question is: why 7 moves (in this case) is enough or in general $\log_{2}N$ is enough to guess the number, where N is the original right edge.