|
|
 |
Условие
Есть клетчатая доска 2015×2015. Дима ставит в k клеток по детектору. Затем Коля располагает на доске клетчатый корабль в форме квадрата 1500×1500. Детектор в клетке сообщает Диме, накрыта эта клетка кораблём или нет. При каком наименьшем k Дима может расположить детекторы так, чтобы гарантированно восстановить расположение корабля?
Решение
Покажем, что 1030 детекторов Диме хватит. Пусть он расположит 515 детекторов в 515 левых клетках средней строки квадрата, а остальные 515 детекторов – в 515 верхних клетках среднего столбца. Заметим, что при любом положении корабля его левый столбец лежит в одном из 516 левых столбцов доски. Если этот столбец – один из 515 самых левых, то корабль накроет детектор из этого столбца, лежащий в средней строке, иначе ни одного детектора из этой строки корабль не накроет. Значит, по показаниям детекторов из этой строки восстанавливается, в каких столбцах лежит корабль. Аналогично строки, в которых он находится, восстанавливаются по показаниям детекторов из среднего столбца.
Рассмотрим теперь произвольную расстановку k детекторов, удовлетворяющих требованиям. Рассмотрим два положения корабля, отличающихся горизонтальным сдвигом на 1. Показания какого-то детектора для них будут различаться, только если этот детектор лежит в самом левом столбце левого корабля или в самом правом столбце правого. Значит, в каждых двух вертикальных прямоугольниках 1500×1, отличающихся горизонтальным сдвигом на 1500, есть
хотя бы один детектор. Аналогично в каждых двух горизонтальных прямоугольниках 1×1500, отличающихся вертикальным сдвигом на 1500, есть хотя
бы один детектор. Назовём такие пары прямоугольников вертикальными и горизонтальными, соответственно.
Выделим все вертикальные пары, лежащие в нижних 1500 и в верхних 1500 строках доски (таких пар 2·515 = 1030). Аналогично выделим все 1030 горизонтальных пар, лежащих в левых 1500 и в правых 1500 столбцах. Разобьём доску на 9 прямоугольных областей так, как показано на рисунке. Выделенные пары не покрывают клеток из E; каждая же клетка в остальных областях покрыта двумя выделенными парами (в D и F – двумя
вертикальными, в B и H – двумя горизонтальными, а в областях A, C, G и I – одной горизонтальной и одной вертикальной). Итак, каждый детектор лежит не более, чем в двух выделенных парах; значит, чтобы в каждой выделенной паре был хотя бы один детектор, требуется не менее
2·1030 : 2 = 1030 детекторов.
Ответ
При k = 1030.
Замечания
Существует много других примеров расположения 1030 детекторов, удовлетворяющих требованиям.
