Раскраска плоскости и теорема Ван дер Вардена о прогрессиях

35

Раскраска плоскости и теорема
Ван дер Вардена о прогрессиях
С. Н. БЕСПАМЯТНЫХ

В этой заметке мы докажем следующие краисное обобщение результата задачи М750.

Теорема о раскраске. Пусть каждый клетка бесконечного листа клетчатой бумаги окрашена в один из N цветов. Тогда для любого набора клеток $a_1, \dots, a_l$ найдется набор одинаково окрашенных клеток $b_1, \dots, b_l$, подобный первому в том смысле, что (см. рис. 1) $B_i B_j = d A_i A_j$ при всех i, j=1, …, l, $e d e A_1, \dots, A_l, B_1, \dots, B_l$ — центры клеток $a_1, \dots, a_l, b_1, \dots, b_l$ соответственно, а d — некоторое натуральное число; иначе говоря, фигуры, образованные центрами клеток $b_1, \dots, b_l$ и $a_1, \dots, a_l$ соответствуют d.

Рис. 1.

Более того, такой набор клеток можно найти в любом квадрате $m \times m$, где m — достаточно большое число, зависящее от количества цветов N и заданного набора $a_1, \dots, a_l$.

(Обратите внимание: «подобие наборов клеток》означает у нас не совсем то, что обычное понятие «подобия фигур»!).

Интересна история этой теоремы. В 1928 году один математик, работший в крупном математическом центре — Геттингене, столкнул с таким вопросом: можно ли утверждать, что при любом разбиении множества натуральных чисел на две части (или на конечное число частей), хотя в одной из них найдется арфметическая прогрессия сколь годно большой заданной длины? Представлялось почти оченьным, что ответ здесь положительный. Однако доказать это, несмотря на кажущуюся простоту задачи, понacularly не удалось, и вскоре она сделалась предметом всеобщого увлечения. Первым добавляя модулой голландец Б. Л. Ван дер Варден, ставший впоследствии известным математиком. После нескольких недель работы он нашел не простое, но в полне элементарное доказательство, основанное на хитроумном применении математической индукции и «приицпа Дирихле» (см. например, «Квант», 1977, № 2, с. 17). В 40-х годах теорема Ван дер Вардена была перенесена на n-мерный случай; теорема о раскраске — это случай размерности n=2.

Вот одна из формулировок теоремы Ван дер Вардена, несколько обобщая исходную задачу.

Для любых чисел N и l можно указать такое число m=m (N, l), что при произвольном разбиении отрезка натурального ряда длины m на N классов по крайней мере в одном из них найдется арфметическая прогрессия длины l.

Покажем, как можно вывести эту теорему из теоремы о раскраске. Возьмем любые m последовательных натуральных чисел и занумерем им стольцы квадрата $m \times m$; разбиению этих чисел на N классов сопоставим

36

раскраску квадрата в $N$ цветов, при котором все клетки всех столбцов, чьи номера входят в один и тот же класс, получают один и тот же цвет (рис. 2). Пусть теперь $a_1, \dots, a_1$ — горизонтальный ряд из $l$ последовательных клеток. Тогда по теореме о раскраске при достаточно большом $m$ в нашем квадрате найдется набор однозвенных клеток $b_1, \dots, b_l$, подобный набор $a_1, \dots, a_l$, то есть горизонтальный ряд равностоящих друг от друга клеток. Очевидно, что номера столбцов, содержащих клетки $b_1, \dots, b_l$, образуют искому прогрессию (разность $d$ этой прогрессии равна «козффициенту подобия» наборов $a_1, \dots, a_l$ и $b_1, \dots, b_l$).

Переход к доказательству теоремы о раскраске, условиями рассматривать не произвольные наборы клеток $a_1, \dots, a_l$ а неторы «стандартные» — такие, как на рисунке 3. Ясно, что от этого общность не построает, потому что любой набор клеток можно дополить до «стандартного», причем если утверждение

Рис. 2.

Рис. 3.

теоремы будет доказано для дополнительного — «стандартного» — набора, то оно завершимо будет справедливо и для исходного. Наборы клеток, подобные «стандартным» наборам, называемыми, коэффициент подобия — коэффициент серии; серий квадратов будет называться набор конгрузных квадратов, состоящих из клеток нашего бесконечного листа, левые нижние клетки которых образуют серию (очевидно, любые соответственные клетки таких квадратов тоже образуют серию). Наконец, два конгрузных раскрашенных квадрата называемо однонаково, то есть их раскраски совпадают при паралельном переносе, совмещающем квадраты.

Таким образом, мы должны доказать, что, каковы бы ни были числа $N$ и $l$, при достаточно большом $m = m(N, l)$ в квадрате $m \times m$, произвольно раскрашением в $N$ цветов, всегда найдется одноцветная серия $b_1, \dots, b_l$ длины $l$.

Доказательство будет вести индукцией по $l$.

При $l=1$, очевидно, можно взять $m(N, 1)=1$, а при $l=2-m(N, 2)=N+1$ (приницп Дирихле!). Допустим теперь, что утверждение теоремы верно для серий длины $l$ при всех, сколько уголно больших $N$, и доказем его для серий длины $l+1$.

Поясним сначала идею доказательства. Пусть имеется серия из $l+1$ квадратов $K_1, K_2, \dots, K_{l+1}$ и в каждом из квадратов $K_i$ выбрана серия из $l+1$ клеток $b_{i,1}, b_{i,2}, \dots, b_{i,l+1}$, причем эти серии одинаково расположены в квадратах (см. рис. 4, где $l=4$). Тогда из клеток $b_{i,j}$ можно образовать еще $l+1$ серий вида $b_{1,j}, b_{2,j}, \dots, b_{l+1,j}$ ($j=1, \dots, l+1$) — на рисунке 4 такая серия для $j=l+1$ показана розовым цветом — и еще одну серию $b_{1,1}, b_{2,2}, \dots, b_{l+1,l+1}$ с несколько большим коэффициентом — эти клетки на рисунке обведены рамками. Если известно, что квадраты $K_{1,b}, \dots, K_{l,b}$ однотипны, а клетки $b_{1,1}, b_{1,2}, \dots, b_{1,l}$ (а вместе с ними все клетки $b_{i,j}$, где $i, j \leq l$) одноцветны, то в каждом из трех серий: $b_{1,1}, b_{1,2}, \dots, b_{1,l+1}$ (серия в квадрате $K_1$), $b_{1,1},$

37

Рис. 4.

$b_{2,2}, \dots, b_{l+1,l+1}$ (серия в рамках) и $b_{1,l+1}, b_{2,l+1}, \dots, b_{l+1,l+1}$ («розовая» серии) все клетки, кроме может быть, последней, однозветны, а крайними клетками служат какие-то две из клеток $b_{1,1}, b_{1,l+1}$ и $b_{l+1,l+1}$ (на рисунке они помещены *)). Поэтому, если среди этих трех клеток найдет две однозветные, мы получим однозветную серию длины $l+1$. Так будет наверняка, по принципиу Дирихле, в случае двух цветов. В случае же $N$ цветов надо рассмотреть не двух-, а $N$-ступенчатую конструкцию (в больших квадратах выбирать серию квадратов поменше, в тех — еще меньше квадраты, и так $N$ раз, пока не получается клетки). При этом размер исходного квадрата должен позволить на каждой «ступени» выделить очередную серию $l+1$ квадратов, среди которых переше л однозветны — тут и должно помочь предположение индекции.

Приведем теперь формульное доказательство теоремы о раскраске. Определим последовательность $(q_r)$, $r=0, 1, \dots, N$, соответствиями

$$q_0 = 1, \quad q_{r+1} = 2m(N^{q_r^2}, l) \cdot q_r$$

и положим $m(N, l+1) = q_N(N^{q_r^2})$ это число раскраок квадрата $q_r \times q_r$ в $N$ цветов; существование числа $m(N^{q_r^2}, l)$ обеспечено предположением индекции, $l=1, 2, \dots$).

Квадрат $q_r \times q_r$ называет квадратом раница $r$. Покажем, что при любой раскраске квадрата $K$ ранга $r+1$ в $N$ цветов в нем можно выбрать серию квадратов $K_1, K_2, \dots, K_{l+1}$ ранга $r$, в котором все квадраты, кроме быты, $K_{l+1}$ однозветны. Представим, что квадрат $K$ разбит на большие «клетки», каждая из которых — это квадрат ранга $r$; «цветом» такой клетки будем считать любой из $N' = N^{q_r^2}$ способов ее раскраски в $N$ цветов. Разделим квадрат $K$ на 4 равных квадрата и выберем из них левый нижний — $Q$ (рис. 4). Он состоит из $m' \times m'$ «клеток», где $m' = m(N', l)$, раскрашенных в $N'$ «цветов», и по определению числа $m'$ в нем найдется серия из $l$ «клеток» одного и того же «цвета», то есть серия однозветных квадратов $K_1, \dots, K_l$ ранга $r$. Остается дополнитель ее до серии из $l+1$ квадратов квадратом $K_{l+1}$, который может и не помещиться в $Q$, но заведomo помещится в квадрате $K$.

Докажем теперь, что в качестве числа $m(N, l+1)$ можно взять $q_N$. Пусть $K$ — произвольный квадрат со стороны $m=q_N$, то есть ранга $N$, окрашенный в $N$ цветов. Выделим в нем квадратов $K(1), \dots, K(l+1)$ ранга $N-1$, первыле $l$ из которых однозветны. Пусть $d_1$ — коэффициент этой серии. Выделим в квадрате $K(1)$ серию квадратов $K(1, 1), K(1, 2), \dots, K(1, l+1)$ ранга $N-2$, первыле $l$ из которых однозветны. Пусть $d_2$ — коэффициент этой серии и пусть $K(i, j)$ — это квадрат, который получается из $K(1, j)$ при переноске, совмещающем $K(1)$ и $K(i)$, $i=2, 3, \dots, l+1$, то есть при переноске на вектор $d_1A_1A_i$ (напомним, что $A_1, A_2, \dots$ — центры клеток «стандартного» набора $a_1, a_2, \dots$). Продолжим этот процесс, выделяя в квадрате $K(1, 1)$ серию $K(1, 1, 1), K(1, 1, 2), \dots, K(1, 1, l+1)$ квадратов ранга $N-3$ с коэффициентом $d_3$ и «разносся» ее по своим квадратам $K(i, j)$ и т. д. Через $N$ шагов мы получим квадраты ранга 0, то есть клетки — $K(i_1, i_2, \dots, i_N)$ ($i_k=1, \dots, l+1$). Каждая из этих клеток является последним звеном в цепочке сложенных квадратов более высоких рангов: $K(i_1) \supset K(i_1, i_2) \supset \dots \supset K(i_1, i_2, \dots, i_N)$. С учетом правила построения серий квадратов отсюда

38

Легко вывести следующие свойства:

1. квадраты $K(i_1, i_2, \dots, i_s, i_{s+1}, \dots, i_r)$ и $K(i'_1, i'_2, \dots, i'_s, i_{s+1}, \dots, i_r)$ у которых первые $s$ индексов не превосходят $l$ (а остальные совпадают), однозначны; в частности, при заданных $p$ и $q$ ($p, q \geqslant 0, p+q < N$) клетки $b_i = K(1, \dots, 1, i, \dots, i, l+1, \dots, l+1)$ (1)

имеют один и тот же цвет при всех $i=1, \dots, l$;

2. вектор, соединяющий центры квадратов $K(i_1, i_2, \dots, i_r)$ и $K(j_1, j_2, \dots, j_r)$ равен $d_1 A_{i_1} \vec{A}_{j_1} + d_2 A_{i_2} \vec{A}_{j_2} + \dots + d_r A_{i_r} \vec{A}_{j_r}$; в частности, для клеток $b_i$ и $b_j$ (см. (1)) он равен $(d_{p+1} + d_{p+2} + \dots + d_{N-q}) A_i A_j$.

Тепер мы уже недалеки от цели. Расмотрим следующие $N+1$ клеток:

$K(l+1, l+1, l+1, \dots, l+1), K(1, l+1, l+1, \dots, l+1), K(1, 1, l+1, \dots, l+1), \dots, K(1, 1, 1, \dots, 1)$. По принципу Дирихле хотя бы две из них однозначны. Пусть для определения этого будут клетки $b_1 = K(1, 1, 1, l+1, \dots, l+1)$ и $b_{l+1} = K(1, l+1, l+1, l+1, \dots, l+1)$ (ср. (1) при $p=1, q=N-3$). Тогда из свойств 1) и 2) вытекает, что клетки $b_1, b_2, \dots, b_{l+1}$, где $b_i = K(1, i, i, l+1, \dots, l+1)$, образуют искому однозветную серию (с коэффициентом $d_2 + d_3$). Теорема о раскраске доказана.

Если эта тема вас заинтересовала, советуем обратиться к книжке А. Я. Хинчина «Три жемчужины теории чисел», где приводится подробное доказательство теоремы Ван держ Вардена о прогрессиях.

Уражнения

1. Показать, что теорема о раскраске позволяет решить все пункты задачи M750.

2. Доказать, что если в теореме Ван держ Вардена слово «арифметическая» заменить на «геометрическая», то она остanetся верной. (Кстати, сам Ван держ Варден доказывал свою теорему именно для геометрических прогрессий.)

3. Доказать, что при любом $n$ и при любом разбиении натурального ряда на $N$ классов хотя бы один из них содержит $n$арифметических прогрессий длины $n$, первый которые образуют геометрискую прогрессию.

4. Привести пример разбиения натурального ряда на два подмножества, ни одно из которых не содержит:

a) бесконечнойарифметической прогрессии;

b) ни бесконечнойарифметической прогрессии, ни бесконечной геометрической прогрессии.

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

6. Доказать, что при любой раскраске клеток в $k$ цветов найдется бесконечное множество вертикальных прямых $\{x_i\}$ и бесконечное множество горизонтальных прямых $\{y_i\}$ ($i=1, 2, 3, \dots$) такие, что в пересечении прямых $y_i$ и $x_j$, где $i \geqslant j$, получается центра однозветных клеток.

Левая спираль ДНК

(Начало см. на с. 31)
ности нахождения, как это и считалось раньше, в В-форме.

Возникает вопрос, что будет, если в длиной молекуле ДНК (напомним, что обычная длиная молекула содержит десятичные нуклеотидов) оказывается участок, имеющий последовательность … ЦГЦГ …?

Опыты показали, что при определении условий такой участок действительно нахождения в Z-форме, хотя вокруг него ДНК остается в обычной форме. Имеются доказательства того, что такое возможно и внутри клетки.

Открытие левой спирали и возможность ее существования в «работающей» ДНК вызвало огромный интерес. Во многих laboratorиях мира сейчас интересно исследовать новый формый, условия, при которых в нее переходят соответствующие участки ДНК. Учены пытаются выяснить ту роль, которую Z-форма и вообщество ДНК изменяет свою структуру играют в работе этой молекулы в клетке.

Несомненно, близжайте годы приесут еще много интересных открытий в этой области.