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 - 04-04-2015 17:39:36

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Embouteillagge sur le périph'

L'explication est très simple à donner, mais pas forcément très simple à trouver. Je vous conseille de regarder comment ça évolue sur quelques exemples.

#0 Pub

 #27 - 05-04-2015 10:31:52

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4753

Embouteillaeg sur le périph'

Bon je crois que j'ai l'explication mais ce ce n'est pas si simple à expliquer .

La situation est symétrique en voitures et cases vides : on pourrait supposer par exemple que les cases vides se déplacent comme les voitures mais dans le sens inverse . On peut donc se placer dans le cas ou le nombre de voitures est supérieur ou égal au nombre de cases vides . On attribue à chaque case le rang dans son peloton de la voiture qui l'occupe , une case vide est numérotée 0 . Au tour suivant chaque case portant un numéro non nul va voir sa valeur décrémentée de 1 , une case précédée d'un 1 va prendre la valeur de la case qui la suit ( sauf si c'est 0 , elle prendra alors la valeur 1 ), les autres cases restent inchangées .

Il est clair que le total des numéros ne peut que décroitre et il ne change pas si et seulement si deux pelotons sont toujours séparés par une unique case vide .

Symétriquement , s'il y a plus de cases vides que de voitures la situation se stabilise quand les voitures sont isolées .

Vasimolo

 #28 - 05-04-2015 16:11:11

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

embouteillage sur me périph'

Je n'ai pas bien compris ton raisonnement avec le total qui ne peut que baisser. Qu'est-ce que ça montre ? Les embouteillages disparaissent forcément ?

 #29 - 05-04-2015 17:46:41

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4753

Embouteillage sur le périp'h

A partir d'un moment la situation se stabilise .

Si le nombre de cases vide est supérieur au nombre de voitures , les voitures sont isolées et tournent régulièrement dans le sens horaire .

Si le nombre de voitures est supérieur au nombre d'espaces libres ce sont les cases libres qui tournent régulièrement dans le sens trigo ( il reste des bouchons ) .

Vasimolo

 #30 - 05-04-2015 18:06:29

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Embouteillage sur le périp'h

Le sens de ma question était davantage : à quel moment prouves-tu que les embouteillages vont disparaitre ? Tu dis que le total descend ou est constant d'un tour sur l'autre, mais cela ne prouve pas que les embouteillages vont disparaitre non ?

 #31 - 05-04-2015 18:32:51

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4753

Embouteilllage sur le périph'

Si , parce que les valeurs ne peuvent pas descendre indéfiniment et la stabilité est atteinte uniquement s'il y une unique case libre entre les groupes de voitures ou une unique voiture entre les blocs de cases libres ( selon la densité d'occupation ) .

Je vais essayer d'illustrer ça dans la soirée smile

Vasimolo

 #32 - 05-04-2015 18:49:39

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Embouteillage sur le pérph'

Pourquoi la stabilité est atteinte uniquement s'il n'y a plus d'embouteillages (dans le cas où ça arrive) ?

 #33 - 05-04-2015 18:58:36

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4753

embouteimlage sur le périph'

En retournant ta question : s'il y a plus de voitures que de cases libres sur le périph , pourquoi y aura-t-il une seule case libre entre chaque groupe de voitures ?

Vasimolo

 #34 - 05-04-2015 19:19:39

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4753

embputeillage sur le périph'

Mon idée est un peu lourde ( j'attends l'astuce qui tue le problème smile )

Un exemple avec 5 voitures sur 9 cases :

http://www.prise2tete.fr/upload/Vasimolo-9cases.png

On peut coder les positions de la façon suivante :

000201321
100103210
010032101
101021020
010210101

ou en décalant les lignes pour suivre les voitures :

000210321
010010321
010100321
010101021
010101021

La position est alors stabilisée .

Entre chaque peloton de plus d'une voiture , les cases vides tournent jusqu'à ce qu'elles ne puissent plus ravitailler le peloton précédent .

Vasimolo

 #35 - 06-04-2015 00:58:50

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

mbouteillage sur le périph'

Vasimolo a écrit:

En retournant ta question : s'il y a plus de voitures que de cases libres sur le périph , pourquoi y aura-t-il une seule case libre entre chaque groupe de voitures (au bout d'un moment)?

Oui, c'est la question que je te pose. Pourquoi ?

Désolé, je n'arrive pas à comprendre certaines phrases dans ton raisonnement, peut-être le vocabulaire... par exemple : "Entre chaque peloton de plus d'une voiture , les cases vides tournent jusqu'à ce qu'elles ne puissent plus ravitailler le peloton précédent". Qu'entends-tu par là ?

 #36 - 06-04-2015 08:48:56

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4753

Embouteillage ssur le périph'

Je vais essayer d'expliquer autrement .

Les voitures sont regroupées en pelotons d'au moins une voiture séparés par des cases vides . La première voiture d'un peloton est numérotée 1 , la deuxième 2 , ... A chaque coup la voiture numérotée 1 se détache de son peloton et les voitures portant un numéro supérieur à 1 voient leur numéro diminuer de 1 . On peut choisir de numéroter les cases plutôt que les voitures une case vide portant alors le numéro 0 les autres le rang de la voiture qui l'occupe .

Par exemple la position initiale est codée :

8765432105432100000005432100000000000

A chaque tour la voiture en tête de peloton va se détacher et les autres membres du peloton vont voir leur numéro diminuer de 1 . Au mieux une voiture va recoller à la queue du peloton pour récupérer le numéro perdu , c'est à dire que le total des valeurs des cases va diminuer sauf si chaque peloton de plus d'une voiture récupère une voiture à l'arrière le total restant alors identique . La situation va décroitre jusqu'à une situation d'équilibre qu'on suppose atteinte . Si tous les pelotons sont constitués d'une seule voiture l'équilibre est évident supposons donc qu'il y a des pelotons de plus d'une voiture . A chaque tour ces pelotons vont perdre leur voiture de tête et récupérer une voiture en queue ce qui veut dire qu'ils sont suivis d'une unique case vide . Si derrière une voiture isolée il y avait plus d'une case vide il y aurait un problème juste après que cette voiture ait raccroché au peloton immédiatement devant elle . Les positions d'équilibre sont donc constituées de voitures isolées ou de cases vides isolées .

J'espère que c'est plus clair smile

Vasimolo

 #37 - 06-04-2015 11:05:20

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

embouteollage sur le périph'

Vasimolo, ce que tu appelles "peloton" je l'appelle "bouchon" et tes "isolés" (succession de 1 voiture + 1 cas libre) je l'appelle "convoi" en un seul lot. C'est peut être plus abordable comme ça. J'ai démontré que l'ensemble des voitures groupées en convoi est stable ou croissant. Au détriment des bouchons et des espaces. J'ai conclu que s'il y a plus de voitures que la moitié de cases sur le circuit, alors au moins 1 bouchon subsistera.

Le schéma d'accroissement des convois est donné par cette configuration:
BCkE---->C(k+1).  (B: bouchon, Ck: convoi de k voitures, E:espace). 
Les bouchons alimentent le convois qui croissent devant un espace libre.

Il est clair par exemple que sur un circuit linéaire avec un nb infini de cases et un nb fini de voitures, seuls les convois subsistent.

 #38 - 06-04-2015 11:33:38

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4753

Embouteillagee sur le périph'

Chacun son chemin smile

Il est clair que l'équilibre est obtenu quand les groupes de voitures ou les groupes de cases vides ne sont séparés que d'une case , après ...

Vasimolo

 #39 - 06-04-2015 13:14:51

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Embouteilage sur le périph'

Oui bravo Vasimolo !

 #40 - 06-04-2015 17:06:02

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

Embotueillage sur le périph'

Titoufred, tu semblais avoir une preuve asez synthétique ?

 #41 - 06-04-2015 18:03:58

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Embouteillage sur le périp'h

En gros, c'est ce que raconte Vasimolo.

Optionnel : on peut déjà remarquer la dualité voitures/espaces : les espaces se déplacent comme les voitures, mais dans le sens anti-horaire.

On appelle embouteillage un groupe de minimum 2 voitures/espaces qui se suivent.

Les embouteillages peuvent diminuer de taille lorsqu'un embouteillage de voiture précède un embouteillage d'espace (dans le sens horaire), mais ils ne peuvent pas grossir. A chaque tour, un embouteillage de voitures (resp. d'espaces) qui ne diminue pas se déplace dans le sens anti-horaire (resp. horaire). Tant qu'il reste à la fois des embouteillages des deux sortes, ils vont donc soit diminuer, soit se déplacer en sens contraires, et lorsqu'ils finissent par se rencontrer, ils se "mangent" l'un l'autre, perdant chacun une unité par tour. Par conséquent, il ne finit par rester qu'un seul type d'embouteillage au plus.

 #42 - 06-04-2015 18:26:51

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

Embouteillage sur le péiph'

Je suis un peu déçu, je m'attendais à voir un truc percutant et court, à la Vasimolo...
Avez vous remarqué qu'on pouvait facilement réduire le nombre de déplacements des voitures sur 2 tours ?

 #43 - 06-04-2015 19:56:21

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

Emboutteillage sur le périph'

Je trouve ça plutôt simple et court comme explication pour un truc que personne n'a trouvé en 144h, hormis Vasimolo.

 #44 - 07-04-2015 10:29:23

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

Embouteillage sur le périp'

Oui Titoufred, mais je pensais à une réponse moins verbale.

C'est vrai qu'avec mon BCkE---->C(k+1), qui est la seule configuration qui fait croître C, je n'ai pas dit que comme C ne pouvait croître infiniment, il fallait que soit B soit E disparaisse.

 

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 51 pommes et que vous en prenez 24, combien en avez-vous ?

Sujets similaires

Sujet Date Forum
P2T
Badaboum ! 3 par franck9525
29-01-2011 Enigmes Mathématiques
31-01-2009 Enigmes Mathématiques
P2T
Les ultracubes par Promath-
20-09-2010 Enigmes Mathématiques
29-10-2007 Enigmes Mathématiques
P2T
En code... par SaintPierre
13-06-2011 Enigmes Mathématiques
P2T
Le compte est bon ! par Rarouuu
16-09-2015 Enigmes Mathématiques
27-04-2014 Enigmes Mathématiques
P2T
26-01-2010 Enigmes Mathématiques
P2T
Mot codé 2! par gilles355
02-09-2012 Enigmes Mathématiques

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