Problème 1025
Vingt-cinq mathématiciens assistent à la représentation du Mage Hic.Le point d'orgue du spectacle est le moment où le mage doit deviner des nombres entiers, compris entre 0 et 1025 inclus, que les mathématiciens ont choisis entre eux avant le début du spectacle.
Pour trouver chacun de ces nombres, le mage doit poser des questions, une au plus par mathématicien, auxquelles les seules réponses autorisées sont « oui » ou « non ».
- 1A. Quel nombre minimum de questions le mage doit-il poser pour être certain de trouver le premier nombre, sachant que les mathématiciens interrogés doivent dire la vérité ?
Pour le deuxième nombre, il est convenu qu'un des mathématiciens mentira s'il est interrogé, les autres disant la vérité. Mais le mage ne sait pas lequel, ni s'il fait partie des mathématiciens interrogés !
- 2A. Quel nombre minimum de questions le mage doit-il poser pour être certain de trouver le deuxième nombre ?
Le problème qui a généré le plus de confusion après le 1021. Les auteurs se sont clairement plantés, en ne considérant pas deux solutions meilleures que celle proposée : une en théorie de l'information respectant l'esprit du problème, et une purement logique. Me concernant, ayant eu la même idée que les auteurs, je me suis satisfait du fait qu'ils comptent correctes les 3 réponses.
Pour la solution considéré (codage de Hamming), j'ai seulement fait un programme qui vérifie expérimentalement la propriété de manière exhaustive (corruption de tous les bits pour tous les mots possible).
Le code est ici.
Pour la solution considéré (codage de Hamming), j'ai seulement fait un programme qui vérifie expérimentalement la propriété de manière exhaustive (corruption de tous les bits pour tous les mots possible).
Le code est ici.
- 1A. 11.
- 2A. 15 (les réponses 11 et 14 ont cependant été acceptées).