Вася отметил невидимыми чернилами одну из клеток таблицы размером $5\times5$ клеток. Разрешается выделить в таблице четыре идущих подряд по горизонтали или вертикали клетки и спросить у Васи, есть ли среди них отмеченная. Каждый следующий вопрос задается после ответа на предыдущий. За какое наименьшее количество таких вопросов можно наверняка определить отмеченную клетку?
Ответ:
Решение:
Петя и Вася играют в такую игру. Вначале в каждой из 2022 коробок лежит по одной спичке. За один ход можно переложить все спички из любой непустой коробки в любую другую непустую коробку. Ходят по очереди, начинает Петя. Побеждает тот, после хода которого в какой-то коробке впервые окажется не меньше половины всех спичек. Кто победит при правильной игре?
Ответ:
Решение:
На столе лежит 101 кучка по 101 спичке. За один ход берется одна спичка из любой кучки. Двое игроков ходят по очереди. Если не позднее 10 000-го хода будет взята последняя спичка из какой-то кучки, взявший её выигрывает, иначе — ничья. Может ли кто-то из игроков выиграть независимо от игры соперника, и если да, то кто?
Ответ:
Решение:
На окружности отмечены 48 точек, делящих ее на равные дуги. Играют двое, ходят по очереди. За один ход разрешается стереть либо три отмеченные точки, лежащие в вершинах равностороннего треугольника, либо четыре отмеченные точки, лежащие в вершинах квадрата. Дважды стирать одну точку нельзя. Проигрывает тот, кто не может сделать ход. Кто при правильной игре выиграет независимо от действий соперника: тот, кто делает первый ход, или тот, кто ходит вторым?
Ответ:
Решение:
На столе лежит палочка длиной 10 см. Петя ломает её на две части и кладёт обе получившиеся палочки на стол. С одной из лежащих на столе палочек Вася проделывает ту же операцию, потом то же делает Петя и т. д. по очереди. Петя хочет, чтобы после 18 разломов все получившиеся палочки были короче 1 см. Вася хочет помешать Пете. Кто из них имеет возможность добиться своей цели независимо от действий соперника?
Ответ:
Решение:
Двое играют в такую игру. За один ход можно положить в одну из клеток квадратной доски $1001\times1001$ один камешек (первоначально доска пуста; в одной клетке может лежать любое число камешков). Ходят по очереди. Как только в каком-то ряду (вертикали или горизонтали) оказывается более 5 камешков, сделавший последний ход признается проигравшим. Кто из игроков сможет выиграть независимо от действий соперника: тот, кто делает первый ход или тот, кто ходит вторым?
Ответ:
Решение:
Коля и Дима играют в игру на доске $8\times8$, делая ходы по очереди, начинает Коля. Коля рисует в клетках крестики, а Дима накрывает прямоугольниками $1\times2$ (доминошками) пары соседних по стороне клеток доски. За свой ход Коля должен поставить один крестик в любую пустую клетку (т. е. в клетку, в которой ещё не нарисован крестик и которая ещё не покрыта доминошкой). Дима за свой ход должен накрыть доминошкой две клетки (ещё не накрытые другими доминошками), в которых суммарно чётное число крестиков (0 или 2). Проигрывает тот, кто не может сделать ход. Кто из игроков имеет выигрышную стратегию?
Ответ:
Решение:
Двум мудрецам, А и Б, назначено испытание. Наутро их приведут в комнату, где на столе по кругу будут лежать шесть одинаковых с виду таблеток, из которых четыре безвредны, а две отравлены. Затем мудрецу А сообщат, какие таблетки отравлены, но передать информацию Б он уже не сможет. Мудрецы должны по очереди (начинает А) съедать по таблетке, пока не останется только две ядовитых. Как мудрецам заранее договориться, чтобы успешно пройти испытание?
Ответ:
Решение:
Есть две коробки, в одной 2017 конфет, а в другой 2018. Играют двое, ходят по очереди. За один ход каждый может съесть любое количество конфет, отличное от нуля, из любой коробки. Правила игры не допускают, чтобы после какого-то хода число конфет в одной из коробок делилось на число конфет в другой. Проигрывает тот, кто не может сделать ход, не нарушив этого условия. Кто сможет выиграть: начинающий игру или второй игрок, как бы ни играл его соперник?
Ответ:
Решение:
Германн и Чекалинский разложили на столе 13 различных карт. Каждая карта может лежать в одном из двух положений: рубашкой вверх или рубашкой вниз. Игроки должны по очереди переворачивать по одной карте. Проигрывает тот игрок, после хода которого повторится какая-то из предыдущих ситуаций (включая изначальную). Первый ход сделал Чекалинский. Кто сможет выиграть независимо от того, как будет играть соперник?
Ответ:
Решение:
Вася знает, что Петя задумал натуральное число, не большее 4. Вася может указать любое натуральное число или несколько чисел и спросить Петю, есть ли задуманное число среди них (например: «Верно ли, что задуманное число равно 2?» или «Верно ли, что задуманное число равно 2 или 3?»). Петя должен ответить «Да» или «Нет». Как Васе за 11 вопросов узнать задуманное число, если Петя в ответ может и соврать, но не больше трех раз?
Ответ:
Решение:
Юра и Яша играют в следующую игру, делая ходы по очереди. Первым ходит Юра.
Изначально на доске написано число $n$. Игрок в свой ход может прибавить к числу на доске любой его натуральный делитель, стереть старое число и записать новое. (Например, если на доске написано число 12, то можно его стереть и написать одно из чисел 13, 14, 15, 16, 18, 24.)
Рассмотрим все возможные натуральные значения $n$ от 2 до 59 включительно.
1. Для скольких из них Юра имеет выигрышную стратегию, если проигрывает тот, кто получит после своего хода число, не меньшее 60?
2. Для скольких из них Юра имеет выигрышную стратегию, если побеждает тот, кто получит после своего хода число, не меньшее 60?
Изначально на доске написано число $n$. Игрок в свой ход может прибавить к числу на доске любой его натуральный делитель, стереть старое число и записать новое. (Например, если на доске написано число 12, то можно его стереть и написать одно из чисел 13, 14, 15, 16, 18, 24.)
Рассмотрим все возможные натуральные значения $n$ от 2 до 59 включительно.
1. Для скольких из них Юра имеет выигрышную стратегию, если проигрывает тот, кто получит после своего хода число, не меньшее 60?
2. Для скольких из них Юра имеет выигрышную стратегию, если побеждает тот, кто получит после своего хода число, не меньшее 60?
Ответ:
Решение:
У Малыша и Карлсона есть длинная шоколадка $15\times100$. Они по очереди выедают из неё квадратные куски любого размера (куски можно выедать только по линиям сетки). Начинает Карлсон. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?
Ответ:
Решение:
Пятачок и Винни-Пух решили съесть квадратную шоколадку $7\times7$. Они поочерёдно по клеточкам выедают из неё кусочки: Пятачок — $1\times1$, Винни-Пух — $2\times1$ или $1\times2$ (кусочки можно выедать не обязательно с краю). Первый ход делает Пятачок. Если перед ходом Винни-Пуха в шоколадке не осталось ни одного кусочка $2\times1$ или $1\times2$, то вся оставшаяся шоколадка достаётся Пятачку. Кто из друзей сможет съесть больше половины всей шоколадки вне зависимости от действий второго?
Ответ:
Решение:
В Тридесятом царстве из каждого города выходит по 30 дорог, причём каждая дорога соединяет два города, не проходя через другие города. Тридесятый царь захотел разместить в некоторых городах по дорожно-эксплуатационному управлению (ДЭУ), обслуживающему все выходящие из города дороги, так, чтобы каждая дорога обслуживалась хотя бы одним управлением и управления были размещены не более чем в половине городов. Может ли так оказаться, что у царя существует ровно 2018 способов сделать это?
Ответ:
Решение:
Между городами страны организованы двусторонние беспосадочные авиарейсы таким образом, что от каждого города до каждого другого можно добраться (возможно, с пересадками). Более того, для каждого города $A$ существует город $B$ такой, что любой из остальных городов соединён напрямую с $A$ или с $B$. Докажите, что от любого города можно добраться до любого другого не более чем с двумя пересадками.
Ответ:
Решение:
В стране Графинии $n$ ($n\geqslant2$) городов. Некоторые города соединены беспосадочными авиалиниями (по каждой авиалинии выполняются рейсы в обоих направлениях) таким образом, что из любого города можно самолётами (возможно, с пересадками) добраться до любого другого, но закрытие любой авиалинии нарушает это свойство. При этом из любого города выходит не больше $d$ авиалиний. Докажите, что все города Графинии можно разбить не более чем на $\frac{n}{2}+d$ групп таким образом, чтобы каждая авиалиния соединяла города из разных групп и для любых двух групп существовало не более одной авиалинии, соединяющей города из этих групп.
Ответ:
Решение:
На олимпиаду приехало несколько участников из $n\gt 1$ регионов, некоторые из них дружат (дружба всегда взаимна). Выяснилось, что для произвольной рассадки нескольких (хотя бы трёх) участников за круглым столом, при которой любые два соседа дружат, участников из каждого региона за столом окажется не более половины общего числа детей за столом. Докажите, что участников можно рассадить по $n$ кабинетам так, чтобы любые два друга оказались в разных кабинетах.
Ответ:
Решение:
В стране $2n$ городов ($n$ — натуральное), некоторые из них соединены двусторонними беспосадочными авиалиниями. Из любого города можно попасть в любой другой, возможно, с пересадками. Президент хочет разделить страну на две области и включить каждый город в одну из двух областей. При этом авиалинии разделятся на $k$ межобластных и $m$ внутриобластных. Докажите, что президент может добиться того, чтобы выполнялось неравенство $k-m\geqslant n$.
Ответ:
Решение:
В стране $N$ городов. В ней действует $N(N-1)$ дорог с односторонним движением: по одной дороге из $X$ в $Y$ для каждой упорядоченной пары городов $X\ne Y$. У каждой дороги есть цена её обслуживания. Для данного $k=1,\ldots,N$ рассмотрим все способы выделить $k$ городов и $N-k$ дорог так, чтобы из каждого города можно было попасть в какой-то выделенный город, пользуясь только выделенными дорогами. Такую систему городов и дорог с наименьшей суммарной стоимостью обслуживания назовём $k$-оптимальной. Докажите, что города можно пронумеровать от 1 до $N$ так, что при каждом $k=1,2,\ldots,N$ существует $k$-оптимальная система дорог с выделенными городами $1,2,\ldots,k$.
Ответ:
Решение: