X = 16 à la première question.



J'ai construit l'arbre en partant de la fin, c-a-d, de feuille la plus en haut où j'ai mis 42 et j'ai complété le reste par déduction.

Joli schéma signé EfCeBa et deux autres bonnes réponses plus lacunaires...
Pour passer à la version originale (12 questions et N jusqu'à 299), il faut s'armer de raisonnements combinatoires

Pour des nombres de 1 a 42, un maximum de 3 réponses négatives et 6 réponses totales:
Les questions devraient être (dans l'ordre):
1) N est-il strictement supérieur à 16?
ensuite:
2) N est-il strictement supérieur à 5 ou 27?(suivant la réponse précédente)
3) N est-il strictement supérieur à 1, 9, 20 ou 34 ?
4) N est-il strictement supérieur à 2, 6, 12, 17, 23, 30 ou 38?
5) N est-il strictement supérieur à 3, 7, 10, 14, 18, 20, 25, 28, 32, 36 ou 40?
6) N est-il strictement supérieur à un des autres nombres pas déjà cités?

Le tout est de poser la bonne question qui tombe entre les bornes fixées par les réponses précédentes.

Pour le problème avec des nombres de 1 a 299, avec un maximum de 3 réponses négatives et 12 réponses totales:

1) N est-il strictement supérieur à 67?
2) N est-il strictement supérieur à 11 ou 123? (en fonction de la réponse précédente)
3) etc...

Je ne sais pas s'il y a un nom a la technique que j'utilise, mais ca ressemble a ca, pour le probleme de 3 négatives parmi 12:

3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 3, 5, 6, 7, 8, 9, 10, 11, 12, 4, 6, 7, 8, 9, 10, 11, 12, 5, 7, 8, 9, 10, 11, 12, 6, 8, 9, 10, 11, 12, 7, 9, 10, 11, 12, 8, 10, 11, 12, 9, 11, 12, 10, 12, 11, 12, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 3, 5, 6, ...etc...
la position des nombres est le nombre N, et le nombre est le numero de la question.
Par exemple, on poserait la quesition : "N est-il strictement supérieur à 10?" en 12eme position.

On peut être élagueur et esthète J'apprécie...

scrablor a écrit:

on ne peut poser que des questions du type « N est-il strictement supérieur à x ? »

j'avais compris que l'on pouvait également demander:
« N est-il strictement inférieur à x ? » puisqu'elle est du même type

comme quoi la résolution est d'abord une histoire de lecture

Généralisons un peu le problème :

Soit n le nombre de questions que l'on peut poser et p le nombre maximal de réponses négatives possibles. On va appeler S(n,p) le nombre de suites de réponses possibles :
[TeX]S(n,p)=\sum_{i=0}^{p}C_{n}^{i}[/TeX]
C'est en effet la somme de toutes les combinaisons à n digits binaires ne contenant pas plus de p "zéro".

On retrouve bien S(6,3)=42 et S(12,3)=299.

Il est clair que une réponse négative à la question N>Q ? définit un ensemble de Q valeur possibles de N.
Pour savoir avec quelle valeur on doit commencer l'interrogation, il suffit de remarquer que si on a une réponse négative à la première question, il nous reste n-1 question et p-1 réponses négatives possibles.

Donc, si on appelle Q(n,p) la question initiale à poser, on a Q(n,p) = S(n-1;p-1)

Pour n=12 et p=3, on a donc :
[TeX]Q(12,3)= S(11,2) =\sum_{i=0}^{2}C_{11}^{i}=67[/TeX]

Si on va au fond du schéma développé par dylasse on a l'algorithme complet du problème

On note :

n : le nombre maximum de questions à poser .
p : le nombre maximum de réponses négatives acceptées .
c : un compteur initialement nul pour répertorier les différentes réponses .
q : la question posée ( plus précisément : "le nombre est-il supérieur à q ?" )
r : 1 ( vrai ) ou 0 ( faux ) valeur Booléenne de la réponse à la question .

Au départ il y a [latex]S(n,p)=C_n^0+...+C_n^p[/latex] valeurs possibles .

Algorithme :

1°) q=c+S(n-1,p-1) .
2°) Si r=0 alors p=p-1 et si r=1 alors c=q .
3°) Si np>0 alors n=n-1 et retour à 1°) .
4°) Le nombre cherché est q+r .

Résultat qui peut paraître étrangement simple , le plus gros du travail ayant été fait par dylasse

Vasimolo