Тема Открытая летняя олимпиада: хард

Открытая летняя олимпиада: хард

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#126400Максимум баллов за задание: 7

Во внутреннем дворике Храма Мудрости хранится запечатанный свиток, в котором записан древний приём из Стиля Обезьяны. Чтобы открыть шкатулку со свитком, нужно ввести шестизначный код, составленный из цифр, выбитых на камнях: $0,$ $1,$ $2,$ $3,$ $3,$ $4,$ $5.$ Каждый символ может быть использован только один раз, а код не может начинаться с $0$ и должен делится на $15.$ Сколько различных шестизначных чисел могут являться кодом?

“Код — не просто число. Он должен быть достоин знания, которое защищает.”

— Мастер Шифу

Показать ответ и решение

Чтобы код открывал шкатулку, он должен делиться на $15,$ то есть одновременно на $3$ и на $5.$ Делимость на $5$ означает, что код заканчивается на $0$ или $5.$ Делимость на $3$ означает, что сумма его цифр делится на $3.$ Так как на камнях выбиты цифры $0,$ $1,$ $2,$ $3,$ $3,$ $4,$ $5,$ их сумма равна $0 +1 +2 +3 +3 +4 +5 = 18.$ Следовательно, если из них составляется шестизначный код, то одна из цифр остаётся неиспользованной, и она должна делиться на $3$ (чтобы сумма оставшихся цифр тоже делилась на $3).$ Такими цифрами являются $0$ и $3.$

Если не используется $0,$ то последняя цифра — обязательно $5,$ остальные цифры — $1,$ $2,$ $3,$ $3$ и $4.$ Выбираем позиции для двух троек среди пяти возможных и расставляем остальные цифры:

2 C25 ⋅3!=-5⋅/4- ⋅(3 ⋅2 ⋅1) =10 ⋅6 = 60 /21

Если не используется одна из троек, то среди оставшихся цифр — $0,$ $1,$ $2,$ $3,$ $4,$ $5$ — все различны. Возможны два случая: последняя цифра — $0$ или $5.$ В первом случае (последняя — $0)$ оставшиеся цифры можно переставить как угодно: $5!= 120$ вариантов. Во втором случае (последняя — $5),$ $0$ не должен стоять первым, поэтому оставшиеся цифры можно переставить $4⋅4!= 4⋅24= 96$ способами.

Всего: $60 +120+ 96= 276$ возможных кодов.

Ответ: 276

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#126401Максимум баллов за задание: 7

В Долине Мира есть дворец площадью $100× 100,$ где размещено $100$ воинов, так что ни один не может ударить другого (никакие двое не стоят в одной горизонтали или одной вертикали). Докажите, что в правом верхнем и левом нижнем квадратах $50× 50$ находится одинаковое количество воинов.

“Настоящий порядок проявляется, когда ты видишь баланс даже в хаосе.”

— Мастер Шифу

Показать доказательство

Разделим дворец на четыре равных квадрата размером $50× 50.$ Обозначим через $k$ число воинов, стоящих в левом верхнем квадрате. Тогда вместе левый и правый верхние квадраты покрывают верхние $50$ строк дворца — в них могут находиться ровно $50$ воинов. Следовательно, в правом верхнем квадрате размещено $50 − k$ воинов. С другой стороны, левый и правый нижние квадраты содержат нижние $50$ строк, и в них тоже находятся $50$ воинов. Значит, в левом нижнем квадрате тоже размещено $50− k$ воинов.

Таким образом, в правом верхнем и левом нижнем квадратах размещено одинаковое число воинов, что и требовалось доказать.

Ошибка.
Попробуйте повторить позже

Задача 3#126402Максимум баллов за задание: 7

Мастер Шифу записал $2025$ чисел в свой древний свиток. Он заметил, что сумма любых двух из этих чисел также присутствует в списке. Какое наибольшее количество из этих чисел может быть ненулевым?

“То, что кажется хаотичным, подчиняется древнему равновесию. Даже Ци следует законам.”

— Мастер Угвей

Показать ответ и решение

Упорядочим все числа, записанные мастером Шифу, по возрастанию. Предположим, что два самых больших из них — $a$ и $b,$ где $a≥ b$ — оба положительные ( $a≥ b> 0).$ Тогда их сумма $a +b$ тоже должна быть записана в свитке. Но она больше $a,$ значит, в списке присутствует число больше максимального — противоречие. Следовательно, в списке может быть не более одного положительного числа. Аналогично, если два наименьших числа $c$ и $d$ — оба отрицательные ( $c≤ d< 0$ ), то их сумма $c+ d$ будет строго меньше $c$ и тоже должна быть в списке — значит, снова противоречие. Поэтому в списке может быть не более одного отрицательного числа.

Значит, среди чисел может быть не более двух ненулевых: одно положительное и одно отрицательное. Всё остальное — нули. Пример, где ровно два ненулевых числа: $1,$ $− 1$ и $2023$ нуля. Все условия задачи выполнены.

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 4#126403Максимум баллов за задание: 7

Во дворце Нефритового Лотоса прошла спартакиада по пяти боевым искусствам: кунг-фу, тайцзи, багуачжан, каратэ и ушу. Каждый из $30$ юных панд участвовал либо в одном, либо в трёх видах искусств. В каждом виде искусств участвовало либо $15,$ либо $25$ панд. Докажите, что такая ситуация невозможна.

“Даже вода, текущая по извилистой тропе, знает, куда ей течь. Если всё выглядит правильным, но ведёт в тупик — это не путь, а иллюзия пути.”

— Мастер Угвей

Показать ответ и решение

Рассмотрим граф, в котором вершины представляют собой $30$ юных панд и $5$ боевых искусств соответственно, а рёбра проведены от каждой панды к тем искусствам, в которых она участвовала. Поскольку каждая панда участвовала либо в одном, либо в трёх видах, из каждой вершины-панды выходит нечётное число рёбер. Всего панд $30,$ значит, общее число рёбер нечётное количество раз увеличивается — то есть общее число рёбер чётное.

Теперь посмотрим на вершины, соответствующие боевым искусствам. В каждом из пяти искусств участвовало либо $15,$ либо $25$ панд — и то, и другое числа нечётные. Значит, от каждой вершины-искусства выходит нечётное число рёбер. Пять нечётных чисел в сумме дают нечётное число — значит, общее число рёбер нечётное.

Получается, что одно и то же число рёбер одновременно чётное и нечётное — противоречие. Следовательно, такая ситуация невозможна, что и требовалось доказать.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 5#126404Максимум баллов за задание: 7

В Долине Мира на Площади Лотоса стартовал Турнир Красок — древняя стратегическая игра мастеров. В одном из матчей играют обезьянка Линь-Линь и кабан Чжу, по очереди раскрашивая $2024$ камня, выложенных в ряд. За каждый ход можно выбрать любой неокрашенный камень и раскрасить его в красный, жёлтый или зелёный цвет. Первой ходит Линь-Линь. Линь-Линь выигрывает, если где-то подряд окажутся камни трёх разных цветов. Иначе побеждает Чжу. Кто из игроков может гарантированно победить, если будет играть правильно?

“Победа приходит не к тому, кто делает первый шаг, а к тому, кто знает, куда ведёт последний.”

— Мастер Угвей

Показать ответ и решение

Предъявим выигрышную стратегию для кабана Чжу. Он мысленно разбивает $2024$ камня на пары: $1$ — $2,$ $3$ — $4,$ …, $2023$ — $2024.$ Когда Линь-Линь делает ход, выбирая и раскрашивая один камень из пары, Чжу на своём ходу выбирает второй камень из той же пары и красит его в тот же цвет. Таким образом, после каждого их полного хода каждая пара оказывается полностью раскрашенной в один цвет.

В конце игры все пары будут раскрашены, причём каждый камень в паре будет иметь тот же цвет, что и его сосед. Значит, в любом тройном наборе подряд идущих плиток обязательно найдутся две одинакового цвета — а значит, тройки из трёх разных цветов не появится нигде. Это значит, что Линь-Линь не сможет выиграть, если Чжу будет придерживаться этой стратегии.

Варианты правильных ответов:

Чжу
чжу
Кабан
кабан
Кабан Чжу
Кабан чжу
кабан Чжу
кабан чжу
Чжу.
чжу.
Кабан.
кабан.
Кабан Чжу.
Кабан чжу.
кабан Чжу.
кабан чжу.

Ошибка.
Попробуйте повторить позже

Задача 6#126405Максимум баллов за задание: 7

В Долине Мира расставлены $n$ древних фонарей (где $n > 3),$ причём никакие три из них не стоят на одной прямой. Каждый фонарь сияет одним из трёх цветов: синим (символизирует воду), красным (огонь) или жёлтым (солнце). Каждый цвет встречается хотя бы один раз. Докажите, что можно выбрать три фонаря разного цвета, которые образуют треугольник, внутри которого не стоит ни один другой фонарь.

“Истинный свет не ослепляет. Он указывает форму в пустоте.”

— Мастер Угвей

Показать доказательство

Рассмотрим треугольник с вершинами в трёх фонарях разного цвета и наименьшей площадью. Пусть это будут фонари $A,$ $B$ и $C.$ Предположим, что внутри $△ABC$ находится ещё один фонарь, скажем, $D.$ Поскольку каждый цвет используется хотя бы один раз, и всего цветов три, то фонарь $D$ совпадает по цвету с одним из трёх — пусть, например, с фонарём $A.$ Тогда $△DBC$ тоже будет состоять из трёх фонарей разного цвета, но его площадь строго меньше площади $△ABC.$ Это противоречит нашему выбору минимального по площади треугольника с разноцветными вершинами.

Значит, внутри найденного треугольника никаких других фонарей нет, что и требовалось доказать.

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#126406Максимум баллов за задание: 7

В Долине Мира начался Великий Турнир Боевых Школ. В турнире участвуют $5$ команд, каждая — из знаменитого монастыря, хранящего древние стили кунг-фу. По традиции, каждая команда должна сразиться с каждой другой ровно один раз — чтобы выявить лучший из стилей. Однако мастера мудры: они знают, что даже сила нуждается в передышке. Поэтому установлены два строгих правила:

$1)$ каждая команда может участвовать не более чем в одном поединке в день;

$2)$ в любые три дня подряд каждая команда может участвовать не более чем в двух поединках.

Какое наименьшее количество дней потребуется, чтобы провести все поединки турнира, соблюдая эти древние законы?

“Сила без равновесия разрушает. Равновесие без силы — бесполезно. Только вместе они ведут к победе.”

— Мастер Шифу

Показать ответ и решение

Допустим, турнир начинается, и в первый день проводятся поединки между несколькими командами. Однако по древнему закону — “не более одного боя в день для каждой школы” — в первый день какая-то команда не будет участвовать ни в одном бою. За следующие три дня эта команда сможет провести не более двух боёв (по правилу “не более двух поединков в любые три дня”). Но ведь всего у каждой школы должно быть четыре боя — ведь каждый сражается с каждым ровно один раз. Значит, чтобы сыграть оставшиеся поединки, этой школе потребуется минимум ещё два дня. В сумме получаем: как минимум $1$ день отдыха $+ 3$ дня с ограничением $+ 2$ дополнительных дня $= 6$ дней.

Приведём пример расписания турнира, в котором всё происходит за $6$ дней:

День $1:$ $A$ — $B,$ $C$ — $D;$

День $2:$ $B$ — $C,$ $D$ — $E;$

День $3:$ $A$ — $E;$

День $4:$ $B$ — $D;$

День $5:$ $A$ — $C,$ $B$ — $E;$

День $6:$ $A$ — $D,$ $C$ — $E.$

Ни одна команда не участвует более одного раза в день, и в любых трёх подряд днях у каждой не более двух боёв. Великие правила соблюдены — и победитель найден достойным образом.

Ответ: 6

Ошибка.
Попробуйте повторить позже

Задача 8#126432Максимум баллов за задание: 7

Во времена расцвета Долины Мира проводился Великий Совет Целителей. От каждого храма исцеления на Совет было приглашено по пять мудрейших лекарей. Однако каждый из них обучался в двух храмах, поэтому представлял на Совете оба. Мастера следовали древнему правилу: для любых двух храмов обязательно найдётся хотя бы один лекарь, который обучался в обоих — чтобы сохранить связь знаний между всеми школами. Сколько могло быть храмов в Долине Мира и сколько лекарей тогда участвовали в Совете?

“Один камень — просто камень. Но множество камней, уложенных с умом, — это мост.”

— Мастер Рино

Показать ответ и решение

Обозначим количество храмов через $a,$ а число лекарей — через $b.$ Построим двудольный граф: одна доля — храмы, другая — лекари. Соединим лекаря с храмом, если он в нём обучался.

По условию:

$1)$ От каждого храма было по $5$ лекарей: всего $5a$ связей.

$2)$ Каждый лекарь представляет два храма: всего $2b$ связей.

Значит, $5a= 2b.$

Кроме того, для каждой пары храмов должен существовать хотя бы один лекарь, обучавшийся в обоих. А таких пар $a(a-− 1). 2$ Можем оценить количество лекарей снизу:

a(a-− 1) b≥ 2

Подставим $5a b= 2$ в неравенство:

5a a(a− 1) 2-≥ ---2--| ⋅2

5a≥ a(a − 1)| ÷ a⁄= 0

5≥ a− 1| + 1

a≤ 6

Кроме того, из равенства $5a= 2b$ следует, что $a$ — чётное. Остаются $a= 2,$ $4,$ $6.$

Возможные случаи:

$1)$ $a =2 =⇒ b= 5;$

Пример:


№ лекаря	Храмы

$1$	$A,$ $B$

$2$	$A,$ $B$

$3$	$A,$ $B$

$4$	$A,$ $B$

$5$	$A,$ $B$

$2)$ $a =4 =⇒ b= 10;$

Пример:


№ лекаря	Храмы

$1$	$A,$ $B$

$2$	$A,$ $C$

$3$	$A,$ $D$

$4$	$B,$ $C$

$5$	$B,$ $D$

$6$	$C,$ $D$

$7$	$A,$ $B$

$8$	$C,$ $D$

$9$	$A,$ $C$

$10$	$B,$ $D$

$3)$ $a =6 =⇒ b= 15.$

Пример:


№ лекаря	Храмы

$1$	$A,$ $B$

$2$	$A,$ $C$

$3$	$A,$ $D$

$4$	$A,$ $E$

$5$	$A,$ $F$

$6$	$B,$ $C$

$7$	$B,$ $D$

$8$	$B,$ $E$

$9$	$B,$ $F$

$10$	$C,$ $D$

$11$	$C,$ $E$

$12$	$C,$ $F$

$13$	$D,$ $E$

$14$	$D,$ $F$

$15$	$E,$ $F$

Ответ: 2 храма и 5 лекарей, 4 храма и 10 лекарей или 6 храмов и 15 лекарей