Задача 109694

Темы:    [ Геометрия на клетчатой бумаге ] [ Процессы и операции ] [ Принцип Дирихле (конечное число точек, прямых и т. д.) ]

Сложность: 6 Классы: 9,10,11

Условие

Автор: Токарев С.И.

В квадрате n×n клеток бесконечной шахматной доски расположены n² фишек, по одной фишке в каждой клетке. Ходом называется перепрыгивание любой фишкой через соседнюю по стороне фишку, непосредственно за которой следует свободная клетка. При этом фишка, через которую перепрыгнули, с доски снимается. Докажите, что позиция, в которой дальнейшие ходы невозможны, возникнет не ранее, чем через [] ходов.

Решение

Будем различать два типа ходов – внутренние и внешние, в зависимости от того, куда ставится фишка, делающая ход: внутрь исходного квадрата n×n клеток, или вне его.

Пусть получена позиция, где дальнейшие ходы невозможны, причем сделано k внутренних ходов и l внешних.

Ясно, что никакие две фишки не находятся в соседних клетках; поэтому в исходном квадрате n×n не менее чем [] клеток пусты. Действительно, нетрудно понять, что квадрат разрезается на доминошки (в случае четной стороны) или доминошки и одну угловую клетку (в случае нечетной), а в каждой доминошке есть хотя бы одна пустая клетка. Так как каждый внутренний ход увеличивал количество пустых клеток не более, чем на 1, а каждый внешний – не более, чем на 2, то имеем неравенство

k+2l[]. (1)
Предположив теперь, что n четно, разобьем исходный квадрат на четырехклеточных квадратиков и заметим, что на каждый квадратик пришлось не менее двух ходов, в которых участвовали (делали ход или снимались с доски) фишки, стоявшие в клетках этого квадратика. Поскольку в каждом внутреннем ходе участвовали фишки не более, чем двух квадратиков, а в каждом внешнем – не более, чем одного, то
2k+l2. (2)
Из неравенств (1) и (2) получаем k+l[] , т.е. утверждение задачи в этом случае верно.

Легко видеть, что оно верно также при n=1 и при n=3 .

В случае n=2m+1 , где m>1 , в кресте, образованном третьей сверху горизонталью и третьей слева вертикалью, выделим 2m доминошек, а остальную часть исходного квадрата разобьем на m² четырехклеточных квадратиков. В каждом внутреннем ходе участвовать могли фишки, принадлежащие не более чем двум из m²+2m рассматриваемых фигур, а в каждом внешнем – не более чем одной. Имеем неравенство
2k+l2m²+2m, (3)
поскольку фишки каждого из квадратиков участвовали не менее, чем в двух ходах, а фишки каждой доминошки – по крайней мере в одном.

Из (1) и (3) следует, что 3(k+l)4m²+4m=n²-1 . Если здесь n² кратно 3, то, очевидно, 3(k+l) n² и k+l=[] , в противном случае n² сравнимо с 1 по модулю 3 и k+l=[] . Тем самым утверждение задачи полностью доказано.

Можно доказать, что для любого ε>0 при достаточно больших n количество ходов будет больше, чем n²(-ε) . Один из методов доказательства заключается в следующем.

Предположим противное.
Рассмотрим каемку нашего квадрата ширины 2, каемку квадрата, получающегося выкидыванием первой, и т.д., всего k=[nε/8] каемок. Заметим, что внутри последней каемки содержится хотя бы n²(1-ε/2)²>n²(1-ε/4) клеток. Тогда за максимум n²(-ε) ходов из нашего квадрата ушло хотя бы [] n²(1-ε) фишек; значит, было хотя бы ε n² ходов, на которых количество фишек в нем уменьшалось на 2; эти ходы вели из первой каемки вовне, и не затрагивали квадрата внутри первой каемки.
Тогда за не более чем n²(-ε) ходов из следующего по величине квадрата ушло хотя бы n²(1-ε) фишек; значит, было хотя бы ε n² ходов, на которых количество фишек в нем уменьшалось на 2; эти ходы вели из второй каемки вовне. Аналогично, из третьей каемки вовне вело хотя бы 2ε n² ходов, из k -й каемки – 2^k-2ε n² ходов. Однако при больших n 2^k-2ε n²=2[nε/8]-2ε n²>n² , т.е. ходов гораздо больше, чем предполагалось. Противоречие.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1999
Этап
Вариант	5
Класс
Класс	10
задача
Номер	99.5.10.4
олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1999
Этап
Вариант	5
Класс
Класс	11
задача
Номер	99.5.11.4