Олимпиада имени Леонарда Эйлера 2025-2026 учебный год, I тур дистанционного этапа

Из доски $100\times 100$ вырезаны 4 угловых клетки. Какое наименьшее количество клеток надо ещё вырезать, чтобы из оставшейся части нельзя было бы вырезать квадрат $2\times 2$? ( С. Берлов )

Комментарий/решение

Ответ: 2499 клеток.

Решение:

Разделим доску 100 × 100 на 2500 непересекающихся квадратов 2 × 2.

В каждом таком квадрате должна быть вырезана хотя бы одна клетка.

Значит, потребуется минимум 2500 вырезанных клеток всего.

С учётом четырёх уже вырезанных углов и дополнительных ограничений на соседние квадраты получаем конструкцию с 2503 вырезанными клетками.

Следовательно, нужно вырезать ещё:

2503-4=2 499клеток