"Иррациональная" прямая на квадратной решётке

Григорий Гальперин, Сергей Дориченко, Владимир Гуровиц

Пусть прямая l: y=ax+b, a>0 составляет острый угол a=arctg a с осью Ox. Рассмотрим квадратную решётку Z² на плоскости Oxy, составленную из единичных квадратов со сторонами, параллельными осям координат. Прямая l пересекает бесконечно много квадратов решётки, а эти квадраты, в свою очередь, разрезают l на бесконечно много отрезков. Обозначим длину отрезка в "первом квадрате" {(x,y)|0<x,y<1} через d₀, а длины "предшествующих" и "последующих" отрезков - через ..., d_-2, d_-1 и d₁, d₂, ... соответственно.

1) Предположим, что прямая l - "рациональная", т. е. a=p/q - рациональное число. Сколько различных чисел встретится в последовательности ..., d_-2, d_-1, d₀, d₁, d₂, ... ? (Выразите ответ в терминах p, q и b и выпишите явно последовательность d₀, d₁, d₂, ... .)

2) Предположим теперь, что прямая l - "иррациональная", т. е. a - иррациональное число. Верно ли, что все числа ..., d_-2, d_-1, d₀, d₁, d₂, ... различны?

3) Если ответ на вопрос предыдущего пнкта отрицательный, то некоторое число d встречается в последовательности длин {d_i|iCZ} более одного раза. Может ли в этой последовательности содержаться бесконечно много одинаковых чисел? Бесконечно много различных чисел?

4) Пусть n(k) означает, сколько раз число d_k встречается в последовательности {d_i|iCZ}. Предположим, что при некотором k число n=n(k) конечно. Найдите все возможные значения n. Например, может ли n быть равно 5? Зависит ли ответ от коэффициентов a и b ?

5) Опишите все положения прямой l, для которых n(k)>1 для всех k.

6) Найдите ..., d_-2, d_-1, d₀, d₁, d₂, ... в терминах a и b или a и b .

7) Спроектируем все вершины решётки на прямую l. Получим бесконечное множество точек на прямой. Будет ли это множество всюду плотным? (Множество на прямой называется всюду плотным, если любой отрезок этой прямой, как бы мал он ни был, содержит хотя бы одну точку множества.) Под проекцией понимается ортогональная проекция, но вы также можете рассматривать проекции в других направлениях.

8) Рассмотрим прямую l в 3-мерном пространстве и её пересечения с кубами 3-мерной решётки Z³. Прямая l вновь разбивается на отрезки

..., d_-2, d_-1, d₀, d₁, d₂, ... .

Ответьте в этом случае на вопросы 1-7.

9) Решите ту же задачу для n-мерной решётки Zⁿ, n>4.

Промежуточный финиш. Задачи 2, 3, 4, 5, 7 снимаются с конкурса.

Леммы Дирихле, Вейля и Кронекера.

Обозначение. Пусть x - действительное число. Дробную часть числа x будем обозначать через {x}.

10. (Лемма Дирихле) Пусть l₁ - иррациональное число. Докажите, что последовательность {l₁n}, nCN всюду плотна на отрезке [0, 1].

Определение. Рассмотрим последовательность a_n, где a_nC[0, 1] при всех nCN. Назовём её равномерно распределённой на отрезке [0, 1], если для любого отрезка Ic[0, 1]

lim (N(I)/N)=|I|

N->oo

где N(I) - число точек a_kCI с номерами k<N, |I| - длина отрезка I.

11. (Лемма Вейля) Пусть l₁ - иррациональное число. Докажите, что последовательность дробных частей {l₁n}, nCN, равномерно распределена на отрезке [0, 1].

Будем теперь рассматривать последовательность векторов a_n=({l₁n},...,{l_sn}) в единичном кубе s-мерного пространства (l_iCR).

12. Покажите, что для любого e>0 существует такое nCN, что для каждого i=1,...,s выполняется 0<{kl_i}<e или 1-e<{kl_i}<1.

Определение. Числа l₀, l₁,..., l_n называются линейно независимыми над Q, если из равенства

s

S k_il_i=0, k_iCQ

i=0

следует, что все k_i равны 0.

13. (Лемма Кронекера) Пусть числа l₀, l₁,..., l_n линейно независимы над Q, причём l₀=1. Докажите, что последовательность векторов a_n=({l₁n},{l₂n},...,{l_sn}) всюду плотна в единичном кубе s-мерного пространства.

Разбиения прямой.

14. Пусть прямая разбита k системами равноотстоящих точек (система с номером i задаётся двумя параметрами: шагом h_i и сдвигом b_i относительно начала координат). Предположим, что расстояния между соседними точками в системах линейно независимы над Q. Скажем, что отрезок разбиения имеет тип (i,j), если его левый конец принадлежит i-ой системе, а правый конец принадлежит j-ой системе (считаем, что на прямой введено направление).

Найдите вероятность того, что отрезок типа (i,j) имеет длину >l, то есть найдите

lim (U_t/M_t)

t->oo

где M_t - число всех отрезков типа (i,j), лежащих целиком в [-t,t], а U_t - число отрезков типа (i,j) длины больше l, целиком лежащих в [-t,t].

(Выразите ответ через параметры h_i и b_i.)

15. Дана иррациональная прямая на квадратной решётке. Найдите вероятность того, что отрезок разбиения соединяет две противополоржные стороны квадрата решётки.

Мозаики.

Пусть P - некоторая плоскость в трёхмерном пространстве. Плоскости вида

x=n, nCZ; y=m, mCZ; z=k, kCZ,

пересекаясь с плоскостью P, разбивают её на многоугольники (будем называть это разбиение мозаикой).

Определение. Средней площадью многоугольника мозаики назовём величину

S= lim (S_t/N_t)

t->oo

где S_t - общая площадь всех многоугольников, целиком содержащихся в круге радиуса t с центром в начале координат, а N_t - количество этих многоугольников.

16. Пусть n систем равноотстоящих прямых разбивают плоскость на части, причём никакие 3 прямые не пересекаются в одной точке, и никакие две системы не параллельны. Пусть s_i_j - площадь параллелограмма, порождённого семействами с номерами i и j. Докажите, что

S^-1= S (s_i_j)^-1 .
i<j

17. Рассмотрим плоскость Ax+By+Cz=0, A, B, C - взаимно простые положительные натуральные числа. Докажите, что число различных многоугольников, образующихся в пересечении плоскостью кубической решётки, не превосходит A+B+C-1. Попробуйте сформулировать условия, при которых достигается равенство. (Два многоугольника считаются одинаковыми, если они получаются друг из друга параллельным переносом.)

18. Пусть три системы прямых

x=n, nCZ

y=m, nCZ

x+ly=an, nCZ, l не принадлежит Q

разбивают плоскость на части. Вычислите вероятность того, что данная фигура является
   а) треугольником;
   б) четырёхугольником;
   в) пятиугольником;
   г) шестиугольником;
   д) семиугольником.