|
#26 - 21-11-2017 11:14:55
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
le jeu des esoions
J'en connais plusieurs également. Celle là a le mérite de ne pas faire entrer de gros mots dedans Sinon, tu peux repartir de mes (4ter) et (5) pour dire que N/2 appels sont les premiers, N/2 sont les derniers, et entre les deux, on a au plus N-5 appels, qui sont autant d'arêtes entre N nœuds, autrement dit une répartition en 5 sous-graphes disjoints minimum... et j'ai plus la suite Mais sinon, la descente infinie est un argument qui reprend aussi la récursion (mais par l'absurde)
#27 - 21-11-2017 14:19:36
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
le jeu drs espions
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
#28 - 21-11-2017 17:16:04
- zobizob
- Amateur de Prise2Tete
- Enigmes résolues : 1
- Messages : 8
Le jjeu des espions
Si un espion appelle tous les autres puis les rappelle ensuite une deuxième fois, à l'exception du dernier qui savait déjà tout à l'issu du premier appel, tout le monde est au courant des secrets des autres. Une borne supérieure est donc 2n-3 Pour établir une borne inférieure on peut construire le graphe dont les sommets sont les espions et tel que deux sommets sont adjacents s'ils se sont téléphoné au moins une fois. Ce graphe est nécessairement connexe et possède donc au moins n-1 sommets. On peut raffiner la borne supérieure pour n=4 avec 4 appels suffisants et n=8 avec 12 appels suffisants. Juste pour savoir, la question 2) est une question ouverte ou il y a une réponse ?
#29 - 21-11-2017 18:46:01
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Le jjeu des espions
Il y a une belle formulation pour le maximum d'échanges (tous les échanges doivent être utiles pour au moins 1 des 2 correspondants).
#30 - 22-11-2017 00:06:18
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
Le jeu es espions
zobizob Tes remarques sont bonnes, tu peux encore un petit peu creuser la borne supérieure, regarde par exemple l'optimum pour N = 5. Il faut ensuite démontrer l'optimalité de cette borne. La question 2 n'est pas ouverte, Ebichu et Scarta connaissaient le problème et Scarta a apporté une preuve. Le problème n'est pas insurmontable puisque j'ai moi même réussi à trouver une preuve (pas forcément la plus simple).
#31 - 22-11-2017 10:33:48
- scarta
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1960
le jeu des rspions
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
#32 - 23-11-2017 18:34:30
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,969E+3
Le jeu des epsions
Un petit essai simpliste (peut-être un peu trop, mais ça a l'air de fonctionner... ) :
Quelques constats :
Constat 1 : Lors de la « montée » d'informations, à la conversation X, il y a au maximum 2 interlocuteurs ayant X+ 1 informations en leur possession.
Constat 2 : Si le cas se présente, ces deux interlocuteurs possèdent exactement les mêmes informations.
Constat 3 : On ne peut obtenir 2 informations complètes à l'issue d'une conversation que si un des interlocuteurs la possède déjà ou si leurs informations sont complémentaires.
Le moment clé est celui ou cette situation se présente la première fois, c'est à dire quand 2 interlocuteurs ou plus possèdent des informations complémentaires.
« X » U « Y » = info complète. Cela a nécessité au minimum N-2 conversations.
A ce moment précis, aucun d'entre eux ne possède la totalité des informations. A ce moment, chacun a besoin d'une conversation au moins si c'est avec avec un complémentaire . Avant ce moment précis, aucun couple ne pouvait le faire.
Tout se passe entre 2 conversations avant ce moment-là (la première ne suffisant pas) et 2 conversations après.
Les deux précédentes peuvent se passer entre 3 ou 4 personnes. Idem pour les suivantes. On est à N-1 conversations au moins.
Si les premières se passent entre 3 personnes :
A et X , A et Y ne mène à rien de constructif, l'une est inutile.
A et X , B et X : On a donc B et X qui ont la même somme d'info. On peut faire B et Y ou X et Y. Il aura fallu 4 conversations pour les 3 premiers informés. Aucun autre couple ne peut disposer d'une info complète sans parler à B, X ou Y. On se retrouve dans la situation intitiale. Il faudra 3 conversations de plus pour informer 3 personnes sans recours à nos trois informés. Ils auraient pu faire aussi bien. Il manque N-3 conversations. Ce n'est pas optimal.
Donc, les deux conversations d'avant engagent 4 personnes.
A et X , B et Y. Les deux premiers possèdent donc la même somme d'infos, comme les deux seconds. On est à N-1 conversations mais on gagne une conversation s'ils se parlent respectivement par la suite. On obtient 4 informés en 4 conversations.
La suite est similaire. Hormis A, B, X et Y , on se retrouve dans la situation initiale. Reproduire la même situation est possible, mais devient inutile car les 4 premiers peuvent faire le même travail.
On a un minima de 2N-4 conversations. Toutes les possibilités d'échange on été étudiées.
#33 - 23-11-2017 19:16:11
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
#34 - 25-11-2017 18:47:36
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
le jeu drs espions
Voici la façon que j'ai de représenter le problème. Je donne un exemple avec 5 espions, avec les appels 12 ; 34 ; 45 ; 24 ; 15 ; 23.
Pour savoir quels sont les secrets connus de l'espion n° k, on part du sommet k en bas du graphe, puis on regarde quels sont les sommets du haut que l'on peut rejoindre en se déplaçant toujours vers le haut ou à l'horizontale.
Cette représentation permet de tout de suite justifier la réversibilité (comme 12 ; 34 ; 45 ; 24 ; 15 ; 23 résout le problème, alors 23 ; 15 ; 24 ; 45 ; 34 ; 12 également), ou d'autres propriétés, comme "12 puis 34 est équivalent à 34 puis 12". Mais elle ne m'a pas permis de trouver une preuve simple du résultat.
J'aime aussi la visualisation du problème sous forme de matrices évoquée au début de l'article de Tijdeman.
#35 - 26-11-2017 18:32:37
- caduk
- Professionnel de Prise2Tete
- Enigmes résolues : 45
- Messages : 398
Le jeu ddes espions
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...
#36 - 26-11-2017 20:10:42
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
le jeu ded espions
Je ne suis pas allé au bout de ta preuve, j'ai déjà deux questions avant d'aller plus loin :
(5:4,5) -- (4:4,5) -- (2:1,2,3,4,5) -- (3:1,2,3,4,5) | (1:1,2)
Ce ne serait pas plutôt : (5:4,5) -- (4:1,2,4,5) -- (2:1,2,3,4,5) -- (3:1,2,3,4,5) | (1:1,2)
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).
Je ne comprends pas. En reprenant mon exemple, ça donnerait que : 12 ; 34 ; 45 ; 24 ; 15 ; 23 deviendrait : 12 ; 45 ; 24 ; 23 ; 34 ; 15 en décalant ces deux appels après. Mais dans cet ordre, ces 6 appels ne font pas une solution, car alors l'espion numéro 5 ne connaitrait pas le secret du numéro 3.
|
|