Hello les gens!



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.