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