Le Docteur No est de retour ! Il était plutôt occupé ces derniers temps à résoudre des problèmes informatiques, mais le voilà revenu et qui s'adonne à son passe-temps favori qui consiste à capturer des mathématiciens pour les soumettre à des énigmes idiotes (voir ici pour des épisodes précédents) :
Le cruel Docteur No a capturé 100 mathématiciens pour les soumettre à une épreuve démoniaque. Après avoir permis aux mathématiciens de se concerter initialement, il va placer sur la tête de chacun d'entre eux un chapeau portant un nombre entier entre 1 et 100 (inclus) de façon que chacun puisse voir le nombre porté par les chapeaux de tous les autres mais pas le sien. Les mathématiciens n'ont aucune information sur la manière dont les numéros seront attribués et il peut parfaitement y avoir des répétitions. Les mathématiciens n'auront plus le droit de communiquer à partir du moment où la distribution des chapeaux commence. Chacun devra émettre un avis sur le numéro qu'il pense que son propre chapeau porte : ces avis seront émis par pli secret et connus du seul Docteur No (i.e., les mathématiciens ne connaissent pas les réponses fournis les les autres). Le Docteur No est plutôt clément aujourd'hui : il libérera les mathématiciens si au moins l'un d'entre eux a fourni une réponse correcte (i.e., deviné le numéro que porte son chapeau) ; dans le cas contraire, il tuera tous les mathématiciens avec ses tortures particulièrement raffinées.
Les mathématiciens pourraient évidemment tous répondre au hasard (auquel cas ils auraient 63% de chances d'être libérés ; je laisse ça aussi en exercice mais ça n'a pas vraiment de rapport avec le problème). Mais en se concertant, ils peuvent s'arranger pour être certains d'être libérés : comment font-ils ?
La solution est simple, mais on peut perdre beaucoup de temps en cherchant dans la mauvaise direction. Je tire ça d'ici (la réponse est indiquée en rot13 dans un commentaire en-dessous) ; ce fil contient d'ailleurs un certain nombre d'autres devinettes rigolotes.
⁂
Sinon, voici un autre problème (pas vraiment une énigme), qui n'a absolument aucun rapport avec celui qui précède si ce n'est qu'il est venu à ma connaissance autour du même moment (il est inspiré de cette question mais c'est une variante assez différente du même genre d'idées) :
On considère n+1 objets et deux joueurs (Alice et Bob). Chacun des deux joueurs a un ordre de préférence (strict) sur les objets, et ces ordres de préférence sont connus de l'un comme de l'autre. Ils vont jouer au jeu suivant : chacun, tour à tour, va éliminer un objet, jusqu'à ce qu'il n'en reste plus qu'un (après n tours, donc). Ce dernier objet est gagné par les deux joueurs (i.e., ils se le partagent, ou si on préfère on peut dire qu'il y en a deux copies et que chacun en reçoit une, bref, chacun cherche à maximiser la valeur qu'il accorde à l'objet restant). Le jeu est à information parfaite (les deux joueurs savent tout : ce que l'autre joueur veut, et ce qu'il fait). Quelle stratégie vont-ils appliquer (en fonction des deux ordres de préférence) ? Et comment peut-on prédire efficacement l'objet final ?
On peut le formaliser plus précisément ainsi : soient 1,…,n les objets, triés dans l'ordre de préférence d'Alice (du moins préféré au plus préféré), et soient σ(1),…,σ(n) les valeurs de préférence de Bob pour les objets dans cet ordre, où σ est une permutation de {1,…,n} (c'est-à-dire qu'il aime le moins l'objet σ−1(1) et qu'il préfère σ−1(n)). Alice va jouer la stratégie qui cherche à maximiser la valeur i du dernier objet restant, tandis que Bob va jouer la stratégie qui cherche à maximiser σ(i) : on demande comment calculer i en fonction de σ et comment Alice doit calculer son premier coup. (On peut évidemment procéder de façon inductive : chaque coup possible d'Alice se ramène à un jeu de même nature avec un objet de moins et les rôles des joueurs échangés, mais ce que je demande c'est si on peut faire mieux ou plus simple.)
À titre d'exemple, si n=2 et que les préférences d'Alice sont 1<2<3, selon les valeurs (σ(1),σ(2),σ(3)) des préférences de Bob pour ces trois objets l'objet choisi est 3 (le préféré d'Alice) dans tous les cas sauf si (σ(1),σ(2),σ(3)) vaut (2,3,1) ou (3,2,1) (i.e., si l'objet préféré d'Alice est celui que Bob aime le moins), auquel cas l'objet choisi est 2 (le deuxième préféré d'Alice). C'est assez intuitif.
Il se peut que la réponse soit très facile : je n'ai pas pris le temps d'y réfléchir (trop occupé que j'étais à coudre des numéros sur des chapeaux).
On pourrait aussi demander ce qui se passe si l'un des joueurs joue la stratégie « gloutonne » (consistant à éliminer à chaque coup son objet le moins préféré), selon que l'autre joueur le sait ou selon que l'autre joueur croit toujours qu'il jouera désormais de façon rationnelle. On pourrait aussi jouer à changer l'alternance des coups entre Alice et Bob (plutôt que de les faire alterner mécaniquement) et chercher l'ordre le « plus équitable » dans un sens qu'il faudrait formaliser. Bon, bref, je trouve l'idée générale du jeu intéressante, mais je ne sais pas quelle est la bonne question à poser (c'est peut-être ça la question, en fait : trouver la question la plus intéressante à poser sur ce jeu).