Prouver qu'il suffit de sept coups

1.

def deviner(secret):
    bas, haut = 1, 100
    coups = 0
    while bas <= haut:
        milieu = (bas + haut) // 2
        coups = coups + 1
        if milieu < secret:
            bas = milieu + 1
        elif milieu > secret:
            haut = milieu - 1
        else:
            return coups

mesures = [deviner(s) for s in range(1, 101)]
print(max(mesures), sum(mesures) / 100)   # 7 5.8

Sept coups au pire, et $5,8$ en moyenne.

2. Démonstration. À chaque coup, le milieu est testé et éliminé, et il reste au plus la moitié des candidats (la plus grande des deux parts, à droite du milieu) : de $100$ on passe à au plus $50$, puis $25$, $12$, $6$, $3$, $1$. Après $k$ coups il reste au plus $\lfloor 100/2^k\rfloor$ candidats ; après six coups il en reste au plus un, que le septième coup trouve. Comme $2^6=64<100\le 128=2^7$, sept coups suffisent toujours, et six ne suffisent pas pour toutes les valeurs (le programme du 1. en trouve : max(mesures) vaut $7$).

3. Il faut le plus petit $k$ tel que $2^k\ge 10^6$, soit $k=20$ (car $2^{19}=524288$ et $2^{20}=1048576$).

Ce que ce chiffre dit : multiplier l'espace de recherche par $10000$ ne coûte que $13$ coups de plus. Une recherche séquentielle, elle, passerait de $100$ à un million d'essais. C'est le même gain que la dichotomie de la racine carrée vue au chapitre 4.