NewbieContest

Pour ceux qui veulent poster des énigmes :D

Soit un cercle de rayon 1. Le côté d'un triangle équilatéral inscrit dans ce cercle a pour longueur sqrt(3). Quelle est la probabilité qu'une corde du cercle, choisie au hasard, possède une longueur supérieure à sqrt(3) ?

C'est un problème connu, pas le droit de chercher sur le web!

Promis, la prochaine fois j'en invente un.

ah ça me dit quelque chose ca...^^

Intuitivement, je dirais que la proba est (2-sqrt(3))/2
Maintenant, faut que je calcule pour vérifier si mon hypothèse est bonne !

edit : En fait je me suis planté mon hypothèse. Je recommence.
J'avais en tête
(2-sqrt(3)/2*2)/2 = (2-sqrt(3))/2

Mais en faisant le dessin au propre et avec des souvenirs de trigo c'était 1/2 et pas sqrt(3)/2 que je devais utiliser
Donc :
(2-1/2*2)/2 = 1/2 !

C'est mon dernier mot Jean-Pierre.

edit2 : Et mon explication :
Soit un diamètre au hasard, et on prend l'ensemble des cordes perpendiculaires à ce diamètre (j'aurais pu prendre le rayon, mais j'avais le diamètre en tête). Les cordes qui ont une longueur > sqrt(3) sont celles situées entre -1/2 et +1/2 sur le diamètre. Donc il y a une longueur de 1 avec ces cordes, sur le total de 2 du diamètre, d'où 1/2 (Mais je suis passé par 4 chemins pour mes calculs. L'expliquer rend le raisonnement plus clair !)

moi je dirais 1/3 mais ça me paraît beaucoup trop simple pour être ça :)

Intuitivement je dirais 1/2,
ensuite je dirais 1/3 avec une démo cette fois : choisir une corde ça revient à choisir une origine sur le cercle et un angle entre entre -90 et 90 degrés, l'origine on s'en fiche, par contre soit l'angle il est supérieur à 30 degrés et la corde a une longueur inférieure à sqrt(3), soit l'angle il est inférieur à -30 degrés et on a la même chose, soit l'angle il est compris entre -30 et 30 degrés et on a une longueur de code supérieure à sqrt(3). Du coup si on considère que tirer la corde au hasard revient à choisir l'angle au hasard, ça donne une proba de (30-(-30))/180 = 1/3.
Je vais vérifier ça en espérant ne pas m'être vautré  =D.

J'suis sûr de mon raisonnement, mais celui de Alka me semble bon aussi. dafuk ..  :?

j'avais le même raisonnement que Alkanor ;)

c'est bon ca me revient c'est pas le "machin"(je me souvient plus du mot ^^ ) de Bertran ou un truc du genre ?

Bsr,

j'aurais fait le même raisonnement qu'Alkanor en terme de superficie et non en terme d'angle car les cordes d'une longueur de plus de sqrt(3) représente une surface (de même que celle d'une longueur de moins de sqrt(3)).

Donc, du disque de rayon 1, je retire deux surfaces: deux segments circulaires dont la longueur de corde est sqrt(3). Ils ont chacun pour surface: 1/2[2pi/3-sin(2pi/3)].

Du coup, la probabilité recherchée est: 1-{2*1/2*[2pi/3-sqrt(3)/2]}/pi=1/3-sqrt(3)/(2pi)1/3+sqrt(3)/(2pi)

Non?

ferbos

correction: une erreur de signe....

On a du 1/2, on a du 1/3, personne pour justifier que ça pourrait être 1/4 ?  ;)

On a du 1/3+sqrt(3)/(2pi) aussi :D

...xD je pense que je vais renommée la discussion "Faites des maths avec BAAL"  :')

Choisie au hasard comment?


Si les deux points sont placés indépendament sur la circonférence ça doit être un tiers
Il suffit de tracer le triangle avec le premier point comme sommet pour voir que le deuxième point a une chance sur trois de tomber dans l'arc de cercle opposé (en gros le raisonnement d'Alkanor).


Bon, j'ai trouvé autre chose.
On détermine la corde par l'aire qu'elle découpe dans le cercle. On choisit l'aire par un tirage uniforme sur l'intervalle ]0,pi/2[ (moitié de l'aire du cercle).
Comme l'aire du triangle équilatéral de côté sqrt(3) est 3/4, l'aire découpée à l'extérieur par chaque côté est (pi-3/4)/3 = pi/3-1/4.
La probabilité qu'on cherche est le rapport entre ces deux aires: (pi/3-1/4) / (pi/2) .

C'est bien de penser à moi mais je suis visiblement à côté de la plaque.

ferbos

Ceux qui veulent chercher tous seuls, ne lisez pas la suite.

...


C'est bien la clé du problème. On obtient une réponse différente selon la façon dont on choisit les cordes "au hasard".
Il faut toujours préciser le procédé utilisé.

Ce problème est connu comme le "paradoxe" de Bertrand. Mais évidemment ce n'est pas vraiment un paradoxe.
Les exemples officiels sont qu'ont peut obtenir 1/4, 1/3, 1/2, mais pourquoi pas 1/3+sqrt(3)/(2pi) également :).

Bien joué à plusieurs d'entre vous donc! (et harvey en particulier).

J'ai déjà dû croiser ça quelque part (dans la chatroom d'arimaa.com, probablement).
Du coup, je me demande comment on trouve 1/4. On peut choisir un point uniformément sur l'aire du cercle et prendre la corde perpendiculaire au rayon, mais ça donne autre chose (9/16).
edit: ok, je me suis planté, c'est bien 1/4.

Bon, on est en chien pour des nouveaux challs.

tien harvey ;) http://therese.eveilleau.pagesperso-orange.fr/pages/paradoxe/textes/bertrand.htm

Probabilité riche :
Newbie et contest sont dans un casino, il veulent gagné de l'argent et vont jouer au dés. Sur la table il y a 2 dés.
Sur quel résultat (somme des deux dés) devront-ils parier pour avoir le plus de chance de gagné ?

Ouais bonne idée ca de me faire gagner de l'argent ^^

J'attends la réponse du coup, histoire de bien miser :)

Enjoy

The lsd

7 ?

PS : Si c'est pas ça, je suis TRÈS curieux d'avoir une autre réponse et un autre raisonnement ...!

Pour moi c'est 7.

Un petit prog en python vite fait :
Le résultat est : {2: 27557, 3: 55564, 4: 83386, 5: 110792, 6: 139362, 7: 166295, 8: 139102, 9: 111369, 10: 83377, 11: 55580, 12: 27616}

D'où 7 !!!
C'est pas mathématique mais les statistiques sont là.

Edit : L'algo tend vers une chance sur 6 d'obtenir 7.

Oui la réponse est bien 7 ! :)

ok c'est noté, je jouerais 7 :)

mais euhhhh pourquoi 7 en fait ?

Enjoy

The lsd

Ça m’étonne que vous n’ayez pas vu ça au Lycée (ou alors vous ne vous en souvenez pas).
Il y’a 1 seule façon d’obtenir 2 (1+1), 2 façons d’obtenir 3 (1+2 ou 2+1), 3 façons d’obtenir 4 (1+3,2+2,3+1), 4 façons d’obtenir 5 (1+4,2+3,3+2,4+1), 5 façons d’obtenir 6 (1+5,2+4,3+3,4+2,5+1), 6 façons d’obtenir 7 (6+1,5+2,4+3,3+4,2+5,1+6).
Ensuite on redescend, 5 façons d’obtenir 8, 4 façons d’obtenir 9, 3 façons d’obtenir 10, 2 façons d’obtenir 11, 1 façon d’obtenir 12 (6+6).

Ça donne donc une probabilité de 6/36 pour 7.

Bon du coup j'en ai deux autres vu qu'on est en proba.
Encore une fois, pas le droit de consulter le web, et pas le droit de donner la réponse si on a déjà vu le problème (ce qui était mon cas pour le problème des dés).

1) Dans un pays lointain où il est traditionnellement important d’avoir un fils, tous les couples adoptent la stratégie suivante afin de s’assurer d’avoir plus hommes dans la famille:
Ils font des enfants jusqu’à ce qu’ils obtiennent un fils, et s’arrêtent là.
Quelle est la proportion d’hommes/femmes dans ce pays?

2) Dans un autre pays, si tous les couples décident de faire des enfants jusqu’à ce qu’ils en aient exactement un de chaque sexe, combien chaque couple aura-t-il d’enfants en moyenne?

Effectivement BAAL je l'ai vue au lycée ^^ et c'était aussi bien comme ca que l'on a vue le prob' ;)
Bien joué ! :)
je réfléchie a ton énigme.

une question bête: Quelle est la probabilité d'avoir un enfant mâle, celle d'une enfant femelle et éventuellement celle d'un enfant du troisième sexe?

ferbos

Toujours 1/2, mais pas de troisième sexe.

Bon aller je me lance pour le 1 :
Intuitivement ça me ferait penser à une sorte de fibonacci, on va voir ça  =D
D'abord tout dépend de la situation initiale, et on va dire qu'on la prend comme N couples + M individus de même sexe sans partenaire.
On suppose que la probabilité d'avoir un garçon est 1/2, qu'il n'y a pas de troisième sexe, que seul le nombre de couples à une génération donnée détermine le nombre de naissances à la génération suivante, qu'à chaque génération chaque couple a un et un seul enfant, et que tout le monde peut se reproduire dès la naissance.
A n=1, il y aura N/2 garçons et N/2 filles. Les N/2 couples ayant donné naissance à des garçons s'arrêtent.
Il reste donc N/2 couples en lice de la génération 0, et N/2 couples de la génération 1. On est dans la même situation qu'à la génération 0 avec M = 0.
En fait cela semble aller contre l'intuition (vu qu'on trouve que la technique ne permet pas du tout d'augmenter la proportion de garçons), mais finalement ça ne l'est pas tant que ça, puisque en s'arrêtant dès qu'on a un garçon, on ne change pas la probabilité 1/2 d'avoir un garçon, donc au final le problème tel que posé par Baal et avec les hypothèses utilisées ici est assez trompeur. Après j'ai peut être mal compris aussi :lol:, ou alors Baal a écrit une devinette dont la résolution dépend de comment on la pose  =D

2) je dirai 2 mais cela me paraît trop évident.

Le raisonnement (sans probabilité): chaque couple veut un enfant de chaque sexe, donc au maximum ils en font deux et ils sauront s'ils ont deux enfants de sexe différents. A moins d'infanticides, je ne vois pas pourquoi ils iraient au-delà. D'où la moyenne de 2.

NB: oui, je sais, je me suis levé du pied gauche.

ferbos

On peut y introduire la formule de Bayes par l'évènement "obtenir 7 sachant que le premier dé donne...". On peut résoudre ainsi le problème avec des dés différents et des sommes différentes.

ferbos

Bizarre le raisonnement d’Alkanor, mais c’est bien la bonne réponse! on ne peut pas tricher avec la probabilité de base, on aura toujours une probabilité de 1/2.
ferbos, tu dois nous dire comment tu obtiens 2.

Pour la 2], je dirais 3 :
- la moitié des couples s'arrêtera au 2e ;
- la moitié de l'autre moitié s'arrêtera au 3e ;
- etc.

A la limite, le nombre moyen d'enfants au delà du premier est donné par 1/2 + 2/(2^2) + 3/(2^3) + ...
Ca revient à étudier la limite de la somme des n/2^n.
En notant S_n = 1/2 + ... + n/2^n on peut montrer qu'on a S_n = (1/2 + 1/4 + ... + 1/2^n) + 1 - (n+1)/2^n (faut bidouiller un peu).
D'où par passage à la limite S_n ---> 2.
Et donc en prenant en compte le premier enfant ça fait en moyenne 3 par couple.

C'est un peu moche, je suis sûr qu'il doit y avoir un raisonnement beaucoup plus élégant. Mais si ça passe par le calcul, je ne m'en prive pas.  =)

EDIT : dans la question initialement posée, "Dans un autre pays, si tous les couples décident de faire des enfants jusqu’à ce qu’ils en aient exactement un de chaque sexe, combien chaque couple aura-t-il d’enfants en moyenne?", ne faut-il pas remplacer le "exactement" par "au moins" ? C'est ce que j'ai supposé en lisant rapidement. Sinon ils font quoi si leurs deux premiers enfants sont des garçons ?

Ah oui désolé, je voulais bien dire “au moins”.
Et oui 3 est bien la bonne réponse, et le raisonnement me paraît juste, je n’en vois pas de plus simple.

Bien joué!

Le raisonnement est le même si le premier gosse est femelle ou mâle. On cherche combien il faut en pondre pour en avoir un du sexe x  (= N), et on ajoute 1.
Il y a une chance sur deux que le môme soit du bon sexe, et une chance sur deux qu'on revienne à la condition de départ. Donc en moyenne, N = 1 + (1/2)*N, soit N=2. La solution du problème, avec la correction mentionnée par Nuco, semble donc être 3 (il faudrait aussi prouver que la série est convergente).

Maintenant, je suis d'accord qu'il y a un problème de formulation. "Exactement un de chaque sexe" suggère que les couples continuent à générer des chiards à l'infini s'ils ont le malheur de commencer par deux glaçons ou deux billes. Du coup, la solution dépend de la période de fertilité et du rythme de production. Si on voulait pinailler (et pourquoi ne le voudrait-on pas?), on pourrait ajouter que les données absentes de l'énoncé affectent aussi le problème corrigé. Le fait que la capacité procréative de certains couples soit interrompue avant qu'ils aient rempli leur objectif implique que la solution ne soit qu'une borne maximale, et qu'une évaluation plus précise dépende, encore, de la période de fertilité, espérance de vie, fréquence des jumaux, etc. Le taux de mortalité par sexe et classe d'âge complique encore les choses.

le terme n/2^n converge fortement vers 0 (ou un truc du genre) la suite (n/2^n) est décroissante et tend vers 0 donc Avec D'Alembert,  la série converge. (2 edits, vivement les vacances !!)


Je ne suis pas tout seul à me lever du pied gauche. Je suis rassuré. C'est sûrement pourquoi on la nomme énigme du soir.

ferbos

poème, math et cryptographie :

Quel nombre ce cache derrière ce petit poème ?

"Que j'aime à faire apprendre un nombre utile aux sages. Glorieux Archimède, artiste ingénieux! Toi, de qui Syracuse aime encore la gloire, soit on nom conservé par de savants grimoires".

ps: elle n'est pas de moi dsl ^^

Pi, j'ai commencé à l'apprendre comme ça d'ailleurs.

À mon tour, une facile :
Jeanne a deux enfants. L'un des deux est une fille. Quelle est la probabilité que l'autre soit un garçon ?

Ouaipe, avec la méthode stp Pixis ;)

Nombre de lettres par mot :)

Oui ! :)
Que = 3, j'=1, aime = 4 etc...;)

Et pour ton énigme je dirais 1/2 mais sa me parais trop simple ? ^^

Ça serait trop simple, oui. Mauvaise réponse !

Pour les deux enfants, on a 4 cas équiprobables : FF, FG, GF, GG
Or si l'un des deux est une fille, il reste 3 cas possibles : FF, FG, GF, et parmi ceux-ci, dans 2 cas sur 3 l'autre enfant est un garçon. Donc 2/3 !

Le piège est dans le "l'un d'eux est une fille" -> c'est très différent de "le premier est une fille" (dans ce cas là ça aurait été 1/2)
Hier soir je suis tombée en plein dedans en lisant trop vite, mais ce matin bien reposée ça a fait tilt :p

Parfait ! Comme quoi l'intuition n'a pas toujours raison, et les mots d'un énoncé sont rarement choisis au hasard !
Bien joué ;)

Autre énigme, un peu plus corsée :
***************************************************************************************************************
* Jessica Pote choisi deux nombres entiers entre 2 et 100 (inclus).                                           *
* Elle va alors voir ses amis Jean-Phil Tou et Homer Dalor.                                                   *
* Elle donne secrètement à Homer la somme de ses deux entiers, et à Jean-Phil le produit de ces deux entiers. *
* Puis leur pose la question : Saurez-vous retrouver mes deux nombres ?                                       *
* Jean-Phil : Je ne sais pas.                                                                                 *
* Homer : Je savais que tu n'allais pas savoir                                                                *
* Jean-Phil : Alors je sais                                                                                   *
* Homer : Alors moi aussi                                                                                     *
*                                                                                                             *
* Précisions :                                                                                                *
*   - Homer sait que Jean-Phil connait le produit, et inversement.                                            *
*   - Homer et Jean-Phil savent tous les deux que la valeur min est 2 et la valeur max est 100.               *
*   - Les deux protagonistes sont pas cons.                                                                   *
***************************************************************************************************************

Mais quels sont ces deux nombres mystérieux ?

Ah oui effectivement kithyane, je viens de relire et me suis rendu compte ^^.

Salut,

Celle-là, c'est loooooong mais ce n'est pas impossible huhu; je conseille même de programmer là-dessus: cella-là s'y prête bien.

ferbos

C'est en effet conseillé. Sinon elle se fait avec papier crayon, mais pas de tête !

pixis: 2 ?
2x2=4 et 2+2=4 ?

Je pense que tu peux relire l'énoncé :) Il y a deux nombres à trouver A et B. L'un des deux protagoniste a la somme (A+B), l'autre le produit (AxB). Ce qu'il faut trouver, ce sont des deux nombres A et B !

Ah dac j'avais mal compris je continue à chercher ^^

Salut !

Ton enigme Pixis est vraiment sympa, ça m'a pris la tête toute la soirée d'hier. J'étais partis dans la mauvaise direction, mais en y repensant aujourd'hui, je crois avoir une (semi) solution. Ceux qui réfléchissent encore, je vous invite a ne pas lire la suite :


###########


Le premier nombre premier superieur a 50 est 53.Pour Homer, si la somme est superieur a 55, il sera incapable d'affirmer que JP ne saurait pas. en effet, le nombre pourrait s'ecrire de la forme 53 + i. Dans ce cas la, la decomposition en produit de facteur premier du produit contiendrais 53. JP sais immediatement que 53 est le premier des deux nombre mystère, car il est impossible de multiplier 53 par un nombre premier sans que le resultat ne depasse 100.

On en deduit que la somme est inferieur a 55.

De plus, on peut utiliser la conjecture de golbach (ouais, je vais chercher loins, mais bon, elle a été verifié pour les "petits" entiers, donc j'ai le droit :p ) pour deviner que si le resultat étais pair, il pourrait s'ecrire comme la somme de deux premiers, et donc il est possible que les deux nombres choisi soient premier, ce qui fait que JP pourra deviner immediatement les deux nombres en voyant le produit.

On en deduit que la somme est inferieur a 55 et impaire.

On peut tres vite verifier a la mano parmi les entier impaire inferieur a 55, il n'y a que 27, 35 et 51 qui ne sont pas premier et qui ne peuvent pas s'ecrire comme la somme de deux premier.

On en déduit que la somme est soit 27, Soit 35, soit 51.

J'ai vérifié avec un script python (en fait j'ai réutilisé celui que j'avais codé hier en cherchant sur une fausse piste) qu'il n'étais pas possible de trouver un ensemble de nombre premier telle que, organisé d'une façon sur deux element, la somme fasse l'une de ces valeurs, et organisé d'une autre, la somme fasse une autre de ces valeurs.

Ensuite, j'ai trouvé les liste suivantes :

Si la somme fait 27, les differentes valeurs possible du produit possible sont :
[72, 92, 110, 126, 140, 152, 162, 170, 176, 180, 182]

Si la somme fait 35 :
[96, 124, 150, 174, 196, 216, 234, 250, 264, 276, 286, 294, 300, 304, 306]

Et 51 :
[144, 188, 230, 270, 308, 344, 378, 410, 440, 468, 494, 518, 540, 560, 578, 594, 608, 620, 630, 638, 644, 648, 650]

Aucune valeur en commun, d'ou en connaissant le produit, JP peut deviner la somme, il connait la somme et le produit, deux equation deux inconnue, il connait les deux nombres.

cependant, mon raisonnement s'arrête la. Homer n'a aucun moyen de savoir lequel des éléments des liste ci-dessus est le bon, donc je ne sais pas comment il peut deviner la valeur des deux éléments.
Je suppose que je dois être capable de restreindre encore mes valeurs possible, mais je n'ai rien trouvé de concluant. Je ne pense pas que mon algorithme soit faux, mais ce n'est pas a exclure :p


###########

Je vais probablement continuer d'y penser, mais je pense que je n'irait pas plus loins de cette façon.

Je voudrais juste rajouter que "les deux protagoniste ne sont pas cons" est un doux euphemisme, j'aimerais bien être aussi vif :D

L'énoncé ne dit pas que le produit ne dépasse pas 100. Ouais, d'ac.

Pourquoi la somme ne serait-elle pas un nombre premier?


À part ça, la deuxième partie de ton raisonnement est juste, la somme ne peut pas être une somme de deux premiers. Ni la somme d'un premier et de son carré, puisqu'un cube ne peut s'écrire que d'une manière comme un produit de deux nombres.

l'enoncé dit bien que chacun des termes doit être inferieur a 100. si le produit vaut par exemple 1855 = 53*5*7, JP deduit immediatement que les deux nombre choisi sont 53 et 35 ;) Je me sert du théorème fondamental de l'arithmétique ici, en considerant la decomposition des deux nombres choisis par Jessica. Si le produit admet 53 comme diviseur, alors au moins un des deux nombre de Jessica admet 53 comme diviseur, et donc ce nombre est 53.

Pour ta seconde remarque, elle est legitime, je m'en suis rendue compte il y a une petite heure, mais les resultat en incluant les nombres premier sont peu concluant, je me retrouve dans le cas ou il est toujours possible qu'un produit de facteur corresponde a plusieurs sommes. je vais continuer de réfléchir un  peu, je pense que j'ai manqué quelque-chose :)

Bon, j'ai fini par resoudre l'enigme ! (enfin, je crois :p )

Voici ma solution :

###########


Le premier nombre premier superieur a 50 est 53.Pour Homer, si la somme était superieur a 55, il serait incapable d'affirmer que JP ne sait pas. en effet, le nombre pourrait s'ecrire de la forme 53 + i. Dans ce cas la, la decomposition en produit de facteur premier du produit contiendrait 53. JP sais immediatement que 53 est le premier des deux nombre mystère, car il est impossible de multiplier 53 par un nombre premier sans que le resultat ne depasse 100.

Pour preciser, si le produit vaut par exemple 1855 = 53*5*7, JP deduit immediatement que les deux nombre choisi sont 53 et 35  Je me sert du théorème fondamental de l'arithmétique ici, en considérant la decomposition des deux nombres choisis par Jessica. Si le produit admet 53 comme diviseur, alors au moins un des deux nombre de Jessica admet 53 comme diviseur, et donc ce nombre est 53.

On en deduit que la somme est inferieur a 55.

De plus, on peut utiliser la conjecture de golbach (ouais, je vais chercher loin, mais bon, elle a été verifié pour les "petits" entiers, donc j'ai le droit :p ) pour deviner que si le resultat étais pair, il pourrait s'ecrire comme la somme de deux premiers, et donc il est possible que les deux nombres choisi soient premier, ce qui fait que JP pourra deviner immediatement les deux nombres en voyant le produit.

On en deduit que la somme est inferieur a 55 et impaire.

On peut tres vite trouver a la mano la liste des entier impaire inferieur a 55 qui ne s'ecrivent pas comme la somme de deux premier, c'est 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53

On en déduit que la somme appartient a cette liste.

A partir de la, j'ai cherché pour chacune de ces sommes les valeurs possibles du produit. Par exemple, pour 11 :

le produit est décomposer en facteur premier, mais je sais que pour 11, les valeur possible du produit sont 2*3*3, 2*2*2*3, 2*3*5 et 2*2*7.
J'ai fais de même avec l'ensemble des nombre de la liste ci dessus, et j'ai isolée les produits qui ne sont associé qu'a une seul somme. Par exemple, J'ai enlevé de ma liste [2, 3, 17] car 3*17 + 2 = 53 et 2*3 + 17 = 23

La liste final des produits associée a une seul somme est la suivante :

On remarque que seul 17 n'admet qu'une seul produit associé pour 4 et 13. 4+13 = 17 et 4*13 = 2*2*13 = 52


Parlons raisonnement : comme Homer avait devinée que JP ne saurait pas, JP sais que la somme des deux nombre appartient a la liste 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53 (ce sont les seuls sommes qui assurent que JP ne peut pas savoir).
De cela, JP deduit la valeurs des deux nombres. Cela veut-dire que le produit est associée a une seul somme. en effet, si le produits est associé a une seule somme, alors JP peut connaitre la somme associé a son produits, et de fait, deux équation deux inconnue, il résout le problème. Au contraire, si le produits peut être associé a plusieurs somme (comme le produit 2*3*17), il n'est pas capable de resoudre le problème et ne peut pas affirmer connaitre les deux entier (Cette reciproque est pas très rigoureuse, j'avoue :p)
Homer peut deviner que le produits appartient a cette liste, et affirme connaitre la reponse. Puisqu'il connait la somme, on en deduit que cette somme est 17. En effet, si la somme étais differentes de 17, il aurait toujours le choix entre plusieurs produits differents et ne pourrait pas resoudre le systeme. Donc la somme vaut 17, le produit vaut 52, et les deux nombres mystères sont 4 et 13 ! :)


###########

Je me répète, mais bon, vraiment sympa comme enigme pixis ! :)

J'aimerais bien savoir comment faire pour resoudre ça a la main, car ma methode ne s'y prête absolument pas :p

Hello,
Très bien joué ! J'ai cherché une solution en ligne depuis, car j'avais la grosse flemme de la rédiger. Et j'en ai trouvé une bien faite.

http://faq.maths.free.fr/texte/faq51.html

C'est long à faire à la main, mais c'est faisable.

Parce qu'on ma posé plusieurs fois la question, j'essaie d'expliquer le début du raisonnement de MioMilo, avec l'histoire de 53 :

Apport pour le raisonnement de MioMilo
Donc oui effectivement ya du raisonnement derrière. Comme Homer dit "Je sais que tu ne savais pas", ça veut dire qu'il sait que Jean Phil avait AU MOINS deux façons différentes de décomposer son nombre (Par exemple s'il a 20, il peut faire 2*10 ou 4*5). Pour que ce soit possible, ça veut, entre autre, dire que le nombre qu'a Jean Phil n'est pas un multiple de deux nombres premiers. Ok. Maintenant, imaginons que Homer a un nombre plus grand que 55, disons 61. Ça veut dire que parmi toutes les décompositions de sommes, il y a 2 et 59, 3 et 58, ... et aussi 8 et 53. (Quelque soit le nombre > 55, il y aura un i + 53 en fait). Comme Homer dit qu'il SAVAIT que JeanPhil ne savait pas, ça veut dire que tous les produits de ses décompositions (donc 2*59, 3*58, ...) donnent un nombre qui peut être décomposé de plusieurs manières. Or 8 * 53 (ou génériquement i*53) ne se décompose pas d'autre manière que i*53 avec i<=100. En effet, 53 est premier, et si i se décompose (genre 8 c'est 2*4) alors ça voudrait dire que les deux nombres peuvent être 8 et 53 OU 2 et 212 ou 4 et 106. Mais 212 et 106 sont supérieur à 100. Et en fait, quelque soit le nombre i, s'il se décompose en deux a*b, les deux parties a et b seront forcément > 2, donc a*53 > 100 et b*53 > 100. Donc c'est pas possible.

Voilà, j'espère que ça aide un peu.

Une prochaine énigme ? Ou j'en sors une nouvelle ?

EDIT : Allez, c'est parti.

**********************************************
42 personnes sont prisonnières dans un camp de sadiques. Ces sadiques aiment s'amuser quand ils tuent leur prisonniers. Ils proposent alors aux prisonniers un jeu (disent-ils, pas sûr que les prisonniers plussoient). Ils vont les mettre les uns derrière les autres, en file indienne, puis ils vont leur placer un chapeau sur la tête, noir ou blanc, aléatoirement (Il est possible que tous les chapeaux soient noirs, ou que 40 d'entre eux soient blancs, et 2 soient noirs. Aléatoirement, ai-je dit). Personne ne sait la couleur du chapeau qu'il porte, mais chacun voit l'ensemble des chapeaux qui sont placés devant lui. Le premier ne sait donc rien, le 2ème voit le chapeau du premier, et le dernier voit tous les chapeaux sauf le sien.
Les sadiques vont alors interroger tous les prisonniers les uns après les autres, en commençant par le dernier dans la file, celui qui voit tout. Chacun des prisonniers interrogé devra dire d'une voix haute et intelligible pour tous : "Noir" ou "Blanc". Une fois qu'un prisonnier a répondu, il est emmené dans une salle à part, hors de la vue des autres prisonniers. Si la couleur donnée à haute voix correspond à celle du chapeau qu'il a sur la tête, alors il est sauvé. Sinon, il est tué (voilà pourquoi ce sont des sadiques). Les autres prisonniers ne savent pas s'il avait raison ou tort.

Comme les sadiques sont tout de même joueurs, ils proposent à l'ensemble des 42 prisonniers de se regrouper avant le jeu, et de discuter comme bon leur semble. Une fois qu'ils ont fini de discuter, le jeu commence, et il n'ont plus le droit de dire quoique ce soit ou de mimer quoique ce soit (autre que dire "Noir" ou "Blanc" quand leur tour viendra.)

Question : Statistiquement, combien de prisonniers peuvent être sauvés ? (Exemple : Si les réponses sont totalement aléatoires, alors statistiquement, 21 seront sauvés)

On suppose que les prisonniers ne sont pas cons.
La réponse est purement logique. Pas de différence entre les tonalités de voix, ou viens la que je te gratte les fesses si t'as un chapeau blanc.
**********************************************

Je crois avoir trouvé celle-ci aussi

###

Le premier prisonnier annonce "Blanc" si il voit un nombre pair de chapeau blanc, et "Noir" si il voit un nombre pair de chapeau noir. Vue que le premier prisonnier voit 41 chapeau, on en déduit que si il voit un nombre paire de chapeau blanc, il voit aussi un nombre impaire de chapeau noire, et vice versa. A cet instant, tout les prisonnier connaissent la parités du nombre de chapeau blanc et du nombre de chapeau noir devant le premier prisonnier.

A partir de la, le second n'a qu'a vérifier la parité du nombre de chapeau noir et blanc. si c'est la parité du nombre de chapeau noir qui a changé, alors son chapeau est noir, et vice versa. Il n'a plus qu'a annoncer la couleur de son chapeau pour être sauvé.

Tout les prisonnier savent qu'a partir du second prisonnier, la couleur annoncée est la couleur du chapeau porté par le prisonnier qui annonce. Ils peuvent donc mettre a jours dans leurs tête la parité du nombre de chapeau noir et du nombre de chapeau blanc, et quand vient leur tour, ils peuvent eux aussi avoir la vie sauve.

Ainsi, tout les prisonnier, du second a l'avant dernier, seront sauvé, soit 40.

Il reste le premier qui a une chance sur deux de s'en sortir, ainsi que le dernier qui ne voit rien qui doit aussi répondre au hasard. au final, il y aura statistiquement 41 prisonnier qui vont être sauvés


###

J'espère que j'ai été claire, le raisonnement est relativement simple (enfin, beaucoup plus que pour l'enigme d'avant en tout cas :p )

 Je connaissais ce problème, et je crois que c’est bien la réponse attendue.
Cela dit, c’est une réponse de logicien, mais moi, étant ingénieur, et ayant l’esprit pratique, je proposerais autre chose.
Cette stratégie suppose que les 42 personnes sont toutes capables de correctement évaluer le nombre de chapeaux devant eux, et de correctement se rappeler des réponses précédentes. C’est assez irréaliste, surtout avec le stress dû au fait qu’ils risquent de mourir dans quelques instants. De plus, le premier prisonnier peut décider intentionnellement de donner la mauvaise réponse, vu que ça ne change pas sa propre chance de survie, et qu’il pourrait être faché d’être le premier. Ensuite, s’ils sont tous logiques, ils mourront tous.

Bref, je proposerais une stratégie plus “robuste“: Le premier prisonnier donne la couleur du chapeau devant lui, le suivant répète. Le suivant donne le chapeau devant lui, le suivant répète, etc... donc la moitié des prisonniers survivent pour sûr, ainsi que la moitié de ceux qui restent, donc environ 75%. L’avantage, comparé à la solution “officielle“, est qu’un prisonnier mal-intentionné ou bête n’affectera pas vraiment la probabilité.

Et bien dans cette optique, j'ai une solution un peu plus optimisée, BAAL (http://sd.keepcalm-o-matic.co.uk/i/keep-calm-i-m-a-fucking-engineer.png) :)
La mienne marche par "paquet" de trois personnes. Le premier donne l'info aux deux autres. En amont, ils se sont mis d'accord que "NOIR" == différent et "BLANC" == pareil.

Ainsi, pour chaque paquet de 3 :
Le premier dit noir ou blanc, en fonction des deux devant lui. S'ils ont la même couleur de chapeau (blanc-blanc ou noir-noir), il dit BLANC, s'ils ont des chapeaux différents (blanc-noir ou noir-blanc), il dit "NOIR".
Le deuxième ayant cette information, déduit la couleur de son chapeau de la couleur de celui qui est devant lui.
Le troisième ayant en tête les deux informations précédentes peut également déduire la couleur de son chapeau.

On en sauve donc 2/3 certains et 1/6 en plus, statistiquement, donc 5/6ème , 35 dans notre cas.

Bien joué à tous, en tout cas !

Aha pas mal!

Mais en fait tout ce qu’on fait là c’est limiter la solution officielle à des groupes de 2 ou 3 prisonniers.
Du coup, “je peux faire mieux que toi“, en les groupant par 4 ;).
Le premier donne la parité pour les 3 suivants, le deuxième en déduit le sien, ainsi que le 3ème et 4ème (contrairement à ce qu’a dit MioMilo, je crois que le dernier prisonnier peut en fait connaître son chapeau également).
Du coup on a une probabilité de 3/4 + 1/8 = 7/8

;)

On peut continuer comme ça pour des groupes de 5, 6, 7, ... jusqu’à 42, et en fait il faut décider du moment auquel on croit que les prisonniers commenceront à commettre des fautes et limiter la taille du groupe.

Reformulons donc la question:
Quelle est la stratégie optimale, sachant la probabilité "p" qu’un prisonnier fasse une erreur (exprès ou pas) ?
Bon ok, pour illustrer, disons que p=1/8.

Tu as tout à fait raison
Je suis en voiture mais j'y réfléchis !

Dans le même esprit "pratique", j'aimerais savoir ce que chacun dit pour déterminer la proportion de chapeaux noirs ou chapeaux blancs qu'il a devant lui. Rouge? Abracadabra? Saperlipopette? Il tape du pied? Cela doit être assez fun au final. Pour rester dans la règle fixée au départ, on ne peut pas dépasser trois. Sinon, les gardiens, s'apercevant de la supercherie, vont s'en prendre aux pauvres prisonniers.

ferbos

Bonsoir !

Il n'y a pas eu d'activité depuis un moment sur ce sujet, j'en profite pour énoncer un petit "puzzle" pas forcement très compliquer mais que j'ai trouvé bien sympa !

Je l'ai trouvé dans un livre qui parle du théorème d’incomplétude de Gödel (Un théorème de logique mathématique qui affirme, pour simplifier, quand dans tout système d'axiome il y aura toujours des énoncés vrai mais impossible a prouver)

Ce "Puzzle Gödelien" peut-être vue comme une introduction au raisonnement derrière ce théorème. je n'ai pas le livre sous les yeux, je vous restitue donc cette énigme de tête. Les connaisseur m'excuserons si je presente la chose de façon inexacte sur la forme et dans les termes utilisés.

Hello.
Alors je viens de lire cette énigme qui semble rigolote. Cependant, j'avoue que j'ai un petit soucis de compréhension :
Qu'appelle-t-on un énoncé "vrai" ?

Effectivement, j'ai manqué de précision alors que c'est un point crucial. Voici plus de détails :

Un postulat X est dit imprimable si la machine peut l'imprimer. On suppose la machine programmée de telle sorte que tout postulat qu'elle peut imprimer sera imprimé tôt ou tard.

De façon informelle, P signifie "imprimable", N signifie "norme" et ! signifie "non"
 P(X) est vrai si et seulement si X est imprimable
PN(X) est vrai si et seulement si la norme de X est imprimable ( c'est à dire si et seulement si X(X) est imprimabe)
!P(X) est vrai si et seulement si X n'est  pas imprimable
!PN(X) est vrai si et seulement si la norme de X n'est pas imprimable

On suppose que tout énoncé imprimé par la machine est vrai.

Voilà, j'espère que le problème est plus clair.

J'ai fais une petite recherche google, et impossible de trouver cette énigme sur le web, elle pourrait potentiellement faire une épreuve de logique pour NC.

Bonjour MioMilo,

Que donne P(), PN(), !P(), !PN()?
Autrement dit, ces 4 séquences sont-elles des énoncés? Et le caractère vide est-il imprimable?

ferbos

La seul contrainte est que les postulats sont de longueur fini, donc à priori il n'y a pas de problème à considérer le postulat vide comme "valide".
Cependant, on ne peut pas savoir à priori si il s'agit d'un postulat imprimable ;)

Salut,

au départ je pensais à P(P()) mais maintenant je me dis que pas sûr.

ferbos

effectivement, P(P()) n'a aucune raison d'être vrais ou faux, ou d'être imprimable ou non imprimable, il n'y a donc pas grand chose a en tirer tel quel.

Voici un joli problème pas tout neuf, mais que peut-être certains ne connaissent pas.

La société Necropost organise un jeu télévisé auquel participent 32 personnes.
Selon la règle, les joueurs passent tour à tour dans une pièce qui contient une machine avec 32 boutons. Chaque bouton affiche le nom d'un joueur différent (on ne sait pas a priori lequel), et chaque joueur peut appuyer sur 16 boutons. Si chaque joueur parvient à afficher son nom, alors ils gagnent tous le dernier esclave bionique i-slave 18. Si l'un d'eux échoue, le jeu s'arrête et ils repartent les mains vides.
 
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.

Quelle est la stratégie optimale, et quelle est leur probabilité de gagner ?
(on cherche une probabilité non-négligeable, disons supérieure à 1/10)

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?

1: Oui, les boutons sont différenciés. On peut supposer qu'ils sont numérotés de 1 à 32 (et un bouton affiche toujours le même nom).
2: Seul celui ou celle qui presse les boutons peut voir l'affichage. Les autres sont en attente dans une autre pièce.
3: On voit les noms à mesure qu'ils s'affichent.
4: Il peut continuer, mais ça ne sert à rien.

Ceux qui attendent ne reçoivent aucune information sur le déroulement du jeu. Ils ne connaissent que les règles et le résultat de leur concertation.

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?

La solution est assez simple, calculer la probabilité qui en résulte est plus complexe. Mais ça reste faisable avec papier et crayon.
Avec les notions mathématiques qui vont bien, on peut en trouver une bonne approximation, qui révèle une propriété intéressante (et contre-intuitive).

Alors, le premier joueur n'ayant aucune information sur les tiroirs en prend 16 au hasard, soit par exemple les 16 premiers. Il a donc une chance sur deux de trouver son nom.

Pour le second c'est plus compliqué, il doit supposer que le premier a trouvé son nom sinon ils ont perdu tous les deux. Donc la probabilité que son nom soit dans les 16 que son collègue a pris est de 15/31 alors qu'il est de 16/31 dans les 16 autres.
Il a donc plus de chances de trouver son nom dans un des 16 tiroirs qui n'ont pas été choisis, les 16 derniers donc, que dans ceux déjà tirés.
La probabilité que les deux gagnent est donc de (1/2)*(16/31) = 8/31.

Est-ce vraiment la meilleure stratégie ? J'ai l'impression que oui mais cela ne m'a pas semblé très dur à trouver...  :? J'ai marché à l'intuition..

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)

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 ?

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

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

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.

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.

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 :D. Je vais m'y remettre du coup. Je dois pouvoir y arriver maintenant...

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

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 ?

Non, ils ne peuvent pas jouer sur le temps.

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

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

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.

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

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

Et oui, la solution est plus que 12 :)

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

Il y a mieux, mais je suis curieux de connaître ton raisonnement pour 18. En effet, il y a beaucoup de raisonnements qui permettent de trouver 17, mais je n'en avais pas trouvé pour 18 !
PS : Harvey est aussi dessus ;)

J'ai cherché, j'ai trouvé 11 -_-
Après, je me suis dit qu'il y avait surement des notions de maths dans l'histoire. J'ai pris une couverture de survie et me suis mis en PLS durant 30 minutes.


Enjoy

The lsd

Edit : ouais, c'était bien 12, j'me suis loupé en comptant.

Je pense que tu as trouvé 12, plutôt (si tu refais ce que tu as fait, je pense).
Pour trouver 17, c'est très faisable, pas besoin de notions de maths.
Pour trouver plus, ça se corse (quoique je ne sais pas comment BAAL a trouvé 18)

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

Bonjour a vous
j'ai regardé j'ai aussi trouvé 12, pouvez vous dire comment vous trouvez 17, pour voir le cheminement svp ?

Il n'y a pas besoin de notion de maths compliquées pour trouver 17. C'est juste un peu de logique. Si vraiment tu ne trouves pas, je peux t'envoyer le raisonnement pour ce résultat.

En revanche, c'est un raisonnement bien différent qu'il faut adopter pour trouver la réponse (supérieure à 17), et qui demande de pousser la logique et les maths à un niveau au dessus

dans ce cas, j'attend de voir le dis raisonnement  :wink:   je prend les pop corn et j'attend

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'etait sur cette maniere de penser, j'avais trouvé 17 aussi en re regardant j'avais arrêté mon raisonnement en plein milieu en fait, par contre j'y suis revenu et pour trouver plus franchement je sais pas ce que vous faites dans la vie mais vous êtes pas la moitié de demeurés  :rolleyes: ;)  je vais me couché, peut être aurais-je la reponse demain matin, ou une illumination dans la nuit  :D

Pour information, Harvey a trouvé, bravo à lui !

Edit : Je pensais ... Il manque la fin, en fait

Oui, enfin j'ai trouvé une manière de faire mieux que 17. Avec 7 questions, il suffit de 4 bits pour garantir 6 réponses. En appliquant le même système 3 fois, on obtient 18 réponses avec 12 bits. Je sais aussi prouver que la solution ne peut pas être supérieure à 20. Mais je ne sais pas encore comment atteindre 20 ni même si c'est possible (sauf si, peut-être, pixis m'a hinté là-dessus), et étendre le modèle jusque-là n'a pas l'air simple.

La réponse est 20.

Je vous encourage à continuer à chercher. Il n’y a pas besoin de maths avancées du tout!
Voici ma méthode pour les n00bs qui ne trouveront pas seuls:

 
On a q questions et un message de m bits (q=23, m=12 dans notre cas).
On pourra donc générer 2^m messages différents, ce qui n’est pas assez pour représenter toutes les 2^q réponses possibles tant que m<q (12<23).

Cela dit, si on est prêt à tolérer e erreurs, on pourra utiliser le même message pour couvrir plusieurs réponses d’un coup.
Pour e erreurs, chaque réponse est couverte par sum{i=0 à e}{C(q, i)} messages différents.
Par exemple, pour q=4, la réponse 0000 est couverte par:
e=0 -> 0000 (total=C(4,0)=1)
e=1 -> 0000 1000 0100 0010 0001 (total=1+C(4,1)=5)
e=2 -> 0000 1000 0100 0010 0001 1100 1010 1001 0110 0011 0101 (total=5+C(4,2)=11)
e=3 -> 0000 1000 0100 0010 0001 1100 1010 1001 0110 0011 0101 1110 1101 1011 0111 (total=11+C(4,3)=15)
e=4 -> 0000 1000 0100 0010 0001 1100 1010 1001 0110 0011 0101 1110 1101 1011 0111 1111 (total=15+C(4,4)=16)
On s’attend bien sûr à retrouver 2^4=16 pour le cas e=4 (peu importe le message de 4 bits, on n’aura pas plus de 4 erreurs).

Vu la symétrie du problème, il est clair que ces messages sont distribués équitablement à travers les 2^q réponses possibles.
Du coup, pour chaque nombre d'erreurs e, il nous suffit de multiplier le nombre ci-dessus par le nombre de messages que nous pouvons utiliser (2^m),
pour savoir combien de messages on couvrera. Si ce nombre atteint ou dépasse 2^q, on peut garantir le nombre d’erreurs correspondant.
En d'autres mots, on peut supporter e erreurs si l’inégalité suivante est satisfaite:
sum{i=0 à e}{C(q, i)} * 2^m >= 2^q

(Points bonus si quelqu’un arrive à écrire tout ça sous la forme e = ... au lieu d’utiliser une inégalité et de tester les “e” un par un).

Dans l’exemple ci-dessus:
e=0 -> on a besoin de m=4
e=1 -> on a besoin de m=2
e=2 -> on a besoin de m=1
e=3 -> on a besoin de m=0

On peut d’ailleurs confirmer l’exemple de harvey: q=7 e=1 -> m=4
Maintenant pour la question initialement posée, on trouve: q=23 m=12 -> e=3
q-e = 20 questions garanties.

#micdrop

Bien joué BAAL. Pour l'aspect mathématique, effectivement il ne faut pas forcément de notions avancées pour trouver le problème (quoique, cf. mes remarques en noir), cependant les maths sous-jacentes qui permettent de généraliser le problème le sont un peu plus.

En fait, c'est ta phrase


que tu utilises pour simplifier le problème (non pas en tant qu'hypothèse, mais en tant que proposition qu'il n'y a pas besoin de démontrer), si j'ai bien compris. Harvey ne l'a pas prise en compte, et du coup avec ton raisonnement il considère que la réponse est <= 20

En effet, il cherche maintenant à prouver l'existence de ces 2^12 différentes informations qui permettent de couvrir tous les cas. Avec ton raisonnement, on montre qu'il ne peut pas y avoir plus de 20 réponses possibles au pire. Cependant, rien ne montre qu'il existe 2^12 solutions toutes distantes de 7 une à une.

Le problème peut être ramené à 4096 secondes (au lieu de 5400). Comme on a sum{i=0 à 3}{C(23, i)} = 2**11 (et que 2**11 * 2**12 = 2**23), pour que la réponse soit bien 20, il faut s'assurer qu'il y existe une partition de l'espace F₂²³ (dimension 23, avec des entiers modulo 2, donc 0 et 1) avec des boules de rayon 3 (au sens distance de hamming) qui sont dans un espace vectoriel de dimension 12, sous EV de F₂²³, donc comme dit plus haut, qu'il existe 2^12 solutions toutes distantes de 7 une à une.

Si une telle partition n'existe pas, ça veut dire que quoiqu'il arrive, des boules auront une intersection non vide, donc il y aura des solutions couvertes par deux informations, et d'autres pas couvertes.

Ce que tu as montré, finalement, c'est que si on prend des boules de rayon 2, alors quelque soit le centre des boules, 2^12 boules ne suffiront pas à décrire l'espace F₂²³, mais que des boules de rayon 3 peuvent potentiellement décrire cet espace. Il faudrait le montrer


:)

J'espère que je suis clair, et que j'ai bien compris ton raisonnement, donc que mes remarques sont légitimes.

Oui j'ai pris un raccourci, basé sur l’intuition (et quelques tests pour m'assurer que ça tenait debout). Je me doutais bien qu'une preuve plus rigoureuse serait reliée à Hamming.

Bravo donc à harvey pour avoir trouvé en premier! (au moins avec la même méthode que moi).

J'ai fait un programme pour générer une solution. L'approche est naïve, mais ça marche...
Il faudrait potasser la théorie des codes cycliques pour améliorer ça.

Voici une épreuve de logique que j’ai proposée il y’a plus d’un an mais qui n’a pas été acceptée car ”trop de solutions alternatives possibles“, et car ”on ne veut plus de suites logiques". Et pourtant, je ne crois pas que les testeurs aient eux-même trouvé de solution alternative ;).

Si quelqu’un arrive à la résoudre et la trouve sympa, peut-être que ça convaincra les admins de la publier:

Trouvez le nombre suivant dans cette suite:
1, 10, 100, 1000, 101, ?, ...

Indice: La réponse n'est pas 1001.

102 ?

Avec quelle logique?
Il faudrait que la "solution alternative" tienne debout pour tous les éléments quand même, et sans considérer tous les premiers comme éléments d'initialisation arbitraire  =).

Soit N un entier positif, si on prend u_n la suite des entiers entre 1 et N ordonnés alphabétiquement, alors pour N = 101 on a :

u₀ = 1
u₁ = 10
u₂ = 100
u₃ = 101
u₄ = 11
u₅ = 12
u₆ = 13
...
u₁₀₀ = 999

Ou en d'autre mots : ["1", "2", ... ,"N"].sorted()

Avec cette logique, les éléments donnés ici permettent de savoir exactement que N = 1000 et que le terme suivant est 102
(Si on avait N > 1000 alors on aurait 1001 après 1000, et non pas 101, donc N <= 1000 et si N < 1000 alors on n'aurait pas 1000 dans les données, donc N = 1000)

Aucun élément n'est en trop, et il ne manque aucun élément

Pas mal en effet! J'accepterais presque ça comme solution alternative.
Cela dit tu n'as pas utilisé l'indice. Alors oui techniquement tu n'as pas trouvé 1001, mais tu devrais pouvoir expliquer pourquoi l'indice est là.

Ah, et aurais-je oublié de préciser?: la suite est infinie. Au temps pour moi (/me hides).

Très bien je vais continuer mes recherches alors. Pour moi l'indice était là parce que quand j'ai vu la suite, j'ai tout de suite pensé à 1001 (pour je ne sais quelle raison) et l'indice m'a dissuadé de faire des recherches dans ce sens. Un moyen d'éliminer une solution alternative, en somme.

Mais du coup ok pour les infos. J'espérais que je n'avais pas raison, et que la solution était plus intéressante :)

:p

Enjoy

The lsd

Pour sa défense, on n'en avait pas dans le log beta de l'épreuve. Mais pour sa pas-défense, on n'a pas refusé l'épreuve pour cette raison, mais plutôt (en modifiant un peu les propos)


Bon après, quand c'est BAAL qui propose, je pense qu'il y a une méthode intelligente à adopter pour attaquer cette épreuve, et je ne pense pas que ce soit une suite 'alakon' avec un truc introuvable sauf si tu tombes sur le PDF de l'étude du truc.

A voir :)

J'ai bien dit "presque". J'avoue que la réponse de pixis n'est pas mal, ça m'apprendra à faire le malin. Cela dit ça ne répond pas au fait que la suite doit être infinie (ainsi que l'indice).

L'épreuve est loin d'être comparable aux meilleurs épreuves de NC, ça n'est qu'une suite logique après tout, il ne faut pas aller chercher trop loin. C'est d'ailleurs pour ça que je n'ai pas trop insisté pour qu'elle soit publiée. Je ne suis pas d'accord avec l'argument des logiques alternatives, mais je suis plus ou moins d'accord avec le fait qu'on ne veuille plus de suites. Cela dit elle est meilleur que la plupart de celles qui sont déjà là.

Salut,

Mmmm je proposerais bien 11 avec une logique un peu tordue mais qui semble fonctionner, voici les 18 premiers éléments que je peux proposer :

1	0000 0001
2	0000 0010
3	0000 0100
4	0000 1000
5	0000 0101
6	0000 0011
7	0000 0111
8	0000 1011
9	0001 0000
10	0001 0001
11	0001 0010
12	0001 0100
13	0001 1000
14	0001 0101
15	0001 0011
16	0001 0111
17	0001 1011
18	0010 0000

Une sorte d'incrémentation binaire par lots de 4 bits avec un règle étrange. Les 0 barrés sont là uniquement pour mieux illustrer la logique, comme si il y avait 8 bits, on pourrait cependant continuer la suite indéfiniment.

Voici les règles :

• A chaque élément de la suite on déplace le 1 soit vers la gauche soit vers la droite dans un bloc de 4 emplacements.
• La direction du déplacement au départ de la suite est de la droite vers la gauche.
• Le 1 peut se déplacer uniquement sur un emplacement contenant un 0.
• Lorsque le 1 ne peut plus se déplacer dans sa précédente direction il change de direction et un nouveau 1 est ajouté après le déplacement à la place du premier 0 disponible en partant de la droite (ce qui permet d'expliquer l'élément 7 par exemple).
• Lorsque les règles précédentes ne peuvent plus être respectées sur le bloc en cours (sur l'élément 9 par exemple) on bascule sur le bloc de 4 suivant et on réinitialise le bloc en cours avec des 0 puis on reprend les règles normalement.

Mon exemple des 18 premiers éléments me semble juste uniquement si la chaine commence à 0. Si ce n'est pas le cas alors il suffit de supprimer les éléments 9 et 18 de mon exemple et d'adapter la dernière règle pour réinitialiser le bloc en cours avec 0001 au lieu de 0000, ça me semble également correct.

Est-ce une solution alternative valable ?

Bien tordue cette réponse ... Mais du coup


Comment l'indice est-il utilisé ?

Sur un raisonnement similaire on aurait pu avoir 1001 comme réponse.
En modifiant la règle du changement de direction de sorte que la direction soit toujours de la droite vers la gauche sauf si on ne peut plus aller à gauche alors on tombe sur 1001 puis 0111 puis 1011 etc...
Mais puisque la réponse n'est pas 1001 alors j'ai juste arrangé la règle pour que ça colle :)

Bien tenté ! Mais je ne considère pas ça comme une alternative valable non plus, le choix des règles est complètement arbitraire, ainsi que la taille du bloc (4) qui est clairement là juste pour trouver le terme 101. Tu le montres toi-même en disant que tu aurais pu modifier les règles pour obtenir 1001.

Tu aurais aussi pu dire "une fois qu'on a un nombre pair de 1, le nombre suivant est 1337".

Dommage, ma solution me semblait plutôt élégante ^^


Il est effectivement possible d'énoncer des règles totalement arbitraires mais mes règles me semblent bien respecter la structure du début de la suite tout en permettant de la continuer indéfiniment (je vois ça comme un compteur binaire, l'ajout d'un nombre tel que 1337 ou de tout autre nombre différent de 1 ou 0 aurait rendu ma solution beaucoup moins élégante) .
Le bloc de 4 est effectivement là pour rester cohérent dans la suite à cause du terme 101 qui vient après 1000, il fallait donc trouver une règle qui permettait au 1 de repartir en arrière.

Ceci dit, ma solution est tellement tordue que je peux concevoir qu'elle ne soit pas considérée comme valable, peut-on vraiment se permettre de réinventer la façon d'incrémenter un nombre en binaire ? ^^

Je vais chercher une autre solution.

Le titre de l'épreuve aurait été "Un deux trois".

Suite à ton indice je propose 1010.

En partant du principe que c'est du binaire, le premier élément étant 1, on constate que les 3 éléments suivants correspondent à l'élément qui précède multiplié par deux (donc trois multiplications par deux). Après ces trois multiplications on soustrait 3 puis on reprend les multiplications etc...
Ce qui donnerait en décimal : 1 2 4 8 5 10 20 40 37 74 ....

Est-ce correct ?

Moi je parie que non parce que ça n'utilise pas l'indice :D

Et que encore une fois, c'est très arbitraire comme règle.

1       un
10      dix
11      onze
100     cent
1000    mille
101     centun
110     centdix
1001    milleun
111     centonze
1010    milledix
1100    millecent
1101    millecentun
1110    millecentdix
1111    millecentonze

Wahouuu! Bien joué Spaulding! and welcome back!

C'est la bonne idée mais je crois que tu as fait des fautes de frappe/calcul.

Sinon ta logique explique bien comment trouver 1001, mais ce n'est pas la bonne réponse ;).

Edit: Ah je crois avoir compris ce que tu as fait. C'est presque ça.

Avec la logique de Spaulding, je trouve

un
dix
cent
mille
centun
centdix
centonze
centmille
dixmilleun
centmilleun
...

De l'ensemble des nombres qui s'écrivent avec n lettres (et qui n'ont que des chiffres 0 ou 1 en décimal), on ne garde que le premier (ici en ordre alphabétique, ça pourrait être aussi l'ordre numérique).
Mais du coup, la réponse est la même et c'est encore pas ça.

un
dix
cent
mille
centun
ungogol ?
Mais aucune idée de la logique.

Bien joué!!

Effectivement il fallait prendre le plus grand nombre de n lettres, nul besoin de se limiter aux chiffres 1 et 0.
La subtilité additionnelle était de trouver "ungogol" au lieu de "milleun".

Le mot de passe aurait donc été:
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

;)

Histoire de relancer le fil, j'aimerais revenir sur le problème des chapeaux (https://www.newbiecontest.org/forums/index.php?topic=4352.msg58318#msg58318) présenté par Pixis. Avez-vous déjà considéré le cas où il y a un nombre *infini* de prisonniers ? Les règles sont les mêmes: ils parlent chacun à leur tour, ne transmettent pas d'autre information que la couleur, leurs capacités intellectuelles et mémorielles sont divines, et ils peuvent se concerter avant de passer l'épreuve. Ils ne peuvent bien sûr pas prévoir l'assignation des couleurs, qui est faite au hasard. L'objectif est que tous trouvent la bonne réponse, sauf un au pire.
Comment font-ils ?
(La solution est en partie expliquée dans une vidéo de Mathologer)

(Au passage, merci BAAL pour ton énigme, je pense que je n'aurais jamais trouvé le gogol sans indice supplémentaire.)

La séquence va jusqu’à l’infini, et donc on trouvera n’importe quelle séquence blanc/noir voulue, autant de fois que l’on voudra. On pourra donc choisir une séquence bien conçue et s’en servir comme ”checkpoint“, pour indiquer une fin de sous-séquence.

Quand on s’approche trop de la fin d’une sous-séquence, on passe à la suivante.

C’est une idée à paufiner. Mais plus j’y pense plus je me dis que ça ne fonctionnera pas, pour des raisons que j’ai du mal à expliquer...

Tu veux saucissonner la séquence infinie en sous-séquences finies ?
Dans ce cas, il faudra que l'un des prisonniers se sacrifie à chaque fois qu'on change de tranche, et une infinité d'entre eux vont se tromper.
Il s'agit bien de trouver un analogue du bit de parité qui fonctionne (façon de parler) sur une séquence infinie quelconque.

Indice: les prisonniers ont droit à l'axiome de choix...

J'ai jeté un coup d'œil à l'axiome de choix mais pas bien compris...

Par contre j'ai une autre idée: Au lieu d'utiliser xor, les prisonniers peuvent se mettre d'accord sur un code qui leur permet d'arriver à une séquence en particulier.

Par exemple:
Le premier prisonnier voit: x100111...
Leur code indique que s'il voit cette séquence, il dira 0, alors que s'il voit x000111..., il dira 1 (ceci est un exemple; 1 et 0 sont interchangeables et ne correspondent pas forcément au 1 du début de la séquence).
Le deuxième prisonnier connaît le même code, et il voit xx00111...
En entendant 0 il peut donc en déduire la couleur de son chapeau: 1.

Le troisième prisonnier voit xxx0111...
Il sait que le second a dit 1, et peut donc en déduire: x1x0111...
Il sait donc que le premier a vu soit x100111..., soit x110111...
Afin de pouvoir en déduire la couleur de son chapeau, il faudrait donc que le code pour le premier étant donné la séquence x110111... soit différent du code pour la séquence x100111...
Il indiquerait donc 1 dans ce cas au lieu de 0.

Le quatrième prisonnier voit xxxx111...
Connaissant les réponses du #2 et #3 il sait que la séquence ressemble à ça: x10x111...
Le code pour x100111... doit donc être différent du code pour x101111...

Et ainsi de suite...

Ça a l'air de fonctionner! Non?

J'ai pas trop compris.
Ça a plutôt l'air de tendre à monter que le problème est insoluble (puisque le premier ne dispose que de deux codes différents).
Dans le cas "fini", on utilise le fait que les prisonniers ont tous une partie de l'information, et que la partie qui leur manque leur est donnée par ceux qui les précèdent dans la chaîne.
Dans le cas infini, il se passe un peu la même chose. Ils sont dans un monde (représenté par une séquence de bits, ou un nombre réel) parmi une infinité indénombrable de mondes possibles. Ils doivent utiliser l'information qu'ils ont pour faire le bon choix. On peut supposer en effet que tous jusqu'au n-ième prisonnier ont répondu correctement, mais comment le n+1ème en déduit-il sa réponse ? Il doit utiliser l'ensemble des réponses, plus l'information qu'il a en commun avec ceux qui ont répondu. Et il partage une quantité *infinie* d'information avec eux, qui se trouve dans la traîne de la séquence. La question est de savoir comment l'utiliser.

C'est le côté mindfuck du problème qui me plaît beaucoup, même si je ne suis pas sûr de comprendre entièrement la solution. L'allusion à l'axiome de choix laissait entendre que les approches purement algorithmiques du problème ne débouchent sur rien, puisque chaque prisonnier doit percevoir et exploiter une quantité infinie d'information, et que rien de tel n'est possible en temps fini. On peut admettre que les prisonniers définissent un code avec un nombre d'entrées infini, et peuvent le lire instantanément...

Moi je ne vois vraiment pas de solution à ce problème. De ce que j'ai compris, s'il y a un nombre infini de prisonniers, alors je il n'y a pas d'information binaire permettant de donner une information globale, puisque l'ensemble de prisonniers est indénombrable
Comme BAAL, je suis allé jeter un coup d'oeil à l'axiome de choix, mais je ne suis pas bien sûr de trouver/comprendre comment l'appliquer.

Après, si tu m'assures qu'il y a une solution à ce problème, alors je suis vraiment curieux, parce que d'après mes recherches, je ne vois pas comment c'est possible. Si jamais une solution existe, je serai extrêmement curieux de la connaitre :)

L'ensemble des prisonniers est dénombrable (aleph-zéro). Autrement, ils ne pourraient pas tous répondre séquentiellement.

J'avais le même avis que toi: ça a vraiment l'air infaisable.
Le principe est de diviser l'ensemble des mondes possibles en classes, de telle sorte que
1. les prisonniers puissent constater dans quelle classe se trouve le monde réel
2. la "distance" entre deux mondes possibles d'une même classe soit finie
3. on puisse choisir un monde de référence au sein de chaque classe (l'axiome de choix sert à ça, entre autre (https://fr.wikipedia.org/wiki/Paradoxe_de_Banach-Tarski))
À partir de là, je pense qu'il en faut peu pour trouver la solution (mais peut-être que ce que je raconte est imbitable).

Pour le moment, je suis d'accord avec les derniers mots de ton dernier post. Il faudra que je revienne dessus.

Alors si ça intéresse encore quelqu'un, voici la solution telle que je la comprends.



On considère que deux séquences de couleurs sont "semblables" si et seulement si le nombre de différences entre elles est fini. Cette relation est transitive: soient trois séquences A,B et C, le nombre de différences entre A et C est, au plus la somme du nombre de différence entre A et B et entre B et C  (et au moins l'écart entre ces deux nombres). C'est donc une relation d'équivalence, et on peut découper l'ensemble des séquences de couleurs possibles en sous-ensembles de séquences semblables (classes d'équivalence). Chaque classe contient une infinité (dénombrable) de séquences, et il y a une infinité (indénombrable) de classes.

Pour décider si une séquence S appartient à une classe C, il suffit de "compter" le nombre de différences entre S et une séquence quelconque de C. Si ce nombre est fini, S appartient bien à C. Pendant la préparation, les prisonniers s'entendent pour choisir une séquence dans chaque classe (c'est là qu'intervient l'axiome de choix, qui dit que c'est possible); appelons-les les représentantes. Puis pendant l'exercice, ils comparent la séquence réelle (appelons-la R) avec chacune des représentantes. Pour une et une seule d'entre elles (appelons-la Q), ils trouveront un nombre de différences fini. À partir de là, on procède comme dans le cas fini. Le premier prisonnier qui parle indique, en disant "noir" ou "blanc", si le nombre de différences qu'il voit entre R et Q est pair ou impair. Le suivant compare cette parité avec le nombre de différences qu'il voit, lui, entre R et Q. Si c'est la même, alors le bit qui correspond à sa position est le même que dans Q, sinon il est différent.

Alors évidemment, on ne peut pas *construire* les objets dont on parle, et il suffit que l'un des prisonniers se trompe pour tout foutre en l'air. Mais ce sont les hasards de la vie.



Voici la vidéo dans laquelle j'ai trouvé ce problème (tout ce qui est sur la chaîne est excellent):
https://www.youtube.com/watch?v=aDOP0XynAzA

Moi ça m’intéresse toujours ;).

C’est juste que je pensais avoir trouvé une solution valable, et après avoir vu la solution, je crois que la mienne marche toujours. En fait c’est peut-être la même solution, juste formulée de manière bien moins élégante. Mais j’ai peut-être tort...

Je ne connaissais pas mathologer, j’ai regardé plusieurs vidéos maintenant, et j’aime beaucoup, merci pour la référence!

Par contre je connaissais une autre chaîne du genre: Numberphile. D’ailleurs, voici un problème que j’ai vu sur Numberphile, mais dont je n’ai pas encore regardé la solution (et je n’ai pas encore vraiment essayé résoudre). Je chercherai donc en même temps que vous:

J'ai relu ta réponse. Si je comprends bien, le code associe à chaque séquence un bit 0 ou 1, avec la propriété que deux séquences ont un bit différent si elles ont un nombre impair de différences, et le même bit si ce nombre est pair. Ça revient effectivement au même. Je donnais aussi le même bit à toutes les représentantes, mais comme celles-ci sont choisies au hasard, je crois que ça ne change rien.

Je zyeute ton problème.

Histoire de relancer cette conversation et de vous motiver, voici la vidéo où j’ai découvert le problème ci-dessus.
Ça vaut le coup de s’y mettre ;).

https://www.youtube.com/watch?v=Y30VF3cSIYQ

Bon j'avoue que c'était assez difficile.
Passons donc à l’épreuve suivante!

Voyez le jeu suivant:
http://www.web-games-online.com/peg-solitaire/index.php

Il existe en deux versions, française et anglaise.
Prenez le temps de jouer quelques parties, c’est fun!

Ce qui est intéressant c'est que dans la version française, si on commence avec le pion central manquant, il devient impossible de résoudre le problème.
Votre mission est de le prouver!

Ah je connais ce jeu, j'avais appris à le résoudre (version anglaise) ya loooongtemps, mais on a un cerveau étonnant et tous les automatismes sont revenus. Il faut que j'essaie la version française, pour me retrouver face à l'impossibilité de le résoudre avec en situation initiale la pièce centrale manquante, et comprendre l'impossibilité. :)

On associe des nombres aux cases comme ceci:
le centre vaut 0, et à chaque fois qu'on va vers le haut ou vers la droite on ajoute 1 modulo 3.
Inversement, on soustrait 1 mod 3 quand on va vers le bas ou la gauche.
Ça donne quelque chose comme ça:
   
        201
       01201
      1201201
      0120120
      2012012
       20120
        201

D'après la règle, pour qu'un pion arrive sur une case 0, il doit soit partir d'une case 2 et retirer un pion d'une case 1,
soit partir d'une case 1 et retirer un pion d'une case 2.
Si on compte le nombre de pions sur chaque type de case avant et après le coup, on obtient dans les deux cas ceci:

       0       1      2
avant: x       y      z
après: x+1     y-1    z-1

On voit que la parité des trois nombres change simultanément. S'il sont tous les trois pairs, ils deviennent tous impairs. Et s'ils sont tous impairs, ils deviennent tous pairs.
C'est aussi le cas avec les autres types de coups.
Or la position de départ avec le pion manquant au centre a 12 pions sur les cases 0, 12 sur les cases 1 et 12 sur les cases 2.
Elle ne peut pas être convertie en une position avec une seule valeur impaire.
Il est donc impossible de ne laisser qu'un seul pion.
.

Mais je ne sais pas prouver que l'autre version est solvable :)

Pas mal du tout! bien joué harvey. C’est exactement la preuve que j’avais lu sur Wikipedia.
En fait je ne savais pas que c’était impossible et j’ai essayé de résoudre pendant plusieurs heures. Au final je suis allé voir la page du jeu sur Wikipedia pour m'inspirer et je me suis rendu compte que c’était impossible, en voyant une belle preuve comme la tienne.

Pour prouver que l’autre version est solvable, il te suffit de la résoudre ;). (Ça j’y suis arrivé).

Pour ceux qui ont de l'endurance en mode bien costaud, cette chasse au trésor sur le thème SF de Philip K Dick a l'air pas mal : http://chasse-au-tresor-pkd.com/

Pour la SIGSEVv1, Pixis a préparé un gâteau au chocolat et à la fraise.
Le gâteau est circulaire, la pâte au chocolat en dessous, et celle à la fraise au dessus.

Il partage le gâteau en 10, et invite les 10 premiers au challenge à le déguster dans l'espace VIP.

Mais l'un.e des 10 insiste pour avoir le chocolat au dessus ! Manque de bol, il n'y a qu'un seul plat et le seul outil pour retourner les parts est une pelle magique qui fait exactement 3/10 de la surface, et permet seulement de retourner 3 parts contigües. #logistique

Combien faut-il d'opérations de retournement pour avoir exactement une part avec le chocolat sur le dessus ?

Pendant qu'il réfléchit, les challengers cherchent le moyen de l'embêter le plus possible, parce que le chall avec les pirates qui se disputent le contrôle de la tireuse à bière était vraiment trop hardcore. Il cherchent donc combien de parts avec le chocolat au-dessus lui demander pour maximiser le nombre de retournements. Que vont-il trouver ?

On se rend compte assez vite qu’il n’y a pas tant d’états uniques grâce aux symétries. J’ai donc fait un double-sided breadth-first-search à la main (cherchant à partir du début et de la fin en même temps afin de trouver une intersection plus tôt).

Mais c’est quand même long... il faudra au moins 6 coups. Et pour la deuxième question, on se rend compte assez facilement que la réponse sera soit 1 soit 10.

Je laisse tomber pour l’instant par manque de temps. Bonne chance aux autres! Quelques questions qui m’intriguent: Comment généraliser pour n’importe quel entier positif n et k (ici n=10 et k=3).

Y a-t-il une formule pour calculer le nombre d’états uniques (dépendant seulement de n). Par exemple, les états 0011000111 et 1110001100 sont les mêmes et ne devraient pas être comptés deux fois (les chaînes ci-dessus devraient être circulaires).

https://oeis.org/A000031

Les solutions pour n=4 ou n=7 peuvent aider...

Un instrument de musique est composé d'une bassine circulaire, d'un mât vertical central et de trois cordes identiques.
Les cordes sont tendues entre le sommet du mât et le bord de la bassine. Le pied du mât est au creux de la bassine.
Comment choisir les points de fixation des cordes à la bassine pour que les trois notes forment un accord majeur "parfait" (eg. Do-mi-sol) ?

(On suppose que la bassine ne se déforme pas, et que le mât est tenu droit par la tension des cordes)

Pour le gateau de la SIGSEVv1, il existe une solution en 7 retournements relativement simple si on pense a utiliser les proprietes circulaire du gateau :
0 - 0000000000
1 - 1110000000
2 - 1111110000
3 - 1111111110
4 - 1111111001
5 - 1111100101
6 - 1100000101
7 - 0000000100

Pour la deuxieme question, il me semble que la reponse est 10 (il devrait etre impossible d'obtenir 10 sans passer par l'etat avec 1 part retournee).
Ou peut etre, the cake is a lie... ;)

Une autre ! Une autre !