Тема:
Все темы
>>
Логика и теория множеств
>>
Теория алгоритмов
>>
Теория игр
>>
Выигрышные и проигрышные позиции
Фильтр
Задачи
Задача 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.
|
|
Задача 109690 |
|
|
Решение
|
|
|
Задача 73543 |
|
|
Двое играют в такую игру. Из кучки, где имеется 25 спичек, каждый берёт себе по очереди одну, две или три спички. Выигрывает тот, у кого в конце
игры – после того, как все спички будут разобраны, – окажется чётное число спичек.
а) Кто выигрывает при правильной игре – начинающий или его партнёр? Как он должен играть, чтобы выиграть?
б) Как изменится ответ, если считать, что выигрывает забравший нечётное число спичек?
в) Исследуйте эту игру в общем случае, когда спичек 2n + 1 и разрешено брать любое число спичек от 1
Решение
а) Вот выигрышная стратегия для второго игрока. Он должен:
1) всегда брать нечётное число спичек (одну или три);
2) оставлять начинающему число спичек, сравнимое с 0 или 1 по модулю 4.
Нетрудно проверить, что это возможно. При этом после шести ходов второго у него окажется чётное число спичек, а в кучке останется 0 или
1 спичка.
б) Вот выигрышная стратегия для первого игрока. Первым ходом он должен взять одну спичку, а дальше играть по стратегии, изложенной в а).
При этом он сделает ровно 7 ходов, и у него окажется нечётное число спичек.
в) 1) Исследуем сначала игры типа а) и б) в случае m = 3. Ясно, что алгоритм, приведённый в а), работает в игре типа а) при любом n, кратном 4,
а в игре типа б) при n ≡ 2 (mod 4).
При других n выигрывает первый. Например, в игре типа а) при 27 спичках он забирает две и "передает" ход второму, который, согласно а)
должен проиграть. При 29 спичках (31 спичке) он забирает одну (три) 3 спички и далее делает еще 7 ходов по тому же алгоритму.
Аналогично разбираются все случаи игры типа б).
2) Более того, аналогичные алгоритмы годятся при любом нечётном m. При этом первый проигрывает в игре типа а) при n, кратном m + 1,
в игре типа б) при n ≡ m+1/2 (mod m + 1), а в остальных случаях выигрывает.
3) При чётном m ситуация несколько другая: первый проигрывает в игре типа а) при n, кратном m/2 + 1, в игре типа б) при n ≡ m/2 (mod m/2 + 1),
а в остальных случаях он выигрывает. Поясним алгоритмы на примере m = 4.
4) Пусть n = 12 (25 спичек). Поскольку 12 кратно 3, в игре типа а) должен выиграть второй. Вот его стратегия.
Второй должен оставлять противнику число спичек, сравнимое с 0 или 1 по модулю 6, имея "на руках" чётное число спичек, и число, сравнимое
с 5 по модулю 6, имея на руках нечётное число спичек. Покажем, что это возможно.
Если первый забирает чётное число спичек, то второй просто дополняет это количество до 6.
Если первый забирает нечётное число спичек из кучки с 6k спичками, то второй дополняет это количество до 5. В кучке остаётся 6k – 5 спичек,
а у второго – снова чётное количество.
Если первый забирает нечётное число спичек из кучки с 6k + 1 спичкой, то второй дополняет это количество до 4. В кучке остаётся
6k + 3 спички,
а у второго становится нечётное количество спичек.
Если первый забирает нечётное число спичек из кучки с 6k + 5 спичками, то второй также дополняет это количество до 4. В кучке остаётся 6k + 1
спичка, а у второго становится чётное количество спичек. В результате в конце игры после последнего хода второго останется 0 или 1 спичка,
а у второго будет чётное число.
5) Пусть n = 14 (29 спичек). Поскольку 14 ≡ 2 (mod 3), в игре типа б) должен выиграть второй. Его стратегия аналогична: оставлять противнику
число спичек, сравнимое с 0 или 1 по модулю 6, имея "на руках" нечётное число спичек, и число сравнимое с 5 по модулю 6, имея на руках
чётное число спичек.
В остальных случаях выигрывает начинающий, придерживаясь аналогичных стратегий.
Ответ
а) Партнёр; б) начинающий.
в) В игре типа а) начинающий проигрывает только в случаях n ≡ 0 (mod m/2 + 1) при чётном m и n ≡ 0 (mod m + 1) при нечётном m;
в игре типа б) начинающий проигрывает только в случаях n ≡ m/2 (mod m/2 + 1) при чётном m и n ≡ m+1/2 (mod m + 1) при нечётном m.
|
|
|
Задача 111765 |
|
|
Решение
n2=1+3+..+(2n-1) при нечетном n , n(n+1)=2+4+..+2n при четном n . Обобщим задачу. Пусть в начале игры на столе лежат купюры достоинством M1>M2>..>M2n . Покажем индукцией по n , что игрок, делающий последний ход (назовем этого игрока последним}, всегда может получить не менее M2+M4+..+M2n тугриков, а игрок, делающий предпоследний ход (назовем этого игрока предпоследним} – не менее M1+M3+..+M2n-1 тугриков. Сразу заметим, что сумма этих чисел равна суммарному достоинству всех купюр; поэтому при оптимальной игре они получат ровно такое количество. База при n=1 очевидна. Пусть утверждение верно для n=k-1 , докажем его для n=k . Пусть k нечетно, тогда ходить должен последний игрок. Он может снять купюры M1 и M2 ; тогда в оставшейся игре он получит не меньше M4+M6+..+M2k , а за этот ход он получит M2 ; поэтому у него окажется не меньше M2+(M4+..+M2k) тугриков, что и требовалось. Покажем, что при любом ходе последнего предпоследний получит не меньше M1+M3+..+M2k-1 тугриков. Пусть последний взял купюры Mi>Mj ; перенумеруем оставшиеся на столе купюры по убыванию: L1>L2>..>L2k-2 . Тогда по предположению индукции предпоследний сможет дальше играть так, чтобы получить не меньше, чем L1+L3+..+L2k-3 . Поэтому нам достаточно показать, чтоПусть 1
Аналогично предыдущему случаю, легко показать, что в левой части неравенства присутствует не меньше d купюр из наибольших 2d купюр M1,..,M2d , откуда сразу следует требуемое.
|
|
|
Задача 35426 |
|
|
Подсказка
Первый может свести игру к повторению ходов второго.Решение
Первым ходом первый идет по диагонали "вправо-вверх", а затем повторяет ходы второго. Если второй идет по диагонали, то и первый то же; если второй вверх, то и первый вверх, аналогично, если второй делает ход вправо, то и первый делает ход вправо. При этом первый будет попадать на четвертую или шестую, или сразу на восьмую клетку по диагонали, если считать, что он стоял на первой. В обозначениях, принятых в шахматах, можно сказать, что первый стоял на поле a1, затем перешел на поле b2, а затем, повторяя ходы второго, он может оказаться на поле d4 или f6, или сразу на выигрышную позицию h8.|
|
|
Страница: << 5 6 7 8 9 10 11 >> [Всего задач: 52]
