Pour 17:
On a 1h30=5400 secondes.
ceil(log_2(5400))=12, on peut donc transmettre 12 bits d'information.

Le premier bit nous indique la majorité des questions 1,2,3:
1 veut dire qu'au moins 2 sont vraies, 0 veut dire qu'au moins 2 sont fausses. Ça donne 2/3 bonnes réponses guaranties.
On fait ça pour les 6 premiers triplets avec les 6 premiers bits, et on a 12/18 bonnes réponses guaranties.
Ensuite on utilise 1 bit par réponse pour arriver à 17/23, et il nous reste 1 bit bonus.

Je crois savoir comment faire pour avoir plus, mais pas le temps de m'y mettre... ça laisse du temps à quelqu'un d'autre de trouver entre temps .

J’ai fait ça un peu différemment, ton code est plus compact, mais il m’a l’air bon! J’aime bien les problèmes où on passe de O(n^2) à O(n) en réfléchissant un peu .

On entend complexité espace/temps asymptotique. Temps la plupart du temps.
Dans le cas de la question ci-dessus, un algo "bête" trouve la réponse en temps O(n^2), mais on peut faire mieux!

Ah non, j'ai trouvé 17=6*2+5, et j'ai un bit bonus, pas 18... 
Mais j'ai d'autres idées à essayer...

Je crois pouvoir faire 18. Y'a-t-il mieux? J'aimerais bien que quelqu'un d'autre réponde aussi, j'ai l'impression d'être le seul à chercher .

Dans la même veine que le fil de discussion “Enigme du soir, Bonsoir !”, on peut ici proposer des problèmes de code/algo qui ne sont pas facilement transférables en challenge officiel. Soit car la solution se trouve facilement sur Google, soit parce qu’on peut toujours réussir avec une solution non-optimale si on laisse le code tourner assez longtemps, ou pour d’autres raisons...

Je commence avec un problème pas trop dur:

Codez une fonction qui prend comme argument un array de int, positifs et négatifs, et qui retourne la somme de la sous-séquence qui donne la plus grande somme.
Par exemple:
input = [3, -10, 3, -2, 5, -7]
output = 6 (somme de [3, -2, 5])

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...

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)...

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...

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.

Pas facile ton énigme... je crois avoir compris mais c’est bien plus dur que ça n’en a l’air.
Juste pour vérifier, il y’a bien une solution mathématique avec papier/crayon?

Je ne suis pas sûr d’avoir compris la question...
1) Les boutons peuvent-ils être différenciés d’une manière ou d’une autre (par nombre, ordre, couleur, ou autre...)?
2) Qui peut voir les noms affichés? tous les joueurs, incluant celui qui pousse les boutons?
3) Voit-on les noms à mesure qu’ils d’affichent? ou alors tous ensemble à la fin?
4) Un joueur s’arrête-t-il une fois qu’il a réussi à afficher son nom, ou a-t-il le droit de continuer?

Euhhh... C'est le meilleur indice en fait.. Je ne vois pas quoi rajouter. Plus on poste sur ce topic plus les challengers cherchent des indices là où il n'y en a pas. Il faudrait le fermer.

#Euh #Eux #Œufs

Deux remarques:
-Bien que je préfère Python, je pense que PHP aide à avancer plus vite sur NC, pour plusieurs raisons.
-Je conseille à tout le monde de faire le plus d'effort possible pour me pas "coder comme un porc". J'ai moi-même eu ce problème pendant longtemps. Pas forcément un problème sur des projets solo et de moyenne envergure comme sur NC. Mais dans la vraie vie, ça fait une énorme différence.

Non, pas de - devant le dt.
Il y'a bien une solution .