Тема:
Все темы
>>
Логика и теория множеств
>>
Теория алгоритмов
>>
Теория игр
>>
Теория игр (прочее)
Фильтр
Задачи
Задача 86105 |
|
|
На плоскости даны 2005 точек (никакие три из которых не лежат на одной прямой). Каждые две точки соединены отрезком. Тигр и Осёл играют в следующую игру. Осёл помечает каждый отрезок одной из цифр, а затем Тигр помечает каждую точку одной из цифр. Осёл выигрывает, если найдутся две точки, помеченные той же цифрой, что и соединяющий их отрезок, и проигрывает в противном случае. Доказать, что при правильной игре Осёл выиграет.
Решение
Выделим из данных точек какие-нибудь 1024. Разобьём выделенные точки на 512 пар и пометим нулём отрезки, соединяющие точки из одной пары. Далее, объединим получившиеся пары по две. Получим 256 четвёрок. Пометим цифрой 1 ещё не помеченные отрезки, соединяющие точки одной четвёрки. После этого объединим получившиеся четвёрки по две. Получим 128 восьмёрок. Пометим цифрой 2 ещё не помеченные отрезки, соединяющие точки из одной восьмёрки, и так далее. На последнем шаге мы объединим получившиеся две группы по 512 точек в одну и пометим ещё не помеченные отрезки цифрой 9.
Предположим, что Тигр раскрасил точки так, что не нашлось отрезка, помеченного той же цифрой, что и оба его конца. В каждой из 512 исходных пар найдётся точка, помеченная ненулевой цифрой, иначе эти две точки образовывали бы хорошую (дающую выигрыш Ослу) пару. Рассмотрим какую-нибудь из 256 четвёрок. В каждой из двух пар, из которых она образована, найдётся точка, помеченная не нулём. Если бы обе эти точки были помечены единицей, они бы бы образовывали хорошую пару. Следовательно, в каждой из 256 четвёрок найдётся точка, помеченная не нулём и не единицей. Продолжая это рассуждение, получаем, что в каждой из 128 восьмёрок найдётся точка, помеченная не нулём, не единицей и не двойкой, и т. д.; в каждой из двух групп по 512 найдётся точка,
помеченная не нулём, не единицей, не двойкой, …, не восьмёркой. Следовательно, эти точки помечены цифрой 9. Но они соединены отрезком, помеченным цифрой 9, что противоречит предположению.
Следовательно, Осёл выигрывает независимо от игры Тигра.
|
|
Задача 98280 |
|
|
Есть доска 1×1000, вначале пустая, и куча из n фишек. Двое ходят по очереди. Первый своим ходом "выставляет" на доску не более 17 фишек по одной на любое свободное поле (он может взять все 17 из кучи, а может часть – из кучи, а часть – переставить на доске). Второй снимает с доски любую серию фишек (серия – это несколько фишек, стоящих подряд, то есть без свободных полей между ними) и кладёт их обратно в кучу. Первый выигрывает, если ему удастся выставить все фишки в ряд без пробелов.
а) Докажите, что при n = 98 первый всегда может выиграть.
б) При каком наибольшем n первый всегда может выиграть?
Решение
а) Приведём стратегию первого игрока. Он вначале за несколько ходов выстраивает 12 серий по 8 фишек, так что соседние серии разделены одним пробелом, последовательно восстанавливая снятую серию и ставя ещё одну. Затем, восстановив конфигурацию после хода второго, он вставляет две фишки в крайние пробелы, получая конфигурацию 17, 8, 8, 8, 8, 8, 8, 8, 8, 17.
При любом ходе второго следующим ходом он строит непрерывный ряд, а именно: если второй снимает крайнюю серию, первый вставляет восемь фишек в пробелы между сериями и пристраивает с краю остальные девять фишек; если же второй снимает среднюю серию (длины 8), то первый своим ходом восстанавливает эту серию (восемь фишек) и заполняет пробелы между сериями (ещё девять фишек).
б) Пусть имеются n ≥ 98 фишек, и первый всегда выигрывает. Рассмотрим конфигурацию после предпоследнего хода первого. В ней несколько серий, разделённых одним или несколькими пробелами, и p фишек в куче. В каждой серии не более 17 фишек, иначе второй снимет такую серию и следующим ходом не удастся выставить все фишки.
В ответ на снятие любой серии первый может только: (а) восстановить снятую серию, затем заполнить все пробелы фишками из кучи и крайней серии (или нескольких крайних) или (б) переставить все фишки с одной стороны от снятой серии в пробелы между сериями другой стороны, пристроив оставшиеся с краю. Назовём серию средней, если на её снятие отвечают способом (а), левой – если способом (б) и фишки переставляются направо; правой – если (б) и налево. Ясно, что если на снятие крайней серии можно ответить способом (а), то можно и способом (б); будем считать, что первый отвечает (б), поэтому левая и правая серии всегда есть. Кроме того, если некоторая серия правая, то все серии слева от неё допускают ответ (б) с перестановкой налево. Мы будем считать, что первый игрок отвечает именно таким образом. Поэтому правые серии – это несколько крайних справа серий. Аналогично для левых серий.
Заметим, что в левых сериях и в куче в сумме не более 17 фишек: все фишки левых серий и фишки кучи нужно выставить или переставить при снятии самой правой из левых серий (аналогично – для правых серий).
Пусть есть ещё k средних серий. Если в одной из них m фишек, то m + k + 1 ≤ 17, поскольку при снятии этой серии надо восстановить m фишек и ещё заполнить по крайней мере k + 1 пробел между сериями, отсюда m ≤ 16 – k.
Итак, n ≤ p + 2(17 – p) + k(16 – k).
Максимум этого выражения достигается при p = 0 и k = 8, что даёт n ≤ 98.
Ответ
б) При n = 98.
|
|
|
Задача 110927[Паук и бабочка] |
|
|
Паук в лесу сплёл паутину. Длинные нити привязал к веткам. И в эту паутину залетела бабочка. За один ход бабочка или паук могут передвинуться по отрезку нити в соседнюю точку пересечения нитей; бабочка также может выбраться на конец нити (ветку), если перед этим находилась в соседней точке пересечения. Они ходят по очереди, начинает бабочка. Если бабочка смогла добраться до веток, она спаслась (это её победа). Если паук добрался до бабочки, он её съедает (и это его победа). Возможен и такой исход, когда никто не побеждает, а игра длится бесконечно.
б) Чем закончится игра, если колец три, а радиусов семь?
в) Чем закончится игра, если колец четыре, а радиусов десять?
г) Разберите общий случай: K ≥ 2 колец и R ≥ 3 радиусов.
Решение
г) Заметим, что у бабочки всегда есть ничейная стратегия. Она состоит в том, что бабочка делает ход по своему кольцу в сторону от паука. При R > 3 очевидно, что пауку надо делать ход по своему кольцу в ту же сторону, иначе бабочка выходит по тому радиусу, на котором сейчас находится. При этом положение членистоногих относительно паутины и друг относительно друга не
меняется, поэтому бабочка снова может сделать аналогичный ход, и так далее до бесконечности.
При R = 3 у паука есть ещё один ход – по своему кольцу в противоположную сторону, когда он оказывается на одном радиусе с бабочкой. Но и тогда бабочку он не поймает. Та делает ход в любую сторону по своему кольцу, паук – по своему (идти вглубь паутины он не может – упускает бабочку), и так до бесконечности.
Рассмотрим следующую стратегию бабочки: двигаться в центр паутины, а потом уходить по радиусу, наиболее удалённому от паука. При этом паук через центр её не догонит (отстаёт по крайней мере на ход), а перехватить, двигаясь по кольцу (естественно, наружному, остальные менее выгодны), сможет только если ему хватит ходов. Это будет при K ≥ R/2 при чётном R и при K ≥ R–1/2 при нечётном R.
Пусть такое неравенство выполнено. Если бабочка двигается по своему кольцу, паук преследует её, не давая вылететь. Как только бабочка делает ход к центру паутины, паук встаёт на её радиус. Далее он сохраняет это свойство по отношению к ней (например, перемещаясь со внешнего кольца на следующее и обратно), тем самым, не давая ей вылететь, пока бабочка не попадает в центр (тут пауку надо выйти на внешнее кольцо, а если он на нём – сместиться по нему куда
угодно). Далее пауку нужно посмотреть, куда двинулась бабочка, и идти ей наперехват по внешнему кольцу (в ту сторону, где путь короче). Вскоре они снова окажутся на одном радиусе (если бабочка будет двигаться не только наружу, она тем более потеряет время, если снова вернётся в центр – паук должен снова действовать так, как описано выше). Далее действия паука повторяются. Итак, в этом случае никто не имеет выигрышной стратегии.
Ответ
а), б) Ничья; в) бабочка выиграет; г) при K ≥ [R/2] ничья, в остальных случаях бабочка выиграет.
|
|
|
Задача 111910 |
|
|
Двое играющих по очереди пишут – каждый на своей половине доски – по одному натуральному числу (повторения разрешаются) так, чтобы сумма всех чисел на доске не превосходила 10000. После того, как сумма всех чисел на доске становится равной 10000, игра заканчивается подсчетом суммы всех цифр на каждой половине. Выигрывает тот, на чьей половине сумма цифр меньше (при равных суммах – ничья). Может ли кто-нибудь из игроков выиграть, как бы ни играл противник?
Решение
Второй может гарантировать себе ничью: ему достаточно всё время писать числа с суммой цифр 1 (например, просто число 1) – действительно, он делает не больше ходов, чем первый, и на каждом ходе пишет число с не большей суммой цифр. Более того, по той же причине первый игрок проиграет, если хотя бы один раз напишет число с суммой цифр больше 1.
Пусть теперь оба игрока пишут только числа с суммой цифр 1 – то есть 1, 10, 100, 1000 или 10000. Тогда проиграть второй не может, а чтобы
выиграть, ему нужно вынудить противника сделать больше ходов; или, что то же
самое, сделать последний ход.
Докажем, что отвечая на числа 10 и 1000 числом 1, а на числа 100 и 1
числом 10, второй игрок добьётся успеха. Действительно, после каждого его хода
сумма чисел на доске делится на 11, а 10000 на 11 не делится. Поэтому остаётся лишь проверить, что такой ход всегда легален – то есть что после него
сумма не станет больше 10000. Для этого заметим, что первое большее 10000
число, кратное 11, – это 10010, а его нельзя получить, прибавляя 1
или 10 к числу, меньшему 10000.
Ответ
Второй игрок может выиграть.
|
|
|
Задача 115395 |
|
|
Шашка бьёт шашку соперника, стоящую на соседнем поле, если следующее за ним поле свободно. При этом своя шашка перемещается на это свободное поле, а побитая шашка соперника снимается с доски.
Бить обязательно: если есть возможность бить, делать вместо этого простой ход какой-либо шашкой нельзя.
Если шашка, побившая шашку соперника, может сразу побить следующую его шашку, она должна продолжать бить тем же ходом.
Кто — Белые или Чёрные — победят в этой игре вне зависимости от игры партнёра? Рассмотрите случаи:
а) У игроков по одной шашке, поле длиной N>2 клеток;
б) У игроков по две шашки, поле длиной N>4 клеток;
в) У игроков по три шашки, поле длиной N>6 клеток;
г) Дополнительное задание. Можно подумать, что численное преимущество решает исход игры. Придумайте и нарисуйте, однако, позицию, где у Белых меньше шашек, чем у Чёрных, и тем не менее, Белые начинают (с простого хода) и выигрывают.
Решение
В этой игре Белые, бесспорно, имеют преимущество, хотя иногда они и проигрывают. Клетки поля мы для удобства иногда будем нумеровать слева направо: 1, 2, 3, .. (N-1), N .В пункте "а" при N=3 Белые проиграют (этот тривиальный случай многие "прозевали"), а в остальных случаях — победят, передвинув шашку с клетки 1 на клетку (N-2) . Эта атака — поставить свою шашку за одну клетку до шашки противника — будет часто в дальнейшем применяться Белыми.
В пункте "б" Белые тоже, казалось бы, должны идти с клетки 2 на (N-3) . Однако, такой ход возможен только если N-3>2 , то есть N>5 . В этом случае у Чёрных только один ход, следует размен, и возникает положение (рис. 5). Теперь Белые ходят с 1 на (N-4) (это возможно, так как N-4>1 при N>5 ) и выигрывают.
Случай же N=5 разбирается отдельно. Все ходы там вынужденные, и побеждают тоже Белые.
В пункте "в" Белые тоже побеждают, атакуя стандартным образом, но это возможно только при N>8 . Вот как пойдёт игра: Белые: 3
Случаи N=7 и N=8 требуют отдельного разбора. При N=7 ход у Белых один, далее серия вынужденных разменов, и возникает позиция (рис. 7), где Белые легко побеждают.
При N=8 у Белых теоретически два возможных первых хода. Поддаться первым ходом ( 3
Возможное (видимо, простейшее) решение дополнительного задания представлено на рисунке 10. Пусть у Чёрных две шашки, у белых — только одна. Ходя на клетку влево, Белые вынуждают Чёрных сдать обе свои шашки следующим ходом.
|
|
|
Страница: << 17 18 19 20 21 22 23 >> [Всего задач: 162]
