"Записки научных семинаров ПОМИ"
Том 501, стр. 194-202
Односторонняя эгоистичная парковка
Н. А. Крюков
Санкт-Петербургский государственный университет,
Университетская наб. 7/9,
Санкт-Петербург, 199034 Россия
kryuknik@gmail.com
- Аннотация:
Пусть $n$ -- целое число. Если $n>1$, расположим на отрезке $[0,n]$ случайным образом интервал $(t,t+1)$ с целыми концами. Таким образом, изначальный отрезок разбивается на два: $[0,t]$ и $[t+1,n]$, каждый из которых далее рассматривается отдельно, аналогично изначальному. Фраза ``случайным образом'' в данной задаче означает, что $t$ является случайной величиной, равномерно распределённой на множестве $\{1,\ldots,n-1\}$. Процесс расположения интервалов заканчивается, когда длина всех оставшихся отрезков становится меньше двух. Обозначим за $X_n$ суммарное количество расположенных отрезков.
В настоящей работе вычислены значения математических ожиданий $\mathbb{E}\{X_n\}$.
Описаный выше процесс можно интерпретировать как процесс парковки машин, у которых руль находится слева. В таком случае, для того чтобы водитель смог выйти, место слева от его машины должно быть свободным. Это в точности означает, что он не может занять самое левое место в каком-либо отрезке. В таком случае $X_n$ -- количество припаркованных машин.
Библ. -- 13 назв.
- Ключевые слова:
случайное заполнение, дискретная задача о ``парковке,'' задача об эгоистичной парковке
[random filling, discrete 'parking' problem, problem of selfish parking]
Полный текст(.pdf)