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.
CLIQUER
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
:
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 :
ICI : 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.
CLIQUER
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
CLIQUER
et résultats avec multiples essais : stationnement
BP moyennes sans contrainte
CLIQUER
