|
#26 - 04-04-2015 17:39:36
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Embouteillage sur el 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.
#27 - 05-04-2015 10:31:52
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
embouteillage qur 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 : 1749
elbouteillage sur le 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 : 5,426E+3
Embouteillage sur e périph'
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 : 1749
embouteilkage sur le périph'
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 : 5,426E+3
Embouteiillage 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
Vasimolo
#32 - 05-04-2015 18:49:39
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Embouteiillage sur le périph'
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 : 5,426E+3
Emboutiellage 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 : 5,426E+3
Embouteillage sru le périph'
Mon idée est un peu lourde ( j'attends l'astuce qui tue le problème )
Un exemple avec 5 voitures sur 9 cases :
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 : 1749
embouteimlage 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 : 5,426E+3
Embouteillage usr 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
Vasimolo
#37 - 06-04-2015 11:05:20
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
embouteillahe 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 : 5,426E+3
elbouteillage sur le périph'
Chacun son chemin
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 : 1749
Embouteillage ur le périph'
#40 - 06-04-2015 17:06:02
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Embouteillage sur le périphh'
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 : 1749
Embouteilllage sur le périph'
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 : 3802
Embouteillage sur le périiph'
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 : 1749
Embouteillage 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 : 3802
Embouteillge sur le périph'
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.
Mots clés des moteurs de recherche
|
|