Поворот на клетчатом листе

[VoloCh]

Может, кто знает, решена ли проблема конечности траектории поворота на целочисленной плоскости? Ну, то есть, берем точку на клетчатом лиcте, поворачиваем ее на некоторый угол (вокруг начала координат), округляем до ближайшего пересечения клеточек и вертим дальше. Вопрос: можем ли уйти в бесконечность?

Ну, "по-научному", наверное, будет так: Пусть $P(\cdot):{\mathbb R}^2\rightarrow {\mathbb Z}^2$ --- оператор округления до ближайшего целого, $F_{\alpha}(\cdot):{\mathbb R}^2\rightarrow {\mathbb R}^2$ --- поворот на угол $\alpha$.

Гипотеза: для любого $\alpha$ для любого $x_0\in {\mathbb Z}^2$ последовательность $x_n=P(F_{\alpha}(x_{n-1}))$ограничена (и, значит, траектория зацикливается).

[Sonic86]

Так. Я правильно понял?: Пусть $O(0;0), A_0(x_0,y_0), x,y \in \mathbb{Z}$ и $A_{n+1}$ - ближайшая точка к $R_O^{\varphi}(A_n)$ с целыми кординатами и ограниченна ли последовательность, например, $\sqrt{x_n^2+y_n^2}$?

Так, для углов $\varphi = \frac{\pi}{2}k$ последовательность очевидно зациклится, цикл будет иметь 4 точки.

-- Ср мар 17, 2010 13:59:21 --

Рассмотрим последовательность $r_n=\sqrt{x_n^2+y_n^2}$. Обозначим отображение $f:A_n \to A_{n+1}$. Для некоторого $R$ множество целых точек делится на 2 множества: точек, с радиус-вектором $r \leq R$ и с $r \geq R$. Точки с $r \leq R$ группируем в множества с одинаковым $r$. Последовательность $r_n$ ограниченна $\Leftrightarrow (r(M) \leq R \Rightarrow r(f(M)) \leq R)$. Ясно, что если для точки $M$ с наибольшим $r$ для любого $\varphi$ $r(f(M)) \leq R$, то и вообще для любой $M$ $r(f(M)) \leq R$ для любого $\varphi$. Выберем $R = \sqrt{p}$, где $p$ - простое число вида $4t+1$. Тогда во множестве точек с целыми координатами есть лишь 4 точки $M_{max}$ с наибольшим $r$, причем они при повороте на $\frac{\pi}{2}$ переходят друг в друга. Тогда несложно подобрать $\varphi : r(f(M_{max})) \leq R$. Например можно взять настолько малое $\varphi$, чтобы $f(M_{max}) = M_{max}$. Соответственно получаем бесконечное множество случаев, когда последовательность ограниченна.

З.Ы. Наверное, это дурацкое решение. Возможно тут все гораздо проще.
P.P.S. Я эту проблему никогда не видел.

[VoloCh]

Sonic86, я не очень понял ваше решение. Впрочем, это не важно.

Суть в не в том, чтобы найти случаи, когда последовательность ограничена (ясно, что их, этих случаев "скока хошь"), а в том, чтобы доказать это для всех. Для всех начальных значений и для всех углов.

Ну... или найти контрпример...

[Sonic86]

Ага, подумаю. Но думаю я хреново, не обижайтесь

[paha]

Что такое "ближайшая точка с целыми координатами"? Ведь может так случится, что их четыре штуки... Определите отображение $P:{\mathbb R}^2\to{\mathbb Z}^2$ корректно

[ИСН]

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

[VoloCh]

paha в сообщении #299325 писал(а):

... Определите отображение $P:{\mathbb R}^2\to{\mathbb Z}^2$ корректно

Да хоть покоординатно берем правило округления из 5-го класса средней школы: 1,5 округляется до 2.
Или наоборот, для усиления "диссипативности": 1,5 округляется до 1.
Не имеет значения правило округления. Можно выбрать любое. Или так: по какому правилу округления $\sqrt2$ на компьютере округляется до 156523876513613576458989735200000-го знака? Вот по тому же правилу и мы...!

Где ж молодежь? Подерзать! Это вам не какая-то опостылевшая надоевшая ВТФ

[paha]

VoloCh в сообщении #299363 писал(а):

Да хоть покоординатно берем правило округления из 5-го класса средней школы: 1,5 округляется до 2.
Или наоборот, для усиления "диссипативности": 1,5 округляется до 1.

Вы уверены, что округление проходят именно в пятом классе?

И Вы уверены что от способа округления (не)существование уходящей на бесконечность траектории не зависит?

О.К., подумаем для "диссипативного" варианта не уменьшающего расстояние до начала координат $|P(A)|\ge |A|$.

[VoloCh]

paha в сообщении #299428 писал(а):

Вы уверены, что округление проходят именно в пятом классе?

Математика. Арифметика. Геометрия. 5 класс; учебник для общеобразовательных учреждений/ Е.А.Бунимович, Г.В.Дорофеев, С.Б Суворова и др.: РАН, РАО, изд-во "Просвещение". --- М.: Просвещение, 2010, 223с. ISBN 978-5-09-020275-6.
Нашли? идем в параграф 7, страницы 34-35.

paha в сообщении #299428 писал(а):

О.К., подумаем для "диссипативного" варианта не уменьшающего расстояние до начала координат $|P(A)|\ge |A|$.

Я не говорил, что $|P(A)|\geqslant |A|$. Я говорил, что $|P(A)|\leqslant |A|$только в спорных

paha в сообщении #299325 писал(а):

Ведь может так случится, что их четыре штуки...

случаях выбора "ближайшего целого". Т.е 1,5 округляется до 1, но 1,501 округляется все же до 2. Впрочем, это мое замечание никак не должно ограничивать ваше желание подумать.

[Circiter]

Мне кажется, что задачу поворота точки с последующим её "округлением" всеми возможными способами до ближайшей точки целочисленной сетки можно понимать как задачу рисования окружности на растровом экране --- окружность подсвечивает пересекаемые ею пиксели. Легко видеть, что диаметр наименьшей объемлющей окружности, построенной вокруг экранного образа исходной окружности, больше начального диаметра, а если заменять такой "описанной" окружностью исходную и повторять процесс, то такие итерации будут расходящимися.

Для демонстрации предлагаю простую C-программульку:

Используется синтаксис C

#include <stdio.h>
#include <math.h>

double DrawCircle(double Radius)
{
    double Angle, MaximalRadius=Radius;

    for(Angle=0; Angle<=2*M_PI; Angle+=0.001)
    {
        double NewRadius=Radius*hypot
            (
                floor(cos(Angle)),
                floor(sin(Angle))
            );

        if(NewRadius>MaximalRadius) MaximalRadius=NewRadius;
    }

    return MaximalRadius;
}

int main(void)
{
    double Radius=0.000001;

    while(Radius<1000)
        printf("%lf\n", Radius=DrawCircle(Radius));

    return 0;
}
 

Эта программка печатает последовательность радиусов (начиная с очень маленького) окружностей и останавливается когда радиусы становятся слишком большими (N.B., используется покоординатное округление вниз).

Вывод программки:

0.000001
0.000002
0.000003
0.000004
0.000006
0.000008
0.000011
0.000016
0.000023
0.000032
0.000045
0.000064
0.000091
0.000128
0.000181
0.000256
0.000362
0.000512
0.000724
0.001024
0.001448
0.002048
0.002896
0.004096
0.005793
0.008192
0.011585
0.016384
0.023170
0.032768
0.046341
0.065536
0.092682
0.131072
0.185364
0.262144
0.370728
0.524288
0.741455
1.048576
1.482910
2.097152
2.965821
4.194304
5.931642
8.388608
11.863283
16.777216
23.726566
33.554432
47.453133
67.108864
94.906266
134.217728
189.812531
268.435456
379.625062
536.870912
759.250125
1073.741824

Такую последовательсноть не назовешь сходящейся. Хотя все здесь написанное не более чем наглядный и ничего не доказывающий эксперимент.

[VoloCh]

Circiter, я в сипрограммазме не силен, но вы явно считали что-то другое, нежели требовалось. Объясните мне по-простому вашу программу. hypot - это кто? почему углы меняются, если в условии угол неизменен? Ваще я эксперименты проводил (давно-давно на турбопаскале). Там красивые облачка получались, особенно если угол взять мало отличным от $0{,}25k\pi$. Точнее, траектория - это было круговое облако вокруг нужной окружности, иногда вычурной формы и иногда радиус облака был сильно больше радиуса начального вектора. Но в бесконечность, конечно,ничего не ушло...

[fiktor]

Боюсь, эта программка не имеет отношения к поставленной задаче. Она каждый раз она ищет точку, являющуюся округлением точки единичной окружности вниз, находящуюся на наибольшем расстоянии от начала координат, то есть точку (-1,1). Затем программа умножает радиус на это расстояние (то есть на $\sqrt{2}$). Итого получаем последовательность, в которой каждое следующее число примерно равно предыдущему, умноженному на $\sqrt{2}$.

[Circiter]

2VoloCh
Проблема в том, что я совершенно не понял вашу задачу.

P.S.:

Цитата:

hypot - это кто?

Просто норма (гипотенуза прямоугольного треугольника с данными катетами).

[Circiter]

А, вот теперь до меня дошло. Действительно интересная динамическая система получается. Бум кумекать.

[Circiter]

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

Это согласуется с такими рассуждениями. Пусть угол поворота достаточно мал. При этом, если расстояние от точки до начала координат тоже достаточно мало, то точка при вращении остается в пределах той же клетки (ближайших точек с целочисленными координатами), в которой она и была. Пусть затем, в результате округления, повернутая точка переходит в ближайшую целочисленную с длиной радиус-вектора большей исходной.

Этот процесс может продолжаться некоторое время (конечное число итераций), в течении которого точка движется параллельно одной из координатных осей. Но, коль скоро длина пути точки при её вращении равна произведению длины радиус-вектора на величину угла поворота, вскоре точка начинает на каждой итерации оказываться в соседней клетке, не имеющей с исходной смежной стороны, двигаясь при этом "в среднем" в одном направлении, под 45 градусов к координатным осям. В силу симметрии, при достаточной точности вычислений, траектория замыкается.

Видимо, и на этот раз я вашу задачу не понял. Никак у меня никаких облачков не выходит. Не могли бы вы ещё раз пояснить условие, а может быть даже привести пример-набросок программного кода (уж его-то я точно скорее-всего пойму)?