Bonjour,

Une énigme librement plagiée sur celle qui avait été proposée sur  "l'île des mathématiques" (juin 2014)

N espions possèdent chacun un secret différent, et leur but est de se communiquer leurs secrets, de manières à ce que chaque espion connaisse chacun des secrets. Pour ce faire, il procèdent par appels téléphoniques, durant lesquels deux espions se partagent tout les secrets qu'ils possédaient avant l'appel. Les conversations téléphoniques ne se font pas entre plus de deux espions. Deux conversations simultanées comptent pour deux appels.

L'objectif est de trouver le nombre minimal d'appels (en fonction de N) pour que chaque espion connaisse tout les secrets.

Exemple: si il y a 5 espions 1,2,3,4,5, qui possèdent les secret s1, s2, s3, s4, s5 (1 connait uniquement s1, 2 connait uniquement s2, ...)
Ainsi, si 1 et 2 se téléphonent, tout deux connaitront s1 et s2
Ensuite, si 1 et 3 se téléphonent, ils connaitront tout les deux s1, s2 et s3 (mais 2 ne connaitra toujours que s1 et s2)
Si ensuite 1 téléphone à 4 puis à 5, puis re-téléphone à 2,3 et 4, tous les espions connaitront tous les théorèmes


1) Une borne supérieure avait été prouvée assez facilement, saurez vous la retrouver?

2) Peut on trouver et démontrer la valeur exacte du nombre minimal d'appels nécessaires?

Si c'est trop dur, j'ajouterai des indices
--------------------------------------------------------------------------------------------
Voici deux indices, chacun donne une piste pour une résolution différente, la première est celle de Scarta, la deuxième est la mienne.

Indice1
Spoiler : [Afficher le message] On peut procéder par l'absurde en supposant qu'il existe en solution en 2n-5 appels, et démontrer qu'il n'est pas possible qu'un espion apprenne son secret de par un autre espion

Indice 2
Spoiler : [Afficher le message] Pour une solution donnée, à partir d'un espion ayant reçu tout les indices, il est possible de construire un arbre d'appels qui indique comment les secrets se sont propagés jusqu'à lui. On peut alors montrer qu'il 'existe pas de moyen de compéter l'arbre avec d'autres appels en moins de 2n-4 appels, en faisant apparaitre un récurrence forte.