Тема:
Все темы
>>
Логика и теория множеств
>>
Теория алгоритмов
>>
Теория игр
>>
Выигрышные и проигрышные позиции
Фильтр
Задачи
Задача 78783 |
|
|
Лежит кучка в 10 миллионов спичек. Двое играют в следующую игру. Ходят по очереди. За один ход играющий может взять из кучки спички в количестве pn, где p – простое число, n = 0, 1, 2, 3, ... (например, первый берёт 25 спичек, второй – 8, первый – 1, второй – 5, первый – 49 и т.д.). Выигрывает тот, кто берёт последнюю спичку. Кто выиграет при правильной игре?
Решение
Докажем, что если число спичек не кратно 6 (в частности, таково, как в условии), то первый выигрывает.
Поскольку 1, 2, 3, 4, 5 являются степенями простых, то в случае числа спичек равного 6k + r, где 1 ≤ r ≤ 5, первый играющий может добиться того, чтобы после его хода осталось 6k спичек.
Теперь заметим, что степень простого числа не делится на 6, поэтому после следующего хода оставшееся число не кратно 6, в том числе не может стать нулевым.
Значит, первый игрок каждым своим ходом может оставлять число спичек, кратное 6. Таким образом, второй игрок выиграть никогда не сможет, следовательно, выиграет первый.
Ответ
Первый игрок.
|
|
Задача 109955 |
|
|
Решение
Выигрывает первый. Сначала ему надо делать ходы длиной в 4 клетки, пока он не встанет на 45-ю клетку. Теперь очередь хода за вторым. Если он тоже все время делает ходы длины 4, очередной ход приведет его на клетку 57. Тогда первый следующим ходом должен пойти на клетку 48 и после ответа второго сходить так, чтобы между ним и вторым оказалось 3 клетки (легко видеть, что это всегда возможно). После этого второй будет вынужден пойти на 1, 2 или 3 клетки и окажется в итоге правее 49-й клетки. Значит, до финиша ему останется больше 48 клеток, и, чтобы добраться туда, он должен будет сделать не меньше 13 ходов. Первый же находится не левее 49-й клетки, и ему до финиша остается не более 52 клеток, которые он сумеет преодолеть за 13 ходов.Рассмотрим теперь случай, когда среди 11 первых ходов второго был ход менее, чем на 4 клетки.
Тогда он после 11-го хода окажется более, чем в 56 клетках от цели, и для ее достижения ему понадобится минимум 15 ходов, а первому до цели остается 56 клеток, и он сможет добраться до нее за 15 ходов, даже если второй при встрече вынудит его сделать ход длины 3 вместо хода длины 4.
Ответ
Выигрывает первый.|
|
|
Задача 111844 |
|
|
Два игрока по очереди проводят диагонали в правильном (2n+1)-угольнике (n > 1). Разрешается проводить диагональ, если она пересекается (по внутренним точкам) с чётным числом ранее проведённых диагоналей (и не была проведена раньше). Проигрывает игрок, который не может сделать очередной ход. Кто выиграет при правильной игре?
Решение
Заметим, что по одну сторону от каждой диагонали находится чётное число вершин, а по другую – нечётное. Поэтому каждую диагональ пересекает чётное число других диагоналей (2n+1)-угольника. Пусть в некоторый момент игры невозможно сделать ход, тогда каждая непроведённая диагональ пересекает нечётное число уже проведённых, а следовательно, и нечётное число непроведённых диагоналей. Такая ситуация возможна только тогда, когда непроведённых диагоналей чётное число (см., например, зад. 30425).
Таким образом, если общее количество диагоналей в многоугольнике нечётно, то выиграет первый, а если чётно – второй. В (2n+1)-угольнике число диагоналей равно (2n + 1)(n – 1) (см. зад. 60391), то есть нечётно при чётном n и чётно при нечётном n.
Ответ
При нечётном n выиграет второй, при чётном – первый.
|
|
|
Задача 109567 |
|
|
На столе лежат три кучки спичек. В первой кучке находится 100 спичек, во второй – 200, а в третьей – 300. Двое играют в такую игру. Ходят по очереди, за один ход игрок должен убрать одну из кучек, а любую из оставшихся разделить на две непустые части. Проигравшим считается тот, кто не может сделать ход. Кто выиграет при правильной игре: начинающий или его партнер?
Решение
Пусть перед каким-то ходом начинающего количества спичек на столе имеют вид 2na, 2nb и 2mc, где 0 ≤ n < m, а числа a, b и c нечётны (назовём такую позицию хорошей). Тогда он своим ходом убирает кучку из 2na спичек, а кучку из 2mc спичек делит на кучки из 2n и 2n(2m–n c – 1) спичек. После этого количества спичек в кучках будут иметь вид 2na', 2nb', 2nc', где a', b' и c' – нечётные числа.
Если это позиция (1, 1, 1), то партнер проиграл.
В противном случае можно считать, что второй игрок своим ходом убирает кучку из 2na' спичек, а кучку из 2nb' спичек делит на две кучки – из 2ku и 2lv спичек, где u и v – нечётные числа и k ≥ l. Тогда 2nb' = 2ku + 2lv. Если при этом k < n, то k = l < n, а если k > n, то l = n; случай k = n невозможен. Таким образом, начинающий снова окажется в хорошей позиции.
Поскольку исходная позиция – хорошая: 100 = 2²·25, 300 = 2²·75, 200 = 2³·25, то при такой стратегии начинающий всегда будет получать хорошую позицию, то есть у него всегда будет ход.
Ответ
Начинающий.
|
|
|
Задача 105083 |
|
|
Система укреплений состоит из блиндажей. Некоторые из блиндажей соединены траншеями, причём из каждого блиндажа можно перебежать в какой-нибудь другой. В одном из блиндажей спрятался пехотинец. Пушка может одним выстрелом накрыть любой блиндаж. В каждом промежутке между выстрелами пехотинец обязательно перебегает по одной из траншей в соседний блиндаж (даже если по соседнему блиндажу только что стреляла пушка, пехотинец может туда перебежать). Назовём систему надёжной, если у пушки нет гарантированной стратегии поражения пехотинца (то есть такой последовательности выстрелов, благодаря которой пушка поразит пехотинца независимо от его начального местонахождения и последующих передвижений).
б) Найдите все надёжные системы укреплений, которые перестают быть надёжными после разрушения любой из траншей.
Решение
а) Обозначим блиндажи, как показано на рисунке. Ограничим начальные положения пехотинца блиндажами O, A2, B2 и C2 (эти блиндажи мы будем называть чётными, а остальные – нечётными). Мы считаем, что пехотинец настолько удачлив, что спасается, если только это возможно.
Заметим, что если какая-то часть системы укреплений сама по себе надёжна, то пехотинец может спасаться только в этой части, таким образом и вся система надёжна. Поэтому, если кроме цикла A1-A2-...-An-A1 имеются другие траншеи, то такая система уже не минимальна.
Покажем, что любой цикл минимален. Разрушив, скажем, траншею An-A1, мы получим линейный лабиринт A1-A2-...-An. Вот как должна действовать пушка. Она последовательно стреляет по блиндажам A2, A3, ..., An. Если сначала пехотинец был в блиндаже с чётным номером, то один из этих выстрелов его накроет. Если же этого не произошло, то пушка производит ещё одну серию выстрелов, начиная с блиндажа A1 или A2 и последовательно перемещаясь по возрастанию номера блиндажа. То, с какого блиндажа она начинает вторую серию, зависит от чётности номера блиндажа, в котором в этот момент находится пехотинец (это легко вычислить, так как сначала номер был нечётен и после каждого перебегания чётность номера меняется).
Осталось рассмотреть системы укреплений без циклов. Покажем, что единственная минимальная надёжная среди них – это трилистник. Возьмём любую систему, не содержащую ни цикла, ни трилистника, и укажем, как должна действовать пушка. (Мы опишем стратегию для связной системы. Если же система несвязна, то есть состоит из нескольких участков, не связанных между собой траншеями, то пушка должна последовательно реализовать эту стратегию для каждого участка.)
Назовём блиндаж перекрёстком, если из него выходят три или более траншеи. Траншею, ведущую из блиндажа, назовём сквозной, если, пробежав через неё, пехотинец может перебежать ещё два раза, не побывав дважды ни в одном блиндаже. Например, в трилистнике траншея A1A2, ведущая из блиндажа A1, не сквозная, а траншея A2A1 из A2 сквозная. Наконец, блиндаж назовём тупиковым, если из него ведёт единственная траншея. Так как наша система не содержит трилистника, из любого блиндажа выходит не более двух сквозных траншей.
Возьмём любой перекрёсток. Если из него ведут две сквозные траншеи, причём каждая ведёт к другому перекрёстку, то выберем одну из них и проследуем через неё до ближайшего перекрёстка. Если из этого нового перекрёстка выходит ещё одна сквозная траншея, ведущая к перекрёстку, перейдём по этой траншее до следующего ближайшего перекрёстка. Действуем так, пока не придём к перекрёстку с единственной выходящей из него сквозной траншеей или с двумя, через одну из которых можно дойти до тупикового блиндажа, не проходя ни одного перекрёстка. В первом случае пройдём по любой несквозной траншее в соседний блиндаж, во втором – пройдём по этой сквозной траншее до блиндажа, соседнего с тупиковым. Таким образом мы определили, с какого блиндажа начать обстрел.
Разобьём блиндажи на чётные и нечётные, так что пехотинец каждый раз перебегает из блиндажа одной чётности в блиндаж другой чётности (это возможно, поскольку циклов в системе нет). Покажем, как нужно стрелять, чтобы гарантированно поразить пехотинца при условии, что он изначально находится в блиндаже той же чётности, что и блиндаж, с которого начнётся обстрел. (Если, сделав все эти выстрелы, пушка так и не накроет пехотинца, значит, он находился в блиндаже другой чётности; теперь уже точно известна чётность блиндажа с пехотинцем.) Пусть пушка последовательно поразит блиндажи, начиная с выбранного и заканчивая перекрёстком. Тогда на обстрелянном линейном участке системы пехотинца нет. Мы так выбрали начальный блиндаж, чтобы среди траншей, ведущих в другие участки системы, было не более одной сквозной. (Если всего их две, то вторая ведёт в только что обстрелянный участок.) Любая несквозная траншея ведёт либо в тупиковый блиндаж, либо в блиндаж, из которого можно попасть в несколько тупиковых или же вернуться на перекрёсток. В обоих случаях за этой траншеей всего один блиндаж чётности, противоположной чётности рассматриваемого перекрёстка. После того как пушка накрыла перекрёсток, пехотинец перебежал как раз в блиндаж, чётность которого противоположна чётности перекрёстка, так что если он находится за этой траншеей, то, ударив по блиндажу, в который ведёт эта траншея, пушка поразит пехотинца. Если же нет, пушка снова бьёт по перекрёстку, не давая пехотинцу пробежать на уже проверенные участки системы укреплений. Проверив все несквозные траншеи, пушка приступает к единственной сквозной, поражает блиндаж, в который ведёт эта траншея, и далее последовательно все блиндажи до ближайшего перекрёстка. Там повторяется проверка несквозных проходов и т. д. Так можно проверить всю систему.
Тем самым, любая система, не содержащая ни циклов, ни трилистника, ненадёжна. Разрушив любую траншею в трилистнике, мы получим ненадёжную систему, так что трилистник является минимальной надёжной системой. Наконец, любая система, состоящая из трилистника и чего-то ещё, надёжна, но не минимальна.
Ответ
Это трилистник и все системы, состоящие только из одного цикла блиндажей A1-A2-...-An-A1.
|
|
|
Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 52]
