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 - 04-08-2015 12:25:50

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

PPrisonniers, ampoules, et durée de jeu 2

La suite du précédent :
Un prisonnier tiré au hasard parmi N est amené chaque jour dans une pièce où se trouve une ampoule, allumée ou éteinte, dans l'état dans lequel l'a laissée le prisonnier précédent.
Les prisonniers seront libérés si l'un d'eux affirme un jour, avec raison, que tout le monde est déjà passé dans la pièce.
Les prisonniers ne communiquent pas entre eux, sauf au tout début, pour mettre au point une stratégie gagnante.

La stratégie adoptée est la suivante:
- le premier prisonnier allume la lumière chaque fois qu'elle est éteinte
- les autres l'éteigne, mais uniquement la première fois qu'ils la voient allumée.
Ce qui permettra a terme au premier d'affirmer que tout le monde est passé après N allumages de la lampe.

Comme l'a fait remarqué scrabblor, parfois le 1er à passer n'est pas le premier à savoir que tout le monde est passé.
http://www.prise2tete.fr/forum/viewtopi … 80#p185274



Pour N=2 par exemple, la séquence "1 2" suffit : 2 sait que quelqu'un est passé la veille, et ça n'est pas lui. La séquence la plus courte est donc "1 2" (impossible de faire moins, sinon tout le monde n'est pas passé)

Pour N=3, la séquence "1 2 3" suffit aussi : 3 voit la lumière éteinte, il sait donc qu'en 2 jours quelqu'un l'a allumé, puis éteinte, donc que 1 et 2 sont passés.
(et encore une fois, impossible de faire moins).

La question est la suivante : pour N=4, 5, ...., jusqu'à 10 mettons, quelle est la séquence la plus courte qui permette à un prisonnierautre que le premier d'affirmer que tout le monde est passé, et ce avant le premier.

Je ferai un tableau de score en fonction des réponses. En cas d'égalité, un petit bonus pour le rang le plus élevé possible pour le prisonnier qui fait l'affirmation
(ex : "1 séquence de 10 coups avec 2 qui affirme à la fin" vaut moins que "une séquence de 10 coups avec 3  qui affirme à la fin", qui elle même vaut moins que "une séquence de 9 coups avec 2 qui affirme à la fin")



Klim : 1er

  • |
  • Répondre

#0 Pub

 #2 - 04-08-2015 16:16:43

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 4045
Lieu: hébesphénorotonde triangulaire

PPrisonniers, ampoules, et durée de jeu 2

Bonjour,

A mon avis, les cas N=2 et N=3 sont des cas particuliers.
A partir de N=4, la séquence la plus courte devrait être :
1-2-1-3-1-4... 1-N-1
A chaque fois que 1 se présente, il trouve la lumière éteinte, ce qui lui prouve que c'est un nouveau prisonnier qui était là avant lui. Finalement, il faut un total minimum de 2N+1 passages pour qu'un prisonnier, en l'occurrence le premier, puisse affirmer que tout le monde est passé.

Quelque chose m'a-t-il échappé ?
Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #3 - 04-08-2015 19:15:35

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

Prisonnniers, ampoules, et durée de jeu 2

En effet. Rien ne t'a échappé, j'ai juste posé le problème avant d'avoir eu le temps d'y réfléchir moi-même.
Je change un peu l'énoncé pour ajouter de l'intérêt : quelle est la séquence la plus courte permettant à un prisonnier autre que le premier d'affirmer que tout le monde est passé, et ce avant le premier
(par conséquent la séquence la plus courte pour l'énoncé peut être plus longue que la séquence la plus courte tout court).

 #4 - 04-08-2015 22:10:11

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 4045
Lieu: hébesphénorotonde triangulaire

prisonnoers, ampoules, et durée de jeu 2

Bonsoir,

Avec le nouvel énoncé et au moins 4 prisonniers, le premier prisonnier autre que le n°1 sera le n°2.
La séquence la plus courte débutera toujours par :
1-2, puis 1-2-3-2, puis 1-2-4-2, ..., et enfin 1-2-N-2.

Elle durera donc 4N-6 jours.

Je suis moins sûr de ma solution, mais c'est mon dernier mot, Jean-Pierre...
Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #5 - 04-08-2015 22:25:17

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

Prisonniers, ampoules, et durée e jeu 2

@Klim : pour n=4, je trouve la même longueur, mais avec une annonce par le 3ème smile

 #6 - 05-08-2015 00:02:49

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 4045
Lieu: hébesphénorotonde triangulaire

Prisonniers, ampoules, et durée de je 2

D'accord ! wink

Alors nouvelle proposition :
1-2-3-1-3, puis 1-3-4-3, puis 1-3-5-3, ..., 1-3-N-3

Le prisonnier n°3 aura la certitude que tout le monde est passé en 4N-7 jours.
Ca marche comme ça ?


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #7 - 05-08-2015 11:17:02

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

Prisonniers, ampoules, et durée de jjeu 2

D'abord, 1-2-3 suffit. Ensuite, tu trouves moins long avec 3 qui répond et pas 2 : c'est pas mal smile

 #8 - 05-08-2015 11:53:30

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 4045
Lieu: hébesphénorotonde triangulaire

Prisonniers, ampouules, et durée de jeu 2

Non, je ne crois pas qu'1-2-3 suffise, car il faut que 3 éteigne la lumière. D'où le début 1-2-3-1-3.

Et oui, c'est plus court avec 3 qu'avec 2 (comme d'ailleurs quand il n'y a que 3 prisonniers), car dans ma séquence, 3 a la certitude que 2 est passé et ne repassera pas, alors que 2 ne sait pas si 3 est passé le 3eme jour ou si c'est 1 qui est passé.

Mais peut-être as-tu mieux que moi ?


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #9 - 05-08-2015 14:07:10

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

prisonniets, ampoules, et durée de jeu 2

Du coup, je suis plus trop sur de comprendre ta séquence. Tu parles de 3 prisonniers, ou alors c'est juste le début d'une séquence plus longue pour + de 3 prisonniers ?

 #10 - 05-08-2015 16:27:18

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 4045
Lieu: hébesphénorotonde triangulaire

prisonniers, ampoulrs, et durée de jeu 2

C'est ma réponse pour N prisonniers, avec N >= 4 :

1-2-3-1-3
1-3-4-3
1-3-5-3
...
1-3-N-3

Le prisonnier n°3 aura la certitude que tout le monde est passé en 4N-7 jours.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #11 - 08-08-2015 15:37:44

PRINCELEROI
Elite de Prise2Tete
Enigmes résolues : 33
Messages : 1274

Prisonniers, amppoules, et durée de jeu 2

Rectification:Pas d'accord klim.
Soit Bn les autres joueurs G le "gagnant" et C le compteur.

Pour N=10

On a B1 B2 .....B8 plus C et G

Le compteur étant le premier à passer on a:
CB1GCGB2GCGB3GCGB4GCGB5GCGB6GCGB7GCGB8G

Soit 31 passages.


Après un mp à klim et sa réponse...

KLIM A RAISON 
 
Bon c'était prévisible... lol

En effet après la séquence CB1 G se doit d'éteindre la lumière et on a donc un GC à rajouter et on obtient 33 passages soit comme l'a noté klim  4N-7.

Bravo à klim !

 

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 : Pif, Paf et ?

Mots clés des moteurs de recherche

Mot clé (occurences)

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