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

   Решение

Темы:    [ Комбинаторика (прочее) ] [ Соображения непрерывности ]

Сложность: 3+ Классы: 7,8,9

Прислать комментарий

Условие

В ряд стоят 30 сапог: 15 левых и 15 правых. Докажите, что среди некоторых десяти подряд стоящих сапог левых и правых поровну.

Решение

Обозначим через L_i число левых сапог из десяти, занимающих с i-го по (i+9)-е места. Тогда  L₁ + L₁₁ + L₂₁ = 15.  Если одно из чисел L₁, L₁₁, L₂₁ равно 5, то мы нашли искомую десятку. Иначе одно из них больше 5, а какое-то – меньше 5. Но L_{i + 1} может отличаться от L_i не более чем на 1. Значит,  L_k = 5  при некотором k. Это и даст искомую десятку.

Замечания

3 балла

Источники и прецеденты использования