Un Peu De Logique

[invite788778a8]

Bonjour,



Voici la solution :

Le mode d’envoi des messages par chaque mutin est simple : les îles sont numérotées de 1 à 11 et ces numéros sont placés sur le sommets d’une polygone régulier à 11 côtés dans le sens des aiguilles d’une montre. Le mutin détenu dans l’île 1 envoie le 1 er jour un message au mutin de l’île 2 puis le 2 ème jour au mutin de l’île 3 puis le 3 ème jour au mutin de l’île 5 et enfin le 4 ème jour au mutin de l’île 9, c’est à dire qu’il envoie des messages aux détenus des îles numérotées 1+1, 1+2, 1+4 et 1+8. De manière générale le mutin de l’île i envoie ses messages dans les îles numérotées i+1, i+2, i+4 et i+8 modulo 11. Dans le message du 1 er jour, chaque mutin déclare son lieu de détention mais à partir du 2 ème jour, le message peut être étoffé par les lieux de détention dont chaque mutin a été informé grâce aux pigeons voyageurs.

A+
-----

[yat]

Voici la solution

C'est donc la solution de matthias...
Merci de nous prévenir, on allait commencer à vraiment se prendre la tête.

[matthias]

Titi, ça fait plaisir de voir que tu lis attentivement les réponses que l'on apporte à ton énigme

[invite006c5686]

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

[invite788778a8]

Bonjour,

Excuse MATTHIAS, mais je n'avais lu ton message 17 pourtant je vérifie a chaque fois avec aller aux derniers messages non lus.

Dans mon message, quand je demandais : comment font ils? j'aurait du préciser comment faisaient ils pour utiliser tous le même mode opératoire.

Hier, je n'ai pas pu articipé activement au débat, et j'ai voulu vous envoyer la réponse (un peu trop rapidement), car j'ai oublié une précision.

Dans l'enoncé il n'a jamais été précisé que les pigeons voyageaient au même moment, mais faisaient que 1 vol par jour.
Donc le 1ER mutin notais sur son message, le nom de son ile et donnait comme instruction le mode opératoire à utiliser et demandais au suivant de faire procèder de même avec les autres mutins.

Maintenant, je ferais plus attention à mes messages et essayerai de na pas envoyer d'enigme si je ne peu pas réagir rapidement.

[yat]

Dans l'enoncé il n'a jamais été précisé que les pigeons voyageaient au même moment, mais faisaient que 1 vol par jour.

Dans ce cas, ça change tout : 2 jours. Le premier jour un mutin envoie un pigeon à un autre mutin avec sa position, en lui disant d'ajouter sa position à la liste et de transférer un peu plus tard dans la journée à une autre ile qui n'est pas encore sur la liste. Le soir du premier jour le dernier mutin à avoir reçu cette chaine connait la position de tout le monde. Il n'a pas besoin d'utiliser son pigeon ce jour là. Le lendemain il renvoie la liste au premier en disant qu'il faut faire circuler dans l'ordre de la liste. A la fin du deuxième jour tout le monde sait ou est tout lemonde.

[matthias]

Il y a un problème dans ta solution yat. Ca marche s'il n'y a qu'un pigeon, ou si les mutins se sont mis d'accord sur la marche à suivre et pour désigner celui qui devait envoyer son pigeon en premier. Sinon un mutin peut recevoir un pigeon, mais pas de chance il avait déjà envoyé le sien ...

[yat]

Il y a un problème dans ta solution yat. Ca marche s'il n'y a qu'un pigeon, ou si les mutins se sont mis d'accord sur la marche à suivre et pour désigner celui qui devait envoyer son pigeon en premier. Sinon un mutin peut recevoir un pigeon, mais pas de chance il avait déjà envoyé le sien ...

C'est aussi le cas dans la solution de Titi, donc pas de remords.

[invite788778a8]

OK

Plantage de TITI

Voici un casse tête trouvé sur un site:

Un paquet de 36 cartes est composé de 9 cartes de chaque couleur (pique, coeur, carreau et trèfle) et le dos de chaque carte a pour unique motif une grande flèche. Le paquet est mélangé par une personne dans le public puis est récupéré par l’assistant du magicien qui a le temps de prendre connaissance du contenu des cartes sans en modifier l’ordre. Le magicien demande alors à son assistant de lui montrer successivement le dos de chacune des cartes en partant de celle qui au-dessus du paquet. A chaque fois, le magicien prédit la couleur de la carte. L’assistant retourne la carte, annonce sa couleur et la met de côté. Le magicien marque un point quand sa prédiction est correcte. Le processus se poursuit jusqu’à épuisement du talon.
En supposant que l’assistant du magicien est assez habile pour orienter discrètement la flèche visible sur le dos des cartes dans un sens convenu avec le magicien, quel est le score maximum que le magicien est certain d’atteindre ?

[kNz]

S'il est obligé de montrer les cartes dans le sens conventionnel, c'est à dire la longueur de la carte à la verticale, alors la flèche ne peut prendre que deux sens, il pourra donc deviner toutes les cartes de deux couleurs à coup sûr donc 18 cartes.

Mais à mon avis il peut faire plus

Et puis de toute façon, à ne dire que pique et carreau, les spectateurs remarqueront vite fait le truc

[yat]

Alors sans faire tout de suite d'estimation du score, je pense qu'il faut déjà parler de la stratégie.
A chaque carte, l'assistant peut donner une information binaire au magicien. C'est ballot, puisqu'il en faudrait deux pour gagner à tous les coups.
De manière immédiate le magicien peut atteindre à coup sur un score de 50%, si l'assistant lui indique que la carte est rouge ou noire, et que le magicien dit toujours coeur dans un cas, pique dans l'autre. Mais il y a nécessairement mieux, et c'est là qu'il va être plus difficile de déterminer le score.

EDIT : Jusque là, grillé par kNz

Connaissant le nombre de cartes restantes, les deux complices peuvent établir une stratégie qui consiste à séparer les quatre couleurs en deux groupes, de sorte qu'en sachant dans quel groupe est la carte, le magicien aura la plus grande propbabilité de gagner en choisissant la carte la plus probable du groupe.

Je dirais intuitivement que, pour que l'information donnée par l'assistant ait le plus de poids possible, il faut que les deux groupes soient équilibrés. Mais je ne suis pas certain que ça soit la meilleure solution dans tous les cas.

En regardant de plus près, je pense que l'on peut calculer brutalement la répartition optimale en termes de probabilités à chaque coup... mais je n'irai pas jusqu'à essayer d'en tirer le score du magicien.

Si A et B sont les deux couleurs du premier groupe, et C et D celles du deuxième, avec P(A)>P(B) et P(C)>P(D), G l'événement "le magicien a choisi la bonne couleur", on a P(G)=P(A)+P(C).

Comme quoi, apparemment, le fait que les groupes soient équilibrés importe peu, le tout est de mettre les deux couleurs les plus probables dans des groupes différents. Il faudra bien évidemment qu'ils se mettent d'accord à l'avance pour déterminer si on met la troisième couleur dans le groupe de la première ou dans celui de la deuxième, et un ordre de priorité au sein des oucleurs pour les cas d'égalité.

Voilà, globalement je pense que c'est la stratégie optimale. Et comme il y a nécessairement des tirages ou les probabilités des différentes couleurs sont différentes (au minimum trois fois sur 4, si on n'a pas de chance), et que dans le pire des cas on reste à 1/2, je sais que le score minimum espéré avec cette stratégie est strictement supérieur à 50%. Qui veut le calculer ?

[kNz]

la réponse yat.

Mais l'énoncé nous demande le nombre que le magicien est sûr d'atteindre, après cela dépend de pas mal de facteurs : chance, disposition des cartes dans le talon, parce que si les 2 couleurs sur lesquelles ils se sont mis d'accords passent dans les 18 premières cartes, puis qu'ensuite 9 autres cartes passent toutes de la même couleur, il est au moins sûr (s'il est un peu malin) de faire 27 points.

[kNz]

En fait j'ai rien dit,

[yat]

Mais l'énoncé nous demande le nombre que le magicien est sûr d'atteindre

Je sais bien, mais...

après cela dépend de pas mal de facteurs : chance, disposition des cartes dans le talon

Voilà le problème... Je ne vois pas d'autre méthode que de construire un arbre immense avec les différentes combinaisons de probabilités possibles... ce que je n'ai pas l'intention de faire. La seule chose dont je suis donc sur quant à la réponse, c'est qu'elle est strictement supérieure à 1/2

parce que si les 2 couleurs sur lesquelles ils se sont mis d'accords passent dans les 18 premières cartes, puis qu'ensuite 9 autres cartes passent toutes de la même couleur, il est au moins sûr (s'il est un peu malin) de faire 27 points.

Eh oui, mais ce qu'il faudrait trouver, c'est la situation qui est la moins avantageuse et qui aboutira au score minimum, la réponse à la question. Le problème, c'est qu'il faut pouvoir prouver que c'est bien le pire des cas.

[kNz]

La seule chose dont je suis donc sur quant à la réponse, c'est qu'elle est strictement supérieure à 1/2Eh oui, mais ce qu'il faudrait trouver, c'est la situation qui est la moins avantageuse et qui aboutira au score minimum, la réponse à la question. Le problème, c'est qu'il faut pouvoir prouver que c'est bien le pire des cas.

Oui mais ce qui m'étonne, c'est que l'énigme me semble un peu trop facile, on est d'accord sur le fait que c'est strictement supérieur à 50% si on utilise ta stratégie, mais quelle est alors la réponse

[yat]

Eh merde...

Je crois que j'ai tout faux. Je viens de faire des tests en simplifiant un maximum pour pouvoir dérouler toutes les combinaisons, et j'ai l'impression qu'on peut quand même, dans le pire des cas, se retrouver avec un score 1/2. Je ne fais qu'optimiser l'espérance mathématique du score.

Voilà une solution qui fait tout foirer : Les deux couleurs qui ne sont pas prioritaire selon les convention des complices, sortent toutes aux 18 premiers tirages. La première fois que chacune tombe, la probabilité est la même que la couleur la plus probable mais plus prioritaire, et pour la suite, comme elles sont moins nombreuses, c'est toujours l'autre couleur de chaque groupe qui sera sélectionnée par le magicien. Il se plante donc sur les 18 premières cartes. Evidemment, il aura tout bon pour les 18 suivantes, mais ça nous fait quand même un score minimum de 50%

Conclusion : ça fait encore un pour moi... la réponse est bien 50%, ta technique était tout aussi efficace et bien plus simple pour aboutir au même résultat.

[kNz]

Et ba en voilà un superbe contre exemple

Donc un beau pour tous les deux..

Finalement, va pour 50% ..

[matthias]

Et pourtant il existe des stratégies qui permettent d'être certain de faire plus de 18 points
Comme je connais déjà le problème, je ne vais pas donner la solution, mais essayez d'imaginer une méthode pour que l'assistant désigne de manière certaine la couleur de certaines cartes (pas toutes évidemment, ce n'est pas possible).

[invite788778a8]

Bonjour,

Matthias a raison.

Pour vous aider, voici le début du principe à utiliser


le sens S des cartes est repéré par les chiffres 0 et 1

On établit une hiérarchie dans la couleur des cartes et par convention on dit que P(trèfle) < P(carreau) < P(cœur) < P(pique)

A vous de jouer

[kNz]

On peut toujours trouver des méthodes où l'assistant prendrait la carte par le coin droit avec la flèche dans un sens ou dans l'autre et avec le coin gauche dans un sens ou dans l'autre, auquel cas, on peut être sûr de toutes les déterminer, mais ça ne doit pas être ça qui est recherché

[yat]

essayez d'imaginer une méthode pour que l'assistant désigne de manière certaine la couleur de certaines cartes (pas toutes évidemment, ce n'est pas possible).

Si je comprends bien, ça veut dire que dans certains cas, la flèche vers le haut va désigner une seule couleur, et la flèche vers le bas signifiera que le magicien doit se débrouiller pour choisir parmi les trois autres...

...ou alors, l'assistant sacrifie une carte sur deux et utilise deux signaux pour désigner l'autre...

...mais là encore, sans indications pour l'autre, le magicien peut se planter à chaque coup et n'avoir toujours qu'un score minimum de 50%

Quant aux indices de titi, ça ne m'avance pas beaucoup...

[matthias]

Non évidemment
Le magicien n'a comme information que le sens de la flèche, une bête information binaire.

[matthias]

...ou alors, l'assistant sacrifie une carte sur deux et utilise deux signaux pour désigner l'autre...

...mais là encore, sans indications pour l'autre, le magicien peut se planter à chaque coup et n'avoir toujours qu'un score minimum de 50%

Oui
Mais on peut changer de tactique un peu avant la fin. Par exemple, l'indication sur la dernière carte ne sert à rien ...

[kNz]

Empêtré, comme yat

[yat]

J'en ai une, et je suis quasiment sur qu'elle marche, mais ne me demandez pas de l'implémenter

On a deux phases : n tirages, ou le magicien dit tout au pif, et l'assistant ne fait qu'envoyer des signaux binaires. Une fois que ces n tirages sont passés, le magicien regarde le nombre de cartes de chaque couleur qui restent dans le paquet, et énumère (dans un ordre établi à l'avance, et l'assistant aura fait cette énumération avant le début des tirages puisqu'il a pu consulter le paquet avant) les différentes combinaisons de couleurs possibles pour les 36-n cartes restantes. On choisit n tel que le nombre de combinaisons possibles avec 36-n cartes soit inférieur à 2ⁿ. Les informations envoyées par l'assistant pendant la première phase donnent le numéro de la combinaison restante, et le magicien est sur de ne plus se tromper.

Y a plus qu'à espérer que n est inférieur à 18...

[yat]

Oui
Mais on peut changer de tactique un peu avant la fin. Par exemple, l'indication sur la dernière carte ne sert à rien ...

Oui, ça je m'en étais bien rendu compte en regardant ce que donnait ma stratégie... le problème, c'est que la carte qui reste (avec ma méthode, donc la mauvaise), si elle reste, c'est que les cartes des autres couleurs sont tombées plus souvent, or à chaque fois qu'un écart se crée, ça veut dire que la couleur la moins probable est tombée et que ça a fait pencher la balance en dessous du 50%... Et le gros problème, c'est que si cette information ne sert à rien, on est obligé de la gaspiller quand même, du coup c'est un bit de perdu dans le flux d'informations...

Par contre, pour l'avant derniere (ou du moins toutes celles qui sont tirées quand il ne reste que deux couleurs), l'information est beaucoup plus utile que pour les autres.

[invite788778a8]

Pour vous aider voici comment le magicien peut prédire au moins 19 cartes :

Avec les dos de deux cartes consécutives, on a quatre configurations possibles selon les sens choisis par l’assistant du magicien avec = 00, 01, 10 et 11 ce qui permet à chaque tirage de rang pair d’annoncer la bonne couleur de la 2 ème carte. Par exemple, il suffit de convenir 00 = Trèfle, 01 = Carreau, 10 = Cœur, 11 = Pique.

Lorsqu’il reste deux cartes dans le paquet, il y a au maximum deux couleurs. Si les couleurs sont identiques, le magicien qui a mémorisé les cartes déjà tirées n’a aucune difficulté à annoncer la couleur des deux dernières cartes. Si les couleurs sont différentes, le sens de la 35 ème carte sert à désigner la couleur de la 35 ème carte de poids P le plus faible. Si =0, la couleur de la 35 ème carte sera de poids le plus faible, si =1, ce sera l’inverse.

Le magicien est donc certain de deviner correctement toutes les cartes de rang 2, 4, 6, ….,34, 35 et 36 soit au total 34/2 + 2 = 19 cartes.

Mais il peut encore mieux faire

[kNz]

Si on creuse l'idée de yat de sacrifier une carte sur deux, on a 4 combinaisons possibles : (ici H et B désignent respectivement haut et bas) HH, HB, BH, BB. Lorsque deux couleurs sont épuisées, on peut alors définir un signe H pour une et signe B pour l'autre, en fonction par exemple de l'ordre alphabétique des couleurs restantes.

Mais il doit y avoir encore une solution qui rend maximal le nombre de points

EDIT : Croisement avec TITI

[matthias]

Pas bête, à creuser.
Mais pour commencer il y a une méthode simple qui permet d'améliorer un peu celle qui consiste à désigner de manière certaine une carte sur deux. Il suffit de l'appliquer jusqu'à ce qu'il ne reste que 2 cartes, et regarder ce qui se passe ensuite.

[yat]

Pas bête, à creuser.
Mais pour commencer il y a une méthode simple qui permet d'améliorer un peu celle qui consiste à désigner de manière certaine une carte sur deux. Il suffit de l'appliquer jusqu'à ce qu'il ne reste que 2 cartes, et regarder ce qui se passe ensuite.

C'est pas ce que vient de proposer kNz ?

EDIT : ah, j'avais pas vu que les deux messages avaient une seule minute d'intervalle... ça doit être un croisement.