Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

Écrire une réponse

Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide !
Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci.
Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Options
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Retour

Résumé de la discussion

caduk
18-11-2017 17:27:58

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.

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete