J'ai trouvé aussi le nom de ce problème, et du même coup un PDF avec 3 preuves différentes. Celle que je donne est proche de la seconde, et celle que j'ai à moitié oubliée est la première

Il y a une belle formulation pour le maximum d'échanges (tous les échanges doivent être utiles pour au moins 1 des 2 correspondants).

Par contre, la version "mail", qui a pour réponse 2n-2 pour tout n, possède une démonstration très simple.

Spoiler : [Afficher le message]
* Il faut (n-1) mails pour qu'un secret arrive à l'ensemble des destinataires
* Un secret se propage uniquement à partir du moment où son détenteur envoie son premier mail.
* Le k-ème secret envoyé sera donc envoyé à partir du k-ème message a minima, donc le dernier secret sera précédé d'au moins n-1 messages, et suivi d'autant pour qu'il se propage.
Le minimum théoriqe est donc de 2n-2, qu'on atteint facilement, par récurrence, le nouvel espion envoie son secret à qui il veut, les autres se partagent la totalité des secrets, et ensuite le re-communique au nouvel espion, soit 2n-2 + 2 = 2(n+1)-2

J'ai ajouté des indices

Gwen
Je n'ai pas compris la deuxième partie de ta démo (Après le moment où tu as construit les N-2 permiers appels)

Sinon, pour tous, voici la démonstration que j'avais trouvé:

En partant d'un appel (X,Y) qui donne toutes les infos aux deux appelants, on peut construire un arbre d'appel en remontant aux fur et à mesure au précédents appels. On crée une arête entre X et Y, et on mémorise leur connaissance selon ce qu'il connaissait avant cet appel.
En remontant les appels en arrière, on rajoute les appels lorsque l'un des appels contient un et un seul sommet déjà relié. Si le sommet pas encore relié est en doublon dans d'autres branches, on le supprime pour garder une forme d'arbre (on ne perd rien car on à gardé le plus récent de ses appels.)
Comme ce n'est pas très clair, un exemple, en reprenant celui d'Ebichu:
12 ; 34 ; 45 ; 24 ; 15 ; 23.
Prenons l'appel 2-3
On trace un arête entre 2 et 3, 2 connaissait 1,2,3,4,5 et 3 connaissait 3 et 4 avant cet appel.
Comme 3 est déjà sur l'arbre, on le supprime de la mémoire de 2
On a l'arbre:
(2:1,2,4,5) -- (3:3,4)
En remontant les appels:
1-5: pas déjà dans les sommets reliés
2-4: 2 et relié, 4 non, on rajoute donc une arête entre 2 et 4, et on supprime 4 de la mémoire des autres branches.
(Ca ne fait rien de le supprimer de 3, car l'appel menant à 3 était plus vieux, et donc apprenait moins)
4 connaissait 4 et 5 avant cet appel, 2 connaissait 2 et 1.
On a donc l'arbre suivant:
(4:4,5) -- (2:1,2) -- (3:3)
4-5: on obtient l'arbre suivant:
(5:5) -- (4:4) -- (2:1,2) -- (3:3)
3-4: déjà tout les deux sur l'arbre
1-2: On obtient finalement l'arbre
(5:5) -- (4:4) -- (2:2) -- (3:3)
                           |
                         (1:1)

On remplace finalement chaque sommet par l'ensemble des secrets qu'il apprend en passant ces tout ces appels dans l'ordre chronologique, on obtient:
(5:4,5) -- (4:4,5) -- (2:1,2,3,4,5) -- (3:1,2,3,4,5)
                                    |
                               (1:1,2)
On a donc N - 1 appels pour l'instant. Chaque série d'appels contient au moins un arbre de ce type.
On cherche à savoir s'il est possible d'ajouter N - 4 arêtes (ou moins) pour que tout le monde sache tout.
Si une solution est trouvée avec des appels passés avant le N - 1 ème appel de l'arbre, on peut trouver une solution de même cardinalité en décalant ces appels après (en conservant l'ordre de tout les appels autre que ceux sur l'arbre). En effet, plus ces appels seront reculés, plus ils apprendront des secrets.
Soit A cet arbre, et G le graphe de tout les appels.
Considérons G - A le graphe constitué de tout les appels de G qui ne sont pas dans A. Ce graphe peut être non connexe.
Considérons une partie connexe: Sur l'ensemble des espions présents dans ce graphe, tous doivent recevoir toutes les informations, car ces sommets ne sont présent dans aucune autre partie connexe (car comme les autres parties ne sont pas connexes avec celle là, elles n'ont pas de sommets en commun).
On a donc comme prérequis que la mémoire des sommets de ce graphe doit couvrir tout les espions.
Dans notre exemple, si notre partie connexe repose sur les sommets des espions 1 et 3, comme {1,2} U {1,2,3,4,5} = {1,2,3,4,5}, il est possible qu'une partie connexe repose seulement sur ces deux sommets.
Par contre, il ne peut pas y avoir une partie connexe qui repose uniquement sur 1 et 5, car dans ce cas, ni 1 ni 5 n connaitront jamais le secret de 3.

Cherchons s'il est possible de trouver une partie connexe sur n espions (excepté les deux qui ont déjà toutes les informations) qui comporte moins de n arêtes:
Il faudra au minimum n - 1 arête pour informer un espions, et il en faudra encore 1 de plus si il y a 3 espions indépendant (c'est à dire que chacun à de l'info que les autres ne connaissent pas).
En effet, si il y à p > 3 espions indépendants, la manière minimale de procéder est 2p - 4, car on peut se ramener à un sous problème en considérant chaque espion indépendant comme un nouvel espion. 

Pour reprendre l'exemple, si l'on prend l'arbre
(5:4,5) -- (4:1,2, 4,5) -- (2:1,2,3,4,5,6) -- (3:1,2,3,4,5,6) -- (6:3,6)
                                    |
                               (1:1,2)
Les espions 5, 6 et 1 ne sont pas indépendant. Si l'on considère une partie connexe sur ces 3 espions, comme chacun connait un secret que personne d'autre n'a, il faudra donc minimum 3  arêtes pour partager leur secret.
Les espions 4,6,1 ne sont pas indépendants, on peut donc se ramener à 4 et 6 indépendants. On peut alors propager le secret en seulement 2 appels: 6-4 puis 6-1
Si la partie connexe contient un espion connaissant tout, cela ne changera pas le nombre minimal possible.

La seule manière de faire moins est donc d'avoir une partie connexe tel qu'il n'y a que deux espions indépendants. Cela n'est possible qu'une seule fois, car ces deux espions doivent connaitre à eux deux tout les secrets, ce sont donc les deux derniers à avoir appelés les espions à la racine de l'arbre.

On déduit donc que comme pour chaque partie à n espions, il faut n appels, on gagne donc encore 1 appels par espion soit n-2 (moins les deux connaissant déjà tout)
et on gagne aussi un appel si on obtient une partie connexe avec deux espions indépendant.
Le minimum est donc 2n - 4.

Bon, ça m'a pas l'air très clair, j'espère que vous comprendrez...