Forum des énigmes mathématiques :
DEFI 173 : Pigeon vole !

Bonjour à tous,

Comme vous l'avez sans doute remarqué, j'ai embauché un stagiaire pour l'été Cela ne veut pas dire que je vais vous laisser tranquille pour autant.

Dans le film Valiant (Vaillant, pigeon de combat en VF) des pigeons sont utilisés pour convoyer des messages et je vous propose de vous pencher quelques instants sur les problemes liés à ce type de transport.



On souhaite transmettre 1 message secret à l'aide de plusieurs pigeons. Afin de ne pas prendre trop de risques au cas où un pigeon tombe aux mains de l'ennemi, on décide de fragmenter le message en plusieurs parties dont on peut faire plusieurs copies. Ces parties sont choisies astucieusement de telle façon que l'absence de seulement l'une d'entre elles rende le message complètement incompréhensible.

En règle générale, on a pu observer que l'ennemi ne pouvait pas intercepter plus de deux pigeons lors d'un meme lancer. D'où la contrainte fondamentale suivante :

A aucun moment, deux pigeons quelconques (ou moins) ne doivent transporter des éléments du message dont la réunion permettrait à l'ennemi de reconstituer le message entier.  

Cependant, malgré les risques encourus, le but essentiel est de transmettre le message et il faut donc que le destinataire puisse le reconstituer à partir des éléments en possession des pigeons arrivant à bon port. L'expéditeur doit donc faire en sorte que le message puisse etre reconstituté quels que soient les pigeons “survivants”. C'est la deuxième contrainte.

Passons maintenant aux questions.

Question 1: (facile)

On fragmente le message en 5 parties A, B, C, D et E et on dispose de 8 pigeons.

Indiquer une répartition des parties du message données à chaque pigeon.


Question 2:

Est-il possible de faire mieux ? C'est-a-dire d'utiliser moins de 8 pigeons toujours avec 5 fragments.

Si vous pensez que oui, indiquez la nouvelle repartition. Sinon expliquez pourquoi.

Question 3:

On dispose maintenant de seulement 5 pigeons et le découpage en 5 parties n'est bien sûr plus suffisant.

Mais en combien de parties au minimum faudrait-il fragmenter le message pour en assurer la transmission en toute sécurité ? Indiquer alors une répartition possible.

Bonne réflexion et n'oubliez pas "A coeur vaillant, rien d'impossible." !

minkus

bonjour minkus
question 1
Pigeon 1: A B
Pigeon 2: C D
Pigeon 3: D E
Pigeon 4: E A
Pigeon 5: A B
Pigeon 6: B C
Pigeon 7: C D
Pigeon 8: D E

Question 2:
On peut faire mieux
ABC
DA
DB
DC
EA
EB
EC

Question 3:
Jedirai que c'est impossible (ca veux dire que j'en ai pas trouvé, mais comme la question n'indique pas le fait que ce soit impossible, j'ai un gros doute)

Question 1 :
C'est j'ai bien compris, il faut retrouver une même partie chez 3 pigeons (pour permettre d'acheminer cette partie si les deux autres sont capturées)et veiller à ce que la réunion de deux pigeons ne constitue pas le message.
Une répartition possible : (AB)(AE)(AD)(BC)(CD)(BD)(CE)(DE).
Question 2 :
Même contrainte : Un pigeon transportera 3 parties et il faudra veiller à ce que un autre ne transporte pas les deux parties complémentaires.
Une répartition possible avec 7 pigeons : (ABE)(AC)(AD)(BC)(DE)(BD)(CE).
Question 3 :
Supposons n parties avec 5 pigeons.
- 1 pigeon avec (n-1) parties n'est pas possible car un autre pigeon transportera la partie complémentaire, donc danger d'interception.
- 1 pigeon avec (n-2) parties nécessitera non seulement que les deux autres parties ne soient pas transportées par le même pigeon, mais aussi qu'elles soient réparties chacunes sur 3 pigeons, donc 6 pigeaons nécessaires. Ce qui donne 7 pigeons au minimum.
Il n'est donc pas possible de transmettre un message en toute sécurité avec 5 pigeons, quelque soit la partition.

bonsoir
question 1
ac ad ae bc bd be ce d
chaque fragment est transporté trois fois; deux pigeons transportent quatre fragments au plus

question 2
on peut faire envoyer les fragments par sept pigeons
abc ad ae bd be cd ce
un pigeon transporte trois fragments; les deux autres fragments doivent être transportés trois fois chacun, mais jamais ensemble (ce qui empêche une solution avec six pigeons)

question 3
il faut dix pigeons
soit a, b, c, d, e, f, g, h, i, j les fragments
pigeon 1 : abcdef
pigeon 2 : abcghi
pigeon 3 : adeghj
pigeon 4 : bdfgij
pigeon 5 : cefhij
soit m le nombre de messages; si on exempte un pigeon de 3 fragments au plus, ceux-ci ne peuvent être transportés trois fois par les autres pigeons sans se retrouver ensemble chez au moins un pigeon; le maximum de fragments est donc 5m-20; le minimum est 3m
5m-20 >= 3m; m >=10
pour chaque fragment, on désignera deux pigeons qui ne le transporteront pas, c'est-à-dire une paire de pigeons par fragment; si deux pigeons sont capturés, leur paire correspondra à ce fragment, qui manquera donc à l'ennemi
cette question a été posée il y a quelques mois dans Expresso, mais je crois qu'on donnait le nombre de messages

Bonjour,

très belle énigme ^{(qui ne demande aucune connaissance particulière)}

Premier constat, si l'on veut que les messages arrivent à bon port, sachant qu'au plus deux sont interceptés, il faut envoyer au minimum 3 exemplaires de chaque fraction de message. A ce moment, inutile de préoccuper de la complétude du message, mais juste des interceptions.

Je numérote les pigeons et note alphabétiquement les parties des messages.

Une rapide permutation permet de traiter la question 1 (répartition équitable).
Question 1:
1: AD - 2: BE - 3: CA - 4: DB - 5: EC - 6: AD - 7: BE - 8: C
^{(toutes les parties sont en 3 exemplaires et avec 2 interceptions l'ennemi ne capte qu'au plus 4 parties)}

Question 2:
De même une permutation légèrement modifiée à la fin permet une répartition pour 7 pigeons:
1: AC - 2: BD - 3: CED - 4: DA - 5: EB - 6: AE - 7: BC
^{(le seul danger est l'interception de 3 dont le complémentaire AB est absent)}
Peut-on descendre en dessous ?
Là il faut réfléchir de façon plus systématique. Je cherche donc à annuler toutes les possibilités pour deux interceptions.
Pour 7 pigeons, les "liaisons" possibles sont :
1-2 2-3 3-4 4-5 5-6 6-7  
1-3 2-4 3-5 4-6 5-7
1-4 2-5 3-6 4-7
1-5 2-6 3-7
1-6 2-7
1-7
Je place ensuite les messages pour éliminer ces "liaisons" (voir 1ère figure):
A (pour les pigeons 5,6 et 7) permet d'éliminer 1-2;1-3;1-4;2-3;2-4;3-4
B (pour les pigeons 1,2 et 3) permet d'éliminer 4-5;4-6;4-7;5-6;5-7;6-7
C (pour les pigeons 4,6 et 7) permet d'éliminer 1-5;2-5;3-5
D (pour les pigeons 4,5 et 7) permet d'éliminer 1-6;2-6;3-6
E (pour les pigeons 4,5 et 6) permet d'éliminer 1-7;2-7;3-7
On obtient une répartition optimale en nombre de messages (12 morceaux contre 13 pour la répartition "équitable" en nombre de messages:
1: B - 2: B - 3: B - 4: CDE - 5: ADE - 6: ACE - 7: ACD

Passons maintenant à 6 pigeons...
Les liaisons se limitent à:
1-2 2-3 3-4 4-5 5-6
1-3 2-4 3-5 4-6
1-4 2-5 3-6
1-5 2-6
1-6
Je place de nouveau les messages pour éliminer ces "liaisons" (voir 2ème figure) :
A (pour les pigeons 4,5 et 6) permet d'éliminer 1-2;1-3;2-3
B (pour les pigeons 1,2 et 6) permet d'éliminer 3-4;3-5;4-5
C (pour les pigeons 3,5 et 6) permet d'éliminer 1-4;2-4;(1-2)
D (pour les pigeons 3,4 et 6) permet d'éliminer 1-5;2-5;(1-2)
E (pour les pigeons 3,4 et 5) permet d'éliminer 1-6;2-6;(1-2)
mais reste 3 liaisons 3-6;4-6;5-6 ne pouvant être éliminées !
Pour 6 le problème n'est donc pas possible.

Question 3:
Pour 5 pigeons, on continue le même raisonnement.
Les liaisons sont au nombre de 10:
1-2 2-3 3-4 4-5
1-3 2-4 3-5
1-4 2-5
1-5
Je coupe une à une les liaisons jusqu'à ce que le problème soit possible (voir 3ème figure) :
A (pour les pigeons 3,4 et 5) permet d'éliminer 1-2
B (pour les pigeons 2,4 et 5) permet d'éliminer 1-3
C (pour les pigeons 2,3 et 5) permet d'éliminer 1-4
D (pour les pigeons 2,3 et 4) permet d'éliminer 1-5
E (pour les pigeons 1,4 et 5) permet d'éliminer 2-3
F (pour les pigeons 1,3 et 5) permet d'éliminer 2-4
G (pour les pigeons 1,3 et 4) permet d'éliminer 2-5
H (pour les pigeons 1,2 et 5) permet d'éliminer 3-4
I (pour les pigeons 1,2 et 4) permet d'éliminer 3-5
J (pour les pigeons 1,2 et 3) permet d'éliminer 4-5

Il faudra donc au minimum fragmenter le message en 10 parties ABCDEFGHIJ.
Une répartition possible est:
1: EFGHIJ - 2: BCDHIJ - 3: ACDFGJ - 4: ABDEGI - 5: ABCEFH
<sup>(elle est à la fois équitable et optimale)

(On peut aussi imaginer que les 5 pigeons puissent faire plusieurs voyages, s'ils ne sont pas interceptés au retour...
ce qui donnerait à l'ennemi 4 (2+2) messages et au destinataire 4 messages (3+1) mais alors le problème est impossible)</sup>



Désolé pour ce post un poil long et merci pour cette énigme bien emballée!

PS: Je n'ose imaginer la généralisation...
La communication de x messages par y pigeons sachant que z messages sont interceptés est-elle sécurisée ?

bonjour,

1. Une répartition possible est:

pigeon 1 : AB
pigeon 2 : CD
pigeon 3 : AE
pigeon 4 : BC
pigeon 5 : AD
pigeon 6 : BE
pigeon 7 : AC
pigeon 8 : DE

2. Oui, on peut faire mieux avec 7 pigeons:

pigeon 1 : ABE
pigeon 2 : AC
pigeon 3 : AD
pigeon 4 : BC
pigeon 5 : BD
pigeon 6 : CE
pigeon 7 : DE

3. Je pense qu'il faudra an minimum 10 parties:

pigeon 1 : ABCEFH
pigeon 2 : ABDEGI
pigeon 3 : ACDFGJ
pigeon 4 : BCDHIJ
pigeon 5 : EFGHIJ

_{pour la 3, je me suis basé sur une des JFF que j'avais posté ()}


Merci pour l'énigme.

bonjour

question 1:

il suffit que chaque partie du message existe au moin chez 3 pigeons (de cette façon on est sur que chaque partie arrivera au destinataire)et que chaque pigeons posséde au maximum 2 parties du message(de cette facon si l'ennemi capture 2 pigeons il n'aura que 4 parties du message et il lui manquera forcement au moin une partie).
je propose cette solution:

AB   AB   AB  CD  CD  CE  AE  DE


question 2

puisque vous ne proposer pas le minimum de nbre de pigeons donc j'ai pas trop cherché j'ai juste trouvé un exemple avec 7 pigeons c'est le même principe que precedement sauf que j'ai donné cette fois à un pigeon 3 fragments à la fois et j'ai évité de donner les 2 fragments supplementaire à aucun autre pigeon voici ma proposition:

ABE   AC   AD  BC  BD  CE  DE

question 3

mon algorithme n'a pas résussit à faire mieu que 10 parties, en voici une répartition possible:

(ABCDEF)   (ABCGHI)   (ADEGHJ)    (BDFGIJ)   (CEFHIJ)

ce qui impose à chaque pigeons de voler avec 6 fragments(pauvres pigeons ).

enfin merci pour l'énigme que je trouve trés simpa .

Salut Minkus

Bon alors tout d'abord, je peux te dire que trop de pigeons ... fait mal à la tête

Pff, je me suis lutté sur la dernière question, j'espère qu'il n'y a pas mieux. Alors :

Question 1 :

Là c'était assez simple (pour nous mettre en confiance surement) :

P1 : A,B           P5 : C,D
P2 : A,B           P6 : C,D
P3 : A,E           P7 : A,E
P4 : C,D           P8 : B,E

Question 2 :

Je tente sur 7 pigeons

Comme il y a 5 morceaux. Il nous faut une solution à 15 caractères à placer. En effet, il doit y avoir par exemple au moins 3 pigeons différents portant A, sinon on perdrait l'information sur le A. Plusieurs cas s'offrent donc à nous :

- On ne met que 2 informations sur chaque pigeons :

Dans ce cas il nous faut 8 pigeons (cf une solution à la question 1) pour placer nos 15 caractères. Donc pas intéressant ici

- On tente de placer 3 informations sur un pigeons et 2 sur les autres :

Par exemple, on place A,B,C sur le pigeon 1. Il nous reste à placer 2 fois A,B et C et 3 fois D et E. Donc il reste 12 lettres pour 6 pigeons.

On doit obligatoirement fixer une lettre de la combinaison triple à chaque fois (ici A,B ou C). Sinon, on ferait intervenir du D,E et clac, foutu

Donc une solution se dégage :

P1 : A,B,C        P5 : A,D
P2 : A,E          P6 : B,E
P3 : B,D          P7 : C,D
P4 : C,E

Donc ceci est une solution à 7 pigeons avec 5 morceaux. Je m'arrête donc ici, la question posée étant :

" Est-il possible de faire mieux ? C'est-a-dire d'utiliser moins de 8 pigeons toujours avec 5 fragments. Si vous pensez que oui, indiquez la nouvelle repartition. Sinon expliquez pourquoi "

Donc je réponds OUI je fais mieux, avec la solution juste au dessus.

Je ne prouve donc pas que 7 pigeons est la soltuion maximale. En continuant les cas, on doit pouvoir le prouver, mais ce n'est pas demandé.

Question 3 :

Passons à la cerise sur le gateau ... la question qui fait mal à la tête. Bon alors là j'ai tout testé, je ne pouvais pas faire le raisonnement comme si dessus, trop de cas.

Et après 3 heures de recherche je dirais, une solution est aparru, c'est pas magnifique

Avec nos 5 pigeons, je trouve qu'il faut fragmenter au minimum le message en 10 morceaux que je noterais A,B,C,D,E,F,G,H,I,J

Ma solution :

P1 : A,C,D,F,G,J         P4 : E,F,G,H,I,J
P2 : A,B,C,E,F,H         P5 : A,B,D,E,G,I
P3 : B,C,D,H,I,J

oufff !! Merci pour l'énigme

Romain

Bonjour

citation :
Question 1: On fragmente le message en 5 parties A, B, C, D et E et on dispose de 8 pigeons. Indiquer une répartition des parties du message données à chaque pigeon.

L'ennemi peut intercepter au plus deux pigeons, donc en répartissant trois copies de chaque fragment sur trois pigeons différents, on assure la deuxième contrainte.

D'après la première contrainte la réunion des éléments transportés par au plus deux pigeons ne doit pas contenir les cinq fragments. On peut donc pour assurer cette contrainte répartir au plus deux fragments par pigeon.

Le premier point indique qu'il y aura copies à répartir sur 8 pigeons. Selon le deuxième point on formera des paires donc une copie se retrouvera seule sur un pigeon. Comme on prône l'égalité des pigeons () on ajoutera une copie supplémentaire.

En respectant ces conditions on pourra par exemple avoir la répartition suivante :

citation :
Question 2: Est-il possible de faire mieux ? C'est-a-dire d'utiliser moins de 8 pigeons toujours avec 5 fragments. Si vous pensez que oui, indiquez la nouvelle repartition. Sinon expliquez pourquoi.

Pour avoir toutes les lettres à l'arrivée il faut comme nous l'avons vu, avoir au minimum trois copies de chaque lettre. En effet supposons qu'une lettre ait été copiée deux fois et répartie sur deux pigeons différents (on notera évidemment qu'il est inutile de placer deux copies identiques sur le même pigeon), alors l'ennemi pouvant au plus intercepter deux pigeons, capturerait les deux pigeons qui transportent les deux copies identiques, et ainsi à l'arrivée il y aurait une lettre manquante et donc le message serait incompréhensible. (1)

On peut placer dans ces conditions au maximum trois lettres différentes par pigeon, ce qui permet d'optimiser le nombre de pigeon pour transporter les copies. En effet si il y aurait 4 lettres sur un même pigeon alors la cinquième lettre n'assurerait pas la contrainte fondamentale puisque si le pigeon portant les 4 lettres et celui portant la cinquième se font capturer par l'ennemi alors le message peut-être recomposé. (2)

On va donc essayer de placer sur chaque pigeon un paquet de trois lettres différentes. On remarque que la répartition de trois paquets différents sur un pigeon respectif est maximale. En effet si on place sur le premier pigeon un paquet abc (a, b et c peuvent caractériser au choix un fragment de message A,B,C,D ou E), alors le deuxième paquet ne pourra pas contenir à la fois d et e, donc la copie e sera jointe à deux fragments parmi abc. On aura alors par exemple bce. Ainsi le troisième paquet ne contiendra ni d et e, ni a et d, donc la copie d sera jointe aux fragments b et c, ce paquet sera bcd. Pour les mêmes raisons le quatrième paquet comporterait également b et c, or a, d et e étant déjà placé dans un paquet, on reformerait un paquet identique. Donc pour alléger les 5 autres pigeons () on se limitera à un paquet de deux copies au plus.

En reprenant notre exemple nous avons pour le moment la répartition suivante :



Donc les fragments B et C sont présents trois fois conformément à (1). Il reste donc à placer deux fragments A, E et D. Si on choisit de former des paquets de deux fragments alors :

A ne peut pas être avec D, car si ce paquet est intercepté avec le second le message est codé par l'ennemi. Ni avec E en raison du troisieme paquet. Donc le fragment A sera placé seul sur un pigeon.
De même E ne peut pas être avec D en raison du premier paquet ni avec A d'après le point précédent, donc E est placé seul également.
Il en va de même pour D.

Or puisqu'il faut deux fragments de chaque lettre, il faudrait alors mobiliser pigeons, mais il nous en reste que 5. Donc on en conclut que la répartition de l'exemple ne permet pas de résoudre le problème. Par conséquent on ne placera que deux paquets de trois fragments différents sur deux pigeons respectifs.

On se ramène donc à la répartition suivante :



Pour former des paquets de deux fragments on voit que D ne peut pas être avec E ni avec A, donc soit avec B soit avec C.
Comme B et C sont déjà présents deux fois, et qu'il faut placer trois fois
le fragment D, on formera un paquet DB et un autre DC. D'où :



Bilan : Il faut encore placer deux fragments A et E et un fragment D.

Comme A ne peut être placé avec D en raison du paquet BCE, il vient que pour former un paquet de deux fragments, on joint A avec E d'où :



Il reste à placer un fragment A, E et D. Comme D ne peut être placé ni avec A ni avec E (vu précédemment) alors on l'isole sur un seul pigeon d'où :



Pour finir on place A et E dans un même paquet pour économiser un pigeon:



Il est donc possible de transporter 5 fragments à l'aide de 7 pigeons en respectant les contraintes de vol, c'est la solution optimale

Les exemples considérés peuvent servir de cas général puisque les rôles des fragments sont symétriques.

Réponse : il est possible de faire mieux en utilisant 7 pigeons pour transporter 5 fragments du message.

citation :
Question 3: On dispose maintenant de seulement 5 pigeons et le découpage en 5 parties n'est bien sûr plus suffisant. Mais en combien de parties au minimum faudrait-il fragmenter le message pour en assurer la transmission en toute sécurité ? Indiquer alors une répartition possible.

Par un raisonnement analogue on montre que le découpage en 6, 7, 8 et 9 parties est insuffisant.

Il faut au minimum fragmenter le message en

Une répartition possible :



Merci pour l'énigme

Question 1)
Un exemple de répartition des 5 fragments entre 8 pigeons


Question 2)
On ne peut le faire avec 6 pigeons, mais on peut avec 7
Voici un exemple


Question 3)
Si on dispose de 5 pigeons :
Avec 9 fragments, on n'y parvient pas, mais avec 10, on a de très nombreuses possibilités
Voici un exemple

Salut !
Dur dur comme défi!

=====>Question 1
Voici une répartition possible :
AB AB AE DE CD BC CD E.

=====>Question 2 :
C'est possible d'utiliser moins de 8 pigeons,par exemple voici la répartition
avec 7 pigeons :
AD AEB AD DE CB BC CE.

=====>Question 3:
Je pense qu'avec si peu de pigeons il est impossible de transmettre un message en respectant les contraintes.

Voilà merci pour ton énigme.

Bonjour minkus,
Pas mal ton stagiaire,mais rien ne vaut tes énigme !!!
Bon!Passons au chose sérieuse!

Question 1:Je dirais,au bol,en étant sûr d'avoir un : 1^er: Rien,  2^ème: A,  3^ème: B,  4^ème: C,  5^ème: Rien,  6^ème: D,  7^ème: E,  8^ème: Rien

Question 2:On dit:

citation :
Deux pigeons quelconques ne doivent transporter des éléments du message dont la réunion permettrait à l'ennemi de reconstituer le message entier.

Donc,par déduction,je dirait 7 pigeons.On fait 5+2=7.

Question 3:Là,c'est la même chose: on doit faire -2.Donc,d'après moi,c'est 3 (5-2=3)

Bonne journée!

Gtmath

Bonjour,

Question 1:

Pigeon 1: A _ _ D _
Pigeon 2: A _ C _ _
Pigeon 3: A B _ _ _
Pigeon 4: _ B _ _ E
Pigeon 5: _ _ C _ E
Pigeon 6: _ _ _ D E
Pigeon 7: _ B C D _
Pigeon 8: _ _ _ _ _  (rien...)

Question 2: On peut facilement descendre à 7 pigeons.
Idem que plus haut, sans le pigeon 8.

Question 3: Il faut fractionner le message en 10 parties, au minimum.
Un exemple:

_ _ _ _ E F G H I J
_ B C D _ _ _ H I J
A _ C D _ F G _ _ J
A B _ D E _ G _ I _
A B C _ E F _ H _ _

C'était très intéressant, surtout la question 3.
_{Où j'ai bien failli répondre: "problème impossible"}  

A+,
gloubi
-

Bonjour

J'ai trouvé cette énigme très intéressante (en espérant que j'ai les bonnes réponses bien sur ) :

1. CD CD CD AB AE BE AB BE
La réunion de deux ne peut jamais donner tout le message (car on n'obtient que 4 parties) et comme chaque lettre apparaît sur au moins 3 pigeons distincts, elle est certaine d'être présente à l'arrivée.

2. Oui, par exemple pour 7 pigeons :
A A A BCD BDE CDE BCE
La réunion de deux entraine :
- soit l'absence de la lettre A.
- soit seulement 4 lettres sur les 5 requises.
Et comme ici aussi, chaque lettre apparaît au moins sur 3 pigeons distincts, elle est certaine d'arriver à destination.

3. Après une longue étude de la question, je pense que le minimum est de 10 parties A B C D E F G H I J.
Voici alors une répartition possible :
ABCDEF
ABCGHI
CDEGIJ
ADFGHJ
BEFHIJ

Pour expliquer rapidement ma méthode : on raisonne en augmentant progressivement le nombre de parties du messages, en calculant le nombre de lettres minimum nécessaire à placer (3n si n lettres), et on utilise le fait qu'aucun des 5 pigeons ne peut transporter n, n-1, n-2 ou n-3 lettres.
De là on compte le nombre de lettres qu'on peut disposer au maximum, à savoir 5(n-4), et le minimum possible est atteint pour n = 10 puisqu'il faut avoir 3n5(n-4).
Il ne reste plus qu'à trouver une disposition (j'ai procédé à tâtons) pour montrer qu'il s'agit bien du minimum.

Merci !

++

on peut faire avec sept pigeons
1: abc

oups, je me suis trompé de entré
je voulais dire
1: abc
2:abd
3:acd
4:bcd
5:e
6:e
7:e

Bonjour minkus


Question 1
On peut faire comme ceci :
Les pigeons sont numérotés de 1 à 8 et les messages de A à E ; une croix à l'intersection de la ligne d'un pigeon et de la colonne d'une partie indique que ce pigeon porte cette partie.
Comme il y a au moins trois croix par colonne, le destinataire peut toujours reconstituer le message.
Et comme chaque pigeon ne porte que deux parties, l'ennemi ne peut pas intercepter le message.



Question 2

C'est possible :
Avec les mêmes conventions que ci-dessus, voici une solution possible.

Il y a trois croix par colonne, donc le destinataire peut toujours reconstituer le message.
Chaque pigeon porte deux parties, sauf le premier, qui porte A, B C. Mais aucun pigeon ne porte simultanément D et E donc l'ennemi ne peut l'intercepter.

Question 3

Il me semble que le nombre minimum de parties est égal à 10.
Solution en image

Là encore, trois croix par colonne, et une inspection montre que deux pigeons ne portent jamais ensemble les 10 parties.
Je n'ai pas trouvé en moins de 10 parties.

Cordialement
Frenicle

Bonjour:

Question 1: (facile)

On fragmente le message en 5 parties A, B, C, D et E et on dispose de 8 pigeons.

Indiquer une répartition des parties du message données à chaque pigeon.

Réponse possible:

AC
AD
AD
BD
BE
BE
CE
C

Question 2:

Est-il possible de faire mieux ? C'est-a-dire d'utiliser moins de 8 pigeons toujours avec 5 fragments.

Par exemple avec 7 pigeons (désolé, je n'ai pas cherché à optimiser ):

AC
AE
AC
BD
BD
BEC
DE

Question 3:

On dispose maintenant de seulement 5 pigeons et le découpage en 5 parties n'est bien sûr plus suffisant.

Mais en combien de parties au minimum faudrait-il fragmenter le message pour en assurer la transmission en toute sécurité ? Indiquer alors une répartition possible.

Oui, c'est 10 fragments. On les appelle: 1,2,3,4,5,6,7,8,9,0.

Une des réponses possibles est:

1e pigeon:124578
2e pigeon:134680
3e pigeon:135679
4e pigeon:235890
5e pigeon:246790

Merci pour cette énigme!

question 1 :
par exemple :
1) A B
2) B C
3) C D
4) D E
5) A C
6) B D
7) A E
8) E

question 2 :  7 pigeons
1) A B C
2) A B D
3) A C D
4) B C D
5) E
6) E
7) E

question 3 : impossible

Bonjour,

Question 1:
Voir la répartition du Tableau 1

Question 3:
Voir la répartition du Tableau 2

Question 3:
N'ayant pas réussi à trouver de solution, j'ai essayé de montrer que c'était impossible. Je ne sais pas ce que ça vaut…

On considère ici que les pigeons ne transportent jamais deux fragments identiques.
Pour être sûr que le destinataire puisse lire le message quels que soient les 2 pigeons attrapés par l'ennemi, chaque fragment du message doit apparaître 3 fois sur trois pigeons différents.
Pour N fragments il y a donc 3N fragments à répartir entre les P pigeons. Soit ici fragments par pigeon en moyenne.
Les pigeons ne devront pas porter moins de fragments en moyenne, sinon on ne pourra pas être certain que les pigeons survivants auront tous les fragments du message.
Pour être certain que l'ennemi ne puisse pas lire le message, le nombre moyen de fragments par pigeon doit être inférieur à .
Pour que les conditions soient remplies, il faut donc satisfaire :


Pour P=5 comme c'est le cas ici, on a:



Ce qui équivaut donc à:



Cette condition ne sera jamais remplie quelle que soit la valeur de N.

On peut vérifier pour la question 2 (à supposer que la méthode soit bonne) :
N=5


P=7 est bien le nombre minimal de pigeon vérifiant la condition (Tableau 3).

je suis pas sur d'avir bien comprit mais je vais quand meme essailé.

question 1 :je pense qu'il faut 1 pigeon qui porte la partie A, deux pigeons qui porte la B,un pour la C,deux pour la D,et deux pour la E.

question 2 : je pense quond aurait put suprimé un pigeon transportan la partie E.

question 3 : On va découper le message en trois. deux pigeons pour la partie A, un pour la parite B,et deux pour la partie C.

Voila seulement il y a une chose que je n'est pas compri si un seul des morceau est perdu alors le message est incomprehensible donc si les mechants intercepte deux fois le meme morceau alors les gentils ne peuvent plus lire le message.sachant que les mechant peuvent intercepter deux message en general sa voudrai dire que pour etre sur de pouvoir lire le message si il était séparé en cinq il faudrait quinze pigeons.voila merci

Chaque partie apparait donc au moins trois fois (pour que l'on puisse en perdre deux sans perdre le message)
Il y a 10 façons de combiner deux parties parmi 5; chaque partie apparait 4 fois; on peut donc supprimer deux combinaisons disjointes, par exemple BC et DE;
Ce qui donne avec 8 pigeons : AB,AC,AD,AE,BD,BE,CD,CE.
Avec 7 pigeons, il faut que l'un transporte trois parties:
ABC,AD,AE,BD,BE,CD,CE.
Avec 5 pigeons,dans une solution symétrique chaque pigeons  transporte k parties parmi n, donc 5k>=3n. n=5 k=3 ne convient pas, par contre on peut trouver une solution avec  n=10 k=6: soient A,B,C,D,E,F,G,H,I,J les parties; une répartition possible:
ABCDEF, ABCHIJ, ADEGHI, BDFGHJ, CEFGIJ

Question 1: (facile)
je répartis de facon a ce que chaque colonne ait au moins 3 croix (voir schéma).

question 2:
voir schéma

question 3:
avec seulement 5 pigeons, il n'y a pas de solution possible.

(les pigeons sont défini par la lettre P)

reponse1:
P1=A,E
P2=B,C
P3=D,E
P4=C,D
P5=A,B
P6=A,D
P7=B,E
P8=C

réponse2:
P1=A,E,C
P2=B,C
P3=D,E
P4=C,D
P5=A,B
P6=A,D
P7=B,E

réponse3:
il faut au minimum 10 parties
P1=A,C,D,F,G,I
P2=A,B,D,F,H,J
P3=B,D,E,G,H,I
P4=B,C,E,F,G,J
P5=A,C,E,H,I,J

Bonjour minkus ,

1) Si c'est facile, je dirais: 1: Rien; 2: A; 3: B; 4: c; 5: Rien; 6: D; 7: E; 8: Rien.

2) Je dirais 6 pigeons car on dit qu'il faut au moin 2 pigeon qui ne transportent rien.(Donc 8 - 2 = 6)

3) 3.Oui je dirais 3...Car on fait 5 - 2 pigeons = 3 pigeons.

Bonne chance à tous!

Merci pour l'énigme!

fedejunior

Bonjour!


1. 1:Rien
2: A
3: B
4: C
5: Rien
6: D
7: e
8: Rien


2.6(8 - 2)


3.3(5 - 2)



Voili voila!

Merci pour l'énigme!

G_Einstein_97

Bonjour,

Je clos cette petite énigme estivale qui semble avoir bien plu à certains si l'on en croit les réponses très détaillées

Impossible de faire mieux que 7 pigeons à la question 2 et pour la question 3, il fallait en effet au moins 10 fragments.

>Gloubi : Je trouve ta réponse à la première question un peu limite. Je ne vois pas l'intérêt d'un pigeon voyageant à vide, à moins qu'il ne soit la 8e roue du carosse indispensable au bon fonctionnement de l'escadron complet
Je l'accepte néanmoins car elle est "mathématiquement" correcte.

>iker : C'est ca qui ne va pas dans ta démo.

citation :
Pour être certain que l'ennemi ne puisse pas lire le message, le nombre moyen de fragments par pigeon doit être inférieur à N/2.

Pour terminer, je tiens à remarquer que certaines réponses se ressemblent un peu trop dans cette énigme et dans les suivantes.

Il s'agit de celles de Gtmaths, fedejunior et G_Einstein_97.

Vu qu'il y a fedejunior dans l'adresse email de Gtmaths, je soupconne le multicompte et cela sera surement regle quand un modo passera par la.

A suivre

minkus

Bonne remarque minkus

Ah oui c'est pas très malin

citation :
Pour terminer, je tiens à remarquer que certaines réponses se ressemblent un peu trop dans cette énigme et dans les suivantes. Il s'agit de celles de Gtmaths, fedejunior et G_Einstein_97.

Ok, ok.J'avoue que j'ai fais du multicompte...Désoler, mais je ne voulais pas que ma réponse ai l'air nul car je ne suis pas fort...Vous porez voir dans des énigme qui suive...Et juste au Modérateurs et au Webmasters: bannisser-moi quand vous voulez...Je suis vraiment, vraiment désoler...

Gtmath

Vous pourez et non pas vous porez...Encors d'ésoler...

Ha!...Et c'est la preuve que j'ai 3 compte...

Salut,

Je ne vois pas l'interet de poster 3 réponses différentes si elle sont globabalement semblables..

Kuider

il ne voulais peut-être pas être le seul à avoir l'air c.. (mais vu qu'il n'a "soit-disant" que 10 ans, on aurait compris...)

Epicurien >

citation :
Je ne vois pas l'interet de poster 3 réponses différentes si elle sont globabalement semblables..

C'est pas faux

Moi si jamais un jour il me vient l'idée de me créer un multicompte ( ) pour participer aux énigmes :

1) je prend une adresse mail qui ne ressemble pas à l'autre.

2) je poste mes messages d'un autre pc

3) ...

( je ne vais pas faire toute la liste du parfait multi-compteur )

Romain

Tu vas donner des idées à certains

Moi je peux toujours m'en sortir en utilisant le compte de ma soeur.

citation :
il ne voulais peut-être pas être le seul à avoir l'air c.. (mais vu qu'il n'a "soit-disant" que 10 ans, on aurait compris...)

c'est peu être une bonne idée pour éviter des situation comme celle ci ... .
non je rigole

Bonjour minkus,

citation :
Je ne vois pas l'intérêt d'un pigeon voyageant à vide

Je voulais simplement abréger la rédaction: réponses quasi-identiques aux questions 1 et 2.

gloubi

citation :
je poste mes messages d'un autre pc

Moi je sais comment la masquer son adresse IP



Kuider.

citation :
Moi je sais comment la masquer son adresse IP

Mais ce n'est pas avec l'adresse IP que les modos détectent les multi-comptes.

Pas de bol...

Ben dans ce cas je crée X comptes chez X différents concurrents

Kuider.

Bonjour,

citation :
Mais vu qu'il n'a "soit-disant" que 10 ans, on aurait compris...

Je n'ai pas "soit-disant" 10 ans, mais véritablement 10 ans...

Gtmath