Тема:
Все темы
>>
Логика и теория множеств
>>
Теория алгоритмов
>>
Теория игр
>>
Симметричная стратегия
Фильтр
Задачи
Задача 110922 |
|
|
Играют двое. В начале игры есть одна палочка. Первый игрок ломает эту палочку на две части. И так игроки по очереди ломают на две части любую палочку из имеющихся к данному моменту. Если, сломав палочку, игрок может сложить из всех имеющихся палочек один или несколько отдельных треугольников (каждый – ровно из трёх палочек), то он выиграл. Кто из игроков (первый или второй) может обеспечить себе победу независимо от действий другого игрока?
Решение
Заметим, что выигрыш возможен только тогда, когда после очередного хода общее число палочек кратно 3. Пусть первого игрока зовут Петя, а второго – Вася. Тогда в первый раз выигрыш возможен после первого хода Васи, в следующий раз – после третьего хода Пети. Первым ходом Петя должен сломать палочку пополам. Как бы ни поделил одну из половинок Вася, треугольник из получившихся трёх палочек сложить нельзя, так как не выполняется неравенство треугольника (одна из сторон равна сумме двух других). Итак, после первого хода Пети образовалось две одинаковые кучки из одной палочки. Своим вторым и третьим ходом Петя должен "повторить ход" Васи на симметричной кучке. Таким образом, после третьего хода Пети перед ним лежат палочки длины a, b, c, a, b, c. Пусть a ≥ b ≥ c . Составим два равнобедренных треугольника: первый со сторонами a, a, c и второй со сторонами b, b, c.
Ответ
Первый игрок.
|
|
Задача 66157 |
|
|
Изначально на столе лежат три кучки из 100, 101 и 102 камней соответственно. Илья и Костя играют в следующую игру. За один ход каждый из них может взять себе один камень из любой кучи, кроме той, из которой он брал камень на своем предыдущем ходе (при своём первом ходе каждый игрок может брать камень из любой кучки). Ходы игроки делают по очереди, начинает Илья. Проигрывает тот, кто не может сделать ход. Кто из игроков может выиграть, как бы ни играл соперник?
Решение
Укажем выигрышную стратегию для Ильи. Обозначим через A, B и C кучки, в которых изначально было 100, 101 и 102 камня соответственно. Первым ходом Илья берёт камень из кучки B. Далее возможны два случая.
1) Своим первым ходом Костя возьмёт камень не из кучки B. Тогда Илья всегда будет повторять ход Кости, то есть брать камень из той же кучки, из которой только что брал камень Костя. Заметим, что, пока Илья действует по этой стратегии, после каждого его хода в каждой кучке остаётся чётное число камней.
Свой второй ход Илья сможет сделать, так как Костя взял свой первый камень не из B. После этого каждым ходом Костя будет брать камень из кучки X, отличной от кучки Y, из которой только что взял Илья. Тогда в X останется нечётное число камней, и Илья сможет взять из X ещё один камень. Значит, действуя по этой стратегии, Илья всегда сможет сделать ход после хода Кости. Поскольку игра рано или поздно закончится, Костя проиграет.
2) Своим первым ходом Костя возьмёт камень из кучки B. В этом случае Илья будет придерживаться следующей стратегии. Если каким-то ходом Костя возьмёт камень из кучки C, то Илья берёт камень оттуда же. Если же Костя возьмёт камень из кучки A или B, то Илья берёт камень из кучки B или A соответственно. Заметим, что, пока Илья действует по этой стратегии, после каждого его хода в C будет чётное число камней, а в A и B камней будет поровну.
Покажем, что и в этом случае Илья всегда сможет сделать ход. Свой второй ход Илья сделать сможет (взяв камень из A). Если на очередном шаге ему нужно брать камень из кучки C, то до этого оттуда брал камень Костя, значит, на предыдущем ходу оба игрока не брали ничего из C. При этом после хода Кости там нечётное число камней, поэтому Илья может взять камень из C. Если же Илье нужно брать камень не из C, скажем, из A, то Костя только что взял камень из B (и, значит, в A ещё есть камень). Следовательно, на предыдущем шаге Костя не мог брать камень из B, поэтому Илья не брал камень из A, то есть он может взять камень оттуда.
Ответ
Илья.
|
|
|
Задача 105123 |
|
|
Двое игроков по очереди выставляют на доску 65×65 по одной шашке. При этом ни в одной линии (горизонтали или вертикали) не должно быть больше двух шашек. Кто не может сделать ход – проиграл. Кто выигрывает при правильной игре?
Решение
Пусть первый поставил на доску первую шашку. Заметим, что от перестановки горизонталей доски ничего не изменяется. То же относится и к
перестановке вертикалей. Поэтому будем считать, что второму игроку дополнительно
разрешается менять местами любые горизонтали и вертикали.
После первого хода первого игрока второй игрок переставит горизонтали и
вертикали так, чтобы первая шашка оказалась в средней вертикали, но не в центре
доски.
Далее он делает ходы симметрично ходам первого игрока относительно центра доски. В частности, вторая шашка тоже окажется в средней вертикали, и первый не сможет занять центральную клетку. Легко проверить, что второй всегда сможет сделать симметричный ход (отдельно следует рассмотреть случай хода в среднюю горизонталь).
Ответ
Второй.
|
|
|
Задача 74569 |
|
|
Решение
В обоих вариантах игры побеждает начинающий. Это справедливо и для любой шоколадки из mn долек (размером m×n), где mn четно (за исключением случая шоколадки 2×n с нечетным n в варианте б) — здесь ответ зависит от mn.)Мы рассмотрим сразу общий случай. Интересно, что выигрышные стратегии в "противоположных"; вариантах а) и б) почти совпадают.
а) Стратегия, обеспечивающая выигрыш начинающему, такова. Хотя бы одно из чисел m и n четно – пусть это будет m (m=2k). Первым ходом начинающий разламывает шоколадку на две одинаковые половины (по n×k долек). Затем каждый ход второго он дублирует на другой половине шоколадки. Таким образом, после каждого хода первого игрока обе половины будут разломаны совершенно одинаковым образом. Ясно, что при этом первый не отломит дольку 1×1 раньше, чем это сделает второй.
б) Здесь при четном m>2 и n>1 начинающий может
использовать ту же "симметричную" стратегию до тех
пор, пока второй не отломит полоску шириной 1; первый
тут же отламывает он нее дольку 1×1 и выигрывает.
В варианте б) игры "симметричная" стратегия для шоколадки
2×n не годится – отламывать полоску шириной 1
нельзя (это немедленно ведет к проигрышу), так что
шоколадку можно ломать только "поперек". Возникает
совсем другая задача, более сложная задача, подробное исследование которой
предоставляется читателю.
Ответ для нечетного mn в общем случае нам неизвестен ни для варианта а), ни для варианта б) игры.
Ответ
|
|
|
Задача 64454 |
|
|
Петя и Вася играют в такую игру. Сначала на столе лежит 11 кучек по 10 камней. Игроки ходят по очереди, начинает Петя. Каждым ходом игрок берёт 1, 2 или 3 камня, но Петя каждый раз выбирает все камни из любой одной кучки, а Вася всегда выбирает все камни из разных кучек (если их больше одного). Проигрывает тот, кто не может сделать ход. Кто из игроков может обеспечить себе победу, как бы ни играл его соперник?
Решение
Расположим камни как показано на рисунке, где кучки соответствуют столбцам.
Петя должен брать несколько камней из одного столбца, а Вася – из разных. Стратегия Васи – делать ходы, симметричные Петиным относительно пустой диагонали. Изначально картинка симметрична. Поскольку строка, симметричная столбцу, не имеет с ним общих камней, то Вася каждый раз сможет восстанавливать нарушенную симметрию, то есть у него всегда есть ход. Так как игра конечна, то когда-то Петя проиграет.
Ответ
Вася.|
|
|
Страница: << 6 7 8 9 10 11 12 >> [Всего задач: 56]
