задача дня-16

[falcao]

Вот ещё одна интересная задача, тоже вероятностная. Предлагаю всем желающим поучаствовать. Условие таково.

В коробке имеется M белых и N чёрных шаров, где M > N. Их начинают поочерёдно перекладывать во вторую коробку, выбирая шары случайным образом, пока первая коробка не опустеет. Перекладывание считается успешным, если в ходе процесса число

Comments

[frank]

Привет, это Фрэнк!

У нас новый флешмоб #прохорошее! Присоединяйтесь и получайте призы!
Расскажите, чем вам запомнится 2021 год: важные результаты, истории из поездок, личные события, впечатления от книг и фильмов, радость от любимого хобби. Всё, чем вы хотите поделиться!
Хештег #прохорошее. До 26 декабря!

Подробности тут: https://afisha-lj.livejournal.com/876696.html

[ditour]

(M-N)/(M+N). Совсем без формул не получается. Самое простое, что приходит в голову - выразить P(M,N) через P(M-1,N) и P(M,N-1), потом мостить треугольник на MN-плоскости по индукции, опираясь на очевидные случаи N=1 и M=N.

[falcao]

Да, верно. Рекуррентных формул можно в принципе избежать, потому что для числа способов они дают треугольник Каталана, а там все формулы уже известны. Но меня эта формула как раз и навела на "ручное" доказательство.

[ditour]

Что такое треугольник Каталана я уж и не помню.

[kaathewise]

Это частный случай cycle lemma, которую можно использовать и для доказательства формулы чисел Каталана.

Рассмотрим последовательность шаров и докажем, что из всех ее M+N циклических перестановок ровно M-N удовлетворяют условию. Для этого по очереди выкинем из нее все пары БЧ, так как "хорошая" перестановка не может начинаться ни с БЧ, ни с Ч, количество "хороших" перестановок не меняется. В итоге останется M-N белых шаров, которые дают M-N "хороших" перестановок из M+N.

[falcao]

Да, я рассуждал точно так же. Про такой способ вывести формулу для собственно чисел Каталана я знал, а вот то, что все числа треугольника Каталана можно быстро получить точно так же - это от моего внимания ускользнуло.

За ссылки на литературу отдельное спасибо.

[roman_rogalyov]

Ответ: p=(M-N)/(M+N)

Я решил её "на физическом уровне строгости": нарисовал "половинку" треугольника Паскаля,
т.е. таблицу, строка которой имеет номер S=M+N-2, начиная от нуля, а номера столбцов убывают от M-1 до нуля.
Число в таблице показывает число успешных перекладываний.

1
1 1
2 1
2 3 1
5 4 1
5 9 5 1
14 14 6 1
14 28 20 7 1

Строится построчно, как треугольник Паскаля (удобно рисовать их вместе):
Скажем, из строки
5 4 1
получается строка
5 (5+4) (4+1) 1

а из
5 9 5 1
получается строка
(5+9) (9+5) (5+1) 1
Крайний левый элемент в данном случае не сохраняется, поскольку в этом случае мы попадём на ось симметрии тр-ка Паскаля - границу неуспешных перекладываний.

Вероятность получается делением на соотв. элемент тр-ка Паскаля.
Разглядывая строку с небольшим номером угадал ответ.
А вот найти этот ответ совсем простым (при этом, видимо, нетривиальным) способом - увы не получилось. :-((

[falcao]

Этот треугольник, который строится по тому же правилу, что и треугольника Паскаля, но на половине доски - как раз и есть треугольник Каталана. Для его чисел есть готовые формулы, которые можно доказать по индукции, если вывести саму закономерность. Но это длинный способ - обычно простой по форме ответ почти всегда говорит о том, что его можно вывести коротким способом.