Salut Caduk,

ça me fait penser à un nuage de n points. Chaque point devant être raccordé à un réseau unique, le calcul est vite fait il me semble: n-1.

Chaque espion en appelle un autre, puis un représentant d'un groupe de deux en appelle un autre, puis un représentant d'un groupe de quatre en appelle un autre,
etc. Donc si N est de la forme 2^n, alors le nombre d'appels nécessaires est n.
Formule générale: n = ent [ log(N) / log(2) + 0,999 ]

Pour 2 espions, 1 appel suffit.
Pour 3 espions, il faut 3 appels.
Pour 4 espions, c'est 4 appels.
Et à partir de 4 espions, chaque nouvel espion imposera 2 appels supplémentaires, soit 2n-4 appels pour n espions.

Il est facile de démontrer que ce nombre d'appels est suffisant par récurrence : on suppose que pour n>=4 espions (appelés E1, ..., En), 2n-4 appels suffisent, et on rajoute un espion En+1. Alors voici une solution utilisant 2n-2 appels : En+1 appelle E1, puis on effectue une solution du problème avec n espions, puis En+1 appelle E1.

Par contre, démontrer que ce nombre d'appels est nécessaire, c'est une autre paire de manches. C'est un résultat connu sous le nom de "gossip problem", et si tu as une démonstration simple, ça m'intéresse...

Ebichu
Oui c'est bien ça. Je ne connaissais pas le nom du problème, j'ai du démo qui est assez élégante, avec une démo relativement simple, même si elle n'est pas forcément évidente au premier abord. Je vais essayer de la comparer à celles que je trouverai sur le net.
godisdead
Oui, c'est effectivement juste, on peut encore améliorer un peu cette borne en arrangeant un peu mieux les appels, regarde le cas ou n = 4

gwen27
Très bien, reste à prouver que l'on ne peut pas faire mieux...

Salut Caduk

J'ai déjà vu ce problème quelque part mais j'ai la mémoire qui flanche .

On trouve facilement pour n espions :

n=1 : 0 appel .
n=2 : 1 appel .
n=3 : 3 appels .
n>3 : 2n-4 appels .

La partie délicate est de monter qu'on ne peut pas faire mieux . Il me semble qu'on y arrive en séparant les espions en deux blocs mais je n'ai pas retrouvé la petite subtilité qui fait fonctionner l'affaire , à suivre ...

Vasimolo

Mes parenthèses étaient mal venues....

Soit E(n) le nb d'échanges.

On a E (2^n) = n. 2^(n-1)

Et aussi, cas général :
E(2n) = 2 * E(n) + n
E(2n+1) = E(n) + E(n+1) + (n+1)

Ainsi :
E(1) = 0
E(2) = 1
E(3) = 3
E(4) = 4
E(5) = 7
E(6) = 9
etc....

J'ai nettement moins que n*ln(n).
E(31) = 79 alors que 31 ln 31 = 106.

Oui en effet, et la méthode est on ne peut plus simple : on met les espions en cercle de 1 à n, les échanges se font alors de 1 à 2, puis 2 à 3...puis n-1 à n, puis n à 1, puis 1 à 2...jusqu'à n-2, et ça fait 2n-3 échanges.

Seuls les échanges par dichotomie sont plus performants pour E(4) = 4 au lieu de 5 en linéaire et E(8) = 12 au lieu de 13 en linéaire.

Je me suis fait bien avoir en faisant d'une généralité l'apparente efficacité de la dichotomie pour les petits nombres.

Effectivement. En prenant les impairs d'un bout à l'autre d'une part, les pairs d'un bout à l'autre d'autre part, on gagne 1 échange. ça marche avec un nb pair ou impair d'espions.

Donc 2n - 4 .

Très intéressant (j'avoue que je le connaissais déjà...)

On peut très facilement montrer que 2 appels de plus suffisent quand on augmente la taille du problème d'une personne
- un tout premier appel pour que le dernier espion appelle le 1er ==> son secret passe ensuite par tout le monde
- un tout dernier appel pour que le premier rappelle le dernier ==> il aura alors les secrets de tout le monde aussi
d'où une progression au pire linéaire.

Concernant une éventuelle borne sup, soyons bourrins: chacun appelle tous les autres, ça nous fait du n(n-1)/2

Pour une valeur exacte, pour les premières valeurs de N, on a
1 ==> 0
2 ==> 1
3 ==> 3
4 ==> 4
et à partir de là, deux appels de plus suffisent toujours donc
5 ==> 6
6 ==> 8
etc... donc plus généralement 2n-4


Pour la démonstration que 2n-4 appels suffisent, c'est bon.
Pour démontrer que 2n-5 appels ne suffisent pas, c'est moins simple.

Supposons qu'il existe N tel que le nombre d'appels soit <= 2N-5

Lemme 1: Après un appel, le fait de changer les deux espions dans tous les appels futurs ne change pas le résultat
Démonstration: puisque à ce moment précis, ils ont exactement les mêmes informations, il sont complètement indistincts et donc peuvent être échangés.
Plus généralement, si deux espions ont la même connaissance au même moment, le résultat reste valable

Lemme 2: Un même appel (A,B) intervient au plus une fois
Démonstration: s'il arrive 2 fois, ou plus, alors considérons le système suivant:
- A et B sont remplacés par A' (et idem pour leur secret)
- tous les appels (A,B) sont supprimés
- tous les appels avec A ou avec B sont remplacés par des appels avec A'
A tout moment, ce que connait A' est identique à ce que connaissaient A et B (au même moment), et la connaissance des autres espions est au moins égale à celle qu'ils avaient aussi au même moment.
Donc, on a un système avec N-1 espions, et au plus 2N-5-2 = 2(N-1)-5 appels nécessaire.
Par argument de la descente infinie, un tel cas n'existe pas.

Lemme 3: Avant un appel, les deux interlocuteurs n'ont aucune information en commun
Démonstration: supposons que A et B s'appellent, et que les deux connaissent déjà le secret de C. Alors:
- soit les deux l'ont appris, après une chaine d'information, d'un ancêtre commun (C ou un ancêtre plus récent, mais on notera C quand même)
- soit A l'a appris de B (directement ou pas)
Dans le premier cas, on a une chaine C -> A1 -> A2 -> ... -> A et une autre C -> B1 -> B2 -> ... -> B
On va supposer que l'appel (C,B1) a lieu après (C,A1), ça ne change rien au problème. D'après le lemme 1, on peut permuter (C,B1)(B1,B2)...(Bk,B) en (C,B1)(C,B2)...(Bk,B) etc... pour avoir à la fin (C,B)
On fait de même avec (C,A1)(A1,A2)(A2,A3)...(Ak,A) => (C,A1)(A1,A2)(A1,A3)...(Ak,A) => (C,A1)(A1,A2)(A1,A3)...(A1,A)
Et enfin l'appel (A,B) devient (A1,C), qu'on avait déjà en début de chaîne. Donc, d'après le lemme 2, ce cas est impossible.
Dans le second cas, c'est encore plus direct: (B,X1)(X1,X2)...(Xk,A) devient après permutations (B,X1)(B,X2)...(B,A), et ajouter un appel (A,B) est aussi contraire au lemme 2.

Corollaire 4: un espion ne reçoit pas son propre secret (puisqu'il le connait déjà)
Corollaire 4bis: l'appel qui apportera tous les secrets à un espion A est son dernier appel (sinon, il communiquera à son prochain interlocuteur B son propre secret)
Corollaire 4ter: un espion passe son dernier appel si et seulement si son interlocuteur aussi (puisque les deux ont la même connaissance à l'issue de l'appel)

Lemme 5: un espion passe son premier appel si et seulement si son interlocuteur aussi
Démonstration: soit (A,B) le premier appel de A, où il recevra le secret de B. Supposons que ça ne soit pas le premier appel de B, et que A reçoive aussi du coup le secret de C.
Désormais, l'espion A connait les secrets A et C, et l'espion B aussi. Plus important, personne d'autre ne connait le secret A.
A partir de là, toute propagation du secret A se fait avec le secret C (puisque tous ceux qui connaissent A connaissent C aussi).
De là, on en déduit que quand C connaîtra le secret de A, on lui rapportera son propre secret (absurde, cf corollaire 4)

Lemme 6: un tel N n'existe pas
Démonstration: on remonte la liste des appels, en partant de la fin, et on prend le premier appel en partant de la fin tel qu'il ne soit pas le dernier des 2 interlocuteurs concernés.
On va le noter (A,B) - techniquement, cela signifie qu'il y a un autre appel avec A ensuite, noté (A,C) et idem un autre appel (B,D) ensuite. D'après (4ter), il n'y a qu'un seul appel (A,C) et un seul (B,D)
D'après (3), la connaissance de A et C est complémentaire, idem pour B et D. Après l'appel (A,B), les deux ont la même connaissance ==> C et D ont la même connaissance aussi.
Deux options: il y a eu un appel (C,D); ou pas (dans ce cas, on applique le lemme 1, ce qui nous ramène au cas précédent mais ne changera pas le résultat).
De plus, ces 4 espions doivent bien avoir des premiers appels (avec X, Y, Z, T). D'après le lemme 5, ces 4 espions sont bien distincts (le premier appel de X correspond au premier appel de A, etc...)
On a donc (dans cet ordre là (logiquement, ou de manière arbitraire sans changer le problème) les appels (A,X),(B,Y),(C,Z),(D,T),*(C,D),(A,B),(A,C),(B,D)
Lorsqu'on arrive à l'étoile, X, Y, Z et T connaissent tous les secrets (puisqu'ils n'interviennent plus).
On peut donc considérer un autre système à N-4 espions, où A et X seraient remplacés par AX, idem BY, CZ et DT. Dans un tel système
- les 4 appels (A,X),(B,Y),(C,Z),(D,T) sont inutiles (espions fusionnés)
- les 4 appels (C,D),(A,B),(A,C),(B,D) sont inutiles (puisque après l'étoile)
Il faut donc au plus 2N-5-8 appels, soit 2(N-4)-5. Par le même argument de descente infinie que précédemment, on en déduit l'absurdité de l'existence de N.

Conclusion: il faut exactement 2n-4 au minimum pour tout n >= 4

Note: je répète que je connaissais déjà ce problème.
Le plus drôle c'est en fait la manière dont il m'avait été présenté la première fois:
- n espions communiquent n secrets, par mail (donc un expéditeur qui partage ses secrets avec un destinataire, mais pas l'inverse). Le résultat est alors de 2n-2
- idem, par téléphone, et là on est surpris de voir que seuls 2 appels sont économisés !!!

Bonjour,

caduk #1 a écrit:

Les conversations téléphoniques ne se font pas entre plus de deux espions. Deux conversations simultanées comptent pour deux appels.

(1) appelle simultanément (2) à (n), et répète tout ce qu'on lui dit. Tout le monde est au courant avec seulement n-1 appels.

Si ce subterfuge n'est pas validé, 2n-3 appels suffisent :
(1) appelle successivement (2) à (n) pour recueillir toutes les informations, puis (2) à (n-1) pour informer tout le monde.

Pour n=4, on peut faire mieux : 1-2, 3-4, 1-3, 2,4

À suivre…

Ajouté :
J'ai fait un script en python qui trouve un nombre de 2n-4 échanges pour n variant de 4 à 10. Je ne sais pas le démontrer, ni si c'est le minimum. Les espions sont ici numérotés de 0 à n-1.

n=4 
 4 échanges (0,1),(2,3),(1,2),(0, 3)

n=5
 6 échanges (3,4),(0,1),(0,2),(0,3),(2,4),(0,1)

n=6 
 8 échanges (0,1),(2,4),(1,5),(1,3),(3,4),(1,2),(0,3),(3,5)

n=7 
10 échanges (0,1),(2,6),(2,5),(0,3),(3,4),(3,5),(2,4),(1,4),(2,6),(0,2)

n=8 
12 échanges (2,3),(4,6),(0,5),(3,7),(3,6),(1,3),(0,3),(1,5),(1,6),(1,2),(2,4),(2,7)

n=9 
14 échanges (0,3),(6,7),(5,8),(1,2),(3,8),(1,4),(6,8),(1,8),(4,6),(0,1),(0,2),(1,5),(2,3),(4,7)

n=10 
16 échanges (4,9),(4,8),(1,5),(2,3),(6,8),(3,7),(0,7),(1,6),(1,7),(3,7),(2,7),(0,6),(5,7),(5,8),(7,9),(4,6)