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.

[matthias]

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 ?

[martini_bird]

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 ?

[matthias]

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

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

[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?????

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

[matthias]

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

Ma solution du message #4 ne te convient pas ?

[yat]

Argh... j'avais cru envoyer un post énorme ce matin, mais apparemment j'ai fait une fausse manip.

Du coup ça va être plus résumé...

Le truc est que, à part en partant du principe que tous les mutins du monde prévoient précisément ce genre de situations et ont donc une stratégie toute faite, on ne peut pas concevoir une stratégie dans laquelle les mutins ou les iles sont numérotées, ni dans laquelle un quelconque choix arbitraire doit être fait à un moment donné.

En gros, tant qu'un mutin n'a pas reçu de pigeon, toutes les iles auxquelles il n'a encore pas envoyé de pigeon sont les mêmes, et choisir sa prochaine cible est un choix totalement arbitraire, donc aléatoire au sein du groupe. Du coup on peut imaginer une situation ou, au bout du quatrième jour, et même si tous les mutins ont fait au mieux avec toutes les informations dont ils disposent, il peut rester trois mutins qui ne savent rien. Mais faut vraiment pas avoir de bol. Je pars d'une situation ou, pour simplifier, le premier jour 10 mutins envoient leur pigeon au 11eme. La suite est un enchainement de coups de poisse du même ordre, mais c'est possible.

La seule manière d'échapper à cette improbable fatalité, c'est que dans leurs messages, les mutins envoient des indications sur leur comportement futur. Mais là, pour moi ça devient un peu compliqué.

[matthias]

Je ne comprends pas ton raisonnement yat. Ici, il me semble que les mutins connaissent les 11 îles et leurs noms. Donc je ne vois pas ce qui les empêcherait d'adopter une stratégie utilisant un classement alphabétique des îles.

Quoique en relisant l'énoncé, le mutin connaît le nom de l'île sur laquelle il est, pas nécessairement le nom des autres. Mais bon, si on considère qu'un mutin sait où il envoie son pigeon (nom de l'île, position géographique, etc), on a alors une stratégie. Si ce qu'il sait, c'est à qui il envoie son pigeon, alors c'est pareil, il connaît le nom des autres mutins ...

[yat]

Je ne comprends pas ton raisonnement yat. Ici, il me semble que les mutins connaissent les 11 îles et leurs noms. Donc je ne vois pas ce qui les empêcherait d'adopter une stratégie utilisant un classement alphabétique des îles.

Le simple fait que choisir le classement alphabétique est un choix arbitraire. Si par exemple ils ont une carte sous les yeux, il sera certainement tout aussi évident de les classer par latitude ou par longitude. Et quand bien même, même si un choix de classement parait plus évident qu'un autre, ça reste nécessairement subjectif.

[matthias]

Le simple fait que choisir le classement alphabétique est un choix arbitraire. Si par exemple ils ont une carte sous les yeux, il sera certainement tout aussi évident de les classer par latitude ou par longitude. Et quand bien même, même si un choix de classement parait plus évident qu'un autre, ça reste nécessairement subjectif.

Oui et alors ? Ils peuvent se mettre d'accord avant d'être exilés sur leur île (la mutinerie étant une activité à haut risque, on ne s'étonnera pas qu'ils soient prévoyants).

[yat]

Oui et alors ? Ils peuvent se mettre d'accord avant d'être exilés sur leur île (la mutinerie étant une activité à haut risque, on ne s'étonnera pas qu'ils soient prévoyants).

Ce qui revient à ta remarque d'hier. Je trouve quand même que la situation est assez particulière et j'ai un peu de mal à croire que les mutins aient pu prévoir ce genre de situation... et même si par bonheur ils avaient pensé à se mettre d'accord sur l'ordre de ces iles, il faut aussi qu'ils aient pu se mettre d'accord sur le n+2^i-1, qui n'est pas la seule solution qui marche.

Enfin, bon quoi qu'il en soit, je ne trouve pas cette solution satisfaisante.

[matthias]

On est bien d'accord, ça ne marche pas s'ils ne se sont pas concertés avant.
Mais je ne vois pas bien ce que tu veux faire sans cette hypothèse, à part chercher le nombre max de jours peut-être.

[yat]

Mais je ne vois pas bien ce que tu veux faire sans cette hypothèse, à part chercher le nombre max de jours peut-être.

On connait déjà le nombre minimum, et j'ai eu vachement de mal à trouver une situation ou ça ne passe pas en 4 jours, avec un minimum de bon sens de la part des mutins. Je pense qu'il est possible de trouver une technique qui permet d'éviter que ça se produise, pour peu que les mutins envoient d'autres informations que les positions connues, c'est à dire en l'occurence des informations sur leur numérotation, la stratégie qu'ils adoptent et ce qu'ils vont faire pour la suite. Et il faut que toutes les initiatives des mutins puissent être indépendantes...

Mais pour moi ça devient un peu trop compliqué. Je pense que je vais confier ma langue à Mousse, mon placide félin tout roux, et attendre patiemment que la solution apparaisse d'elle-même...

[matthias]

On connait déjà le nombre minimum, et j'ai eu vachement de mal à trouver une situation ou ça ne passe pas en 4 jours, avec un minimum de bon sens de la part des mutins.

Oui mais c'est ça le problème. On peut évaluer différentes stratégies, mais si on prend la même stratégie pour tout le monde tu vas encore me dire qu'ils se sont concertés
S'ils sont complètements idiots, ils envoient tous les jours leur position (et uniquement la leur) à la même personne et on ne s'en sort pas.
S'ils ne sont pas complètement stupides, ils envoient chaque jour toutes les informations dont ils disposent à quelq'un (avec répétition possible). Là encore, ça peut ne jamais finir, s'ils envoient les infos toujours à la même personne.
S'ils envoient chaque jour au moins leur position à une personne différente, là on a enfin un majorant.

Mais bon, il faut bien faire des choix de stratégie ...

[yat]

Oui mais c'est ça le problème. On peut évaluer différentes stratégies, mais si on prend la même stratégie pour tout le monde tu vas encore me dire qu'ils se sont concertés

Pas forcément... et il y a un monde entre avoir une stratégie commune et agir de manière totalement stupide comme ce que tu décris plus bas. Un peu comme dans le problème des lions ou surtout l'autre problème des pirates (celui avec les sept pirates qui se partagent dix pièces d'or). Le résultat est surprenant, mais pourtant chaque intervenant a simplement fait le choix qui lui était le plus avantageux à chaque fois qu'il a eu une décision à prendre. Je pense qu'il pourrait très bien y avoir, dans l'énigme des mutins, une ou plusieurs manière de raisonner qui permettent de garantir une solution en 4 jours même si chaque mutin en choisit une différente, en se basant sur le seul postulat que chaque mutin choisit une stratégie valable...

...c'est peut-être pas super clair, mais ce que je veux dire, c'est que si chaque stratégie dépend des stratégies des autres, cette dépendance n'est peut-être pas suffisamment contraignante pour qu'il n'existe pas de stratégie qui soit objectivement gagnante pour le groupe, sans concertation.

Mais comme je n'ai pas la solution, je ne devrais pas m'avancer trop. Bon, Titi, on cale. C'est quoi la solution ?

[matthias]

Je pense qu'il pourrait très bien y avoir, dans l'énigme des mutins, une ou plusieurs manière de raisonner qui permettent de garantir une solution en 4 jours même si chaque mutin en choisit une différente, en se basant sur le seul postulat que chaque mutin choisit une stratégie valable...

Je ne pense pas.

1er jour :
pas de chance, les mutins de 1 à 10 envoient leurs infos à 11. 11 l'envoie à 10.

2ème jour :
Les mutins 1 à 9, n'ont reçu aucune info, pas de quoi étayer une quelconque stratégie, pas de chance ils envoient leurs infos à 10 (ils ne sont pas stupides, ils ne les renvoient pas à 11).
Les mutins 10 et 11 les envoient à 9 (1 à 9 toujours indiscernables pour eux).

3ème jour :
même raisonnement, même malchance.
1 à 8 envoient à 9
9 à 11 envoient à 8

4ème jour :
toujours pareil.
1 à 7 envoient à 8
8 à 11 envoient à 7

résultat des courses :1 à 6 ne connaissent rien, 7 à 11 connaissent tout.
Qu'est-ce qui a cloché dans leur stratégie ?

Ou alors il faut supposer qu'ils s'envoient aussi des infos sur les coups qu'ils comptent jouer.

[yat]

Ca ressemble beaucoup à la situation extrème que que j'ai établi tout à l'heure en message 18 (qui est hélas un court résumé de ce que j'avais écrit avant et perdu suite à une fausse manip).

Rien n'empèche le mutin 11, dans sa lettre au mutin 9, de lui préciser à qui il a l'intention de l'envoyer le lendemain. Et ainsi de suite. Donc déjà, avec un minimum de bon sens de la part des mutins (et en partie de la part de ceux qui possèdent le plus d'informations), ce cas de figure extrème aboutit à une situation finale ou trois mutins seulement ne sont pas encore au courant après quatre jours, mais le seront le lendemain. Je pense qu'on peut aller plus loin, puisque là je ne considère que le comportement des mutins qui connaissent toutes les positions. Si les autres notent un peu ce qu'ils ont prévu de faire, ça permet d'éviter les coïncidences fâcheuses. Mais pour décrire les différentes stratégies, je pense qu'on est obligés d'énumérer tous les cas de figure, ce qui devrait être extrêmement fastidieux. Il y a peut-être une solution miraculeusement simple, que Titi ne va plus tarder à nous exposer.

[matthias]

Rien n'empèche le mutin 11, dans sa lettre au mutin 9, de lui préciser à qui il a l'intention de l'envoyer le lendemain. Et ainsi de suite.

Oui je suis d'accord, mais on ne peut pas dire que ce soit simple.

Donc déjà, avec un minimum de bon sens de la part des mutins (et en partie de la part de ceux qui possèdent le plus d'informations), ce cas de figure extrème aboutit à une situation finale ou trois mutins seulement ne sont pas encore au courant après quatre jours, mais le seront le lendemain.

Ca commence à être un peu plus qu'un minimum de bon sens.

Il y a peut-être une solution miraculeusement simple, que Titi ne va plus tarder à nous exposer.

Je pense que l'on a déjà répondu au problème initial, et qu'on est parti sur un problème plus dur. Enfin on sait jamais.

[yat]

Oui je suis d'accord, mais on ne peut pas dire que ce soit simple.
Ca commence à être un peu plus qu'un minimum de bon sens.

Bah... question de point de vue. Personnellement, dans la mesure ou ce brave mutin connait la position de tout le monde et sait que les autres ne savent quasiment rien, je trouve que s'arranger pour que cette information circule de manière efficace relève du bon sens. Il doit bien se douter que s'il se contente d'envoyer la liste chaque jour à un autre mutin sans rien préciser d'autre, les infos vont se croiser. A sa place je ferais donc un gentil petit arbre binaire avec les noms des iles pour planifier les redistributions par la suite.

Par contre, quand il s'agit de gérer les trois mutins restants, j'abonde dans ton sens ça devient très compliqué.

Je pense que l'on a déjà répondu au problème initial, et qu'on est parti sur un problème plus dur

Vu le dernier message de TITI78, soit il faut aller plus loin, soit il n'a pas vu ta réponse