Inscription / Connexion Nouveau Sujet
Niveau 2 *
Partager :

DEFI 173 : Pigeon vole !**

Posté par
minkus Posteur d'énigmes
08-07-07 à 18:57

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.

DEFI 173 : Pigeon vole !

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

Posté par
simon92
re : DEFI 173 : Pigeon vole !** 08-07-07 à 19:32

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

Posté par
Nofutur2
re : DEFI 173 : Pigeon vole !** 08-07-07 à 20:31

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

Posté par
plumemeteore
re : DEFI 173 : Pigeon vole !** 08-07-07 à 21:52

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

Posté par
manpower
re : DEFI 173 : Pigeon vole !** 09-07-07 à 11:57

gagné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
(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)

DEFI 173 : Pigeon vole !

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 ?

Posté par
lo5707
re : DEFI 173 : Pigeon vole !** 09-07-07 à 13:01

gagné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é ( JFF_les boules numérotées)


Merci pour l'énigme.

Posté par
master_och
re : DEFI 173 : Pigeon vole !** 09-07-07 à 15:56

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

Posté par
lyonnais
re : DEFI 173 : Pigeon vole !** 09-07-07 à 17:09

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

Posté par
infophile
Ca vole haut ! 09-07-07 à 17:47

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


\blue \bullet 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.

\blue \bullet 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.

\blue \bullet Le premier point indique qu'il y aura \rm 3\times 5=15 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 :

3$ \blue \rm \fbox{Pigeon 1: AB\\Pigeon 2: AB\\Pigeon 3: CD\\Pigeon 4: CD\\Pigeon 5: DE\\Pigeon 6: BC\\Pigeon 7: AE\\Pigeon 8: AE}

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.


\red \bullet 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)

\red \bullet 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)

\red \bullet 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.

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

\rm \fbox{ABC\\BCE\\BCD}

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 :

 \bullet 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.
\bullet 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.
 \bullet Il en va de même pour D.

Or puisqu'il faut deux fragments de chaque lettre, il faudrait alors mobiliser \rm 2\times 3=6 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.

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

\rm \fbox{ABC\\BCE}

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

\rm \fbox{ABC\\BCE\\DB\\DC}

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

\red \bullet 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ù :

\rm \fbox{ABC\\BCE\\DB\\DC\\AE}

\red \bullet 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ù :

\rm \fbox{ABC\\BCE\\DB\\DC\\AE\\D}

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

\rm \fbox{ABC\\BCE\\DB\\DC\\AE\\AE\\D}

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 : \rm \red OUI il est possible de faire mieux en utilisant 7 pigeons pour transporter 5 fragments du message.


 \\ 3$ \red \rm \fbox{Pigeon 1: ABC\\Pigeon 2: BCE\\Pigeon 3: DB\\Pigeon 4: DC\\Pigeon 5: AE\\Pigeon 6: AE\\Pigeon 7: D}

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 \rm \red 10 parties

Une répartition possible :

3$ \red \rm \fbox{Pigeon 1: ABCEFH\\Pigeon 2: ABDEGI\\Pigeon 3: ACDFGJ\\Pigeon 4: BCDHIJ\\Pigeon 5: EFGHIJ}

Merci pour l'énigme

Posté par
dhalte
re : DEFI 173 : Pigeon vole !** 09-07-07 à 22:57

gagnéQuestion 1)
Un exemple de répartition des 5 fragments entre 8 pigeons
\begin{matrix}\text{pigeon}&\text{fragments} \\
 \\ 1 & AC \\
 \\ 2 & AD \\
 \\ 3 & AD \\
 \\ 4 & BD \\
 \\ 5 & BE \\
 \\ 6 & BE \\
 \\ 7 & CE \\
 \\ 8 & C \end{matrix}

Question 2)
On ne peut le faire avec 6 pigeons, mais on peut avec 7
Voici un exemple
\begin{matrix}\text{pigeon}&\text{fragments} \\
 \\ 1 & ABC \\
 \\ 2 & ABD \\
 \\ 3 & ACD \\
 \\ 4 & BCD \\
 \\ 5 & E \\
 \\ 6 & E \\
 \\ 7 & E \end{matrix}

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
\begin{matrix}\text{pigeon}&\text{fragments} \\
 \\ 1 & ABCDEF \\
 \\ 2 & ABCGHI \\
 \\ 3 & ADEGHJ \\
 \\ 4 & BDFGIJ \\
 \\ 5 & CEFHIJ \end{matrix}

Posté par
Nilot
re : DEFI 173 : Pigeon vole !** 10-07-07 à 13:53

perduSalut !
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.

Posté par Gtmath (invité)re : DEFI 173 : Pigeon vole !** 10-07-07 à 15:35

perduBonjour 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 : 1er: 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

Posté par
gloubi
re : DEFI 173 : Pigeon vole !** 10-07-07 à 16:40

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

Posté par
xtasx
re : DEFI 173 : Pigeon vole !** 11-07-07 à 13:15

gagné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 !

++

Posté par
fong
re : DEFI 173 : Pigeon vole !** 11-07-07 à 13:35

perduon peut faire avec sept pigeons
1: abc

Posté par
fong
re : DEFI 173 : Pigeon vole !** 11-07-07 à 13:39

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

Posté par
frenicle
re : DEFI 173 : Pigeon vole !** 11-07-07 à 19:46

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

DEFI 173 : Pigeon vole !

Question 2

C'est possible :
Avec les mêmes conventions que ci-dessus, voici une solution possible.
DEFI 173 : Pigeon vole !
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
DEFI 173 : Pigeon vole !
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

Posté par
laotze
re: 11-07-07 à 21:33

gagné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!

Posté par
evariste
re : DEFI 173 : Pigeon vole !** 12-07-07 à 08:55

perduquestion 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

Posté par
iker
re : DEFI 173 : Pigeon vole !** 12-07-07 à 15:41

perduBonjour,

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 \frac{3N}{5} fragments par pigeon en moyenne.
Les pigeons ne devront pas porter moins de \frac{N}{P-2} 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 à \frac{N}{2}.
Pour que les conditions soient remplies, il faut donc satisfaire :
\frac{N}{P-2} \le \frac{3N}{P} < \frac{N}{2}

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

\frac{1}{3}N \le \frac{3}{5}N < \frac{1}{2}N

Ce qui équivaut donc à:

\frac{1}{3} \le \frac{3}{5} < \frac{1}{2}

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
\frac{5}{P-2} \le \frac{15}{P} < \frac{5}{2}

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

DEFI 173 : Pigeon vole !

DEFI 173 : Pigeon vole !

DEFI 173 : Pigeon vole !

Posté par ranma (invité)reponse à pigeon vole 13-07-07 à 15:37

perduje 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

Posté par
piepalm
re : DEFI 173 : Pigeon vole !** 16-07-07 à 09:34

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

Posté par deltree (invité)réponses 17-07-07 à 20:40

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

réponses

réponses

Posté par
rezoons
re : DEFI 173 : Pigeon vole !** 20-07-07 à 11:34

gagné(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

Posté par fedejunior (invité)re : DEFI 173 : Pigeon vole !** 25-07-07 à 18:28

perduBonjour 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

Posté par G_Einstein_97 (invité)re : DEFI 173 : Pigeon vole !** 25-07-07 à 18:46

perduBonjour!


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

Posté par
minkus Posteur d'énigmes
re : DEFI 173 : Pigeon vole !** 28-07-07 à 16:55

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

Posté par
monrow Posteur d'énigmes
re : DEFI 173 : Pigeon vole !** 28-07-07 à 17:08

Bonne remarque minkus

Posté par
infophile
re : DEFI 173 : Pigeon vole !** 28-07-07 à 17:10

gagnéAh oui c'est pas très malin

Posté par Gtmath (invité)re : DEFI 173 : Pigeon vole !** 28-07-07 à 18:36

perdu

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

Posté par fedejunior (invité)re : DEFI 173 : Pigeon vole !** 28-07-07 à 18:56

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

Posté par fedejunior (invité)re : DEFI 173 : Pigeon vole !** 28-07-07 à 18:57

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

Posté par
Epicurien
re : DEFI 173 : Pigeon vole !** 30-07-07 à 18:34

Salut,

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

Kuider

Posté par
lo5707
re : DEFI 173 : Pigeon vole !** 30-07-07 à 19:39

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

Posté par
lyonnais
re : DEFI 173 : Pigeon vole !** 30-07-07 à 19:41

gagnéEpicurien >

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

C'est pas faux :D

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

Posté par
infophile
re : DEFI 173 : Pigeon vole !** 30-07-07 à 20:05

gagnéTu vas donner des idées à certains

Posté par
1 Schumi 1
re : DEFI 173 : Pigeon vole !** 30-07-07 à 20:09

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

Posté par
master_och
re : DEFI 173 : Pigeon vole !** 30-07-07 à 20:23

gagné

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 ... DEFI 166 : Hanjie ! Haaaannnnjie ! .
non je rigole

Posté par
gloubi
re : DEFI 173 : Pigeon vole !** 31-07-07 à 12:50

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

Posté par
Epicurien
re : DEFI 173 : Pigeon vole !** 01-08-07 à 01:10

Citation :
je poste mes messages d'un autre pc


Moi je sais comment la masquer son adresse IP



Kuider.

Posté par
1 Schumi 1
re : DEFI 173 : Pigeon vole !** 01-08-07 à 10:25

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

Posté par
Epicurien
re : DEFI 173 : Pigeon vole !** 01-08-07 à 18:04



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

Kuider.

Posté par Gtmath (invité)re : DEFI 173 : Pigeon vole !** 06-08-07 à 17:56

perduBonjour,

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

Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 97:28:38.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !