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
[+]

 #26 - 21-11-2017 11:14:55

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1552

Le jeu es espions

J'en connais plusieurs également. Celle là a le mérite de ne pas faire entrer de gros mots dedans smile
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 big_smile
Mais sinon, la descente infinie est un argument qui reprend aussi la récursion (mais par l'absurde)

#0 Pub

 #27 - 21-11-2017 14:19:36

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1552

le jeu des zspions

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 jeu ds 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 : 3263

Le je udes 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 : 241

Le jeu des epsions

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 : 1552

Le je udes espions

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,717E+3

Le jjeu des espions

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 : 241

Le jeu dees espions

J'ai ajouté des indices

 #34 - 25-11-2017 18:47:36

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 530

Le jeu des sepions

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.

http://www.prise2tete.fr/upload/Ebichu-gossip.png

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 : 241

me jeu des 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 : 530

Le je des 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.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

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

Sujets similaires

Sujet Date Forum
02-02-2014 Enigmes Mathématiques
P2T
Echecs 8 par Vasimolo
05-03-2011 Enigmes Mathématiques
P2T
Passera, passera pas ? par Alexein41
24-01-2011 Enigmes Mathématiques
P2T
L'indice de l'air par nodgim
15-10-2016 Enigmes Mathématiques
P2T
Bonne année ! par scrablor
01-01-2012 Enigmes Mathématiques
P2T
P2tcraft par Clydevil
10-05-2011 Enigmes Mathématiques
P2T
Gâteau 141 par Vasimolo
12-08-2017 Enigmes Mathématiques
P2T
5=9 (aide) par Caroee91
07-07-2012 Enigmes Mathématiques
P2T
Divisibilité par perceval
07-05-2008 Enigmes Mathématiques

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