Comments on Le retour du cruel Docteur No

The fun part with the first problem is that there are a lot of strategies that always succeed. I wonder if we can give an exact count.

Très belle énigme ! Le problème de solution rétro-gloutonne de User 42 est aussi très élégant.

Je rajoute juste un éclaircissement. Pour savoir la dernière valeur restante à la fin dans le jeu avec Alice et Bob, on voit que le jeu est équivalent au même jeu mais avec la valeur la plus basse selon le joueur qui termine, disons A, qui est enlevée. Quand cette valeur est enlevée, le joueur qui termine devient B, et donc la prochaine valeur à enlever est la plus basse selon B. Puis le dernier joueur change encore, on enlève la plus basse valeur selon A, puis selon B, etc. L'ordre dans lequel les objets sont éliminés par les joueurs est l'ordre inverse de celui-ci.

Ma solution:

Ba nggevohr q'ninapr à pundhr znguézngvpvra ha ahzéeb A rager 1 rg 100, pundhr znguézngvpvra nlnag fba cebcer ahzéeb. Dhnaq yrf puncrnhk fbag vafgnyyéf, yr znguézngvpvra snvg yn fbzzr zbqhyb 100 qrf ahzéebf dh'vy ibvg. Chvf vy snvg fba ahzéeb A zbvaf yn fbzzr dh'vy n gebhiér (gbhwbhef zbqhyb 100), rg naabapr yr eéfhygng (bh 100 fv yr eéfhygng rfg 0).

Qh pbhc: yr znguézngvpvra ahzéeb A n envfba fv rg frhyrzrag fv yr gbgny qr gbhf yrf ahzéebf rfg pbateh à A zbqhyb 100. Ha rg ha frhy znguézngvpvra qbaaren yn obaar eécbafr: pryhv qbag yr ahzéeb pbeerfcbaq à yn fbzzr eéryyr.

Cette solution a une propriété intéressante: un seul des mathématiciens donnera la bonne réponse, jamais plus. Ce qui me fait poser la question: y a-t-il une stratégie gagnante pour laquelle ce n'est pas le cas ? J'ai un argument probabiliste qui dit que non, mais je ne sais pas s'il est assez rigoureux.

Le voici: si je prends un mathématicien quelconque, quelle que soit sa stratégie, son numéro est aléatoire et il a donc une probabilité 1/100 de donner la bonne réponse. Ceci est vrai pour les 100 mathématiciens (évidemment, selon la stratégie, ces probabilités ne sont pas indépendantes). Donc l'espérance du nombre de mathématiciens qui trouvent leur numéro est 100*1/100 = 1 (ça me semble vrai mais je ne sais pas rendre cette étape rigoureuse). Quelle que soit la stratégie suivie, en moyenne il y a 1 mathématicien qui trouve. Dans le cas où tout le monde répond au hasard, parfois personne ne trouve, parfois 2 ou 3 mathématiciens trouvent… en moyenne ça fait 1. Avec la stratégie ci-dessus, ça fait toujours 1, point final.

Pour une stratégie donnée, soit P(n) la proba que n mathématiciens trouvent leur propre numéro. On a ∑P(n) = 1 (définition d'une proba) et aussi ∑nP(n) = 1 (espérance). Si la stratégie est gagnante (il y a toujours au moins 1 mathématicien qui trouve), alors P(0) = 0. On a donc (en soustrayant les sommes) ∑(n-1)P(n) = 0 pour n>1, et donc toutes les P(n) sont nulles pour n>1. Autrement dit, P(1)=1 et toutes les autres probas sont nulles.

CQFD: avec une stratégie gagnante, on a (presque-sûrement) un mathématicien qui trouve la bonne réponse, et un seul.

Ah, j'ai oublié de poster ça avec : <URL: http://www.cmapx.polytechnique.fr/~benaych/benaych.chapeaux.pdf >

Bonjour,

La réponse pour la question avec Alice et Bob me semble surprenante : la stratégie adoptée est un algorithme glouton mais renversé. C'est-à-dire que pour savoir la valeur restante à la fin, on commence par supprimer la valeur la plus petite selon le joueur qui *termine*, puis la valeur la plus petite selon l'autre joueur, et ainsi de suite.

Pour montrer ça, supposons que l'ordre selon le joueur qui termine soit 1 < 2 < ⋯ < n. Soit A le joueur qui commence (qui peut être ou non le joueur qui termine). Soit B l'autre joueur. On fait par récurrence sur n. Si A supprime la valeur 1, alors par hypothèse de récurrence le résultat obtenu est celui où les valeurs sont réduites à [3,n] et où B commence. Mais toujours par récurrence, il en va de même si A choisit 2. Ainsi on peut supposer que A choisit un élément de [2,n]. Mais pour chaque choix possible dans [2,n], par hypothèse de récurrence, le résultat sera le même que si on avait enlevé la valeur 1. Et donc on peut enlever la valeur 1.

Il y a peut-être un raisonnement plus explicatif que ça. Intuitivement, on n'a "aucun intérêt" à supprimer la dernière valeur car elle sera, dans le pire des cas, supprimée par le joueur qui termine.

In the first situation, Doctor No is more devious than it first seems. I knew the theoretical solution immediately, but it only works if all the mathematicians know basic arithmetic on small integers, and it's an easy bet that some of them will blunder that. I wonder if there's a solution that doesn't require that at all.

In the second situation, you might want to mention explicitly before the small font text that Alice has the first choice.