Задача
№ 14275
Оценка + пример (экстремальные комбинаторные задачи)
Ур. 7
Всероссийская олимпиада школьников по математике, 11 класс, региональный этап, 2016, задача 4
Есть клетчатая доска $2015\times2015$. Дима ставит в $k$ клеток по детектору. Затем Коля располагает на доске клетчатый корабль в форме квадрата $1500\times1500$. Детектор в клетке сообщает Диме, накрыта эта клетка кораблём или нет. При каком наименьшем $k$ Дима может расположить детекторы так, чтобы гарантированно восстановить расположение корабля?
Ответ:
Решение: