Арифметический бильярд

Геометрический алгоритм НОД и НОК

Арифметический бильярд для чисел 15 и 40: наибольший общий делитель — 5, наименьшее общее кратное — 120.

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

Арифметические бильярды обсуждались как математические головоломки Хьюго Штейнхаусом ^[1] и Мартином Гарднером [ ^2] и известны учителям математики под названием «Бумажный бассейн». ^[3] Они использовались как источник вопросов в математических кругах. ^[4]

Путь арифметического бильярда

Арифметический бильярд для чисел 10 и 40.

Рассмотрим прямоугольник с целочисленными сторонами и построим путь внутри этого прямоугольника следующим образом:

• начните с угла и двигайтесь по прямой линии, которая образует угол 45° со сторонами;
• каждый раз, когда траектория касается стороны, отражайте ее под тем же углом (траектория делает поворот на 90° либо влево, либо вправо);
• в конце концов (т.е. после конечного числа отражений) траектория достигает угла и там останавливается.

Если длина одной стороны делит другую, путь представляет собой зигзаг, состоящий из одного или нескольких сегментов. В противном случае путь имеет самопересечения и состоит из сегментов различной длины в двух ортогональных направлениях. В общем случае путь представляет собой пересечение прямоугольника с сеткой квадратов (ориентированных под углом 45° относительно сторон прямоугольника).

Арифметические характеристики пути

Арифметический бильярд для чисел 3 и 8: наибольший общий делитель — 1, наименьшее общее кратное — 24.

Назовем и длинами сторон прямоугольника и разделим это на единичные квадраты. Наименьшее общее кратное — это количество единичных квадратов, пересекаемых арифметическим бильярдным путем, или, что эквивалентно, длина пути, деленная на . В частности, путь проходит через каждый единичный квадрат тогда и только тогда, когда и взаимно просты . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\cdot b}$ ${\displaystyle \operatorname {lcm} (a,b)}$ ${\displaystyle {\sqrt {2}}}$ ${\displaystyle a}$ ${\displaystyle b}$

Предположим, что ни одна из двух сторон не делит другую. Тогда первый сегмент арифметического бильярдного пути содержит точку самопересечения, которая находится ближе всего к начальной точке. Наибольший общий делитель — это число единичных квадратов, пересеченных первым сегментом пути до этой точки самопересечения. ${\displaystyle \gcd(a,b)}$

Число точек отскока для арифметического бильярдного пути на двух сторонах длины равно , и аналогично для двух сторон длины . В частности, если и взаимно просты, то общее число точек контакта между путем и периметром прямоугольника (т.е. точек отскока плюс начальный и конечный углы) равно . ${\displaystyle a}$ ${\displaystyle (a/\operatorname {gcd} (a,b))-1}$ ${\displaystyle (b/\operatorname {gcd} (a,b))-1}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a+b}$

Конечный угол пути противоположен начальному углу тогда и только тогда, когда и делятся на одну и ту же степень двойки (например, если они оба нечетные), в противном случае это один из двух соседних углов, в зависимости от того, имеет ли или больше множителей в своем разложении на простые множители . ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 2}$

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

Точки контакта между арифметической бильярдной дорожкой и периметром прямоугольника распределены равномерно: расстояние по периметру (т.е. возможно, огибая угол) между двумя такими соседними точками равно . ${\displaystyle 2\gcd(a,b)}$

Зададим координаты в прямоугольнике так, чтобы начальная точка была , а противоположный угол был . Тогда любая точка на траектории арифметического бильярда, имеющая целочисленные координаты, обладает тем свойством, что сумма координат четна (четность не может меняться при движении по диагоналям единичных квадратов). Точки самопересечения траектории, точки отскока и начальный и конечный углы — это в точности точки в прямоугольнике, координаты которых кратны , и такие, что сумма координат четна и кратна . ${\displaystyle (0,0)}$ ${\displaystyle (a,b)}$ ${\displaystyle \gcd(a,b)}$ ${\displaystyle \gcd(a,b)}$

Идеи доказательства

Отражая биллиард, мы можем визуализировать путь как прямую линию. В этом примере отношение двух данных чисел равно 2/3.

Отражение бильярда: Рассмотрим квадрат со стороной . Отображая несколько копий исходного прямоугольника (с зеркальной симметрией), мы можем визуализировать арифметический путь бильярда как диагональ этого квадрата. Другими словами, мы можем думать об отражении прямоугольника, а не сегментов пути. ${\displaystyle \operatorname {lcm} (a,b)}$

Сведение к случаю взаимно простых чисел: удобно изменить масштаб прямоугольника, разделив и на их наибольший общий делитель, операция, которая не меняет геометрию траектории (например, количество точек отскока). ${\displaystyle a}$ ${\displaystyle b}$

Обратное течение времени: движение по траектории «обратимо во времени», что означает, что если траектория в данный момент пересекает один конкретный единичный квадрат (в определенном направлении), то нет никаких сомнений, из какого единичного квадрата и с какого направления она только что пришла. ^[4]

Доказательство можно найти в популяризаторской статье. ^[5]

Одно обобщение

Периодический путь в обобщенном арифметическом бильярде со сторонами 35 и 14.

Если мы позволим начальной точке пути быть любой точкой в ​​прямоугольнике с целочисленными координатами, то существуют также периодические пути, если только стороны прямоугольника не являются взаимно простыми. Длина любого периодического пути равна . ${\displaystyle 2\operatorname {lcm} (a,b)\cdot {\sqrt {2}}}$

Ссылки

1. Steinhaus, Hugo (1999). Mathematical Snapshots (Dover Recreational Math Series ed.). Courier Corporation. стр. 63. ISBN 0486409147.
2. Гарднер, Мартин (1984). Шестая книга математических развлечений из "Scientific American" . Издательство Чикагского университета. С. 211–215. ISBN 0226282503.
3. "Paper Pool Game". NCTM Illuminations . Национальный совет учителей математики . Получено 10 января 2018 г.
4. Tanton, James (2012). Математическое изобилие! Первые пять лет Института математики Св. Марка . Математическая ассоциация Америки. стр. 145–156. ISBN 978-0883857762.
5. Перукка, Антонелла (24 апреля 2018 г.). «Арифметический бильярд». Plus Magazine . Кембриджский университет . Получено 23 декабря 2018 г.