Задача 67508
|
|
 |
Условие
В квадрате $2025 \times 2025$ отмечено несколько клеток. За один ход Кирилл может узнать количество отмеченных клеток в любом клетчатом квадрате со стороной меньше $2025$ внутри исходного квадрата. Какого наименьшего количества ходов точно хватит, чтобы узнать количество отмеченных клеток во всём квадрате?Решение
Обозначим исходный квадрат через $K$.Оценка. Пусть ходов только 4. Ясно, что каждый из соответствующих четырёх квадратов должен содержать свою угловую клетку у $K$.
Если квадраты не покрывают $K$, то Кирилл ничего не узнает о количестве отмеченных клеток среди непокрытых. Если же квадраты покрывают $K$, то какие-то из них пересекаются (иначе рассмотрим квадрат, содержащий центральную клетку, его сторона не меньше 1013; но тогда стороны остальных квадратов не больше 1012, и взяв из них два квадрата, примыкающих к одной стороне K, видим, что эта сторона покрыта не полностью).
Пусть на каждом ходу отвечали, что отмечена одна клетка. Тогда отмеченных клеток в $K$ могло быть как 4 (все его угловые клетки), так и меньше — когда была отмечена клетка из пересечения двух или более квадратов вместо углов $K$, попавших в эти квадраты.
Пример. Возьмём: 1) два квадрата со стороной 1013, покрывающие два противоположных угла; 2) центральную клетку; 3) два квадрата со стороной 1012, покрывающие два других противоположных угла. Первые два квадрата пересекаются как раз по центральной клетке, так что по первым трём числам мы узнаем, сколько отмеченных клеток покрывают первые три квадрата. Остальное покрывают (без пересечений) оставшиеся два квадрата.
