Inscription / Connexion Nouveau Sujet

1 2 +


Niveau 2 *
Partager :

Joute n°149 : Les 007 espions

Posté par
godefroy_lehardi Posteur d'énigmes
07-06-14 à 10:10

Bonjour à tous,

L'île de la physique a envoyé 7 de ses meilleurs agents de renseignement sur l'île des maths afin de découvrir les 7 théorèmes secrets que les mathiliens gardent jalousement pour eux (toute ressemblance avec des matheux existants ou ayant existé est évidemment exclue).

Au terme de la mission, les 7 théorèmes sont découverts (un par agent).

Afin d'être sûr que, en cas de capture, l'un au moins des agents parvienne à ramener l'ensemble des 7 théorèmes, ils décident de se téléphoner pour partager leurs découvertes.
Lors d'un coup de fil, chacun explique tous les théorèmes qu'il connaît à son interlocuteur, qui lui raconte à son tour les siens.
Précision : ils ne peuvent pas faire de conférences à plusieurs. Chaque échange téléphonique se passe entre deux personnes seulement.

Mais, par mesure de sécurité, il faut limiter le nombre d'échanges téléphoniques au strict minimum.

Question : Comment faut-il organiser les appels pour que chacun des 7 agents connaisse les 7 théorèmes en un minimum d'appels ?
S'il existe plusieurs solutions, une seule suffira.

Question subsidiaire : saurez-vous reconnaître ces 7 agents secrets ?

Joute n°149 : Les 007 espions Joute n°149 : Les 007 espions Joute n°149 : Les 007 espions

Posté par
cercus
Joute n°149 : Les 007 espions 07-06-14 à 10:54

perdusalut, voici la réponse : il faudra 12 appels

par exemple : Soit les sept agents positionnés comme ceci :

1 2 3 4

5 6 7

alors 1->5 1->6 1->7
      2->5 2->6 2->7
      3->5 3->6 3->7
      4->5 4->6 4->7

merci pour l'énigme

Posté par
Nofutur2
re : Joute n°149 : Les 007 espions 07-06-14 à 11:02

gagnéJe tente ma chance... ayant trouvé plusieurs solutions à 10 appels.. D'ailleurs il semblerait que le nombre d'appels nécessaires soit de la forme 2*(n-2)pour n>2.
Donc 10 appels.
Une solution possible (entre parenthèses les théorèmes connus des deux interlocuteurs à l'issue de leur communication.

1-2 (1-2)
2-3 (1-2-3)
3-4 (1-2-3-4)
5-6 (5-6)
6-7 (5-6-7)
4-7 (1-2-3-4-5-6-7)
3-6 (1-2-3-4-5-6-7)
3-5 (1-2-3-4-5-6-7)
3-2 (1-2-3-4-5-6-7)
3-1 (1-2-3-4-5-6-7)

Posté par
Nofutur2
re : Joute n°149 : Les 007 espions 07-06-14 à 11:20

gagnéPour les 7 agents secrets, on reconnait :
- OSS 117 (J. Dujardin)
- Mata Hari
- James Bond (Sean Connery)
- Ahmed Balafrej(Mossad)
- Austin Powers (Mike Myers)
- Ian Flemming
- Charles de Beaumont (Chevalier d'Eon).

Posté par
Alexique
re : Joute n°149 : Les 007 espions 07-06-14 à 13:14

perduBonjour,

je propose 11 appels au minimum et puisque c'est la méthode qu'on demande, je la détaille :

Généralisons à n agents. Le but est que l'un obtienne toutes les données le plus vite possible en un minimum de temps pour après appeler un à un les collègues qui n'ont pas encore tous les théorèmes. Il faut passer n-1 appels (en file indienne c'est-à-dire un agent appelle un autre qui n'a jamais été appelé avant) pour que les deux derniers et seulement les deux derniers aient tous les théorèmes et après il y a n-2 personnes à mettre au courant (on se fiche de l'ordre cette fois) donc n-2 appels d'où 2n-3 appels minimum au total...ce qui fait 2*7-3=11 dans ce cas...

Merci pour l'énigme.

Posté par
benmagnol
Ca coute cher en téléphone 07-06-14 à 13:47

perduBonjour,
Soient A,B,...,G les 7 espions
Soit An le fait que A détienne un secret
1 : A1 tel à B1 => A2 B2
2 : B2 tel à C1 => B3 C3
3 : C3 tel à D1 => C4 D4
4 : D4 tel à E1 => D5 E5
5 : E5 tel à F1 => E6 F6
6 : F6 tel à G1 => F7 G7
puis
7 : G7 tel à A2 => G7 A7
8 : A7 tel à B3 => A7 B7
9 : B7 tel à C4 => B7 C7
10 : C7 tel à D5 => C7 D7
11 : D7 tel à E6 => D7 E7
12 : E7 tel à F6 => E7 F7
Donc en 12 coups de fils minimum les 7 espions connaissent les 7 secrets
Ma stratégie se résume dans le fait que le mieux informé téléphone toujours au moins bien informé pour maximiser le taux de diffusion du secret
Merci godefroy-lehardi pour cette énigme

Posté par
LeDino
re : Joute n°149 : Les 007 espions 07-06-14 à 15:38

gagnéBonjour,

Je propose une solution en 10 appels.
En numérotant les espions (et théorèmes) de 1 à 7, et en notant * tous les théorèmes :


Espions :        E1   E2   E3   E4  E5   E6   E7
------------------------------------------------
Théorèmes :      1    2    3    4   5    6    7

Appels           E1   E2   E3   E4  E5   E6   E7
------------------------------------------------
1 appelle 2      12   12   3    4   5    6    7  
3 appelle 4      12   12   34   34  5    6    7  
5 appelle 6      12   12   34   34  56   56   7  
1 appelle 3     1234  12  1234  34  56   56   7  
5 appelle 7     1234  12  1234  34  567  56  567 
1 appelle 5     ****  12  1234  34  ***  56  567 
3 appelle 7     ****  12  ****  34  ***  56  *** 
1 appelle 2     ****  **  ****  34  ***  56  *** 
1 appelle 4     ****  **  ****  **  ***  56  *** 
1 appelle 6     ****  **  ****  **  ***  **  *** 


Bravo et merci pour ce défi vraiment original et étonnant .
La solution que je propose n'améliore que d'une unité la solution "naïve" dans laquelle 1 appelle successivement tous les autres pour apprendre tous les théorèmes, puis les rappelle pour les mettre au courant.
Dans ce cas la solution naïve compte   N = n - 1 + n - 2 = 2n - 3 = 11  appels.

Posté par
LeDino
re : Joute n°149 : Les 007 espions 07-06-14 à 19:33

gagnéPour la "vraie" énigme :

Hubert Bonisseur de la Bath - Alias OSS 117
Margaretha Geertruida Zelle - Alias Mata Hari
James Bond  - Alias agent 007
Elie Cohen  - Alias Combattant 88
Austin Power - Alias International Man of Mistery
Ian Lancaster Fleming - Alias agent de sa Majesté lui même et père de James Bond
Charles de Beaumont - Alias le Chevalier d'Eon

Posté par
dubo34
re : Joute n°149 : Les 007 espions 08-06-14 à 07:16

perduSoit A,B,C,D,E,F les 7 agents
Une solution parmi tant d'autres (mais est ce la plus optimisée?)
11 coups de téléphone
1:AB
2:BC
3:CD
4E
5:EF
6:FG
7:GA
8:FB
9:FC
10:FD
11:FE

Posté par
plumemeteore
re : Joute n°149 : Les 007 espions 08-06-14 à 11:12

gagnéBonjour Godefroy.
Il y a dix échanges.
Soient A, B, C, D, E, F et G les agents secrets et 1, 2, 3, 4, 5, 6 et 7 les théorèmes que chacun détient respectivement au départ.
Les dix échanges sont : A-B, B-C, C-D, E-F, F-G, C-F, D-G, C-A, D-B, G-E.
Après les cinq premiers échanges :
A : 12
B : 123
C : 1234
D : 1234
E : 56
F : 567
G : 567
Lors des deux échanges suivants, C et F se complètent mutuellement, ainsi que D et G.
Lors des trois derniers échanges, trois des quatre agents complets complètent les trois autres.

Posté par
littleguy
re : Joute n°149 : Les 007 espions 08-06-14 à 14:07

perduBonjour,

Je propose 10 appels, organisés comme ceci :

A1 joint respectivement A2, A3, A4, A5, A6.
Après ces 5 appels A1 et A6 connaissent les sept théorèmes.

L'un des deux téléphone alors à A2, A3, A4, A5, A7 et après ces 5 nouvelles conversations, tout le monde connaît tout.

Pour la subsidiaire :
Hubert Bonisseur de La Bath - OSS117)
Margaretha Geertruida Zelle - Mata Hari
James Bond - 007
Eli Cohen - Kamel Amin Taabat
Austin Powers
Ian Fleming
Charles de Beaumont - chevalier d'Eon

Posté par
manitoba
re : Joute n°149 : Les 007 espions 08-06-14 à 15:58

perduBonjour,

11 échanges téléphoniques.

1-2,3-4,5-6,1-3,5-7,1-7
1-2,1-3,1-4,1-5,1-6.


Merci pour la joute

Joute n°149 : Les 007 espions

Posté par
manitoba
re : Joute n°149 : Les 007 espions 08-06-14 à 16:46

perduQuestion subsidiaire
Pas trouvé le n°4

1:Jean Dujardin dans OSS117:Le caire, nid d'espions
2: Mme Mata Hari
3:Sean Connery
4: ?
5: Austin Powers
6: Ian Fleming
7: Charles de Beaumont, chevalier d'Eon.

Posté par
geo3
re : Joute n°149 : Les 007 espions 08-06-14 à 17:08

perduBonjour

1 communique avec  2 =>  1 et 2 connaissent les théorèmes 1 et 2
3 communique avec  4 =>  3 et 4 connaissent les théorèmes 3 et 4
5 communique avec  6 =>  5 et 6 connaissent les théorèmes 5 et 6  
5 communique avec  7 =>  5 et 7 connaissent les théorèmes 5 et 6 et7  
1 communique avec  3 =>  1 et 3 connaissent les théorèmes 1, 2,3,4
après
1 communique avec 7  =>  1 et 7 connaissent les théorèmes 1,2,3,4,5,6,7  
1 communique avec 5  =>  5 connaît les théorèmes 1,2,3,4,5,6,7
1 communique avec 2  ( 5 ou 7)  => 2 connaît les théorèmes 1,2,3,4,5,6,7
1 communique avec 3  ( 5 ou 7)  => 3 connaît les théorèmes 1,2,3,4,5,6,7
1 communique avec 4  ( 5 ou 7)  => 4 connaît les théorèmes 1,2,3,4,5,6,7
1 communique avec 6  ( 5 ou 7)  => 6 connaît les théorèmes 1,2,3,4,5,6,7
=>
11 appels
A+

Posté par
Alishisap
re : Joute n°149 : Les 007 espions 08-06-14 à 23:07

perduBonjour et merci pour l'énigme !
Je voulais faire un programme mais Python s'embrouille étrangement dans les listes, il faudrait que je songe à changer de moyen de programmation (Mapple ?). En attendant ma réponse :

J'appellerai les 7 agents A, B, C, D, E, F et G.
Voici comment organiser les appels (11 en tout) :

Appel 1 : A B
Appel 2 : C D
Appel 3 : E F
Appel 4 : A C
Appel 5 : B D
Appel 6 : E G
Appel 7 : F G
Appel 8 : A E
Appel 9 : B F
Appel 10 : C G
Appel 11 : C D


À bientôt.

Posté par
lenain
Mon nom est Nain, Lenain 09-06-14 à 06:36

perduBonsoir

Je propose 11 appels

Ou encore 10 appels et 1 texto

En tout cas 11 échanges téléphoniques...

Merci pour ce petit casse-tête.

Posté par
dpi
re : Joute n°149 : Les 007 espions 09-06-14 à 06:44

gagnéBonjour,

On pense arriver avec 11 appels, mais on peut faire 10
On dira que les théorèmes trouvés portent le même chiffre que l'agent trouveur.
appels     th connus
23         23
12         123
17         1237
45         45
56         456
51         1234567
67         1234567
63         1234567
14         1234567
52         1234567
soit 10 appels

Posté par
masab
re : Joute n°149 : Les 007 espions 09-06-14 à 23:10

gagnéBonjour godefroy,

On peut organiser comme suit les appels pour que chacun des 7 agents connaisse les 7 théorèmes en 10 appels :

[[1, 2], [3, 4], [5, 6], [1, 3], [1, 7], [1, 5], [1, 2], [1, 3], [1, 4], [6, 7]]

Il faut interpréter ce vecteur comme suit :
[1, 2] signifie que les agents 1 et 2 se téléphonent
[3, 4] signifie que les agents 3 et 4 se téléphonent
[5, 6] signifie que les agents 5 et 6 se téléphonent
etc

Il n'y a pas de solution en 9 appels.

Merci pour cette énigme.

Posté par
weierstrass
re : Joute n°149 : Les 007 espions 10-06-14 à 07:06

gagnépas trop sur de moi, mais on va répondre quand même...
[3, 1], [7, 5], [6, 4], [1, 2], [5, 6], [2, 5], [2, 3], [2, 7], [6, 1], [4, 2]
une solution possible...
merci pour cette énigme

Posté par
ksad
re : Joute n°149 : Les 007 espions 10-06-14 à 16:25

gagnéBonjour
Allez, zou!, voici la solution que je propose.
Je trouve plusieurs stratégies en 10 coups de téléphone, dont celle illustrée par la figure ci-dessous.
(A lire par colonne, de haut en bas : en "surligné orange", les deux interlocuteurs qui se parlent au téléphone, et en noir les cases correspondant au partage de connaissance des théorèmes recueillis).
En appelant A,B,C,D,E,F,G les 7 espions, les 10 conversations sont ici successivement :
A+B, C+D, A+C, A+E, F+G, A+F, E+G, A+D, C+F, A+B

Joute n°149 : Les 007 espions

Je n'ai malheureusement pas pu trouver de solution plus efficace qu'en dix coups de téléphone... mais beaucoup de solutions possibles en 10.
Merci pour cette belle joute !

... et pour la question subsidiaire:
- Jean Dujardin, dans le rôle de OSS117
- Margaretha Geertruida Zelle, alias Mata Hari
- Sean Connery, dans le rôle de James Bond
- Eli Cohen (espion israélien)
- Mike Myers, dans le rôle d'Austin Powers
- Ian Fleming (qui fut un véritable espion, avant d'écrire les James Bond)
- le Chevalier d'Eon

Posté par
weierstrass
re : Joute n°149 : Les 007 espions 10-06-14 à 21:16

gagnéquestion subsidiaire:
1)OSS 117 (facile c'était marqué )
2)Mata Hari
3)James Bond
4)Hercule Poirot?
5)Austin Powers
6)Ian Fleming
7)Chevalier d'Éon

Posté par
pyth
re : Joute n°149 : Les 007 espions 10-06-14 à 21:27

perdu1 appelle 2
2 appelle 3
3 appelle 4
4 appelle 5
5 appelle 6
6 appelle 7

donc 6 appels suffisent

celui qui doit tout connaitre doit recevoir 6 informations donc il faut au minimum 6 appels

Conclusion le mieux est de faire 6 appels

Posté par
spelecameleon
réponse à la joute n° 149 10-06-14 à 22:01

gagnéBonjour,

je propose une série de 10 appels à l'issue desquels les 7 espions connaitront chacun les 7 théorèmes.

Appel 1 : espion 1 et 2
Appel 2 : espion 2 et 3
Appel 3 : espion 6 et 7
Appel 4 : espion 5 et 6
Appel 5 : espion 3 et 4
Appel 6 : espion 4 et 5
Appel 7 : espion 3 et 6
Appel 8 : espion 1 et 3
Appel 9 : espion 1 et 2
Appel 10 : espion 1 et 7


Cordialement

Posté par
basilide
re : Joute n°149 : Les 007 espions 11-06-14 à 10:22

gagnéIl faut faire exactement 7+3 appels : 10 appels

Voici comment va-t-on les organiser :

On va noter A jusqu'à G les 7 espions, et on va numeroter, respectivement, 1 à 7 les théorèmes qu'ils ont trouvé.
Donc au début, A a découvert le théorème 1, B le 2, C le 3, D le 4, E le 5, F le 6 et G le 7.

1er appel : A appelle B. A la fin de cet appel, A et B connaissent les théorèmes 1,2.
            Notons : A-12, B-12, C-3, D-4, E-5, F-6, G-7.

2è appel : C appelle D. A la fin de cet appel, C et D connaissent les théorèmes 3,4.
           Notons : A-12, B-12, C-34, D-34, E-5, F-6, G-7.

3è appel : E appelle F. A la fin de cet appel, E et F connaissent les théorèmes 5,6.
           Notons : A-12, B-12, C-34, D-34, E-56, F-56, G-7.

4è appel : A appelle C. A la fin de cet appel, A et C connaissent les théorèmes 1,2,3,4.
           Notons : A-1234, B-12, C-1234, D-34, E-56, F-56, G-7.

5è appel : F appelle G. A la fin de cet appel, F et G connaissent les théorèmes 5,6,7.
           Notons : A-1234, B-12, C-1234, D-34, E-56, F-567, G-567.

6è appel : A appelle F. A la fin de cet appel, A et F connaissent les théorèmes 1,2,3,4,5,6,7.
           Notons : A-1234567, B-12, C-1234, D-34, E-56, F-1234567, G-567.

7è appel : C appelle G. A la fin de cet appel, C et G connaissent les théorèmes 1,2,3,4,5,6,7.
           Notons : A-1234567, B-12, C-1234567, D-34, E-56, F-1234567, G-1234567.

8è appel : A appelle B. A la fin de cet appel, A et B connaissent les théorèmes 1,2,3,4,5,6,7.
           Notons : A-1234567, B-1234567, C-1234567, D-34, E-56, F-1234567, G-1234567.

9è appel : C appelle D. A la fin de cet appel, C et D connaissent les théorèmes 1,2,3,4,5,6,7.
           Notons : A-1234567, B-1234567, C-1234567, D-1234567, E-56, F-1234567, G-1234567.

10è appel : E appelle F. A la fin de cet appel, E et F connaissent les théorèmes 1,2,3,4,5,6,7.
            Notons : A-1234567, B-1234567, C-1234567, D-1234567, E-1234567, F-1234567, G-1234567.

Posté par
basilide
re : Joute n°149 : Les 007 espions 11-06-14 à 10:43

gagnéRéponses à la question subsidiaire :
A- Hubert Bonisseur de La Bath
B- Mata Hari
C- James Bond
D- Eli Cohen
E- Unknown
F- Unknown
G- Chevalier d'Eon Charles-Geneviève-Louis-Auguste-André-Timothée d'Éon de Beaumont

Posté par
seb_dji
re : Joute n°149 : Les 007 espions 11-06-14 à 11:32

perduil faut 10 appels:
agent1 appelle agent2
agent3 appelle agent4
agent5 appelle agent6
agent1 appelle agent7
agent5 appelle agent6
agent1 appelle agent4
agent5 appelle agent7
agent4 appelle agent2
agent1 appelle agent3
agent1 appelle agent6

Posté par
LittleFox
re : Joute n°149 : Les 007 espions 12-06-14 à 12:00

perduIl faut organiser les appels pour que chacun des 7 agents connaisse les 7 théorèmes en un minimum d'appels de la façon suivante :

Soit A,B,C,D,E,F,G nos agents, les appels sont dans l'ordre :
A<->B
B<->C
C<->D
D<->E
E<->F
F<->G
G<->H
G<->F
F<->E
E<->D
D<->C
C<->B
B<->A
soit 11 appels.

Ce n'est pas l'unique solution et pas la plus efficace car on pourrait s'arranger pour faire des appels en même temps :
A<->B, C<->D, E<->F
A<->C, E<->G
A<->E
A<->C, E<->G
A<->B, C<->D, E<->F

qui fait aussi 11 appels mais en 5 temps au lieu de 11.

Nos agents sont de gauche à droite :
Hubert Bonisseur de La Bath, alias OSS 117
Margaretha Geertruida « Grietje » Zelle, alias Mata Hari
James Bond, alias 007
Eli Cohen
Austin Powers
Ian Lancaster Fleming
Charles-Geneviève-Louis-Auguste-André-Timothée d'Éon de Beaumont, alias le chevalier d'Éon

Posté par
torio
re : Joute n°149 : Les 007 espions 12-06-14 à 14:47

perdu11 appels :

Coup de téléphone numéro 1  :  1 téléphone à 2
Coup de téléphone numéro 2  :  2 téléphone à 3
Coup de téléphone numéro 3  :  3 téléphone à 4
Coup de téléphone numéro 4  :  4 téléphone à 5
Coup de téléphone numéro 5  :  5 téléphone à 6
Coup de téléphone numéro 6  :  6 téléphone à 7
Coup de téléphone numéro 7  :  6 téléphone à 5
Coup de téléphone numéro 8  :  5 téléphone à 4
Coup de téléphone numéro 9  :  4 téléphone à 3
Coup de téléphone numéro 10  :  3 téléphone à 2
Coup de téléphone numéro 11  :  2 téléphone à 1


A+
Torio

Posté par
damidou
re : Joute n°149 : Les 007 espions 12-06-14 à 17:37

perduJe dirai qu'ils y arriveraient en 13 appels

Posté par
Cpierre60
re : Joute n°149 : Les 007 espions 13-06-14 à 11:30

gagnéBonjour,
Je n'ai pas trouvé mieux que 10 échanges.
En appelant :
A, B, C, D, E, F et  G nos 7 agents,
AB un échange de A avec B (et ainsi de suite),
je propose parmi de nombreuses possibilités, les échanges successifs suivants :
AB, BC, DE, EF, FG, BF, CG, AF, BE, CD
Remarque : même résultat en prenant cette liste dans l'ordre inverse.
Merci pour cette énigme.

Posté par
weierstrass
re : Joute n°149 : Les 007 espions 13-06-14 à 17:58

gagnécorrection...
Pour le numéro 4), il s'agit d'Eli Cohen, et bien évidemment pas d'Hercule Poirot (j'étais pas sûr pour celui là...)

Posté par
arnaudmagnol
re : Joute n°149 : Les 007 espions 15-06-14 à 19:19

perduBonjour,
En me basant sur des essais à quelques joueurs :
L'énigme réduite à trois joueurs donne 3 coups de fils
Pour 4 espions, il faut quatre appels

Donc pour 7 espions, on forme un sous-groupe de 3, un sous-groupe de 4. Soit 7 appels.
Puis pour faire la "jonction" entre les deux groupes, il faut quatre appels.


Donc au total : 11 appels sont nécessaires.

Merci pour l'énigme

Posté par
jgeneve
re : Joute n°149 : Les 007 espions 18-06-14 à 10:07

perduBonjour,

je propose   11  coups de téléphone.

Merci pour l'énigme

Posté par
pallpall
re : Joute n°149 : Les 007 espions 18-06-14 à 10:25

perduBonjour,

il faut au minimum 11 appels pour que tous les agents aient tous les théorêmes.

Merci pour l'énigme.

Posté par
rschoon
re : Joute n°149 : Les 007 espions 20-06-14 à 14:01

gagnéBonjour à tous.

Sauf erreur, il faut au minimum 10 appels : (1,2),(1,3),(1,4),(1,5),(6,7),(1,6),(2,6),(3,6),(4,6),(5,7).

Réponse à la question subsidiaire :OSS117, Mata Hari, James Bond, Austin Powers, Ian Fleming, Chevalier d'Eon.

Merci pour l'énigme

Posté par
panda_adnap
re : Joute n°149 : Les 007 espions 21-06-14 à 13:41

gagnéBonjour,

Je propose 10 coups de fil

1-2
1-3
1-4
1-5
6-7
1-6
1-2
1-3
1-4
5-7

Posté par
fffmatf
re : Joute n°149 : Les 007 espions 27-06-14 à 19:33

perduBonjour,

Il faut 11 appels (sauf erreur) :

Posons :

a=agent n°1 -> (connait le th. 1)
b=agent n°2 -> (connait le th. 2)
c=agent n°3 -> (connait le th. 3)
d=agent n°4 -> (connait le th. 4)
e=agent n°5 -> (connait le th. 5)
f=agent n°6 -> (connait le th. 6)
g=agent n°7 -> (connait le th. 7)

Solution :

"<->" symbolise un appel et un partage des connaissances des théorèmes.
1,2,3,4,5,6,7 symbolisent les théorèmes.

a <-> b = (1;2) <-> (1;2)
a <-> c = (1;2;3) <-> (1;2;3)
a <-> d = (1;2;3;4) <-> (1;2;3;4)
a <-> e = (1;2;3;4;5) <-> (1;2;3;4;5)
a <-> f = (1;2;3;4;5;6) <-> (1;2;3;4;5;6)
a <-> g = (1;2;3;4;5;6;7) <-> (1;2;3;4;5;6;7)

Finalement, a et g connaissent tous les théorèmes (dans la mesure où "a" a une bonne mémoire, sinon il risque de foutre le bordel)

Il manque donc :
7 à f
6 et 7 à e
5,6 et 7 à d
4,5,6 et 7 à c
3,4,5,6 et 7 à b

Donc, il suffit à a de passer un autre appel à chacun d'entre eux :
a <-> b
a <-> c
a <-> d
a <-> e
a <-> f

Finalement, il faut 11 appels pour que tous les agents connaissent les 7 théorèmes (sauf erreur incongrue).

Cependant, pour gagner du temps, a et g devraient se partager les appels à la fin (même si le nombre d'appels resterait le même).

Merci pour la joute !

Posté par
wow1296
re : Joute n°149 : Les 007 espions 28-06-14 à 01:00

perduBonsoir !

Pour moi, si les 7 agents sont A, B, C, D, E, F et G, quelques soient les théorèmes secrets qu'ils connaissent respectivement au départ, une bonne organisation des appels téléphoniques entre ceux-ci serait par exemple :

AB - BC - CD - DE - EF - FG - GA - AB - BC - CD - DE (AB représente une conversation entre l'agent A et l'agent B)

Ainsi, il semble que le nombre minimal d'appels nécessaires s'élève à 11.

Merci pour cette énigme

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°149 : Les 007 espions 29-06-14 à 10:59

Clôture de l'énigme :

Bravo à LeDino qui, le premier, a découvert l'identité des 7 agents secrets.

Par ailleurs, comme il l'a clairement montré, le score optimal n'est guère éloigné du score "standard". Mais c'est toujours ça

Posté par
weierstrass
re : Joute n°149 : Les 007 espions 29-06-14 à 11:07

gagnémasab a l'air sur de sa réponse...
une démonstration sur l'inexistence d'une solution en 9 appels?

Posté par
Cpierre60
re : Joute n°149 : Les 007 espions 29-06-14 à 11:37

gagnéBonjour,

Citation :
une démonstration sur l'inexistence d'une solution en 9 appels?

Si j'avais su la faire, j'aurais répondu beaucoup plus vite, avant de me résoudre à proposer 10 échanges !

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°149 : Les 007 espions 29-06-14 à 13:09

La formule générale est bien 2(n-2).

J'avais trouvé une démonstration directe mais je l'ai oubliée

En revanche, ça se fait très bien par récurrence. Je vous laisse chercher un peu ?

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°149 : Les 007 espions 29-06-14 à 13:11

La formule est valable pour n4, évidemment.

Posté par
weierstrass
re : Joute n°149 : Les 007 espions 29-06-14 à 13:28

gagnéBien sur, la démonstration devient alors évidente:
solution en bas (je ne pouvais pas blanquer)





























supposons que pour n espions, 2n-4 appels suffisent, si on rajoute un espion, il effectuera le premier appel avec le premier. On effectue alors les 2n-4 appels entre les n premiers espions. Le n+1 espion téléphonera donc au premier espion pour avoir l'ensemble des démos.
On se retrouve alors avec 2n-4+2 = 2(n+1)-4 appels.

Posté par
Cpierre60
re : Joute n°149 : Les 007 espions 29-06-14 à 15:09

gagnéSalut weierstrass,
Je suis ton raisonnement.
Et je me dis que tu as démontré que si 2(n-2) échanges suffisent au rang n, ils suffiront au rang n+1...
Mais cela démontre-t-il que 2(n-2) échanges sont nécessaires pour tout rang n ? avec un de moins n'y arriverait-on pas...dans un cas particulier....pour n>x... ?
Ma conviction n'est pas faite !

Posté par
weierstrass
re : Joute n°149 : Les 007 espions 29-06-14 à 15:19

gagnéeffectivement, il manque une étape dans mon raisonnement...

Posté par
masab
re : Joute n°149 : Les 007 espions 29-06-14 à 15:22

gagnéPersonnellement un programme info m'a montré qu'il n'y a pas de solution en 9 appels ! Je n'ai pas pris le temps de chercher une preuve directe.

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°149 : Les 007 espions 29-06-14 à 16:12

@ Cpierre60 : excellente remarque !
J'avais loupé cet aspect.

Posté par
LeDino
re : Joute n°149 : Les 007 espions 29-06-14 à 17:13

gagnéBonjour tout le monde !

J'avais vu également que la conjecture en 2n-4 est toujours réalisable.
Au passage, la preuve en question (présentée par Weierstrass) est assez siouxante...
... parce qu'il faut bien réaliser que la détention par l'un des agents de plusieurs théorèmes, se propagera à l'ensemble des agents selon les mêmes modalités que dans le cas de la détention d'un seul théorème (ce qui permet de prouver la récurrence).


Par ailleurs, je n'ai vu aucune preuve qu'elle est minimale...
Et pour ma part, j'ai le vague sentiment comme Cpierre60, qu'il peut y avoir des valeurs de n2n-4 pourrait être améliorée.
Fausse intuition ?

Le sujet reste ouvert ...

Posté par
weierstrass
re : Joute n°149 : Les 007 espions 01-07-14 à 20:03

gagnéEn attendant une quelconque piste sur la détermination du minimum, voilà une autre démonstration directe du fait que le problème peut être résolu en 2n-4 appels:

soit les espions numérotés de 1 à n, on efectue les étapes suivantes:
[1,2];[n,n-1];[1,3];[n,n-2];[1,4];[n,n-3];...;[1,n-1];[n,1]
que l'on peut interpréter avec le schéma ci-dessous

Le 1 et le n auront parcouru les numéros de 2 à n-1, donc auront toutes leurs démos.
Le 1 en arrivant au n-1 aura la démo du n, le n en arrivant au 2 aura la démo du 1.
pour un espion k compris entre 2 et n-1, il aura les démos de 1 à k-1 par le 1, et les démos de k+1 à n par n.

1 et k effectuent chacun n-2 appels, on trouve donc une solution en 2n-4 appels.

En espérant que ça puisse vous donner des idées...

Joute n°149 : Les 007 espions

1 2 +


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

Temps de réponse moyen : 120:22:15.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


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 !