Физтех 2024, отборочный этап, 11 класс, второй тур, задача 8

В каждую клетку доски клеток поставили либо чёрную, либо белую шашку. Оказалось, что в любом «уголке» из клеток стоит хотя бы одна чёрная шашка. Какое наименьшее количество чёрных шашек может стоять на доске?

Ответ

Ответ. .

Решение. В любом клетчатом квадрате должно стоять не менее чёрных шашек (иначе найдётся «уголок» без чёрных шашек). Выделим правый (-й) столбец, а оставшуюся доску разобьём на квадратов . В каждом квадрате стоит не менее чёрных шашек. Значит, всего есть не менее чёрных шашек.

Поставим чёрные шашки во , , , -й столбцы (их ровно ), а белые шашки — в остальные клетки. Тогда в любом «уголке» из клеток окажется чёрная шашка.

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

Физтех 2023, отборочный этап, 9 класс, второй тур, задача 5

За круглый стол сели 165 магистров двух орденов: ордена Лжецов (они всегда лгут) и ордена Рыцарей (они всегда говорят правду). Хотя бы по одному магистру из каждого ордена есть. Какое наибольшее число из сидящих за столом могло сказать: «Через 5 человек от меня есть магистр из ордена Рыцарей»?

Сложная

Комбинаторика

Физтех 2024, отборочный этап, 10 класс, второй тур, задача 9

В каждую клетку доски 24 × 30 клеток поставили либо чёрную, либо белую шашку. Оказалось, что в любом «уголке» из 3 клеток стоит хотя бы одна чёрная шашка. Какое наибольшее количество белых шашек может стоять на доске?

Сложная

Комбинаторика

Физтех 2023, отборочный этап, 9 класс, четвёртый тур, задача 5

У Олега есть конфеты 16 сортов. Он хочет выложить конфеты в ряд так, чтобы для любых двух различных сортов нашлись рядом лежащие конфеты этих сортов. Какого наименьшего количества конфет ему для этого хватит?

Сложная

Комбинаторика

Физтех 2023, отборочный этап, 11 класс, четвёртый тур, задача 4

У Олега есть конфеты 32 сортов. Он хочет выложить конфеты в ряд так, чтобы для любых двух сортов нашлись рядом лежащие конфеты этих сортов. Какого наименьшего количества конфет ему для этого хватит?

Сложная

Комбинаторика