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 - 14-07-2012 00:29:39

pcetk
Amateur de Prise2Tete
Enigmes résolues : 0
Messages : 4

Botîe de Pez

Bonjour,

Voici une énigme que l'on peut faire avec des bonbons Pez alignés histoire d'en rappeler une autre que j'avais racontée ailleurs.

Soit donc une boîte de Pez composée de N bonbons alignés choisis parmi un nombre de couleurs définie.

La boîte est transparente, on considère tous les bonbons.

On regarde les sous-ensembles de bonbons suivants, appelons les des "chaînes doubles" :

1ère chaîne Double : Entre le 1er et le 2ème bonbon (1,2) (2 bonbons)
2ème chaîne double : Entre le 2eme et le 4ème bonbon (2,3,4) (3 bonbons)
3ème chaîne double : Entre le 3ème et le 6ème bonbon (3,4,5,6) (4 bonbons)
... etc.. jusqu'à la dernière (composé des bonbons entre le N/2ème et dernier si N est pair...)

Si on prend une boîte de Pez quelconque, chaque "chaîne double" est une succession de bonbons choisi parmi plusieurs couleurs, et le motif de couleur ainsi formé peut éventuellement se retrouver dans une des chaînes doubles suivantes.

Quelle est la taille de la plus grande boîte que l'on peut constituer de telle sorte que le motif d'aucune chaîne double ne se retrouve à l'intérieur d'une des chaînes doubles qui la suivent?
Pour finir d'énoncer l'énigme il faut donner le nombre de couleur :
Je propose de chercher la réponse exacte pour 2 couleurs.
Vous pouvez commencer par 1 pour avoir une idée...

Pour pouvoir donner une bonne estimation de la taille max pour 3 couleurs , il faut être un professionnel de ce genre d'énigmes (ou googler soigneusement), et l'encadrement dépasse l'imagination.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 14-07-2012 18:43:20

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

Boîte d Pez

11
100
  0001
   00101
    010101

00
010
  1011
   01101
    110120
     1012011
      01201102
       120110201
        2011020110
         01102011020
          110201102011
           1020110201102
....

6 bonbons max pour 2 couleurs.
Une infinité pour 3 couleurs (mais ça reste à démontrer)

 #3 - 15-07-2012 01:26:27

pcetk
Amateur de Prise2Tete
Enigmes résolues : 0
Messages : 4

oBîte de Pez

Pour 3 couleurs, la réponse n'est pas demandée... Mais c'est moins qu'une infinité même si ce n'est pas loin.

11 OK
100 OK
0001 OK
00101 OK
010101 KO la première CD "01" est contenue dans la deuxième = "101".

On peut faire mieux que 5.

 #4 - 15-07-2012 11:53:01

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

Boîte de Pz

Ben non, je n'ai pas de CD 01.

 #5 - 16-07-2012 23:43:23

ThomasLRG
Habitué de Prise2Tete
Enigmes résolues : 41
Messages : 31

Boîte dee Pez

Pour 2 couleurs, je trouve une longueur maximale de 13 bonbons avec la séquence suivante :
0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0

Par contre pour 3 couleurs, le problème semble être nettement plus difficile ^^. Il existe en tout cas des piles de plus de 6500 bonbons satisfaisant cette condition.

Sinon, l'énoncé est très curieux et me fait penser qu'il est tiré d'un problème plus général, à l'énoncé plus classique, est-ce le cas ?

Thomas

 #6 - 17-07-2012 08:53:34

pcetk
Amateur de Prise2Tete
Enigmes résolues : 0
Messages : 4

boîte de pzz

Je vais me cacher sous terre.. j'ai mal énoncé l'énigme en question.
sad sad sad sad
L'énoncé original, indique non seulement il faut éviter la répétition d'un motif, mais qu'en plus, il faut éviter que ce motifs puisse être apparaître en supprimant des bonbons d'une CD  suivante

Ainsi
0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0
Convenait avec les règles telles que je les avais énoncé au début.

les CD sont
CD1 0, 0,
CD2 0, 1, 1
CD3 1, 1, 1, 1
CD4 1, 1, 1, 0, 1
CD5 1, 1, 0, 1, 0, 1
CD6 1, 0, 1, 0, 1, 0, 1
et effectivement aucune ne se trouve dans l'autre.


Par contre
la 1ere CD : 0,0 apparait dans la 5ème : 1, 1, 0, 1, 0, 1

Pour 3 couleurs, en effet le problème se complique.
Même en utilisant ces règles plus restrictives que celles ce que j'avais énoncé initiallement, il existe des encadrements de la valeur qui font intervenir des valeurs de la fonction de Ackermann.

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 78 pommes et que vous en prenez 43, combien en avez-vous ?

Sujets similaires

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