ВсОШ 2025, 9 класс, задача 1

Сложная
Комбинаторика
Источник:
Всероссийская олимпиада школьников, Заключительный этап, 2025, 9 класс, Первый тур

На прямоугольном листе бумаги провели несколько отрезков, параллельных его сторонам. Эти отрезки разбили лист на несколько прямоугольников, внутри которых нет проведённых линий. Петя хочет провести в каждом из прямоугольников разбиения одну диагональ, разбив его на два треугольника, и окрасить каждый треугольник либо в чёрный, либо в белый цвет. Верно ли, что он обязательно сможет это сделать так, чтобы никакие два одноцветных треугольника не имели общего отрезка границы?

Верно или неверно?

Войдите, чтобы проверять ответы

Ответ. Да, верно.

Решение. Пусть Петя проведёт в каждом из прямоугольников диагональ из левого нижнего угла в правый верхний. После этого все треугольники, примыкающие к левым верхним углам прямоугольников, он покрасит в чёрный цвет, а остальные — в белый. Докажем, что такая раскраска подойдёт. Рассмотрим общий отрезок границы двух треугольников. Если этот отрезок диагональный, то сверху к нему примыкает чёрный треугольник, а снизу белый. Если отрезок горизонтальный, то к нему сверху примыкает белый треугольник, а снизу — чёрный; случай вертикального отрезка аналогичен. Поэтому такая раскраска подходит.

Похожие задачи

ВсОШ 2025, 9 класс, задача 6

Петя выбрал 100 попарно различных положительных чисел, меньших 1, и расставил их по кругу. Затем он проделывает с ними операции. За одну операцию можно взять три стоящих подряд (именно в таком порядке) числа a, b, c и заменить число b на a-b+c. При каком наибольшем k Петя мог выбрать исходные числа
Сложная
Комбинаторика

ВсОШ 2026, 9 класс, задача 1

Сначала на тарелке лежат 75 конфет. Петя и Вася по очереди берут из тарелки любое натуральное количество конфет до тех пор, пока конфет на тарелке не останется. Начинает Петя. При каком наименьшем k Петя может играть так, чтобы гарантировать, что в конце игры количества конфет у мальчиков отличаются
Сложная
Комбинаторика

ВсОШ 2023, 9 класс, задача 3

(20 баллов) Каждое натуральное число, большее 1000, окрасили либо в красный, либо в синий цвет. Оказалось, что произведение любых двух различных красных чисел - синее. Может ли случиться, что никакие два синих числа не отличаются на 1? (С. Берлов)
Сложная
Теория чисел
Комбинаторика

ВсОШ 2021, 9 класс, задача 1

На окружности отмечено 1000 точек, каждая окрашена в один из k цветов. Оказалось, что среди любых пяти попарно пересекающихся отрезков, концами которых являются 10 различных отмеченных точек, найдутся хотя бы три отрезка, у каждого из которых концы имеют разные цвета. При каком наименьшем k это возм
Сложная
Комбинаторика