Il me semble que k réponses où k est le plus petit entier tel que $2^k\geq N$ est un bon candidat

Vasimolo

Exprimer la borne supérieure en base 2, puis compter le nombre de digits. Si je ne me trompe pas, ce nombre de digits est la réponse cherchée.

Klim.

$$ceiling\,(\log_2 N)\,?$$
où ceiling(x) est le plus petit entier supérieur ou égal à x
On procède par dichotomie.
(Il faut n réponses pour distinguer $2^n$ ≥ N  cas)

La logique voudrait que l'on réponde log2(n), en procédant par dichotomie.
Cependant, on a vu récemment que pour une question à laquelle on répond par oui ou non, il existe le cas où il n'y a pas de réponse; donc on peut même faire log3(n)

Par exemple, pour trouver un nombre entre 1 et 9; on peut poser 4 questions basiques:
- est il compris entre 1 et 4? non
- est il compris entre 5 et 7? oui
- est il compris entre 5 et 6? oui
- est-ce 5? oui
=> La réponse est 5

mais on peut aussi faire en 2 questions:
- l'ensemble A contient les chiffres de 1 à 3; ne contient pas les chiffres de 7 à 9; quant aux chiffres de 4 à 6 je ne te le dis pas. Le nombre est-il dans A? réponse "?"
- l'ensemble B contient 4 et pas 6; quant à 5 je ne te le dis pas. Le nombre est-il dans B? réponse "?"
=> La réponse est 5

On ne peut éliminer que la moitié des nombres à coup sûr à chaque question, donc je verrais bien

n questions, avec n minimum pour avoir 2^n > N

gwen27 a écrit:

On ne peut éliminer que la moitié des nombres à coup sûr à chaque question, donc je verrais bien

n questions, avec n minimum pour avoir 2^n >= N

Je récupère cette réponse, qui est d'une limpidité absolue... en changeant le "strictement supérieur" en "supérieur ou égal" néanmoins.

La formulation mathématique brute a été correctement donnée par Franck et Halloduda.

Bravo à tous !