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

 #1 - 19-03-2018 10:41:51

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 883
Lieu: Seahaven island

Grraphe de clones

Hello les gens!

https://img.huffingtonpost.com/asset/59ce6237200000c0070844b2.jpg

Le docteur Evil a encore frappé avec ces tortures particulièrement raffinées:
Il vous a capturé et vous explique ce qui va se passer. Dans quelques heures, il va réaliser un certain nombre de clones de vous même. Au moment du clonage vous serez endormi et votre mémoire sera intégralement copiée, vous serez donc physiquement et mentalement indiscernable. Chacun des vos clones ainsi que la version originale de vous même se réveilleront dans une pièce (une pièce par clone). Dans chaque pièce se trouvera un certain nombre de téléphones permettant chacun d'appeler un autre clone dans une autre pièce, ainsi qu'un téléphone spécial pour contacter Dr Evil. Bien sur lorsqu'on dispose d'un téléphone pour communiquer d'une pièce A à une pièce B alors on dispose d'un téléphone pour communiquer en retour de la pièce B à la pièce A. Ainsi le Dr Evil construit un réseau de clones dont il est le seul à connaitre la structure mais il vous assure que se réseau est connexe (qu'il existe bien une chaîne possible de téléphones de n'importe quelle pièce à n'importe quelle autre). Enfin le Dr Evil vous précise que dans chaque pièce il y a au sol un numéro de série unique (personne ne dit que les numéros de séries commencent à 1 ni ne se suivent, on sait juste qu'ils sont uniques)

Pour être libéré il faudra qu'au moins l'un d'entre vous utilise le téléphone spécial pour appeler Dr Evil (rappel: il y a un téléphone spécial par pièce) et lui annoncer avec certitude combien vous êtes au total dans son réseau, toute erreur sera fatale.

Vous ne disposerez de rien de pratique pour prendre des notes dans les pièces, il ne vous reste que quelques heures pour mettre au point une stratégie que vous pourrez appliquer de manière réaliste avec seule votre mémoire (il va sans dire que tous vos clones et vous même se souviendront de la stratégie mise au point à leur réveil).

Bonne chance!



merci à tous les participants! et donc une solution:


Spoiler : [Afficher le message]
Il y a plusieurs aspect au problème, l'un est juste de réaliser le comptage, l'autre est de pouvoir briser la symétrie qu'il existe au départ entre les clones.
Si on suppose dans un premier temps que la symétrie est brisée, par exemple que les clones sont au départ au courant que l'un d'entre eux sera mis dans une salle au murs rouges et sera le seul dans ce cas, alors il suffit qu'ils se mettent d'accord pour que ça soit cet individu spécial qui réalise le comptage. Pour réaliser le comptage c'est en fait assez simple: l'individu spécial appelle tous ces voisins et leur demande de se compter puis de nous rappeler avec le résultat. Lorsqu'on nous demande de nous compter ça revient à appeler nous même tous nos voisins, à leur demander de se compter, à sommer tout, ajouter 1 (nous même) et à rappeler celui qui nous avait demander de faire cette tache. Pour éviter de compter plusieurs fois des gens par différents chemins, il suffit en fait que les gens à qui on demande de se compter et qui sont déjà en train de faire une tache de comptage (ou l'ont terminé) répondent juste 0. Ainsi on va bien compter tout le monde une fois, avec un comptage qui suivra un arbre, inclus dans le graphe total, grossissant depuis l'initiateur du processus.
Maintenant comment briser la symétrie: on va enrichir un peu ce protocole de comptage en transmettant pendant celui l'identifiant du clone qui a fait naître cette demande de comptage, c'est à dire que si un certain ID nous demande "comptez vous" alors on donnera ce même ID aux voisins à qui on demandera la même chose. Il y aura ainsi un ID par processus de comptage. Ensuite, si on demande à un clone soit qui ne fait rien, soit qui compte déjà (ou a fini) avec un ID plus élevé que celui qu'on lui donne, alors il arrête tout ce qu'il fait, et commence un processus avec le nouvel ID comme si on lui avait jamais rien demander avant. Au départ tous le monde lance un processus de comptage, mais le processus de comptage avec le plus faible identifiant, va petit à petit tuer tous les autres processus de comptage qui n'aboutiront jamais, puis terminer, et le clone dans la salle de plus faible ID, qui sera le seul a avoir vu son processus aboutir, pourra appeler Dr Evil pour lui communiquer le résultat. Voila voila.
Niveau mémoire, les clones sont libres de passer les appels à un rythme qu'ils peuvent gérer, à tout moment ils ont en mémoire:
-l'identifiant de leur processus en cours.
-la somme partielle du processus en cours.
-le téléphone qui leur a ordonné de faire un comptage.
-le status de chaque autre téléphone (déjà appelé et en train de compter/comptage fini/pas encore appelé)
Et devront avoir encore un peu de cerveau dispo pour ajouter à leur compte les résultats qu'on leur communique, ou comparer leur ID à un autre lorsqu'on les appelle. Ce qui est très réalisable et surtout indépendant de la taille du graphe total.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 19-03-2018 12:00:30

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3556

graphe de ckones

On peut par exemple mettre en place cette stratégie, établie par le plus rapide qui l'adopte : il se désigne A et appelle un clone au hasard qu'il bâptise B et lui explique que le prochain qu'il appellera sera bâptisé C et devra expliquer à son tour cette stratégie au prochain.

Chacun des appelés appelle :
-un supposé nouveau (si déja bâptisé, recommence avec un autre) et lui explique la stratégie.
-un autre clone, s'il existe, lorsque le 1er qu'il a bâptisé dit qu'il a fini sur une lettre x. Désigne alors par la lettre suivante cet autre clone qui ne le rappelera à son tour que lorsque il aura fini.
- quand plus aucun clone à appeler, rappelle celui qui l'a bâptisé en indiquant la dernière lettre en cours.
Ainsi A recevra au bout d'un certain temps un appel de B qui lui indiquera la dernière lettre en cours. Et A procède comme ci-dessus jusqu'à qu'il n'ait plus aucun correspondant non bâptisé.

Bien sûr, s'il y a plus de 26 clones, à Z on reprend à AA, puis si nécessaire AAA...

 #3 - 19-03-2018 13:48:35

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 883
Lieu: Seahaven island

graphe de xlones

@nodgim: L’établissement de la stratégie peut se faire (et a priori doit se faire) avant le clonage, et au réveil tout le monde s'en souviendra. Baser la stratégie sur "le plus rapide à commencer" ne marchera pas, car rien empêche qu'a des endroits relativement opposés du réseau deux personnes commencent a faire la même chose.

 #4 - 20-03-2018 08:04:47

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3556

Grahe de clones

C'est à peine plus compliqué.

Stratégie :

-Chacun se désignera par le n° de sa pièce p et son rang r. r = 1 pour tous au départ.

-Chacun sera amené à appeler un seul correspondant (provisoirement). Tout clone appelé prendra le p de son correspondant si celui ci est inférieur au sien. il prendra alors le rang r+1 si ce correspondant est au rang r.Tout clone appelant qui aura un correspond de p < au sien propre cesse toute activité jusqu'à nouvel appel. Un contact non attendu entre 2 clones de même pièce p sera ignoré.   

-La chaine de plus petit p s'établira donc ainsi : un appelant lui a donné son p et son r. Il appelle à son tour un correspondant en lui transmetttant p et et r+1. Il devient alors dormant. Il n'appelle plus tant qu'il ne reçoit pas un retour de (p, r+1) qui lui indiquera un n° r ' >= r+1. Le dormant redevient actif alors en appelant un correspondant différent de r' et r-1, en lui transmettant p et r'+1.

-Un dormant recevant tout autre appel ne donne que son n° p pour faire cesser l'activation si l'appelant est d'un p > au sien propre. Si le p est  < au sien propre, il oublie son propre réseau pour prendre possession du nouveau.

-Un dormant devra donc mémoriser son appelant  (p r-1) et ne le rappeler que lorsqu'il aura fait l'appel de tous les autres. Il lui transmet alors le rang qui lui aura été communiqué.

-C'est donc le dormant de plus petit p et de plus petit rang ( = 1 ) qui sera le seul à communiquer le nombre de clones.

 #5 - 20-03-2018 09:24:40

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 883
Lieu: Seahaven island

graphe de clobes

@nodgim: Pas facile à suivre mais ça semble correct smile Bravo. C'est une version "profondeur", il y a aussi une version "largeur" si les clones sont plus impatients.

 #6 - 21-03-2018 06:48:25

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3556

Graphe d eclones

Oui, je comprends la version "largeur" où là chaque appelé du réseau survivant appelle tous les autres. C'est juste un peu plus délicat à gérer, et il faut savoir faire des additions.

 #7 - 23-03-2018 14:45:57

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 883
Lieu: Seahaven island

graphe de clpnes

Ha c'est plus ce que c’était P2T, moins de monde ou alors ils sont plus mous! (ou ce que je propose est soit trop dur soit trivial) Qq indices avant la fin:
Spoiler : [Afficher le message]
Il y a deux aspects du problème à adresser:
-Comment une personne seule qui voudrait compter les gens devrait procéder.
-Comment élire initialement une telle personne.

 #8 - 23-03-2018 17:52:44

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 669

Graphe de clnoes

J'ai tenté d'y reflechir sans succés sad

J'ai une heure de route, j'aurais peut-etre l'illumination !

 #9 - 23-03-2018 19:08:14

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,818E+3

Grapphe de clones

Ou peut-être que ça n'intéresse qu'un public très restreint... et que les autres ont fui ce site qui est ces derniers temps quasiment intégralement consacré aux énigmes mathématiques que seul 3 ou 4 membres suivent, parfois.

 #10 - 27-03-2018 16:39:42

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 883
Lieu: Seahaven island

Graphe de cloes

Hello, merci à tous les participants! et donc une solution:

Spoiler : [Afficher le message]
Il y a plusieurs aspect au problème, l'un est juste de réaliser le comptage, l'autre est de pouvoir briser la symétrie qu'il existe au départ entre les clones.
Si on suppose dans un premier temps que la symétrie est brisée, par exemple que les clones sont au départ au courant que l'un d'entre eux sera mis dans une salle au murs rouges et sera le seul dans ce cas, alors il suffit qu'ils se mettent d'accord pour que ça soit cet individu spécial qui réalise le comptage. Pour réaliser le comptage c'est en fait assez simple: l'individu spécial appelle tous ces voisins et leur demande de se compter puis de nous rappeler avec le résultat. Lorsqu'on nous demande de nous compter ça revient à appeler nous même tous nos voisins, à leur demander de se compter, à sommer tout, ajouter 1 (nous même) et à rappeler celui qui nous avait demander de faire cette tache. Pour éviter de compter plusieurs fois des gens par différents chemins, il suffit en fait que les gens à qui on demande de se compter et qui sont déjà en train de faire une tache de comptage (ou l'ont terminé) répondent juste 0. Ainsi on va bien compter tout le monde une fois, avec un comptage qui suivra un arbre, inclus dans le graphe total, grossissant depuis l'initiateur du processus.
Maintenant comment briser la symétrie: on va enrichir un peu ce protocole de comptage en transmettant pendant celui l'identifiant du clone qui a fait naître cette demande de comptage, c'est à dire que si un certain ID nous demande "comptez vous" alors on donnera ce même ID aux voisins à qui on demandera la même chose. Il y aura ainsi un ID par processus de comptage. Ensuite, si on demande à un clone soit qui ne fait rien, soit qui compte déjà (ou a fini) avec un ID plus élevé que celui qu'on lui donne, alors il arrête tout ce qu'il fait, et commence un processus avec le nouvel ID comme si on lui avait jamais rien demander avant. Au départ tous le monde lance un processus de comptage, mais le processus de comptage avec le plus faible identifiant, va petit à petit tuer tous les autres processus de comptage qui n'aboutiront jamais, puis terminer, et le clone dans la salle de plus faible ID, qui sera le seul a avoir vu son processus aboutir, pourra appeler Dr Evil pour lui communiquer le résultat. Voila voila.
Niveau mémoire, les clones sont libres de passer les appels à un rythme qu'ils peuvent gérer, à tout moment ils ont en mémoire:
-l'identifiant de leur processus en cours.
-la somme partielle du processus en cours.
-le téléphone qui leur a ordonné de faire un comptage.
-le status de chaque autre téléphone (déjà appelé et en train de compter/comptage fini/pas encore appelé)
Et devront avoir encore un peu de cerveau dispo pour ajouter à leur compte les résultats qu'on leur communique, ou comparer leur ID à un autre lorsqu'on les appelle. Ce qui est très réalisable et surtout indépendant de la taille du graphe total.

 #11 - 27-03-2018 23:31:32

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,167E+3

Graphe de clonse

gwen27 a écrit:

Ou peut-être que ça n'intéresse qu'un public très restreint... et que les autres ont fui ce site qui est ces derniers temps quasiment intégralement consacré aux énigmes mathématiques que seul 3 ou 4 membres suivent, parfois.

Je crois qu'il ne faut pas se faire d'illusions , l'ensemble des énigmes du site concerne un public très restreint et je ne pense pas ( bien au contraire ) que les énigmes mathématiques ont fait fuir les intervenants de P2T . Si de nombreux participants réguliers ont préférés migrer vers d'autres sites ( un en particulier ) ce n'était pas pour fuir les mathématiques ( toutes les rubriques restent ouvertes ici ) . Nous sommes nombreux à participer à plusieurs sites ( moi le premier ) , après on peut choisir de proposer une énigme ici de temps en temps ou réfléchir à une autre ou encore laisser délibérément mourir le site .

Vasimolo

 #12 - 28-03-2018 07:20:38

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1461
Lieu: Coutiches

Graphe de lcones

Je lis les énoncés avec intérêt, mais (comme pour celui-ci par exemple), je n'aboutis souvent pas... et je ne poste donc pas. hmm
Ceci dit, je suis resté avec le problème de départ : Comment faire pour qu'un moi-même plutôt qu'un autre prenne l'initiative. N'en trouvant pas, j'étais parti avec l'idée qu'il ne fallait pas utiliser ce moyen là, j'ai donc été un peu déçu en lisant le coup de la pièce rouge...
De même en lisant la méthode, j'aurai probablement besoin d'un petit calepin quand même pour noter tous les chiffres, au risque qu'un moi-même ne se plante désastreusement.
L'absence de note me laissait penser que la solution serait plus astucieuse et moins "lourde".
Intéressante énigme malgré tout ! (Mais (un peu ?) trop compliquée pour mon petit cerveau...)

 #13 - 28-03-2018 08:20:28

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 883
Lieu: Seahaven island

Graphe ed clones

@golgot59: " j'ai donc été un peu déçu en lisant le coup de la pièce rouge..."
Il n'y a pas de pièce rouge dans la solution, je ne parle de cela que pour faciliter la compréhension de la suite et ne traiter que de l'aspect comptage d'abord. Bien sur que dans la vrai solution, détaillée ensuite, les individus n'ont pas de moyen de se différencier et doivent tous commencer un comptage et utiliser l'ID pour que la différenciation se fasse progressivement smile.  Pour ce qui est de la difficulté d'appliquer le protocole, si chacun se limite a utiliser leur téléphone dans l'ordre et a attendre la réponse de celui qu'il contacte avant d'en appeler un autre, alors il n'ont plus besoin de faire de somme (juste ajouter 1) et moins de chose à gérer.

 #14 - 28-03-2018 15:44:07

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1461
Lieu: Coutiches

graphe de clines

LOL ! Même avec les explications, je ne trouve pas ça si simple... J'ai quand même l'impression d'avoir compris, mais sans avoir le recul pour bien comprendre comment ça se passe vraiment.
A méditer...

 #15 - 28-03-2018 16:10:46

Synar
Visiteur

Gaphe de clones

Bonjour,
sauf erreur de ma part, nul besoin de briser la symétrie tant qu'on prend son temps.

La solution la plus simple est que chaque personne dresse la liste (voir dessine le graphe) de ses voisins distants d'au plus k téléphones. Une fois fait, il appelle ses voisins et en déduit la liste pour k+1 et ainsi de suite. Si un voisin est en retard, il attend. Si la liste pour k+1 est identique à celle pour k, il appelle le docteur et compte les gens dans la liste.

 #16 - 28-03-2018 16:51:05

emmaenne
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3073
Lieu: Au sud du Nord

Graphe d clones

J'espère souvent comprendre lors des explications finales, mais là, plus je lis moins je comprends.
Mais c'est souvent le cas sur ces énigmes mathématiques. Presque à chaque fois j'ai l'impression de lire une langue étrangère. sad


Dans le cadre de la quinzaine du beau langage, ne disez pas disez, disez dites. (Julos Beaucarne)

 #17 - 28-03-2018 17:06:25

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3556

Garphe de clones

Cependant, il n'y a pas de mathématique dans cette énigme.

C'est juste de la méthode. L'idée générale est d'abord de savoir qui sera le chef d'orchestre. J'avais choisi celui qui a le n° de pièce le plus petit car le plus facile à mémoriser. Ensuite, ce plus petit n° sert de code pour les échanges, il annule les autres tentatives de comptage. Ensuite, le comptage proprement dit est assez simple, celui qui reçoit un appel prend le n° + 1 de celui qui l'a appelé. Ensuite, on élabore une méthode pour le retour du dernier n° connu vers le chef d'orchestre.

 #18 - 28-03-2018 22:56:10

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

graphe de cloneq

Si de nombreux participants réguliers ont préférés migrer vers d'autres sites ( un en particulier )

Quel est donc ce site le plus populaire ? Je réfléchis à aller chercher ma dose ailleurs, mais je ne connais pas bien les autres dealers.

 #19 - 28-03-2018 23:37:50

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,818E+3

Graphe de clnoes

Si c'est une dose d'énigme que tu cherches , peut-être, si c'est une dose de maths, tu risques le sevrage...

 #20 - 29-03-2018 00:44:19

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,818E+3

graphe de cloned

Pour ce qui est de la fuite, je persiste et signe...

Car les membres "concepteurs" saturent un peu, on a une vie IRL, et les membres actif (mais sans plus d'implication ) attendent du tout cuit. Si personne ne veut franchir le cap de la conception, ou finit par déseperer à se sentir seul à le faire (coup de chapeau à jackv en passant) , c'est un méchant cercle vicieux..

En plus, passer des mois à concevoir pour 3 ou 4 participants, ce n'est pas gratifiant. Alors que je trouve que certaines énigmes dernièrement proposées sans réponse du concepteur sont tout juste des idées en passant mais ne reflètent pas l'esprit de ce qui doit être proposé ici.

Une officielle pourrait rattraper un peu le coup peut-être ? big_smile

 #21 - 29-03-2018 13:41:58

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 883
Lieu: Seahaven island

grapge de clones

@emmaenne: oui parfois la logique et les maths utilisent un langage à eux mais les idées derrières ne sont pas nécessairement très dures.
Si un arrière arrière arrière....grand père encore vivant, voulait savoir combien il a au total de descendance, il pourrait passer un coup de fils à tout ses enfants et leur demander de se compter (et eux feraient de même en appelant leurs enfants)
Dans mon problème de clone il n'y a que deux difficiles supplémentaires, la première est d'avoir qq qui joue le rôle de l'arrière arrière arrière....grand père pour piloter/centraliser le comptage, et l'autre est qu'il faut éviter de compter des "enfants" plusieurs fois par plusieurs chemin téléphoniques différents, car dans mon exemple ce n'est pas un "arbre" aussi propre.

 #22 - 29-03-2018 23:38:43

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,167E+3

Graphe de cllones

Désolé Clydevil de parasiter un peu ton énigme mais ce n'est pas moi qui ai lancé l'offensive smile

Pour moi une belle énigme a plusieurs vies .

Le forum laisse vivre librement les énigmes au-delà du temps prévu par les auteurs et c'est la seule chose qui a vraiment un sens . On aime bien les énigmes du ch'ef mais le forum c'est autre chose . Après on peut dire qu'on ne va pas gâcher ses cartouches sur un petit site ou trop peu de personnes applaudissent mais : bof .

Ici , tout le monde participe et c'est ça qui est vraiment intéressant si on veut bien mettre son ego de côté .

Vasimolo

 #23 - 30-03-2018 09:16:54

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 883
Lieu: Seahaven island

Graphe ed clones

@Vasimolo: Allez-y shootez vous, ca fait remonter l'enigme sur la page tongue

 #24 - 31-03-2018 01:11:04

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,818E+3

raphe de clones

@ clydevil : Tu deviens limite méprisant : "shootez-vous" , vous êtes mous"... Tu me déçois.

 #25 - 31-03-2018 07:37:53

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3556

fraphe de clones

Je n'ai pas ressenti du tout comme toi les remarques de Clydevil, Gwen.

Cool...

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
P2T
Soyez poétique. par dhrm77
29-03-2009 Enigmes Mathématiques
P2T
Billard 2 par Vasimolo
10-02-2010 Enigmes Mathématiques
P2T
Nervures optimales par Clydevil
18-09-2011 Enigmes Mathématiques
P2T
08-09-2011 Enigmes Mathématiques
22-12-2015 Enigmes Mathématiques
P2T
Sonar par Clydevil
14-08-2018 Enigmes Mathématiques
P2T
Nombre univers par nodgim
24-11-2015 Enigmes Mathématiques
P2T
11-10-2012 Enigmes Mathématiques
18-02-2014 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