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 - 30-03-2015 20:32:49

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

Embouteillge sur le périph'

http://www.prise2tete.fr/upload/titoufred-periph2.png

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 ?

  • |
  • Répondre

#0 Pub

 #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… smile

 #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 roll

 #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...

http://www.prise2tete.fr/upload/morgu_07-Capture.PNG

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. smile

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... smile

 #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 smile

 #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 smile

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. smile

 #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 sad

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 smile

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

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 ?

Sujets similaires

Sujet Date Forum
P2T
12-02-2010 Enigmes Mathématiques
P2T
Les Trois Portes. par Enelya!
08-10-2009 Enigmes Mathématiques
P2T
Baba par Vasimolo
03-09-2009 Enigmes Mathématiques
P2T
24-09-2014 Enigmes Mathématiques
P2T
Un héritage P2T par Vasimolo
29-08-2009 Enigmes Mathématiques
P2T
Premier de cordée par nodgim
02-04-2018 Enigmes Mathématiques
P2T
Sudoku en couleur par Jackv
19-01-2021 Enigmes Mathématiques
P2T
Suite à compléter par Yodette
27-09-2017 Enigmes Mathématiques
11-05-2010 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