ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65707
Темы:    [ Таблицы и турниры (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4
Классы: 10,11
В корзину
Прислать комментарий

Условие

Есть клетчатая доска 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 детекторов, удовлетворяющих требованиям.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2015/2016
этап
Вариант 4
класс
Класс 11
задача
Номер 11.4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .