Олимпиада Туймаада по математике. Старшая лига. 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$ это верно

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