Un Peu De Logique

[invite788778a8]

Une mutinerie s’est déclarée à bord du Neptunia. Pour punir les 11 mutins, la capitaine les a placés dans onze îles différentes. Chaque mutin connaît l’existence des onze îles, le nom de l’île sur laquelle il est détenu mais ignore l’affectation de ses camarades sur les dix autres îles. Bientôt les mutins découvrent qu’ils peuvent communiquer entre eux grâce à des pigeons voyageurs qui peuvent aller d’une île à l’autre en portant des messages. Cependant chaque mutin ne peut utiliser quotidiennement qu’un seul pigeon à destination d’un seule île. En combien de jours les onze mutins peuvent-ils être tous informés de leurs affectations respectives ?

[yat]

Je pense qu'il va y avoir une différence significative entre l'option ou les mutins adoptent tous une stratégie optimale et celle ou ils envoient leurs pigeons un peu au pif, et également entre le cas ou ils ont du bol et celui ou ils n'en ont pas.

Donc pour commencer, la borne inférieure, le cas idéal.
Au début du jour j, chaque mutin connait la position de n-1 autres mutins (n en comptant la sienne), et envoie le papier à un autre mutin. Par chance, chacun reçoit un pigeon qui ne lui apporte que des informations nouvelles, et au soir chacun connait la position de 2n-1 autres mutins (2n en comptant la sienne). Il est clair que dans ce cas idéal, à la fin du quatrième jour tout le monde connait la position de tout le monde.

Du coup je pense que ça répond à la question "En combien de jours les onze mutins peuvent-ils être tous informés de leurs affectations respectives ?". Mais je vais essayer de trouver le temps de me pencher plus sérieusement sur les stratégies à adopter.

[yat]

Après relecture, je me rends compte que ma description de la situation optimale part quand même s'un certain a priori. Pour être plus général, un mutin qui connait la position d'un mutin (lui ou un autre), c'est une information. Dans le meilleur des cas (c'est à dire s'il n'y a pas de redondance d'informations dans les pigeons reçus), le nombre d'informations est doublé chaque jour. On a 11 informations au départ et on doit en avoir 121 à la fin, on aboutit donc bien à quatre jour dans le meilleur des cas, indépendament de la méthode employée.

[invitec314d025]

Il y a au moins une solution en 4 jours d'ailleurs.
Si au jour i, le mutin n envoie ses informations au mutin n+2^i-1 (dans Z/11Z), ça doit marcher.

Chaque mutin ayant la bonne idée de numéroter les îles en fonction de leur ordre alphabétique, ils peuvent même le faire à coup sûr

[A voir en vidéo sur Futura]

[invite788778a8]

bravo à vous deux et à demain

[yat]

Si au jour i, le mutin n envoie ses informations au mutin n+2^i-1 (dans Z/11Z), ça doit marcher.

Chaque mutin ayant la bonne idée de numéroter les îles en fonction de leur ordre alphabétique, ils peuvent même le faire à coup sûr

[MODE=tetracapillotomie]Eh oui... mais ça implique que les mutins fassent différents choix, qui dans l'absolu sont totalement arbitraires : on peut classer les iles par ordre alphabétique, par longitude ou par superficie, et envoyer les informations au mutin 2+n^i-1 ou 2+n^4-i. Dans tous les cas, la stratégie appliquée à l'ensemble du groupe est optimale. Mais pour que ça marche, il faut qu'ils adoptent tous le même, et donc qu'ils fassent tous les mêmes choix arbitraires, puisque l'énoncé semble bien dire qu'ils n'ont pas pu se concerter avant. Il serait intéressant de voir s'il y a un type de stratégie qui permette à chaque mutin d'exploiter toutes les informations dont il dispose, sans préjuger des choix de ses camarades. C'est le choix du nombre 11 plutôt que 16, qui me faisaient penser qu'il y avait une stratégie objective, bien balaise et bien efficace derrière... Mais apparemment ce qu'on a proposé était la solution attendue... donc [/MODE]

Ca me fait penser à une autre énigme avec des pirates. Mais comme elle a déjà été postée dans le coin, je vais en mettre une qui ressemble.

C'est une arène avec n lions affamés. Ces lions sont très intelligents, et ont deux priorités dans la vie :
1-ne pas se faire bouffer par les autres lions
2-bouffer
Si un lion mange un morceau de viande, il s'endort, et devient un morceau de viande potentiel pour un autre lion (un seul : ces lions ne partagent pas de repas). Par contre, en apparence ces lions sont très civilisés, et ne vont pas chercher à attaquer un lion éveillé, ou à se battre pour un morceau de viande.
Alors que les lions déambulent tranquillement, le dresseur balance un morceau de viande dans l'arène. Que se passe-t-il, en fonction de n ?

[invite4793db90]

Salut,

j'ai résolu le cas n=1 !



Plus sérieusement, la configuration initiale lions éveillés/endormis joue un rôle : quelle est-elle ?

[invitec314d025]

Eh oui... mais ça implique que les mutins fassent différents choix, qui dans l'absolu sont totalement arbitraires : on peut classer les iles par ordre alphabétique, par longitude ou par superficie

Là tu es en train de me parler de mutins amateurs. Mais je suis sûr que ce problème est connu de tous les mutins dignes de ce nom et qu'ils se sont mis d'accord avant de se mutiner

[invite1d77d8d9]

Pour les lions je dirait que quel que soit n, il ne reste qu'un lion a chaque fois, sauf si n=0 évidemment.

Car siil y a un morceau de viande, un lion le mange, s'endort et se fait manger a son tour et ainsi de suite jusqu'au dernier lion.

[invitef4181796]

Les lions sont tres intelligents, on pourrait aussi imaginer qu'un lion s'avance et mange le morceau de viande, puis s'endort. Les autre lions se rendent compte que le repas fini, ils sont vulnérables et peuvent donc etre mangés. Chaque lion se dit que si il mange le lion endormi et s'endort à son tour, pensant qu'aucun autre lion n'osera venir le manger, il y en aura bien un, au tour suivant, qui fera la meme erreur. Finalement, il reste n lions, dont un qui aura fait un bon repas suivi d'une sieste, et n-1 qui auront la migraine.

[invite6de5f0ac]

Les lions sont tres intelligents, on pourrait aussi imaginer qu'un lion s'avance et mange le morceau de viande, puis s'endort. Les autre lions se rendent compte que le repas fini, ils sont vulnérables et peuvent donc etre mangés. Chaque lion se dit que si il mange le lion endormi et s'endort à son tour, pensant qu'aucun autre lion n'osera venir le manger, il y en aura bien un, au tour suivant, qui fera la meme erreur. Finalement, il reste n lions, dont un qui aura fait un bon repas suivi d'une sieste, et n-1 qui auront la migraine.

...et le premier lion peut très bien décider d'espérer que les autres sont plus cons que lui, et donc ne pas toucher à la viande, en espérant qu'à la fin ils ne seront plus que deux, et que le premier qui craque sera la victime...

Salut,

-- françois

[invitef4181796]

...et le premier lion peut très bien décider d'espérer que les autres sont plus cons que lui, et donc ne pas toucher à la viande, en espérant qu'à la fin ils ne seront plus que deux, et que le premier qui craque sera la victime...

Salut,

-- françois

Oui, bien sur, je partais de l'hypothese qu'au debut, aucun lion ne savait que manger le plongerait dans le sommeil, et que tous les lions raisonnent exactement de la meme façon (ce qui est un peu tiré par les cheveux, je suis d'accord)

[invite788778a8]

Bonjour,

Je reviens sur mes pirates, c'est vrai qu'il faut 4 jours, mais comment font-ils?????

[invite35452583]

C'est une arène avec n lions affamés. Ces lions sont très intelligents, et ont deux priorités dans la vie :
1-ne pas se faire bouffer par les autres lions
2-bouffer
Si un lion mange un morceau de viande, il s'endort, et devient un morceau de viande potentiel pour un autre lion (un seul : ces lions ne partagent pas de repas). Par contre, en apparence ces lions sont très civilisés, et ne vont pas chercher à attaquer un lion éveillé, ou à se battre pour un morceau de viande.
Alors que les lions déambulent tranquillement, le dresseur balance un morceau de viande dans l'arène. Que se passe-t-il, en fonction de n ?

En supposant qu'aucun lion ne s'endorme.
Aucun lion n'est mangé.
Le morceau de viande est mangé si et seulement si n est impair.

[invite6de5f0ac]

En supposant qu'aucun lion ne s'endorme.
Aucun lion n'est mangé.
Le morceau de viande est mangé si et seulement si n est impair.

Bonsoir,

Je suppose que ça se démontre en une demi-ligne par un théorème de point fixe?

-- françois
P.S. - Réflexion faite, ta solution me paraît la plus plausible, si et seulement si les lions sont aussi intelligents que le dit l'énoncé...

[yat]

En supposant qu'aucun lion ne s'endorme.
Aucun lion n'est mangé.
Le morceau de viande est mangé si et seulement si n est impair.

Bon, y a une grosse ellipse dans la démo, mais c'est bien le résultat. En effet, de manière évidente s'il n'y a pas de lion le morceau de viande n'est pas mangé, martini_bird a résolu le cas pour n=1 (le morceau de viande est mangé), donc si n=2 un lion qui déciderait de manger le morceau de viande se transformerait en morceau de viande et placerait l'autre lion dans la situation n=1, donc se ferait manger. Les lions étant tous deux intelligents, aucun ne touche à ce morceau de viande. Du coup, pour n=3, un lion qui mangerait le morceau de viande serait en sécurité puisqu'il placerait les deux autres lions dans la situation n=2.
Récursivement, on aboutit donc facilement (et une fois qu'on a pigé le truc ) à la conclusion que le morceau de viande est mangé si et seulement si n est impair.

[invite006c5686]

9 jours. Le mutin concerné sait ou il est; et inutile d'envoyer le dernier pigeon!!!!