|
Целочисленная аппроксимация отрезка
М. М. Галламов
Аннотация:
Пусть $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}$.
Ключевые слова:
Задача С. В. Конягина о шахматной раскраске, прямая с иррациональным угловым коэффициентом и шахматная раскраска, цепная дробь, геометрическая интерпретация цепной дроби, алгоритм “вытягивания носов”, целочисленная решётка, аппроксимация отрезка количество целых точек внутри треугольника.
Поступила в редакцию: 07.06.2022 Принята в печать: 08.12.2022
Образец цитирования:
М. М. Галламов, “Целочисленная аппроксимация отрезка”, Чебышевский сб., 23:4 (2022), 20–38
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/cheb1220 https://www.mathnet.ru/rus/cheb/v23/i4/p20
|
|