Maths Olympiad Prep

Library / /26 of 57

Combinatorics Difficulty 6.7 National olympiad Prove it Russia

Given a 2015×20152015 \times 2015 checkered board. Dmitry chooses kk cells and places a detector in each of them. After that Dmitry goes out, and then Nick places on a board a cellular square 1500×15001500 \times 1500 (the square lies within the board, and its sides lie on the grid lines).

Each detector informs Dmitry whether its cell is covered by the square or not. Find the least possible kk such that Dmitry can place detectors in order to determine the location of Nick's square for sure.
(O. Dmitriev, R. Zhenodarov)

Есть клетчатая доска 2015×20152015 \times 2015. Дима ставит в kk клеток по детектору. Затем Коля располагает на доске клетчатый корабль в форме квадрата 1500×15001500 \times 1500. Детектор в клетке сообщает Диме, накрыта эта клетка кораблём или нет. При каком наименьшем kk Дима может расположить детекторы так, чтобы гарантированно восстановить расположение корабля? (О. Дмитриев, Р. Женодаров)

Solutions — 2

Solution 1

k=2(20151500)=1030k = 2(2015 - 1500) = 1030.
To win with 10301030 detectors, it suffices to locate them in the 515515 leftmost cells of the middle row and in the 515515 topmost cells of the middle column.

For the estimate, notice that the union of any two vertical 1500×11500 \times 1 rectangles differing by a horizontal 15001500-shift should contain at least one detector; a similar claim holds for horizontal rectangles. Consider such pairs of vertical rectangles located in the bottom 15001500 rows, as well as those located in the top 15001500 rows. Consider also similar pairs of horizontal rectangles. Each of these 210302 \cdot 1030 pairs contains a detector, and each detector is covered by at most two such pairs.

Figure 1

Note. There exist many other examples of arrangements of 10301030 detectors that satisfy the requirements.

Solution 2

k=2(20151500)=1030k = 2(2015 - 1500) = 1030.
Покажем, что 10301030 детекторов Диме хватит. Пусть он расположит 515515 детекторов в 515515 левых клетках средней строки квадрата, а остальные 515515 детекторов — в 515515 верхних клетках среднего столбца. Заметим, что при любом положении корабля его левый столбец лежит в одном из 516516 левых столбцов доски.

Если этот столбец — один из 515515 самых левых, то корабль накроет детектор из этого столбца, лежащий в средней строке, иначе ни одного детектора из этой строки корабль не накроет. Значит, по показаниям детекторов из этой строки восстанавливается, в каких столбцах лежит корабль. Аналогично, строки, в которых он находится, восстанавливаются по показаниям детекторов из среднего столбца.

Рассмотрим теперь произвольную расстановку kk детекторов, удовлетворяющих требованиям. Рассмотрим два положения корабля, отличающихся горизонтальным сдвигом на 11. Показания какого-то детектора для них будут различаться, только если этот детектор лежит в самом левом столбце левого корабля или в самом правом столбце правого. Значит, в любых двух вертикальных прямоугольниках 1500×11500 \times 1, отличающихся горизонтальным сдвигом на 15001500, есть хотя бы один детектор. Аналогично, в любых двух горизонтальных прямоугольниках 1×15001 \times 1500, отличающихся вертикальным сдвигом на 15001500, есть хотя бы один детектор. Назовём такие пары прямоугольников вертикальными и горизонтальными, соответственно.

Выделим все вертикальные пары, лежащие в нижних 15001500 и в верхних 15001500 строках доски (таких пар 2515=10302 \cdot 515 = 1030). Аналогично, выделим все 10301030 горизонтальных пар, лежащих в левых 15001500 и в правых 15001500 столбцах. Разобьём доску на 99 прямоугольных областей так, как показано на рис. 10. Выделенные пары не покрывают клеток из EE; каждая же клетка в остальных областях покрыта двумя выделенными парами (в DD и FF — двумя вертикальными, в BB и HH — двумя горизонтальными, а в областях A,C,GA, C, G и II — одной горизонтальной и одной вертикальной). Итак, каждый детектор лежит не более, чем в двух выделенных парах; значит, чтобы в каждой выделенной паре был хотя бы один детектор, требуется не менее 21030/2=10302 \cdot 1030/2 = 1030 детекторов.

Figure 1
Рис. 10

Замечание. Существует много других примеров расположения 10301030 детекторов, удовлетворяющих требованиям.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.