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

jonas (2012-12-30T17:17:18Z)

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 >

tchanf (2010-10-13T14:57:43Z)

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

Fork (2010-07-18T07:48:27Z)

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

Ruxor (2009-05-24T23:15:02Z)

Apokrif → Non, un mathématicien qui est déjà passé se le rappelle et n'allume plus jamais la lumière (ni ne fait quoi que ce soit). C'est ce que Julien voulait dire par « une seule fois » (la formulation est concise et peut-être pas super claire).

Apokrif (2009-05-24T23:12:34Z)

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

Daniel (2007-09-25T13:14:48Z)

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 !

Jonas (2007-06-13T09:49:55Z)

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

Jonas (2006-12-31T12:06:29Z)

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.

FreeCorp (2006-11-28T17:13:37Z)

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.

Ni (2006-11-24T23:09:36Z)

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?

Nicky (2006-11-24T20:24:33Z)

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.

Groug (2006-11-22T17:16:35Z)

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…

Ryusenshi (2006-11-22T00:36:05Z)

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.

Gru (2006-11-21T23:38:50Z)

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

Touriste (2006-11-21T23:05:56Z)

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.

phi (2006-11-21T19:32:26Z)

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?

Anonymous Coward (2006-11-21T18:23:38Z)

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

Julien (2006-11-21T17:57:51Z)

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.

Ruxor (2006-11-21T13:09:44Z)

Non, on n'a en effet pas le droit de modifier l'ordre dans lequel les boîtes sont rangées.

Nick (2006-11-21T10:48:23Z)

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"

Vicnent (2006-11-21T10:34:05Z)

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

Nick (2006-11-21T10:32:28Z)

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

Nick (2006-11-21T10:03:19Z)

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


You can post a comment using the following fields:
Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: ca2422


Recent comments