|
#1 - 30-03-2015 20:32:49
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Embouteillge sur le périph'
Des voitures roulent sur un périph'. Les règles de circulation sont les suivantes, au tour par tour : Si une voiture a une case libre devant elle, elle avancera d'une case au tour suivant Sinon, elle reste bloquée sur place.
Sur l'exemple donné, seules les voitures vertes vont avancer au tour suivant.
Comment va évoluer la situation ?
#2 - 31-03-2015 00:13:15
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
Embouteillage ssur le périph'
Sur l'exemple, il y a 18 voitures et 37 cases: à la fin les voitures vont se repartir sur tout le périph en étant intercalées d'une case vide, et à un endroit 2 voitures seront séparées de 2 cases. Soient V=voiture et C = case vide, on aura ...VCVCVCVCVCCV...
De manière générale si nv=nombre de voitures et nc=nombre de cases sur le circuit, on aura: - si 2*nv=nc alors répartition parfaite homogène ...CVCVCVCV... - si 2*nv<nc (donc n=nc-2*nv) alors répartition homogène avec un trou de n+1 cases vides entre 2 voitures à un endroit.
- si 2*nv>nc: je verrai ce cas plus tard
#3 - 31-03-2015 02:47:18
- picnel
- Amateur de Prise2Tete
- Enigmes résolues : 0
- Messages : 1
Embouteillae sur le périph'
les 3 vertes avancent d'une case. Les 3 nouvelles vertes avancent d'une case. Ainsi de suite les 3 tours suivants. Puis la dernière verte avance pour les 3 prochains tours et il n'y a plus que des vertes.
#4 - 31-03-2015 08:00:01
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
embouteilkage sur le périph'
Bonjour, À partir de la 17ème étape, chaque voiture a un espace libre devant elle, sauf une qui en a deux. La situation reste ensuite stable, l'ensemble se décalant d'une case à chaque étape.
#5 - 31-03-2015 10:42:57
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
embouteillage sur lr périph'
@kossi_tg : Quel est ton raisonnement ?
@picnel : La verte du haut va avancer au tour suivant, mais au tour d'après elle se retrouve bloquée dans l'embouteillage de devant.
@enigmatus : Quel est ton raisonnement ? Que va-t-il se passer dans le cas général ?
#6 - 31-03-2015 11:08:13
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3222
- Lieu: Luxembourg
Embouteilage sur le périph'
Cela finira en file indienne car le groupe du bas, comptant moins de voitures, va rattraper les deux groupes du haut qui fusionneront.
#7 - 31-03-2015 11:25:34
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Embouteillage sr le périph'
Quelle que soit la voiture qu'on fait avancer en premier, on se retrouve toujours dans la même configuration. Il y a 37 cases et 18 voitures, on trouve une case sur deux occupée (36) avec une case libre surnuméraire après 1 tour complet. Pour la généralisation: Si plus du double de cases que de voitures, on trouvera tjs les voitures espacées de 2 cases. Sinon, il faut regarder, mais je pense qu'on aura un seul groupe de voitures collées.
#8 - 31-03-2015 12:14:12
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Embouteillage sur le ériph'
titoufred #5 a écrit:Quel est ton raisonnement ?
Ce n'est pas un raisonnement, mais une simulation…
#9 - 31-03-2015 16:38:55
- dahaouid
- Habitué de Prise2Tete
- Enigmes résolues : 49
- Messages : 34
rmbouteillage sur le périph'
La situation va s'arranger ! Il y a 18 voitures pour 37 emplacements, au bout d'un moment il y aura toujours une place libre entre chaque voiture. Je n'ai pas d'équation pour l'exprimer mais vérifié sur Paint en faisant la simulation
#10 - 31-03-2015 18:28:32
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
embouteilmage sur le périph'
@Franky : certes, mais les 2 groupes-embouteillages auront eu le temps de se dégraisser un peu non ?
@nodgim : quel est ton raisonnement ?
@enigmatus et dahaouid : bravo pour les simulations ! Pouvez-vous deviner ce qui va se passer dans le cas général suivant le nombre de voitures et le nombre d'espaces ?
#11 - 31-03-2015 21:07:40
- morgu_07
- Amateur de Prise2Tete
- Enigmes résolues : 41
- Messages : 9
Embouteilllage sur le périph'
Résumons... Il y a 37 cases en tout, 18 voitures et 19 places libres.
Tant qu'il n'y a pas plus de 18 voitures, les embouteillages disparaitrons gentiment jusqu'à obtenir le résultat d'une voiture - une place libre - une voiture - un place libre...
Si il y a 19 voitures (ou plus), il y en aura toujours une (ou plus) qui sera bloqué.
#12 - 31-03-2015 21:08:41
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
embouteollage sur le périph'
Salut !
Amusant ce problème.
Intuitivement, j'aurai tendance à dire que s'il y a au moins 2 espaces par voiture, le bouchon se résorbera totalement, et que s'il y en a moins, alors le bouchon persistera forcément.
Reste à le prouver...
#13 - 31-03-2015 21:28:50
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Embouteillaeg sur le périph'
@morgu_07 : bravo, c'est bien ça sur l'exemple donné. Comment raisonnes-tu pour le cas général ?
@golgot59 : comme tu dis, reste à le prouver...
#14 - 31-03-2015 21:54:04
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
embouyeillage sur le périph'
* le dernier où 2*nv>nc (nv=nbre de voitures et nc=nbre de cases sur le circuit) La répartition est homogène et un embouteillage de n+1 voiture à un endroit du type ...CVCVCVVV...VVCVCVCV... où n=2*nv-nc.
Je n'ai pas vraiment de raisonnement à fournir. C'est une vue d'esprit, il m'a suffi de voir et d'imaginer l'évolution de la situation puis de conclure sur qui se passe
#15 - 31-03-2015 22:04:04
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
elbouteillage sur le périph'
@kossi_tg : tu crois qu'il ne pourrait pas y avoir plusieurs embouteillages dans ce cas ?
#16 - 31-03-2015 22:43:08
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
embouteillage qur le périph'
Bonsoir
Je n'ai pas trop réfléchi au problème mais il est clair que le nombre de blocs ne peut que croître . L'équilibre final sera donc atteint quand les voitures seront isolées ou les blocs de voitures séparés par une unique case vide ( selon que le nombre de voitures est supérieur ou inférieur à la moitié des cases du périph ) .
J'essaierai de regarder ça en détail ce week-end
Vasimolo
#17 - 31-03-2015 22:59:04
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
embouteillage sur le oériph'
Si si, il pourrait y avoir plusieurs embouteillages. Cela dépendrait de la répartition initiale.
Dans tous les cas, quand les espaces disponibles entre les embouteillages initiaux seront remplis (absence de 2 cases vides consécutives), tous les embouteillages restants resteront inchangés à la position près.
Dans ma réponse précédente, je considérais les nv voitures constituant un seul embouteillage initial.
#18 - 01-04-2015 18:31:26
- Fito11235
- Professionnel de Prise2Tete
- Enigmes résolues : 49
- Messages : 173
embouteillage qur le périph'
Coucou; En raisonnant avec un embouteillage de 4 voitures, on se rend compte qu'elles finiront toutes par avoir une case libre devant elle.
xxxx xxx x xx x x x x x x Elles pourront ainsi avancer à chaque tour jusqu'à être bloquées par un embouteillage plus loin.
Dans le cas précis de l'exemple, La voiture verte du haut rattrapera l'embouteillage devant elle puis restera bloquée 5 tours avant de repartir.
La voiture du bas rattrapera l'embouteillage formé par les 2 autres files.
Tout finira par se réguler étant donné qu'il y a 18 voitures pour 37 emplacements. On aura donc exactement (au bout de 13 tours ?)1 espace entre chaque voiture. Et la première sera à 2 espaces de la dernière de la file.
Merci.
#19 - 01-04-2015 19:00:49
- Sydre
- Professionnel de Prise2Tete
- Enigmes résolues : 15
- Messages : 245
Embouteillage sur le périph''
On considère un périphérique de 2*n ou 2*n+1 cases.
V représente une voiture et C une case vide.
Cas d'une seule file de k voitures :
Si k <= n : les voitures se répartissent selon le motif [VC] répété k fois.
Si k > n : les voitures se répartissent selon le motif [VC] répété n-k fois plus le motif [VV] répété n-k-1 fois.
Interaction entre 2 files de k1 et k2 voitures distantes de d1 et d2 cases :
Si d1 < 2*k1 et d2 < 2*k2 alors les 2 files restent séparées sinon les 2 files fusionnent.
État final de l'exemple :
[VCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCVCC]
#20 - 01-04-2015 19:14:21
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Embouteillage sur le périph''
On peut décrire une petite arithmétique spéciale pour ce problème. Soit Bk (bouchon), groupe de k voitures touche-touche. 1111.. Soit Ck (convoi) k voitures espacées de 2 cases et encadrées d'une case libre (0101010) Soit Ek (espace) une suite de k cases libres (00000)
Evolution d'un B,C ou E encadré de B,C ou E:
Pour un B: CBk----->Bk E(>1)Bk---->B(k-1) E1Bk--->Bk
Pour un C: ECkB---->C(k-1) ECkE----->Ck BCkB----->Ck BCkE----->C(k+1)
Pour un E BEkC---->E(k-1) CEkB---->E(k-1) BEkB---->E(k-2) CEkC---->Ek BE1B----->E1
(1)Seuls les convois peuvent croître, les bouchons et les espaces sont stables ou décroissants. Un bouchon n'est stable que s'il est précédé d'un convoi ou d'un autre bouchon (E1 intercalé).
(2)Comme sur un tour, si on n'est pas en stablité intégrale, c'est que les décroissances sont compensées par les seules croissances des convois.
(3)On observe aussi qu'un espace n'est stable qu'entouré de 2 convois.
(4)On observe également, et c'est sans doute le plus important, que la longueur cumulée des convois (la somme des k des Ck) est stable ou croissante sur 1 tour. En effet ECkB (ce qui fait diminuer la longueur d'un convoi) précède obligatoirement un BCkE (qui fait augmenter la longueur d'un convoi).
De toutes ces observations, on peut conclure:
Les espaces autres que E1 qui ne sont pas encadrés par des convois s'amenuisent. Les E1 encadrés par des bouchons disparaissent avec le bouchon amont (sauf dans le cas exceptionnel ou 1 seul bouchon et 1 seul E1 sur le circuit, où cette situation est stable). La longueur cumulée des convois est stable ou croissante, au détriment des bouchons et des espaces.
Conclusion: S'il y a plus de voitures que le double de cases, il ne restera que des convois et des bouchons. Sinon, il n'y aura que des convois et des espaces. Si, comme dans la figure proposée, il y a moitié moins, ou moitié moins une, voitures que cases, il ne restera qu'un convoi (et respectivement un espace E1).
#21 - 02-04-2015 23:56:15
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
embputeillage sur le périph'
@Vasimolo : Oui d'accord ça ne peut que croitre. Mais va-t-on forcément atteindre les équilibres dont tu parles ?
@kossi : ok pour le cas où il y a un seul embouteillage initial. Et dans les autres cas ?
@Fito : dans l'exemple donné, il reste toujours des embouteillages après 13 tours... Que va-t-il se passer dans le cas général ?
@Sydre : Quel est ton raisonnement ?
@nodgim : Ok sur tout, sauf quand tu dis qu'un bouchon n'est stable que s'il est précédé d'un convoi. Que conclues-tu de toutes ces observations ?
#22 - 03-04-2015 09:35:44
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Embouteillage suur le périph'
Titoufred, j'ai complété et corrigé avec tes observations. Je n'ai pas réfléchi plus dans le cas où le nombre de voitures dépasse la moitié du nombre de cases, c'est à dire dans le cas où des bouchons subsisteront. En effet, selon les conditions de départ, le nombre et la longueur des bouchons en situation stabilisée sera variable. On doit pouvoir la prédire. T'es tu intéressé à cet aspect ?
#23 - 03-04-2015 17:19:13
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
embouteullage sur le périph'
@nodgim : tu as prouvé que d'un tour à l'autre, les bouchons ne peuvent que diminuer ou rester stables, mais qu'est-ce qui prouve qu'ils vont disparaitre sur le long terme dans certains cas ?
#24 - 04-04-2015 13:17:22
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
emvouteillage sur le périph'
Il y a pas mal de paramètres qui laissent penser que la position finale sera constituée de blocs de voitures séparés par un blanc ou des blocs de blancs séparées par des voitures isolées mais je n'ai pas mis le doigt sur le potentiel qui va décroître au fil des mouvements
Il est clair que le nombre de blocs ne peut que croître et leur tailles diminuer il reste à voir pourquoi la situation ne peut se stabiliser qu'avec des singletons entre les blocs
Vasimolo
#25 - 04-04-2015 17:37:57
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Embouteeillage sur le périph'
Il va y avoir un seul embouteillage: quand une voiture verte avance, elle a bloqué auparavant les voitures se trouvant derrière elle. Inévitablement il existe une voiture qui bloque 1 autre au tour un (considérons que c'est le maximum), ce qui induit un décalage de 2 voitures minimum deux tours plus tard puisque d'autres voitures l'auront rattrapée (si ce n'est pas le cas ce n'était pas le maximum au départ donc contradiction), et ainsi de suite en augmentant de 1voiture tous les deux tours, au final il ne restera qu'une file indienne
Je ne suis pas sûr qu'il y ait une seule file, à voir
Un promath- actif dans un forum actif
Mots clés des moteurs de recherche
|
|