3-ші халықаралық Жәутіков олимпиадасы, 2007 жыл

Бізге 111 түйме берілген. Осы түймелерді өлшемі $n\times n$ болатын тақтаның шаршыларына ортақ қабырғалы көрші шаршылардағы түймелер санының айырмасы дәл 1-ге тең болатындай етіп салу керек (шаршыда бірнеше түйме болуы немесе ол бос болуы әбден мүмкін). Қандай максимал $n$ үшін осы шараны іске асыруға болады?

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

Ответ:n=13.

докажем что n\le15. Если n=15,то докажем что количество монет на доске будет больше или равно 112.Если разделить эту доску на прямугольники 1 * 2, то получим 112 прямоугольников и одну лишнию клетку. Количество монет в каждом прямоугольнике больше или равно 1, и в лишней клетке больше или равно 0 значит на доске количество монет больше или равно 112.если n больше 15, то следовательно количество монет на доске будет увеличиваться. При n=14 невозможна, так как при таких же действиях получим 98 прямоугольников где в каждом прямоугольнике нечётное количество монет.

Приводим пример для n=13 где 0,1,2- кол-во монет

1010101010101

0101010101010

1010101010101

0101010101010

1010101010101

0101010101010

1010101010101

0101010101010

1010101010101

0101010101010

1010101010101

2121212121212

1212121212121

Ответ: $n=14$

Давайте раскрасим наше поле 14x14 в шахматную раскраску. Тогда будет $\frac{14^2}{2}= 98$ белых и 98 черных клеток. В каждую черную клетку мы положим монетку. Тогда в любых двух соседних клетках будет разное количество монет, и будет использовано менее 111 монет.

Теперь мы докажем, что $n\le 14$.

i) $n$ кратно двум. Тогда пусть $n =2k$ Разделим нашу доску на $1*2k$ прямоугольников. Каждый прямоугольник $1*2k$ разделим на $k$ прямоугольников $1*2$. Из условия известно, что в прямоугольнике $1*2$ есть по крайней мере 1 монета, поэтому в $1*2k$ есть по крайней мере $k$ монет $\rightarrow$ В прямоугольнике $2k*2k$ есть по крайней мере $2k^2$ монет, поэтому $2k^2 \le 111 \rightarrow 2k^2 \le 110 \rightarrow k^2 \le 55 \rightarrow k\le 7 \rightarrow n \le 14$

ii) $n$ не делится на 2. Тогда пусть $n=2k+1$. Аналогично разделим наш прямоугольник на k прямоугольников $2*(2k+1)$ и 1 строку. В каждом прямоугольнике $2*(2k+1)$ есть по крайней мере $2k+1$ монет, а в каждом $1*2k+1$ есть по крайней мере k монет, поэтому в $(2k+1)*(2k+1)$ есть по крайней мере $k*(2k+1) + k = 2k(k+1)$ монет, что означает $111 \ge 2(k+1)k \rightarrow 55 \ge k(k+1)\rightarrow 6 \ge k \rightarrow 13 \ge n$.

Из i) и ii) мы получаем, что $n \le 14$

Для любого квадрата $n \times n (n \geq 15)$, выделим квадрат $15 \times 15$. Заметим, что в любом прямоугольнике $1 \times 2$ или $2 \times 1$ количество монет не меньше 1. Тогда в квадрате $n \times n$ можем расположить не менее 112 таких прямоугольников. Откуда общее количество монет не менее 112. Противоречие. Теперь мы имеем оценку $n \leq 14$.

При $n=14$ имеем 98 прямоугольников, где сумма в каждом нечетная, откуда всего четное количество монет. Противоречие. Теперь мы имеем оценку $n \leq 13$.

Пример:

Сделаем шахматную раскраску, где на черных клетках будут стоять по 1 монете.

Теперь выберем любые 13 белых клеток, дальше поставим по 2 монеты на каждую клетку. Остальные оставим пустыми. Откуда $13*2+85=111$.