2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Игра с кучками камней
Сообщение17.04.2018, 17:36 
Модератор
Аватара пользователя


11/01/06
5710
Есть $n$ камней распеделённых по $k>1$ непустым кучкам, а сами кучки расположены по кругу. Таким образом, у каждой кучки есть две соседние.
Игра состоит в последовательности ходов. На каждом ходе выбирается случайно и равномерно одна кучка, и один камень из неё перекладывается в случайно выбранную соседнюю кучку. Если исходная кучка при этом становится пустой, то она исчезает, и игра продолжается с оставшимися $k-1$ кучками на круге.
Игра заканчивается, когда остаётся ровно одна кучка.

Найдите мат. ожидание количества ходов в такой игре, если в начальном расположении количества камней в кучках по кругу равны $x_1$, ..., $x_k$ (с условием $x_1+\dots+x_k=n$).

 Профиль  
                  
 
 Re: Игра с кучками камней
Сообщение21.04.2018, 14:29 
Заслуженный участник


10/01/16
2318
$S_2(x_1,...,x_k)$ - второй симметрический.
Индукция, однако:
База $n=2$ явно проверяется в соответствии с формулой полной вероятности
Шаг: пишем рек. формулу; счастливым образом, появление нулей среди $x_i$-х не мешает работать угаданной формуле...
Ну, замечательная задача: так редко удается получать явные ответы!

-- 21.04.2018, 16:30 --

И вдвойне неожиданно, что от порядка следования чисел ответ не зависит!

 Профиль  
                  
 
 Re: Игра с кучками камней
Сообщение21.04.2018, 15:57 
Модератор
Аватара пользователя


11/01/06
5710
DeBill, всё верно!
Источник задачи: https://mathoverflow.net/q/296418
Говорят, что тот же ответ обобщается на произвольные регулярные связные графы (на кучках-вершинах).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group