Stationnement sur le boulevard périphérique


Ce problème m'a été soumis par Diophante.

Problème Diophante n° G172

Des segments ont été délimités par 4026 marques blanches le long du BP (boulevard périphérique)
nouvellement transformé en aire de stationnement.
Sachant que pour se garer toute voiture occupe deux segments adjacents,
la capacité maximale de stationnement est de 2013 voitures.
A la première heure de la journée, le BP est complètement libre.
Les voitures arrivent les unes après les autres et choisissent de manière aléatoire deux segments adjacents libres
jusqu’à occuper la dernière place disponible.
Combien de voitures en moyenne (arrondi à l’entier le plus proche) parviennent à stationner le long du périphérique ?



L'animation suivante modélise le stationnement pour un nombre de voitures pouvant aller jusqu'à 180 avec 360 bandes.

Choisir le nombre de places, régler la vitesse et observer.

PLEIN ECRAN

Les résultats obtenus concordent sensiblement avec l'espérance théorique attendue :
la limite est de 1- 1/e2 dès que le nombre de voitures dépasse plusieurs centaines.
Donc environ 86,4664%. Ainsi pour 4026 voitures, une moyenne de 1741 voitures peuvent se garer.

Ne pas hésiter à étudier les démonstrations proposées par Diophante.

Voici l'algorithme qui permet de calculer avec un tableur,
l'espérance mathématique du nombre de voitures qui peuvent se garer en fonction du nombre initial de marques n.

On désigne par E(n) l'espérance mathématique du nombre de voitures
qui peuvent se garer avec n marques tracées le long du boulevard périphérique.
Quand la première voiture se gare, elle laisse une bande de 4024 segments disponibles.
La deuxième voiture laisse deux bandes dont les longueurs sont k et 4022 - k, avec k pouvant varier de 0 à 2011,etc...
Il s'agit donc de calculer E(4024) et le résultat demandé (à l'arrondi près) est E(4024) + 1.
On calcule à la main les premières valeurs de E(n) :
E(0) = 0
E(1) = 0
E(2) = 1
E(3) = 1 + 1/2(E(1) + E(1)) = 1 + 1/2(0 + 0) = 1
E(4) = 1 + 1/3( E(2) +E(1) + E(1) + E(2)) = 1 + 2/3/(1 + 0 ) = 5/3
E(5) = 1 + 1/4(E(3) + E(1) + E(2) + E(2) + E(1) + E(3)) = 1 +2/4(E(3)+E(2)+E(1)) = 1 +2/4(1 + 1 + 0) = 2
E(6) = 1 + 1/5(E(4) + E(1) + E(3) + E(2) + E(2) + E(3) + E(1) + E(4)) =1 +2/5 (E(4) + E(3) + E(2) + E(1)= 1 + 2/5*11/3= 37/15
etc...
Dans ces calculs, on considère que s'il y a k segments adjacents libres,
la voiture qui se gare choisit un emplacement quelconque avec la même probabilité 1/(k-1).
E(k) est alors égal à 1 +2 * somme(E(i)) /(k-1) pour i variant de 1 à k--2


Les calculs du fichier Excel suivant sont fondés sur cet algorithme :
http://magicmaths.pagesperso-orange.fr/pages/truc_mat/textes/G172-TE.xls

Diophante m'indique par ailleurs l'origine de ce problème sur le site d'IBM Research Ponder
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/June2011.html,
avec les solutions multiples qui en sont données et notamment la solution élégante
d'Austin Shapiro qui donne la formule générale :
http://magicmaths.pagesperso-orange.fr/pages/truc_mat/textes/ponder_june_solution_Austin.pdf

 

Cette deuxième animation permet de traiter le cas général.
On peut répéter l'expérience un certain nombre de fois pour obtenir une moyenne sur le nombre de lancements.
Être patient si le nombre de lancements dépasse la dizaine.

PLEIN ECRAN

Les animations suivantes, proposent le stationnement de voitures sur le BP sans aucune contrainte de marques :
Les voitures se garent sur une position libre aléatoire quelconque.
Avec visionnement des voitures : stationnement BP voitures sans contrainte
et résultats avec multiples essais : stationnement BP moyennes sans contrainte

 


  Menu trucs  Accueil