Целочисленная аппроксимация отрезка
М. М. Галламов
Аннотация:
Пусть
$OXY$ — декартова система координат с целочисленной решёткой, единичные квадраты которой раскрашены в шахматном порядке. Целочисленная аппроксимация отрезка
$AB$ задается с помощью клетчатой области
$\mathbb{S}_{AB}$ из (раскрашенных) клеток, внутренность каждого из которых.имеет непустое пересечение с
$AB$. Если
$P^{\pm}_{AB}$ — правая и левая замкнутые полуплоскости, определяемые прямой
$l_{AB}$ посредством точки
$A$ и
$B$, то $\mathbb{S}^{\pm}_{AB}=\mathbb{S}_{AB}\cap P^{\pm}_{AB}$ —
его правая и левая области. (Внутри
$\mathbb{S}_{AB}$ нет целых точек.) Ломанные
$\mathrm{L}^{\pm}(A^{\pm},B^{\pm})$ из
$\mathbb{S}^{\pm}_{AB}$ с концами
$A^{\pm}$ и
$B^{\pm}$ и целыми вершинами —
правая и левая (целочисленными) аппроксимациями отрезка $AB$ — концы выбираются из вершин крайних клеток. Если
$l_{AB}$ параллельна одной из осей координат, то полагаем
$\mathbb{ S}_{AB}=\varnothing$ и тогда
аппроксимация отрезка $AB$ есть
минимальный отрезок с целыми концами, содержащий $AB$. Такие аппроксимации строятся с помощью алгоритма
“вытягивания носов”, который представляет собой геометрическую интерпретацию цепной дроби углового коэффициента прямой
$l_{AB}$. На основании этого метода построения получена точная формула для вычисления числа целых точек внутри произвольного треугольника, а также частично решена задача С. В. Конягина о шахматной раскраске:
Если $\mathbf{U}(t)$ множество всех раскрашенных клеток из треугольника, отсекаемого прямой $f_{t}:y= -\alpha x+t$,
$\alpha,\ t>0$,
то разность $u(t)$ между белыми и черными клетками из $\mathbf{U}(t)$ для каждого положительного иррационального $\alpha$ не ограничена ни снизу, ни сверху, когда $t\rightarrow\infty$.
Решение получено для чисел вида:
$e^{\pm1}$,
$\mathrm{tg}^{\pm1}$,
$[a^{-}_{0}; a^{-}_{1},a^{-}_{2},\ldots]^{\pm1}$,
$[a^{+}_{0};a^{+}_{1},a^{+}_{2}, \ldots]^{\pm1}$,
$[a^{+}_{0};a^{-}_{1},a^{+}_{2},\ldots]^{\pm1}$, где верхний индекс плюс (минус) указывает на четность (нечетность) элемента цепной дроби, определяемой
$\alpha$.
Метод построения аппроксимации отрезка был применен при решении задачи о шахматной раскраске для чисел
$\frac{\sqrt{5}+1}{2}$,
$[a^{+}_{0};a^{+ }_{1},a^{+}_{2},\ldots]$,
$a^{-}_{2n+1}$ и
$[a^{-}_{0};a^{-}_{1},a^{-}_{ 2},\ldots]$, если ограничено
\begin{equation*} \begin{array}{l} 2^{k-1}b_{3}b_{9} \cdots b_{6(k-1)+3} + \cdots + 2^{2}\sum^{k}_{i_{1}>i_{2}>i_{3}=1} b_{6(k-i_{1})+3}b_{6(k-i_{2})+3} \\ b_{6(k-i_{3})+3} + 2\sum^{k}_{i_{1}>i_{2}=1} b_{6(k-i_{1})+3}b_{6(k-i_{2})+3} + \sum^{k}_{i=1}b_{6(k-i_{1})+3} + 1, \end{array} \end{equation*}
для некоторых $b_{n}=\left\lfloor\frac{a^{-}_{n}-1}{2}\right \rfloor$, представляющих целую часть
$\frac{a^{-}_{n}-1}{2}$. Так при
$b_{n}=0$ цепная дробь $[a^{-}_{0};a^{-}_{1},a^{-}_{2}, \ldots]=\frac{\sqrt{5}+1}{2}$.
Ключевые слова:
Задача С. В. Конягина о шахматной раскраске, прямая с иррациональным угловым коэффициентом и шахматная раскраска, цепная дробь, геометрическая интерпретация цепной дроби, алгоритм “вытягивания носов”, целочисленная решётка, аппроксимация отрезка количество целых точек внутри треугольника.
УДК:
51
Поступила в редакцию: 07.06.2022
Принята в печать: 08.12.2022
DOI:
10.22405/2226-8383-2022-23-4-20-38