Inscription / Connexion Nouveau Sujet

1 2 +


Posté par
LeDino
re : Joute n°149 : Les 007 espions 01-07-14 à 22:24

gagnéJoli schéma .

J'ai regardé les configurations en  n = 2^k  parce qu'elles me semblaient éventuellement prometteuses pour un meilleur optimum que  2n-4. Mais pas du tout. Ce n'est pas ça qui prouve quoi que ce soit, mais du coup mon intuition à changé de camp ...

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

gagnéJe pense que tu as suivi le même raisonnement que moi...
Je pensais améliorer pour n=8, mais je n'ai pas réussi!
Pourtant, je pensais également qu'on pourrait améliorer...

Posté par
Cpierre60
re : Joute n°149 : Les 007 espions 02-07-14 à 15:23

gagnéBonjour à tous,
Pour ma part, j'avais surtout voulu dire que je n'étais pas convaincu par la démonstration qui passait de condition suffisante à nécessaire abusivement.
Pour me faire comprendre, j'avais cherché à introduire un doute !
J'ai cherché (je cherche encore) à démontrer, par exemple par l'absurde, que "2n-3 est impossible", ce qui en complément de "2n-4 suffisant" bouclerait le dossier, mais, plus difficile à faire qu'à dire !
Profitons-en pour remercier les initiateurs de ces énigmes qui nous obligent à faire fonctionner nos cerveaux, au-delà de ce qu'ils s'imaginent, j'en suis persuadé.

Posté par
Cpierre60
re : Joute n°149 : Les 007 espions 02-07-14 à 16:17

gagné

Citation :
J'ai cherché (je cherche encore) à démontrer, par exemple par l'absurde, que "2n-3 est impossible", ce

Merci de lire "2n-5" et non pas 2n-3...erreur grossière, mais vous aviez rectfié !

Mon idée est de remonter.

Si à l'issue du (2n-5) ème échange, tout le monde sait tout, nécessairement au coup d'avant on avait telle ou telle situation, donc auparavant ...pour arriver à un niveau où c'est manifestement impossible.

Posté par
JOKERISWALID
Pk n-2 04-07-14 à 13:34

moi j'ai trouvé 11
mais apparemment la bonne réponse c'est 10
quelq un peux m'explique le truc de n-2

Posté par
weierstrass
re : Joute n°149 : Les 007 espions 04-07-14 à 15:21

gagnéIl suffit de regarder les réponses de ceux qui ont obtenu un smiley, la solution qu'ils proposent résout le problème en 10 appels.

On peut démontrer facilement que pour n espions, on peut résoudre ce problème en 2(n-2) = 2n-4 appels, avec n4.( voir post du 29/06/14 à 13h28, et celui du 01/07/14 à 20h03,
pour voir deux démonstrations différentes)
Pour 7 espions, on sait donc que l'on peut trouver des solutions pour 2(7)-4 = 10 appels

Sauf que l'on ne sait pas si ce résultat de 2n-4 appels est le minimum, la question est donc soit de démontrer que pour plus de 4 espions, on ne peut pas résoudre le problème en moins de 2n-4 appels, soit de trouver une solution en moins de 2n-4 appels, et dans ce cas, trouver une formule qui généralise ce minimum (si c'est possible).

Posté par
LeDino
re : Joute n°149 : Les 007 espions 04-07-14 à 16:32

gagné

Citation :
quelqu'un peux m'expliquer le truc de n-2

Quand on cherche à généraliser le problème en considérant n  agents détenant chacun un secret, il existe une solution "naïve" c'est à dire très simple, qui permet de distribuer tous les secrets à tous les agents en  N = 2n - 3  appels.
Il suffit pour cela que dans un premier temps un agent appelle tous les autres pour collecter tous les secrets (donc n-1 appels), puis dans un deuxième temps qu'il rappelle tout le monde (sauf le dernier appelé) pour "distribuer" l'intégralité des secrets (donc n-2 appels).
Dans ce cas on a bien les  n  secrets distribués aux  n  agents en  N=2n-3  appels.

Dans son post de du 01-07-14 à 20:03, weierstrass a montré une solution encore meilleure, qui garantit la distribution en N = 2n-4 appels. Dans sa solution l'agent n°1 appelle les agents 2 à n-1. Et l'agent n appelle parallèlement et dans l'ordre inverse, les agents n-1 à 2.
En procédant ainsi, il y a au total N = (n-2) + (n-2) = 2n-4 appels...
... et on constate que les secrets sont intégralement distribués (parce que lorsque l'un des deux "agents appelants" (le n° 1 et le n°n) appelle un agent que l'autre a déjà appelé... tous les secrets sont mis en commun.

Voici le schéma des appels (avec l'ordre qui est important) :

Joute n°149 : Les 007 espions

La question qui demeure est la suivante :
Grâce à la solution directe de Wierstrass (ou grâce à une démonstration par récurrence comme celles qui ont été évoquées dans la discussion), on a la preuve d'une conjecture "faible", qui est que l'optimum est au pire égale à  2n - 4. Il reste donc la conjecture "forte" à prouver, à savoir que l'optimum est exactement et tout le temps égale à  2n-4.

Posté par
LeDino
re : Joute n°149 : Les 007 espions 04-07-14 à 16:34

gagnéBonjour Weierstrass,

J'ai été interrompu dans la rédaction de mon message... que j'ai de ce fait posté en différé et "en aveugle", sans savoir que tu avais répondu entre temps ...

Posté par
JOKERISWALID
re : Joute n°149 : Les 007 espions 04-07-14 à 19:01

Citation :
Quand on cherche à généraliser le problème en considérant n  agents détenant chacun un secret, il existe une solution "naïve" c'est à dire très simple, qui permet de distribuer tous les secrets à tous les agents en  N = 2n - 3  appels.
Il suffit pour cela que dans un premier temps un agent appelle tous les autres pour collecter tous les secrets (donc n-1 appels), puis dans un deuxième temps qu'il rappelle tout le monde (sauf le dernier appelé) pour "distribuer" l'intégralité des secrets (donc n-2 appels).
Dans ce cas on a bien les  n  secrets distribués aux  n  agents en  N=2n-3  appels.

Dans son post de du 01-07-14 à 20:03, weierstrass a montré une solution encore meilleure, qui garantit la distribution en N = 2n-4 appels. Dans sa solution l'agent n°1 appelle les agents 2 à n-1. Et l'agent n appelle parallèlement et dans l'ordre inverse, les agents n-1 à 2.
En procédant ainsi, il y a au total N = (n-2) + (n-2) = 2n-4 appels...
... et on constate que les secrets sont intégralement distribués (parce que lorsque l'un des deux "agents appelants" (le n° 1 et le n°n) appelle un agent que l'autre a déjà appelé... tous les secrets sont mis en commun.
Grand merci pour cela

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 !