Германн и Чекалинский разложили на столе 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$.
Ответ:
Решение:
В стране 998 городов. Некоторые пары городов соединены двусторонними авиарейсами. Согласно закону, между любой парой городов должно быть не больше одного рейса. Другой закон требует, чтобы для любой группы городов было не больше $5k+10$ рейсов, соединяющих два города этой группы, где $k$ — количество городов в группе. В настоящий момент законы соблюдены. Докажите, что министерство развития может ввести несколько новых рейсов так, чтобы законы по-прежнему соблюдались, а общее количество рейсов в стране стало равным 5 000.
Ответ:
Решение:
У каждой из 100 девочек есть по 100 шариков; среди этих 10000 шариков есть по 100 шариков 100 различных цветов. Две девочки могут обменяться, передав друг другу по шарику. Они хотят добиться того, чтобы у каждой девочки было по 100 разноцветных шариков. Докажите, что они могут добиться этого такой серией обменов, чтобы любой шарик участвовал не более чем в одном обмене.
Ответ:
Решение:
В лагерь приехали 10000 детей, каждый дружит ровно с 11 другими детьми в лагере (дружба взаимна). Каждый ребёнок носит футболку одного из семи цветов радуги, причём у любых двух друзей цвета различны. Вожатые потребовали, чтобы какие-нибудь дети (хотя бы один) надели футболки других цветов (из тех же семи). Опрос показал, что 100 детей менять цвет не намерены. Докажите, что некоторые из остальных детей всё же могут изменить цвета своих футболок так, чтобы по-прежнему у любых двух друзей цвета были различны.
Ответ:
Решение:
В стране есть $n\gt 1$ городов, некоторые пары городов соединены двусторонними беспосадочными авиарейсами. При этом между любыми двумя городами существует единственный авиамаршрут (возможно, с пересадками). Мэр каждого города $X$ подсчитал количество таких нумераций всех городов числами от 1 до $n$, что на любом авиамаршруте, начинающемся в $X$, номера городов идут в порядке возрастания. Все мэры, кроме одного, заметили, что их результаты подсчётов делятся на 2016. Докажите, что и у оставшегося мэра результат также делится на 2016.
Ответ:
Решение:
На соревнованиях по фигурному велосипедированию было 100 судей. Каждый судья упорядочил всех участников (от лучшего по его мнению — к худшему). Оказалось, что ни для каких трёх участников $A$, $B$, $C$ не нашлось трёх судей, один из которых считает, что $A$ — лучший из трёх, а $B$ — худший, другой — что $B$ лучший, а $C$ худший, а третий — что $C$ лучший, а $A$ худший. Докажите, что можно составить общий рейтинг участников так, чтобы для любых двух участников $A$ и $B$ тот, кто выше в рейтинге, был бы лучше другого по мнению хотя бы половины судей.
Ответ:
Решение:
У Васи есть 20 гирь, среди которых нет трёх, равных по весу. Он может разложить эти все гири как на 10, так и на 11 куч с равными весами. Докажите, что у Васи найдутся две гири, веса которых различаются ровно в 4 раза.
Ответ:
Решение:
В стране некоторые пары городов соединены односторонними прямыми авиарейсами (между любыми двумя городами есть не более одного рейса). Скажем, что город $A$ доступен для города $B$, если из $B$ можно долететь в $A$, возможно, с пересадками. Известно, что для любых двух городов $P$ и $Q$ существует город $R$, для которого и $P$, и $Q$ доступны. Докажите, что существует город, для которого доступны все города страны. (Считается, что из города можно долететь до него самого.)
Ответ:
Решение:
В классе каждый ученик дружит ровно с шестью другими, и у любых двух учеников есть ровно два общих друга. Сколько учеников в этом классе?
Ответ:
Решение:
Однажды зимой 43 ребёнка бросались снежками. Каждый из них бросил ровно один снежок в кого-то другого. Известно, что:
- первый бросил снежок в того, кто бросил снежок во второго,
- второй бросил снежок в того, кто бросил снежок в третьего,
- …
- сорок третий бросил снежок в того, кто бросил снежок в первого.
Ответ:
Решение: