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$