В стране 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 ребёнка бросались снежками. Каждый из них бросил ровно один снежок в кого-то другого. Известно, что:
- первый бросил снежок в того, кто бросил снежок во второго,
- второй бросил снежок в того, кто бросил снежок в третьего,
- …
- сорок третий бросил снежок в того, кто бросил снежок в первого.
Ответ:
Решение:
В шахматном турнире в один круг участвовало два мальчика и несколько девочек. Мальчики набрали на двоих 8 очков, в то время как все девочки набрали очков поровну. Сколько девочек могло участвовать в турнире? (Победа — 1 очко, ничья — 0,5 очка, поражение — 0 очков.)
Ответ:
Решение:
В стране 100 городов. Между любыми двумя городами либо нет соединения, либо налажено авиасообщение, либо есть железная дорога (одновременно и авиасообщения, и железной дороги быть не может). Известно, что если два города соединены с третьим железной дорогой, то между ними есть авиалиния, а если два города соединены с третьим авиалиниями, то между ними есть железная дорога. Из-за стихийного бедствия отменили все авиарейсы в стране. Правительство постановило в некоторых городах разместить центры гуманитарной помощи, причём так, чтобы из каждого города можно было добраться в подобный центр. Докажите, что необходимо открыть хотя бы 20 таких центров.
Ответ:
Решение:
На квалификационное соревнование, по результатам которого отбираются участники на областной чемпионат, подали заявки 80 команд. Отбор происходит по следующей схеме.
У каждой команды есть некоторый счёт побед и поражений (изначально 0–0). В каждом матче принимают участие две команды с одинаковым текущим счётом, и одна из них побеждает, а другая проигрывает (ничьих не бывает). Если команда набирает 3 поражения, она выбывает из отбора. Если команда набирает 3 победы, она выходит в основную часть и тоже прекращает участие в квалификационном соревновании. Турнир оканчивается, когда судьба каждой команды будет определена.
1. Сколько команд попадёт на областной чемпионат?
2. Сколько будет сыграно матчей?
У каждой команды есть некоторый счёт побед и поражений (изначально 0–0). В каждом матче принимают участие две команды с одинаковым текущим счётом, и одна из них побеждает, а другая проигрывает (ничьих не бывает). Если команда набирает 3 поражения, она выбывает из отбора. Если команда набирает 3 победы, она выходит в основную часть и тоже прекращает участие в квалификационном соревновании. Турнир оканчивается, когда судьба каждой команды будет определена.
1. Сколько команд попадёт на областной чемпионат?
2. Сколько будет сыграно матчей?
Ответ:
Решение:
В футбольном турнире участвовало десять команд, каждая сыграла с каждой один раз. Команды, занявшие первое и второе место, в сумме набрали всего лишь на пять очков меньше, чем все остальные команды вместе. Сколько очков набрала команда с минимальным количеством очков? За победу в футбольном турнире дают 3 очка, за ничью — 1, за поражение — 0.
Ответ:
Решение:
В стране 3 мегаполиса и 7 городков. Авиакомпания планирует расписание полётов между ними. Руководитель хочет, чтобы выполнялись следующие условия:
- от любого населённого пункта до любого другого можно добраться (прямым рейсом или с пересадками);
- если из пункта $A$ есть рейс в пункт $B$, то и из пункта $B$ есть рейс в пункт $A$;
- из двух мегаполисов можно улететь ровно в четыре населённых пункта, а из одного — в три;
- из каждого городка можно улететь ровно в один населённый пункт.
Ответ:
Решение:
В школьном шахматном турнире участвовали 4 человека: Андрей, Ваня, Дима и Саша. Каждый сыграл дважды с каждым своим соперником. В каждой игре за победу давалось 1 очко, за ничью — 0,5 очка, за поражение — 0 очков.
Известно, что по окончании турнира
Известно, что по окончании турнира
- все ребята набрали разное количество очков;
- Андрей занял первое место, Дима — второе, Ваня — третье, Саша — четвёртое;
- Андрей одержал столько же побед, сколько и Саша.
Ответ:
Решение:
В турнире по шашкам участвовали ученики 10 и 11 классов. Каждый сыграл с каждым один раз. За победу участник получал 2 очка, за ничью — 1 очко, за проигрыш — 0 очков. Одиннадцатиклассников было в 10 раз больше, чем десятиклассников, и они вместе набрали в 4,5 раза больше очков, нежели все десятиклассники. Сколько очков набрал самый успешный десятиклассник?
Ответ:
Решение:
В турнире участвовали 50 шахматистов. В некоторый момент турнира была сыграна 61 партия, причем каждый участник сыграл либо две партии, либо три (и никто не играл друг с другом дважды). Могло ли оказаться так, что никакие два шахматиста, сыгравшие по три партии, не играли между собой?
Ответ:
Решение:
На карте точками обозначены города, а линиями — дороги. Какое наименьшее число дорог нужно добавить, чтобы из городов выходило поровну дорог?
Ответ:
Решение:
В футбольном турнире принимали участие 35 команд, среди которых команды «Белка» и «Стрелка». Правила футбольного турнира следующие: каждая команда играет с каждой по одному разу, в каждом матче победившая команда получает 3 очка, проигравшая — 0 очков, а в случае ничьей обе команды получают по 1 очку. По результатам турнира команда «Белка» набрала 100 очков, а команда «Стрелка» со всеми командами сыграла вничью. А какая наибольшая сумма очков могла быть у команды, занявшей второе место по результатам турнира?
Ответ:
Решение:
В классе 31 ученик. У трёх из них ровно по три друга, у следующих трёх — по шесть, у следующих трёх — по девять, …, у следующих трёх — по тридцать. Сколько друзей у 31-го ученика? (Дружба между людьми взаимна.)
Ответ:
Решение: