[harvey]

Il n'y a pas deux joueurs, mais 32 ! Autant que de boutons.

Avec deux joueurs/deux boutons, la solution ressemble à ce que tu décris. Ils s'arrangent pour ne pas presser le même. Si le premier réussit, le second aussi, ils ont donc une chance sur deux.

(Et on peut effectivement parler de tiroirs à la place, c'est d'ailleurs comme ça que le problème était originalement formulé)


J'ai oublié de préciser: la configuration de la machine (quel bouton correspond à quel nom) est choisie au hasard.
(ou pas, en fait osef)

[Darkkuk]

Ah, aux temps pour moi, désolé. Malgré la relecture, j'ai apparemment lu trop vite l'énoncé..

Avant de proposer à nouveau une solution et avant de paraître ridicule une seconde fois, je vais poser une question supplémentaire :
Sait-on à quel essai le joueur a trouvé son nom ? Je veux dire par là : mettons que le premier joueur trouve son nom au 13e essai par exemple, les autres joueurs savent-ils qu'il n'est pas allé jusqu'au bout et qu'il s'est arrêté au 13e essai ?

[harvey]

Non, il n'y a aucun retour d'information. Les épreuves peuvent aussi bien se faire en parallèle.

[pixis]

C'est mon énigme préférée, j'adore l'aspect contre-intuitif du résultat en trouvant une stratégie qui fait passer les chances de 1/(2^32 ) à un ratio bien plus important (effectivement de l'ordre du 1/10). C'est le même genre que le paradoxe des anniversaires. J'aime beaucoup

[BAAL]

Le meilleur que je trouve pour l'instant c'est que les premiers 16 choisissent les 16 premiers boutons. Les 16 restants choisissent les boutons restants.
Ça donne un taux de réussite de [(16!)^2]/[32!], soit environ 1.66e-9. Pas terrible...

Ça donne le bon résultat pour 4 joueurs (le seul cas que j'ai pu vérifier à la main).

Si je m'autorisais à coder j'aurai peut-être une meilleur idée de stratégie...

Edit:
J’ai oublié de préciser... J’arrive à ce résultat pathétique après plusieurs heures de recherche... J’ai même trouvé une probabilité de plus de 2000.

[harvey]

Quelques chtiots indices, si vous voulez encore chercher. Y'a pas de mal à sécher, c'est vraiment pas évident. Sinon Pixis a d'autres jolies énigmes sous le coude.

- Le nombre de joueurs pourrait être 100, 1000 ou 2^1000, ça ne change pas grand chose. La probabilité de succès est (presque) la même, et tend vers une constante quand ce nombre augmente (on suppose naturellement que les joueurs ne commettent pas d'erreur). Cette constante limite est 1-ln(2).
- On pourrait se demander si le choix de la bijection (assignations bouton<->nom) n'a pas un impact. En fait, les joueurs peuvent annuler la stratégie de l'organisateur, s'il y en a une, de sorte que tout se passe comme si ce choix était aléatoire (cette remarque est plus pertinente en rapport avec la formulation habituelle du problème, qui donne des numéros aux joueurs).

Enfin:
Le fait que chaque joueur puisse voir l'affichage à mesure qu'il passe l'épreuve est capital.

[BAAL]

Aaaaaaaah, je n'arrive pas à croire que je n'ai pas pensé à concevoir une stratégie utilisant ce que tu suggères sous le "Enfin". Je me disais bien que c'était impossible sinon . Je vais m'y remettre du coup. Je dois pouvoir y arriver maintenant...

[pixis]

Sinon Pixis a d'autres jolies énigmes sous le coude.

Yes, j'en ai deux très sympathiques, une fois que celle en cours sera résolue, je vous les posterai.

Have fun BAAL sur celle de Harvey, elle est vraiment intéressante, et pas triviale

[Stockage]

Les joueurs ont quelques heures pour se préparer et discuter de leur stratégie. En revanche, il ne peuvent plus communiquer dès que le jeu commence.
La salle où se trouve la machine est insonorisée, entourée d'une cage de Faraday, et toute tentative de triche les condamne à 30 ans de travaux forcés dans les mines de Necropost sur la ceinture d'astéroides.

Les joueurs peuvent-ils rester aussi longtemps qu'ils veulent dans la salle ?
Je veux dire, utiliser le temps est-il autorisé ou est-ce considéré comme de la triche ?

[pixis]

Non, ils ne peuvent pas jouer sur le temps.

[BAAL]

Bon je crois avoir enfin trouvé la solution!

Merci pour les indices! C'était pas évident du tout, ainsi que pour l'énigme, elle était très sympa.

Savoir qu'on cherche une limite autour de 0.30 m'a indiqué que ma solution pour 4 participants (0.25) n'était pas assez bonne. Et quand on se rend compte qu'ils peuvent utiliser le résultat qu'ils voient avant de choisir le prochain bouton on se rend compte qu'ils peuvent effectivement faire mieux que 0.25.
Au lieu de choisir en avance les boutons 1 et 2, le premier participant doit commencer par le bouton 1, puis choisir le bouton correspondant au numéro qu'il aura trouvé, ce qui donne une indication supplémentaire aux suivants. Par exemple s'il tombe sur le bouton 3, il appuye le bouton 3.
Quand ça sera le tour du participant numéro 3, il commencera par le bouton 3, s'il tombe sur 3 c'est bon, sinon il sait que son nom sera associé au bouton 1.

Pour 4 participants on trouve facilement une probabilité de 10/24 en listant toutes les possibilités (ce que je montre ci-dessous).

Pour plus de 4 participants à première vue on pourrait penser que la stratégie ne marche plus et qu'il faut l'améliorer, mais finalement non!

En fait on se retrouve avec un certain nombre de cycles mutuellement exclusifs. Par exemple avec 6 participants si les boutons 123456 font afficher les participants 451326, on a les cycles: 431, 52, 6. La stratégie est gagnante dans ce cas car chaque cycle a une longueur inférieure ou égale à 3 (le nombre de choix pour 6 numéros).

La question est donc: pour n participants, quelle est la probabilité qu'aucun cycle n'ait une longueur strictement supérieure à n/2?

Ce n'est pas immédiatement évident. On fait donc quelques tests pour des n pas trop grands:

n=2:
permutations possibles - groupement possibles
12 - (1)(2)
21 - (12) PERDU

n=4:
1234 - (1)(2)(3)(4)
1243 - (1)(2)(34)
1324 - (1)(23)(4)
1342 - (1)(234) PERDU
1423 - (1)(234) PERDU
1432 - (1)(24)(3)
2134 - (12)(34)
2143 - (12)(34)
2314 - (123)(4) PERDU
2341 - (1234) PERDU
2413 - (1234) PERDU
2431 - (142)(3) PERDU
3124 - (123)(4) PERDU
3142 - (1234) PERDU
3214 - (13)(24)
3241 - (134)(2) PERDU
3412 - (13)(24)
3421 - (1234) PERDU
4123 - (1234) PERDU
4132 - (124)(3) PERDU
4213 - (134)(2) PERDU
4231 - (14)(23)
4312 - (1234) PERDU
4321 - (14)(23)

Ici on voit qu'on gagne sur 10/24 des cas. Le 24 s'obtient facilement avec 4!.
Mais comment obtient-on le 10? Ou alors 24-10=14?
Essayons de compter le nombre de cas où on perd (14):

2341 - (1234)
2413 - (1234)
3421 - (1234)
4123 - (1234)
3142 - (1234)
4312 - (1234)
1342 - (1)(234)
1423 - (1)(234)
2314 - (123)(4)
3124 - (123)(4)
2431 - (124)(3)
4132 - (124)(3)  
3241 - (134)(2)
4213 - (134)(2)

C'est le nombre de cas où on choisit 4 numéros parmi 4 (C(4,4)) pour former un cycle,
plus le nombre de cas où on choisit 3 numéros parmi 4 (C(4,3)) pour former un cycle.
Pour chacun des choix ci-dessus, on peut créer un cycle de (4-1)! et de (3-1)! façons différentes respectivement.
Du coup on obtient 14 en faisant:
C(4,4) * (4-1)! + C(4,3) * (3-1)! = 6 + 8 = 14

Si on essaye la même chose avec n=6 on se retrouve avec:
C(6,6) * (6-1)! + C(6,5) * (5-1)! + C(6,4) * (4-1)! = 120 + 144 + 90 = 354
Donnant une probabilité de gagner de (6!-354)/6! = 366/720 = 0.508...
C'est bien trop... on a dû manquer quelque chose...

En effet. Il faut aussi permuter les numéros non choisis ci-dessus.
Dans le cas C(6,4), il nous reste deux numéros non choisis, qu'on peut permuter de 2! façons différentes.
Dans les deux premiers cas on a 0 et 1 numéro à permuter respectivement, donc 0! et 1!, ce qui ne fait aucune différence:
C(6,6) * (6-1)! * 0! + C(6,5) * (5-1)! * 1! + C(6,4) * (4-1)! * 2! = 120 + 144 + 180 = 444
Et donc une probabilité de gagner de (6!-444)/6! = 276/720 = 0.383...
C'est moins que 10/24 (et plus que [1-ln(2)], c.f. hint de harvey), on est donc sur la bonne voie.

En général, pour n participants, on a:
C(n,n) * (n-1)! * 0! + C(n,n-1) * (n-2)! * 1! + C(n,n-2) * (n-3)! * 2!
+ ... +
C(n,n/2+1) * (n/2)! * (n/2-1)!
C'est à dire:
Somme pour m allant 1 à n/2 de: C(n, n/2+m) * (n/2+m-1)! * (n/2-m)!
La probabilité de perdre est la somme ci-dessus divisée par n!, et sachant que C(n,k) = n! / (k!(n-k)!), on peut simplifier et obtenir que la probabilité de perdre est:
Somme pour m allant de 1 à n/2 de: 1/(n/2+m)

Bien plus simple que la formule ci-dessus! (Ça me dit qu’il y’avait un moyen plus simple d’y arriver...)
La probabilité de gagner est donc:
1 - [Somme pour m allant de 1 à n/2 de: 1/(n/2+m)]

Pour n=32, on obtient 6647386466233 / 20629078984800 = 0.3222337978...

La probabilité de perdre peut s'écrire "n=32, sum 1/(n/2+m), m=1 to n/2" sur Wolfram Alpha:
https://www.wolframalpha.com/input/?i=n%3D32,+sum+1%2F(n%2F2%2Bm),+m%3D1+to+n%2F2

J'espère que c'est bien ça...

Après je ne sais pas comment calculer que la limite quand n tend vers l’infini est 1-ln(2)...

[harvey]

Wééé!
*clap clap clap*

Effectivement, la meilleure stratégie est d'assigner un numéro à chaque joueur, que chacun commence par le bouton qui correspond à son numéro, et qu'il choisisse le bouton suivant en fonction de l'affichage du bouton précédent. De cette façon, tous les joueurs suivent les mêmes cycles et factorisent leur probabilité d'échec. La seule manière qu'ils échouent est que la permutation des numéros contiennent un cycle de longueur supérieure au nombre de boutons qu'ils ont le droit d'essayer. Quelle est cette probabilité ?

Dans une permutation de N éléments, la probabilité que le plus grand cycle ait une longueur M (avec M > N/2) est 1/M.
Mais ça ne dépend pas de N ? Ben non.
Comme tu l'as montré, pour dénombrer le nombre de cycles de taille M, il faut multiplier:
- le nombre de manières de choisir M éléments parmi N (coefficient binomial de M parmi N, soit N!/(M!*(N-M)!)) )
- le nombre de manières d'ordonner ces M éléments pour qu'ils forment un cycle (factorielle de M-1)
- le nombre de manières d'ordonner les N-M éléments restant (factorielle de N-M)
Le tout divisé par le nombre total de permutations possibles (factorielle de N) pour obtenir une probabilité.
Et il y a une grosse simplification en cours de route:
    C(N,M) * (M-1)! * (N-M)! / N!
=   (N!/(M!*(N-M)!)) * (M-1)! * (N-M)! / N!
=   (N!/N!) * ((N-M)!/(N-M)!) * ((M-1)!/M!)
=   1/M

Pour avoir la probabilité d'échec, il faut donc additionner la probabilité que le plus grand cycle soit de taille M, pour M allant de N/2+1 à N (en supposant N pair). La limite 1-ln(2) s'obtient avec un peu d'analyse: quand N augmente, cette somme se rapproche de l'intégrale de 1/x entre N/2 et N. Soit, comme la primitive de 1/x est ln(x):
  ln(N) - ln(N/2)
= ln(N) - (ln(N) - ln(2))
= ln(2)

Je ne connais pas de moyen "plus simple" que celui-là.
Je n'ai pas inventé ce problème, et je n'en suis jamais arrivé au bout non plus, n'empêche que c'est une chouette idée. Gégé BAAL.

Plus de documentation sur ce sujet:
https://en.wikipedia.org/wiki/100_prisoners_problem

[pixis]

Un grand bravo à BAAL, la solution est loin d'être triviale ! Puisque les neurones sont maintenant chauds, en voici une nouvelle :

Marc va passer un examen de logique de 1h30 avec son pote Vincent. L'examen se compose de 23 questions vrai/faux. Vincent est incollable en logique, il a toujours su répondre à toutes les questions, ce n'est pas un problème pour lui (on considère donc qu'il aura toutes les bonnes réponses). En revanche, Marc est une bille, mais aimerait bien avoir la meilleure note possible. Heureusement pour lui Vincent est d'accord pour l'aider (... à tricher. Bouh, pas bien).

Pendant l'examen, chacun peut partir quand il veut (mais il ne peut plus revenir après). Par ailleurs, toutes les techniques de triches classiques (telles que "Si j'écris de la main droite alors la réponse est vraie") sont connues des examinateurs et punissables de mort (oui, carrément).

Enfin, ils ont tous les deux synchronisé leur montre à la seconde près.

Avec une stratégie bien préparée, à combien de questions Marc peut-il être certain de répondre correctement grâce à son ami Vincent ?

NB : La seule information tangible et utilisable est donc le moment où Vincent sort de la salle. Rien d'autre.

[BAAL]

Peut-on supposer que Vincent trouve toutes les réponses et les écrit à la vitesse de la lumière?

J’imagine que la réponse est plus que 12 = ceil(log(90*60))?

Sinon je vais y réfléchir, mais pas tout de suite, j’ai des choses à finir IRL avant, l’énigme de harvey m’a déjà pris trop de temps ce week-end...

[pixis]

On peut supposer que Vincent peut répondre instantanément.

Et oui, la solution est plus que 12