Задача М750‍‍‍

В решении мы многократно используем «принцип Дирихле»‍.

а) Этот пункт — частный случай следующего.

б) Рассмотрим горизонтальную полосу бумаги ширины $lN$‍‍ (рис. 1). Она состоит из бесконечного числа столбцов высоты $lN$‍.‍ Среди них найдутся $m$‍‍ одинаково окрашенных столбцов (общее число разных раскрасок конечно). Проведём через эти столбцы $m$‍‍ вертикальных прямых.

Так как каждый из выбранных столбцов окрашен в $N$‍‍ цветов, найдётся цвет, который встретится в одном (и, стало быть, в любом) из них не меньше $l$‍‍ раз (иначе высота столбца меньше $lN$‍).‍ Через клетки этого цвета проведём $l$‍‍ горизонтальных прямых.

в) Пусть клетки окрашены в красный и синий цвета. Рассмотрим цепочку попарно не пересекающихся квадратов $3\times3$‍,‍ расположенных по «диагонали» (рис. 2). Среди них найдутся два одинаково раскрашенных квадрата (число способов раскраски квадрата $3\times3$‍‍ в 2 цвета конечно). На диагонали каждого из квадратов есть по 2 клетки одного цвета (на рисунке 2 это красные клетки). Рассмотрим клетки, получающиеся в пересечении вертикальных и горизонтальных полосок, проходящих через эти красные клетки. Если хотя бы одна из них красная — задача решена. Если нет, то все они синего цвета, и из них легко выбрать такие три, что их центры образуют равнобедренный прямоугольный треугольник.

г) Будем рассуждать аналогично с решением пункта в). Рассмотрим бесконечную цепочку достаточно больших квадратов, расположенных по диагонали (что значит «достаточно большой» — выяснится ниже). Среди них всегда найдутся два одинаково раскрашенных. Пусть сторона большого квадрата настолько велика, что вдоль его диагонали можно поместить больше квадратов $4\times4$‍,‍ чем число способов раскраски квадрата $4\times4$‍‍ в 3 цвета. Тогда на диагонали каждого из двух выбранных нами одинаковых больших квадратов будет по крайней мере по 2 одинаково раскрашенных квадрата $4\times4$‍‍ (рис. 3). На диагонали каждого из них найдутся как минимум по 2 одинаково окрашенных (и одинаково расположенных) клетки — на рисунке 3 их центры помечены красными точками; одинаковый цвет имеют и 4 соответственные клетки этих квадратов с синими центрами, а также 2 соответственные клетки больших квадратов с жёлтыми центрами. Если цвета каких-то двух из указанных трёх групп клеток совпадают, то, очевидно, один из треугольников, выделенных на рисунке 3, будет искомым. В противном случае можно считать, что цвета всех этих клеток совпадают с цветами их центров. Тогда в какой бы из трёх цветов — жёлтый, синий или красный — ни была окрашена клетка с чёрным центром (см. рис. 3), один из трёх равнобедренных прямоугольных треугольников с общей вершиной в этом центре и двумя другими вершинами или в жёлтых точках, или в крайних синих, или в крайних красных будет «одноцветным».

Эта задача тесно связана с так называемой «теоремой Ван-дер-Вардена о прогрессиях», о которой мы расскажем‍ в одном из ближайших номеров.