Республиканская олимпиада по математике, 2024 год, 9 класс

Дано целое число $n>1$. Доску $n\times n$ раскрасили шахматным образом в белый и черный цвет. Фигурой назовем любой непустой набор различных клеток доски. Фигуры $F_1$ и $F_2$ назовем подобными, если $F_1$ можно получить из $F_2$ с помощью поворота относительно центра доски на угол кратный $90^\circ$ и параллельного переноса. (Любая фигура подобна самой себе.) Фигуру $F$ назовем связной, если для любых клеток $a,b\in F$ найдется последовательность клеток $c_1,\ldots,c_m\in F$ такая, что $c_1 = a$, $c_m = b$, а также $c_i$ и $c_{i+1}$ имеют общую сторону для каждого $1\le i\le m - 1$. Найдите наибольшее возможное значение $k$ такое, что для любой связной фигуры $F$, состоящей из $k$ клеток, найдутся фигуры $F_1,F_2$ подобные $F$, что в $F_1$ белых клеток больше, чем черных, а в $F_2$ белых клеток меньше, чем черных. ( Зауытхан А. )

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

Понятно что для четных $n$ ответ $n^2-1$.

Пусть $n$ нечетное. Тогда если $k$ хотя бы $2n-1$ тогда покроем первую строку и первый столбец. И остальные клетки просто положим так чтобы они образовали связную фигуру. Понятно что при таком складывании нельзя делать параллельные переносы. (Уточнение в условии). И понятно что при нечетном $n$ поворачивать фигуру бессмысленно. Тогда такая фигура не подходит условию. Значит $k$ меньше $2n-1$. Если $k=2n-2$ то расставим $2n-2$ клеток по первой строке и по первому столбцу без крайней клетки. Тогда у нас одинаковое количество черных и белых клеток. И при переносе каждая клетка меняет свой цвет на противоположный. Таким образом их всегда одинаковое количество. Значит $2n-2$ не подходит. Докажем что $2n-3$ подходит. Легко понять что какой-то столбец и какая-та строка будет свободной. Значит можно использовать параллельный перенос. Так как $2n-3$ нечетное то у нас количество черных и белых клеток не равно. Тогда при переносе количество белых и черных и поменяется, значит цвета что было больше станет меньше, что подходит условию.