Comments on De quelle science relèvent ces énigmes ?

et pour pour l'enigme des 3 mathematiciens et des chapeaux a 2 couleurs aussi preciser que dr No cree un nombre de chapeaux tres largement superieur au nombre de mathematiciens il me semble. Bref , s'assurer que la proba d'avoir un chapeau d'une couleur est de 50%

pour l'enigme des 3 mathematiciens et des chapeaux de 2 couleurs possibles…….il faut preciser que dr No cree autant de chapeaux d'une couleur que de l'autre…..sinon ca marche pas

Another puzzle that appears similar to the first one here is <URL: https://mathoverflow.net/questions/326669/guessing-each-others-coins >.

Here's another problem.

You play the following card game. At the start of the game, you get ten cards, the spades from 4 to king inclusive, and the dealer gets ten cards, the hearts from 4 to king inclusive. Each round, first you discard a card from your hand at your choice, then the dealer discards a card from his hand face up randomly. If your card is higher rank than the dealer's card, then you win this round; if your card is lower rank than the dealer's card, then the dealer wins this round; if they're of the same rank, nobody gets a point. After ten rounds, when all the cards have been used up, the game ends. If you have won more rounds than the dealer during this game, then you win 10 cents; if the dealer has won more rounds than you, then you lose 10 cents; if you and the dealer won the same amount of rounds, then nobody pays anything. Is there a strategy you can use to make the expected value of money you win positive?

The first problem, with the hundred boxes, was posed in KöMaL this november with the number B. 4491.: <URL: http://www.komal.hu/verseny/feladat.cgi?a=honap&h=201211&t=mat&l=en >

on peut ensuite compliquer un peu en ne donnant pas aux mathématiciens la position initiale de l'interrupteur…

Après plus d'un an de retard et avoir réfléchi sur le problème des interrupteurs, j'en arrive à la même solution que Julien (non j'ai pas réfléchi pendant un an ! Juste hier dans mon lit).

@Julien: "Pour l'interrupteur: un mathématicien est désigné comme compteur et est le seul à avoir le droit d'éteindre la lumière et il le fait dès que possible… les autres ont le droit d'allumer la lumière une seule fois et seulement si elle est éteinte. Ça peut prendre du temps, mais le compteur n'a qu'à attendre de voir la lumière allumée suffisament de fois."

Cette solution ne marche que si chaque mathématicien va dans la pièce en au plus une occasion.

La technique du glaviot a l'avantage extraordinaire sur la technique de l'interrupteur en ce sens que celui qui crache le 50 ème glaviot SAIT que tout le monde est passé ! Pas besoin d'un mathématicien-compteur (d'ailleurs on sait que les mathématiciens comptent souvent très mal) Le Dr NO va t-il l'accepter ? That is the question !

One more puzzle like these: <URL: http://www.jsoftware.com/jwiki/Essays/88_Hats >

Ruxor, thanks very much for the task with the 100 boxes (I've more or less alredy heared of the other ones). In the university, I've now been discussing this task with others for some time now, and I've even learnt of such things as the Poisson-Dirichlet distribution.

Après la combinatoire cybernétique, un peu de cyberchéologie : je suis tombé sur la source du premier problème aujourd'hui (attention SPOILER, il y a aussi la solution) http://www.math.dartmouth.edu/~pw/solutions.pdf

Et si vous en redemandez, Peter Winkler a même réuni une "Connoisseur's Collection" d'énigmes mathématiques trouvable dans toute bonne librairie.

Pour le problème des généraux byzantins, il suffit que chaque mathématiciens se gènere une paire de clef asymétrique pour faire de la signature, puis chaquun signe le message qui dit ce qu'il a recu du Dr No et l'envoie à tout le monde. On fait ensuite une deuxième passe ou tout le monde transmet aux autres tous les messages signés qu'il a reçu, et si un traitre a signé deux messages différents, tout le monde est au courant (et les traitres ne peuvent pas forger de signatures pour accuser les autres).

Comment ça je triche?

Tiens, j'ai trouvé la solution du troisième problème (tout seul, pour de vrai). Alors voilà.

Les mathématiciens choisissent une numérotation pour les couleurs de chapeau, mettons de 0 à n-1 s'il y a n chapeaux. Par la suite j'identifierai par commodité de langage couleur et numéro. Le gars en queue de file fait la somme modulo n des couleurs de tous ceux qui sont devant, et annonce le résultat (en général, sauf miracle, il se goure). Puis l'avant dernier de la file fait la somme de toutes les couleurs des chapeaux qu'il voit devant lui. Il retranche (toujours modulo n) le résultat de cette somme à ce que vient d'être annoncé, et annonce ce qu'il obtient. Par la suite, les mathématiciens parlent dans l'ordre inverse de l'ordre de la file (de la queue vers la tête, donc). Chacun prend le premier nombre annoncé, en retranche tous les nombres annoncés par la suite, ainsi que toutes les couleurs des chapeaux qu'il voit devant lui, et annonce le résultat.

Les problèmes 3 et 4 (les deux problèmes de chapeaux, quoi) sont en fait des problèmes de la théorie des codes correcteurs d'erreur. Le quatrième problème est encore plus marquant si on augmente le nombre de mathématiciens présent : avec par exemple 127 mathématiciens suffisamment astucieux, il existe une stratégie qui leur garantit 127 chances de survie sur 128, si le Dr No tire vraiment la couleur des chapeaux au hasard…

Pour le problème des trois chapeaux, je pense que la meilleure stratégie est :
- si un mathématicien voit que les deux autres ont des chapeaux de même couleur, il annonce au Docteur qu'il a un chapeau de l'autre couleur;
- si au contraire il voit que les deux autres ont des chapeaux de couleur différente, il ne dit rien.

De la sorte :
- si les trois mathématiciens avaient tous les trois des chapeaux de même couleur (ce qui a une probabilité 1/4 d'arriver) alors ils vont tous les trois faire une annonce fausse.
- si au contraire deux avaient un chapeau d'une couleur et le troisième d'une autre, les deux premiers ne diront rien et le troisième fera une annonce juste. Et ils seront sauvés, avec une probabilité 3/4.

Enfin, c'est de loin la plus facile de ces énigmes.

Pas grand chose à dire, si ce n'est que je veux une réponse un de ces quatre :)

Ben ça circule vite, on en parlait au café il y a moins d'une semaine, avec des petites variantes dans l'énoncé c'est d'ailleurs intéressant de voir comment des petites variantes dans l'énoncé modifient imperceptiblement les difficultés.

Tiens (Julien) je pensais à autre chose, qui risque d'être plus long:
les jours sont comptés modulo 50, le mathématicien n allume ssi le jour est n (mod 50). Il faudra là encore attendre longtemps…

Et pour les boîtes, si le mathématicien n (éventuellement avec une renumérotation car le méchant Dr No risque d'anticiper) ouvre les boîtes n et suivantes (cyclant), on ne parvient pas à 30%… Mais avec un recouvrement plus sophistiqué qui répartit mieux les intersections, on y arrive?

Ça te plait pas comme discipline "théorie des jeux" ?

Le coup des chapeaux à la queue-leu-leu est une question de checksum… le dernier fait le checksum des chapeaux et on remonte la file en utilisant la magnigicence des codes correcteurs d'erreur. Ça marche quels que soient le nombre de mathématiciens et le nombre de couleurs…

Pour l'interrupteur: un mathématicien est désigné comme compteur et est le seul à avoir le droit d'éteindre la lumière et il le fait dès que possible… les autres ont le droit d'allumer la lumière une seule fois et seulement si elle est éteinte. Ça peut prendre du temps, mais le compteur n'a qu'à attendre de voir la lumière allumée suffisament de fois.

Je vais quand meme reussir:
pour les trois avec des chapeaux B ou N.

Le premier qui passe:
Si ses deux copains ont la meme couleur de chapeau alors il dit une couleur au hasard. probabilte de mourir =1/2(chapeaux identiques)*1/2(couleur donnee est bonne).
Soit les mathematiciens sont libres, soit les deux autres savent qu'ils ont des couleurs differentes. Dans ce cas le deuxieme sait quoi repondre. A moins qu'il ne soit tres con:
"What is your favorite colour?
Red… Heu… Blu…AAAARRRRRgh"

Le premier problème a doné lieu à une discussion sur fr.sci.maths : <URL: http://groups.google.fr/group/fr.sci.maths/browse_thread/thread/4dd4014bb136508e/48b93387d09ef15c?hl=fr#48b93387d09ef15c >

De quelle science ? Eh bien disons que je vois là un problème, qu'il s'agit de le modéliser puis de le résoudre… alors je vais précher pour ma paroisse : la recherche opérationnelle :-)

Je te propose de rattacher ces enigmes a la branche "sciences de l'ingénieur". Exemple :

Pour les 50 avec l'interupteur :

Le premier qui passe allume la lumiere et, pendant que le Dr No a le dos tourné pour se moucher (c'est l'hiver et tout le monde a la creve), il crache un gros glaviot parterre.

Quand un autre mathmaticien passe pour la premier fois dans la salle, il crache aussi un gros glaviot et compte ceux qu'il trouve parterre.

S'il y en a 50, il dit que tout le monde est passé.

Juste pour etre sur, les mathematiciens n'ont pas le droit de modifier l'odre dans lequel les boites sont rangees?