Олимпиада Туймаада по математике. Старшая лига. 2019 год

План картинной галереи — клетчатая фигура, где каждая клетка — это зал, и из любой клетки можно дойти до любой другой, переходя в соседние по сторонам клетки. Смотритель, находясь в одном из залов, следит за всеми залами, в которые можно попасть из этой клетки одним ходом ферзя (не выходя за пределы галереи). Какое наименьшее число смотрителей потребуется, чтобы в любой галерее из $n$ залов ($n > 2$) все залы оказались под присмотром? ( H. Alpert, E. Roldan )

Комментарий/решение

Ответ целая часть от n/3

Почему нельзя меньше

Контр пример

■////■

□////□

□ □ □

///□

///■

(Не обращайте внимания на /)

И т.д

Тогда чтобы бить покрашенную клетку ферзь должен стоять на той же вертикальной прямой что и эта клетка, тогда очевидно что для каждых 3 клеток должен быть хотябы 1 ферзь

Лемма

Для того чтобы покрыть любые 1-5 клеток при правильном расположении достаточно будет лишь 1 ферзя

Доказательство

Пусть $k$ это такое число которое делится на 3

Тогда рассмотрим случаи когда клеток у нас $k$ ,$k+1$ и $k+2$

1 случай

Пусть клеток у нас $k$

И у нас есть какое то расположение этих $k$ клеток тогда начнём воссоздать это расположение ставя по 3 клетки за 1 так называемый ход

Очевидно что для покрытия этих 3 клеток достаточно будет лишь 1 ферзя т.к они могут быть либо уголком из 3 клеток либо прямой из 3 клеток и обе эти фигуры можно покрыть 1 ферзем

Тогда за k/3 ходов которые мы сделаем нам достаточно лишь будет k/3 ферзей что не противоречит ответу

2 случай

Пусть клеток у нас $k+1$

Тогда для какого расположение из $k$ клеток

Просто добавим в какую то тройку 1 клетку ( тройка это та фигура на которые я поделил расположение в прошлом случае)

Заметим что если получившийся фигуру мы сможем вписать в квадрат 3×3 то 1 ферзь сможет покрыть все эти 4 клетки и условие будет выполнено

И у нас есть лишь 1 случай когда мы не можем вписать и это тот случай где у нас будет прямая из 4 клеток

Очевидно что её можно будет покрыть.

Тогда для k+1 тоже верно

3 случай

Пусть залов у нас $k+2$

Тогда также как в предыдущем случае рассмотрим расположения

И поделим их на 2 отдельных случая

1 подслучай

Если мы расположим эти 2 клетки в разные тройки

Очевидно что противоречий не будет т.к мы рассмотрели это в случай номер 2

2 подслучай

мы расположили эти 2 клетки в 1 тройку тогда чтоб эту тройку нельзя было вписать в квадрат 3 на 3

В ней должна быть прямая из 4 клеток и ещё 1 клетка расположенная где-то

Эти случаи очевидны

Тогда для всех

$k$ , $k+1$ и $k+2$ это верно

А значит задача решена

Задача: Необходимо найти наименьшее количество смотрителей, чтобы все клетки галереи размером $n \times n$ (при $n > 2$) были под присмотром, если смотритель следит за всеми клетками, которые можно достичь ходом ферзя из своей клетки.

Решение:

Ферзь на клетчатой доске может двигаться в любом из восьми направлений: по вертикали, горизонтали и диагоналям. Таким образом, он охватывает все клетки, находящиеся на его пути.

Для минимального количества смотрителей, которые смогут покрыть все клетки галереи, нужно правильно разместить смотрителей так, чтобы их зоны охвата пересекались.

Минимальное количество смотрителей для покрытия всей доски размером $n \times n$ (где $n > 2$) будет равно:

$$\left\lceil \frac{n}{2}\right\rceil$$.

где $\lceil x \rceil$ — это операция округления числа $x$ до ближайшего целого числа, не меньшего $x$.

Таким образом, для доски размером $n \times n$ минимальное количество смотрителей равно $$\left\lceil \frac{n}{2} \right\rceil$$.

\end{document}