|
||||||||||||||||||
|
Содержание№66Это задача не входит в тематический конкурс. Результат учитывется только в основном зачете Марафона. Конкурсная задача №66 (8 баллов) Двое играют в такую игру: Каждый игрок очередным своим ходом берет из кучки, содержащей n камней, некоторое количество камней. За один ход можно взять количество камней, являющееся целой неотрицательной степенью одного из двух фиксированных натуральных чисел (a и b). Выигрывает тот, кто возьмет последний камень. 1. Существуют ли такие a и b, при которых шансы на выигрыш у второго игрока выше, чем у первого? 2. Оценить шансы игроков для случаев, когда a и b - простые числа. 3. Перед началом игры игроки делают ставки. Обе ставки забирает победитель. Ставка первого игрока в пять раз больше. Зато первый игрок имеет право (до того как узнает число n) выбрать числа a и b. Кому из игроков выгодны такие условия? Примечания: 1. Число «камней» n для каждой игры выбирается случайно из диапазона [1.. 1000000] (распределение равномерное). 2. Соперники играют наилучшим образом. Решение
1. Нет. 2. Пусть a и b нечетны. Тогда шансы игроков равны. В самом деле, при нечетном n выигрывает первый игрок (как бы он ни играл), а при четном - второй.
Если одно из чисел равно 2, а другое нечетно и отлично от 3,
шансы первого игрока составляют 2/3 (точнее, 0.666667). Если {a,b} = {2,3}, шансы первого игрока на победу возрастают до 4/5. При n, не кратном 5, первый игрок после каждого своего хода будет оставлять в кучке кратное 5 число камней (для этого ему достаточно взять 1, 2, 3 или 4 камня). Поскольку среди возможных ходов нет кратных 5, второй игрок рано или поздно проиграет. При n, кратном 5, роли поменяются.
3. Описанные условия выгодны первому игроку.
Опишу простой и достаточно быстрый (временнАя сложность O(n*log^2(n))
алгоритм посторения множества A, состоящего из n, благоприятных для
второго игрока: Обсуждение Пара {2, 45} не единственная, для которой правила, описанные в пункте 3 выгодны первому игроку. Существует целый ряд натуральных b, кратных 3, для которых пара чисел {2, b} дает первому игроку шансы выше 5/6. В качестве b можно взять 27, 30, 33, 51, 54, 60, 69, 75, 105, 114, 120, 123, 126, 135, 147…
Придумывая эту задачу, я первоначально полагал, что первый игрок будет иметь
наилучшие шансы при {a,b} = {2,3}. Ведь именно при таких a и b первый игрок
имеет максимальное (при фиксированном n) количество вариантов своего первого
хода. А именно возможность первым же ходом загнать соперника во множество А и
определяет преимущество первого игрока. Награды За правильное решение этой задачи Олег Полубасов получает 8 призовых баллов. За правильное (но не совсем строгое) решение Виктор Филимоненков получает 7 призовых баллов. За верное решение пунктов 1 и 2 Андрей Богданов и Владислав Франк получают по 4 призовых балла. Эстетическая оценка задачи - 3.8 балла
|
|||||||||||||||||
|
||||||||||||||||||
|