Индукция в комбинаторике

Подсказка 1

Разберемся с ответом. Если мы хотим доказывать, что нет, то нам надо доказывать, что для всевозможных колод у второго вероятность будет меньше 1/2. Это вообще непонятно как делать. А вот если же мы хотим доказывать, что ответ - да, то нам надо привести всего одну «хорошую» колоду. Давайте подумаем, если у нас дано количество синих, красных и зеленых карт каждого человека, то как бы для нас удобно было бы выражать вероятность, ведь наши переменные никак друг от друга не зависят(мы хотим выразить в общем случае вероятность и подставить одну и ту же переменную вместо всех для первого игрока в конце).

Подсказка 2

Наверное было бы удобно делать это рекуррентой, поскольку игра идет по шагам. Мы хотим как-то зафиксировать нашу конструкцию. Давайте подумаем как это можно было бы сделать не вводя кучи переменных. Пусть у нас r, g, b — количество соответственно красных, зеленых и синих карт у первого. Тогда, если мы хотим доказать, что при какой-то колоде все хорошо, то либо нам опять рассматривать все колоды и как-то усреднять (что то же самое, что и доказывать, что ответ «нет», в смысле рассмотрения всевозможных колод), либо брать какую-то конкретную колоду, методом крайнего. Какие колоды при этом кажутся интуитивными в таком случае?

Подсказка 3

Во-первых, интуитивной кажется колода копирующая первого игрока, но чисто навскидку, ситуации симметричны и вряд ли там будет строго больше 1/2 вероятность. Давайте также поймем, что скорее всего число 30 здесь просто так, кроме разве что того, что оно кратно 3. А это значит, что по нашему предположению, мы можем масштабировать колоду, при этом не меняя кардинально конструкцию взятия колоды второму, чтобы было выполнено условие. Но тогда это значит, что мы либо берём какую-то фиксированную долю от колоды для каждого цвета, а если так, то нужны еще согласованности с делимостью на эту долю и это как-то все очень шатко, если мы предполагаем, что можно масштабировать. Это наталкивает нас на мысль, что по хорошему бы брать какое то маленькое (чтобы и для маленьких размеров колод, скажем, меньших 30 условие было выполнено) фиксированное число карт одного цвета, тоже самое с другим, и все остальное - третьего цвета.

Подсказка 4

Чтобы можно было брать маленькое число карт в колоде и все работало, хотелось бы брать по 0 или 1 карте каких-то двух цветов, а все остальное отдавать другому. Ну и при этом понятно, что если мы будем выражать реккурентой нашу вероятность, то если мы, скажем, возьмем 1 зеленый, 1 синий и остальное - красным, то нам надо будет еще выражать как-то реккуренту для подсчета, когда у нас 0 зеленых, 1 синий и остальные - красные, 1 зеленых, 0 синих, остальные - красные, а также 0 зеленых, 0 синих, остальные -красные. Что как бы муторно. Тогда давайте возьмем остальные красными, а одну либо синей, либо зеленой.

Подсказка 5

Теперь надо выбрать - зеленая или синяя, но чисто интуитивно, чтобы вероятность была повыше, нам хотелось бы взять карту, как бы посильнее чем остальные, то есть красные. Ну тогда, давайте возьмем синюю. И теперь будем искать вероятность реккурентно. Напишите эти реккуренты, как мы выяснили, для вероятности, когда одна синяя, а остальные красные и когда только красные.

Подсказка 6

Если вероятность победы второго, когда только красные это v(r, g, b), где r, g, b - кол-во красных, зеленых и синих у первого соответственно, то v(r, g, b) = (g * 1 + r * v(r - 1, g, b)) / (r + g + b) - просто перебираем исходы и варианты, когда победим.

Подсказка 7

Напишите такую же рекурренту для u(r, g, b), где это вероятность когда одна синяя и остальные красные(очевидно, она будет выражаться через себя и v(r, g, b)), после чего попробуйте и для v, и для u найти общий вид реккуренты (очевидно, сначала для v, так как она проще и в итоге, искать надо u), перебирая маленькие значения, после чего задача будет решена.

Подсказка 8

Не забудьте доказать эти формулы по индукции, найдя базу и сделав переход (быть может сам переход натолкнет вас на вид, как должны выглядеть v и u).