Задача 254. Игра в «Перемещение фишки»-VI
На доске 50×50 на клетках одной из диагоналей стоит по шашке. Андрей и Борис ходят по очереди, начинает Андрей. За один ход игрок сдвигает одну из шашек на одну клетку вниз. Если при этом шашка сходит с доски, игрок забирает ее себе в карман. Какое наибольшее количество шашек может забрать себе в карман Андрей, как бы ни играл Борис?
Решение:
Пронумеруем шашки в соответствии с их высотой на диагонали. Так Андрей забирает первую шашку первым ходом. Далее его стратегия заключается в спуске всех шашек на вторую линию. Если Борис какую-то спускает на первую, то Андрей следующим ходом её забирает, что не меняет порядка и чётности ходов. На спуск всех шашек со второй по пятидесятым ребятам потребуется 0+1+…+48=1176 ходов. Это число кратно двум, при этом ход Андрея всегда чётный (не учитывая его первый ход, где он забрал первую шашку), поэтому, когда все шашки будут не выше второй линии, то будет очередь хода Бориса. Отсюда следует, что Андрей может забрать их все.
Ответ:
50.
Задача 255. Игра в «В слепую»-III
На бесконечном шоссе находятся полицейская машина (ездит со скоростью до 100 км/ч) и вор на угнанном мотоцикле (ездит со скоростью до 80 км/ч). Полицейские не знают, в каком месте шоссе находится вор. Как им действовать, чтобы наверняка догнать вора? (Вор не может съехать с шоссе или спрятаться).
Решение:
Отправим мысленно в обе стороны дороги двух помощников, едущих со скоростью большей, чем скорость вора, но меньшей, чем скорость полицейской машины. Пусть полицейская машина догонит сначала первого помощника, потом — второго, потом — снова первого, потом — снова второго и т. д. Ясно, что когда-нибудь один из помощников перегонит угонщика, а значит, и полицейский когда-то догонит угонщика.
Задача 256. Игра в «Заполнение доски»-XXIV
Город представляет собой прямоугольную сетку 10×12. Две компании по очереди ставят на неосвещенных перекрестках фонари. Каждый фонарь освещает в городе прямоугольник с вершиной в этом фонаре, являющийся правым-нижним углом города. Проигрывает компания, которая осветит последний перекресток. Какая компания побеждает при правильной игре?
Решение:
Заметим, что так как игра конечна, то одна из компаний точно имеет выигрышную стратегию. Покажем, что это не может быть вторая компания. Предположим противное.
Тогда первым ходом за первую компанию поставим фонарь в правый нижний узел сетки. Этот фонарь не освещает других перекрестков, а любой другой фонарь освещает тот перекресток, на котором он стоит.
Теперь на каждый ход второго игрока будем отвечать согласно его выигрышной стратегии, то есть ставить фонарь в ту клетку, в которую при выигрышной стратегии на очередном шаге поставил бы фонарь второй игрок, если бы нашего первого хода не было.
Заметим, что такой ход всегда возможен: первый нами поставленный фонарь на игру не влияет. Ведь никакие другие перекрестки он не освещает, а тот перекресток, в котором он стоит, в любом случае сразу бы осветили, значит, в стратегии второго игрока не может быть хода, на котором он ставит фонарь в правый нижний узел. Поэтому у нас на месте первой компании всегда есть ход, значит, мы побеждаем.
Итак, мы получили противоречие, значит, у второй компании выигрышной стратегии нет. А так как при правильной игре всегда выигрывает одна и та же компания, то это первая компания, что мы и доказывали.
Ответ:
Выигрывает первая.
Задача 257. Игра в «Заполнение доски»-XXV
В ряд выложен 2021 шарик. Андрей и Борис играют в игру, делая ходы по очереди, начинает Андрей. За каждый ход разрешается покрасить один из еще не покрашенных шариков в один из трёх цветов: красный, жёлтый или зелёный (в начале игры все шарики не покрашены). После того, как все шарики покрашены, победа присуждается Андрею, если в ряду найдутся три подряд идущих шарика трёх разных цветов; иначе победа присуждается Борису. Кто из игроков имеет выигрышную стратегию?
Решение:
Приведём одну из возможных выигрышных стратегий за Андрея.
Пронумеруем шарики подряд числами от 1 до 2021. Первым ходом покрасим в красный цвет шарик номер 1011 (средний во всём ряду). Пусть Борис, не умаляя общности, свой ход сделал в левую половину. Тогда вторым ходом Андрей красит в жёлтый цвет шарик с номером 1014.
Таким образом, Андрей после своих двух первых ходов получил ситуацию KOOЖ. Если Борис покрасит один из двух шариков между покрашенными Андреем в красный или жёлтый цвет, то Андрей сможет сразу докрасить оставшийся шарик в зелёный цвет так, чтобы образовалась тройка подряд идущих разноцветных. Если Борис покрасит один из двух шариков в зелёный, то Андрей в ответ покрасит оставшийся шарик в красный цвет, и снова образуется разноцветная тройка лежащих подряд шариков.
Осталось заметить, что Андрей может заставить Бориса сделать ход между покрашенными первыми двумя ходами шариками. Сам Андрей туда ходить не будет, и после покраски всех остальных шариков по чётности будет ход Бориса. Значит, Андрей победит.
Ответ:
Андрей.
Задача 258. Игра в «Камешки»-XXX
Есть 5 запечатанных коробок карандашей, в которых 10, 11, 12, 13, 14 карандашей (на каждой написано, сколько в ней). Андрей и Борис берут себе по очереди по карандашу, пока не разберут все; начинает Андрей. Каждый игрок в любой момент имеет право распечатать коробку, заплатив за это рубль сопернику. Кто и сколько рублей выиграет при наилучшей игре сторон?
Решение:
Заметим, что Борис может открыть не более одной коробки. Действительно, если Андреем открывается коробка с чётным числом карандашей, то следующую коробку также придётся открывать Андрею. Тогда Андрей должен открыть хотя бы одну коробку с нечётным числом карандашей. Борису же достаточно ровно в этот момент открыть другую нечётную коробку — суммарно в них будет чётное число карандашей, поэтому следующую коробку также открывает Андрей. Почему одну коробку Борису придётся открыть? Потому что Андрей может начать игру с нечётной коробки, возьмёт из неё последний карандаш, поэтому Борису придётся открыть вторую. В итоге Борис откроет на три коробки меньше и выиграет 3 рубля.
Ответ:
Борис - 3 рубля.
Задача 259. Игра в «Числа»-XXVI
На столе лежат 10 карточек с числами 1, 2, 3, …, 10. Андрей и Борис по очереди берут по карточке, пока не разберут все. Начинает Андрей. Какую наибольшую сумму может гарантировать себе Андрей, как бы ни играл Борис?
Решение:
Играя за Андрея, хочется каждый раз брать карточку с наибольшим числом. Однако Борис тоже может брать такие карточки и мешать нам. Поймем, что на первом ходе Андрей может взять карточку с числом 10, на втором шаге — с числом хотя бы 8 (хотя бы одна карточка из трех наибольших еще осталась), на третьем — хотя бы 6, на четвертом — хотя бы 4, на пятом — хотя бы 2 (каждый раз берем наибольшую карточку из оставшихся). То есть мы доказали, что Андрей всегда может набрать себе хотя бы 10+8+6+4+2=30.
Однако Борис может тоже играть по такой же стратегии — брать каждый раз наибольшую карточку из оставшихся. Тогда, аналогично, Борис всегда может забрать себе 9+7+5+3+1=25. То есть Борис всегда может оставить Андрею не более 55-25=30.
Тем самым мы доказали, что Андрей всегда может забрать себе 30, а Борис всегда может сделать так, чтобы больше 30 Андрей не забрал. Следовательно, наш ответ — ровно 30.
Ответ:
30.
Задача 260. Игра в «В слепую»-IV
Андрей загадал целое число, а Борис пытается его угадать. На каждом шаге он выбирает целое число N и задает Андрею вопрос: «Верно ли, что загаданное число равно N?».
(a) Если Борис не угадал, то Андрей обязан перезагадать свое число, увеличив его на N.
(b) Если Борис не угадал, то Андрей сообщает Борису, больше или меньше загаданное число, чем N, а затем обязан перезагадать свое число, либо увеличив его на N либо уменьшив его на N (Борис не знает, какой из этих двух вариантов выберет Андрей).
Может ли Борис действовать так, чтобы через несколько шагов гарантированно угадать текущее загаданное число?
Решение:
(a) Пусть Андрей загадал значение — х, а Борис задаст вопросы следующего вида: «Верно ли, что загаданное число равно n+Sn?», где n — какое-то число, Sn — сумма чисел из предыдущих вопросов. По условию Андрей увеличивал свое значение на число из вопроса Бориса, если Борис не угадал, поэтому вопрос Бориса вида: «Верно ли, что загаданное число равно n+Sn?» — по смыслу эквивалентен вопросу: «Верно ли, что x=n?».
Переберем значения n в следующем порядке: 0, 1, -1, 2, -2, 3, -3,…
То есть первые несколько вопросов выглядят так:
«Верно ли, что загаданное число равно 0?»
«Верно ли, что загаданное число равно 1+0?»
«Верно ли, что загаданное число равно -1+((1+0)+0)?»
«Верно ли, что загаданное число равно 2+((-1+1+0)+(1+0)+0)?»
…
Тогда Борис рано или поздно выберет значение n равное изначально загаданному x и, спросив «Верно ли, что загаданное число равно x+Sn» угадает текущее число.
(b) Пусть Борис сначала задаст вопрос, который не изменит числа: «Верно ли, что загаданное число равно 0?» Либо он угадает, либо сможет узнать знак загаданного числа. Без ограничения общности далее считаем, что загаданное число положительное, иначе задаем следующие вопросы с противоположным знаком. (И также будем считать - что если Борис угадал число в какой-то момент, то он автоматически выиграл.)
Теперь пусть Петя задает вопросы вида:
«Верно ли, что загаданное число равно 2-1?»
«Верно ли, что загаданное число равно 22-1?»
«Верно ли, что загаданное число равно 23-1?»
«Верно ли, что загаданное число равно 24-1?»
…
«Верно ли, что загаданное число равно 2k-1?»
Если Андрей ответит, что загаданное число в данный момент N>2k-1, то после вычитания или прибавления к N числа 2k-1 новое число также будет строго положительным.
Борис будет задавать вопросы до тех пор, пока впервые не получит ответ, что в данный момент загаданное число N<2k-1. Заметим, что такой момент наступит, потому что 2k-1=(2-1)+(22-1)+…+(2k-1-1)+k, то есть как минимум на шаг с номером k0, где k0 — изначальное загаданное число, Андрей ответит отрицательно на этот вопрос, так как каждый раз число увеличивалось максимум — на сумму чисел во всех предыдущих вопросах.
Перед последним вопросом загаданное число будет лежать в границах 0<N<2k-1, то есть после изменения на 2k-1 оно не превосходит по модулю числа 2k+1-2.
Пусть Борис задаст вопрос: «Верно ли, что загаданное число равно 0?» И тем самым поймет знак загаданного числа в данный момент.
То есть теперь нам известны знак и границы, в которых лежит текущее загаданное число.
После этого, пока не угадаем число, будем задавать вопросы:
«Верно ли, что загаданное число равно MAXi?», где MAXi — текущее максимальное по модулю значение для загаданного числа (может быть как положительным, так и отрицательным числом)
«Верно ли, что загаданное число равно 0?»
После первого вопроса (про MAXi) мы либо угадали число, либо "потенциальные числа" теперь изменили знак (то есть Андрей вычел MAXi из загаданного), либо сохранили знак (Андрей прибавил MAXi к загаданному числу). Следующий вопрос определяет прибавили или вычли MAXi и тогда мы снова знаем границы для загаданного числа, но теперь "потенциальных значений" на одно меньше. Значит, такими вопросами число рано или поздно будет угадано.
Ответ:
(a) Да
(b) Да
Задача 261. Игра в «Распределение»-III
Андрей принес Борису и Владимиру палку колбасы. Они начинают ее делить. Сначала Борис режет палку на две части разного веса. Затем Владимир режет одну из частей на две так, чтобы веса всех трёх кусков были различны. Из трёх полученных кусков Владимир берёт средний по весу, а остальные два куска достаются Борису. Какую наибольшую долю колбасы может себе гарантировать Борис при любых действиях Владимира?
Решение:
Назовём треть веса колбасы фунтом. Покажем, как Борис может получить не менее 2 фунтов. Сначала он делит колбасу на кусок A в 1 фунт и кусок B в 2 фунта. Если Владимир разделит B, то получатся части весом больше фунта и меньше фунта, поэтому Владимиру достанется кусок A в 1 фунт, а Борису — остальное. Если же Владимир разделит кусок A, то кусок B останется самым большим и достанется Борису, то есть Борис получит даже больше 2 фунтов. Покажем, как Владимир обеспечит себе не менее фунта. Когда Борис разрежет колбасу на два куска, Владимир посмотрит, есть ли среди них кусок в 1 фунт. Если есть, то он режет другой кусок на две части. Если нет, то Владимир от большего куска отрезает 1 фунт. В обоих случаях получаться три куска: меньше фунта, ровно фунт и больше фунта, и Владимиру достанется 1 фунт.
Ответ:
2/3 колбасы.
Задача 262. Шахматы на шахматном поле-V
На бесконечной шахматной доске стоят ферзь и невидимый король. Известно, что ферзь дал шах по горизонтали, и король ушел из под шаха. Докажите, что ферзь может ходить так, чтобы король наверняка еще раз попал под шах.
Решение:
Введем нумерацию горизонталей: пусть строка шахматной доски, на которой находится ферзь вначале будет 0-ой. Над горизонталью с ферзем – 1, 2,… горизонтали, а под ней -1, -2, …
Если король ушел из под шаха, то он находится либо на 1-ой, либо на -1-ой горизонтали.
Пусть первым ходом ферзь сходит на одну клетку вверх. Либо король попадет под шах, либо он был на горизонтали с номером -1, а после своего хода может находиться только на 0-ой, (-1)-ой, или (-2) -ой строчке.
Назовем “шагом вправо” следующие два подряд хода ферзя:
1) По диагонали вправо-вниз на три клетки; (после такого хода либо король попадает под шах, либо после своего хода может находиться только на 0-ой, (-1)-ой, или 1-ой строчке.)
2) На три клетки вверх; (либо король попадает под шах, либо после своего хода находится только на 0-ой, (-1)-ой, или (-2)-ой строчке.)
Аналогично “шаг влево”:
1) По диагонали влево-вниз на три клетки;
2) На три клетки вверх;
Заметим, что когда ферзь делает “шаг влево” или “шаг вправо”, он сдвигается на 3 клетки вправо или влево. Также король всегда должен находится на полосе из 0 и (-1)-ой горизонтали, иначе попадет под шах. И также можно заметить, что за один “шаг” король будет атакован, если он находился между вертикалями начальной и конечной позиции “шага”. То есть задача сводится к тому, что нужно доказать, что ферзь сможет догнать короля “шагами влево и вправо”, если за один “шаг” ферзь перемещается на 3 клетки по горизонтали, а король максимум на 2 клетки по горизонтали.
Но это утверждение уже легко доказать: отправим мысленно в обе стороны две вспомогательные фигуры, перемещающиеся со скоростью 2,5 клетки за “шаг”. Пусть ферзь догонит сначала первого помощника, потом — второго, потом — снова первого, потом — снова второго и т. д. Ясно, что когда-нибудь один из помощников перегонит короля, а значит, и ферзь когда-то догонит короля, то есть король когда-то будет под шахом.
Задача 263. Игра в «Крестики-нолики»-VI
Игра происходит на клетчатом поле 9×9. Андрей и Борис ходят по очереди, начинает Андрей. Он ставит в свободные клетки крестики, Борис — нолики. Когда все клетки заполнены, подсчитывается количество строк и столбцов, в которых крестиков больше, чем ноликов, — число K и количество строк и столбцов, в которых ноликов больше, чем крестиков, — число H (всего строк и столбцов — 18). Какую наибольшую разность K-H может обеспечить Андрей, как бы ни играл Борис?
Решение:
Первый игрок может занять первым ходом центральную клетку, а далее действовать симметрично второму игроку (относительно центра). В результате в центральных строке и столбце крестиков будет больше, а все остальные разобьются на пары центрально симметричных (так столбцу будет соответствовать столбец, горизонтально симметричный ему), где один ходит в K (как множество таких), а другой — в H, поскольку число крестиков и ноликов в них будет также симметричным. В итоге разница K-H=2.
Второму игроку, чтобы не допустить худшего для себя исхода, следует играть так — если у него есть возможность сходить (центрально) симметрично ходу первого игрока, то он так и делает. Иначе он ходит в случайное место, но не в центр. В итоге он добьётся того же симметричного распределения, как добивался выше первый с тем же результатом.
Ответ:
2.