Текст статьиВагутен Н. Арифметические препятствия // Квант. — 1979. — № 3. — С. 22—30.
Во многих математических теориях и прикладных задачах, а также в математических играх и головоломках возникают вопросы такого рода: можно ли перейти от одной позиции к другой с помощью некоторых «допустимых» операций (ходов)? Как найти нужную цепочку ходов, если она существует, или доказать, что переход невозможен? В этой статье мы разберём несколько задач такого типа. Их объединяет ещё и внешнее сходство: в каждой из них фигурируют целые числа, а «препятствия» переходам, как правило, имеют арифметическую природу.
Примеры, с которых начинается обсуждение каждой задачи, вполне доступны даже ученикам младших классов. Упражнения «со звёздочкой» и доказательства общих результатов требуют от читателя серьёзных размышлений. Заканчивается статья трудными олимпиадными задачами, последняя из которых примыкает к неэлементарной, бурно развивающейся сейчас теории арифметических групп.
1. Задача о коне
Задача 1. Даны натуральные числа $m$ и $n$. На одном из полей бесконечной шахматной доски стоит фигура, которая ходит «буквой Г» на $m$ полей в одном из направлений и на $n$ в перпендикулярном; назовём её $\{m;n\}$-конём. На какие поля доски этот конь может попасть?
Обычный шахматный конь ($\{1;2\}$-конь) может из любого начального поля $O$ попасть на любое другое: за три хода он может попасть на соседнее с $O$ поле, а такими элементарными шагами можно, конечно, прийти куда угодно.
Рис. 1. $\{1;3\}$-конь может попасть на соседнее (по диагонали) поле того же цвета; такими шагами он может обойти все одноцветные поля.
А вот $\{1;3\}$-конь, несколько ходов которого показаны на рисунке 1, никак не может попасть на соседнее (по горизонтали) с начальным поле. На шахматной доске очень легко объяснить, что препятствует такому переходу: $\{1;3\}$-конь всегда ходит по полям одного цвета. С другой стороны, нетрудно показать, что $\{1;3\}$-конь может обойти все поля одного цвета: за три хода он может сдвинуться по диагонали на соседнее поле того же цвета (рис. 1), а такими элементарными шагами уже легко обойти все одноцветные поля.
Попробуйте решить задачу 1 для чисел
2 и 5;
3 и 7;
10 и 25;
19 и 79.
Оказывается, $\{m;n\}$-конь может попасть на любое поле в том и только том случае, когда $m$ и $n$ имеют разную чётность и их наибольший общий делитель равен 1.
Полный ответ к задаче 1 приведён в конце пункта 3 (упражнение 10). Сейчас мы займёмся более простым вопросом. Результат, который мы получим, полезен и для задачи о коне, и для более серьёзных математических задач.
2. Представление НОД
Задача 2. Даны натуральные числа $a$ и $b$. За один ход разрешается прибавить к некоторому целому числу одно из чисел $a$, $b$ или вычесть из него одно из этих чисел. Можно ли таким образом из числа $0$ получить число $c$?
В этой задаче множество «позиций» — это множество $\Z$ всех целых точек числовой прямой.
Начнём с конкретного примера. Предположим, что у покупателя и кассира есть только купюры в 10 и 25 рублей, причём (чего не бывает в математических задачах!) в неограниченном количестве. Ясно, что покупатель может заплатить кассиру $c$ рублей в том и только том случае, когда $c$ кратно 5.
Ещё пример. Пусть на множестве $\Z$ разрешены ходы $\pm19$ и $\pm79$. С помощью этих ходов можно получить любое целое число: их комбинация позволяет сдвинуться на расстояние 3, а затем и на расстояние 1 (рис. 2, а).
Рис. 2. Числа 19 и 79 взаимно просты, поэтому после нескольких делений с остатком получается остаток $1=\gcd(19,79)$.
Более сложный пример: $a=819$, $b=357$. В этом случае тем же приёмом удаётся найти кратчайший сдвиг — на 21 (рис. 3, а). Таким образом, здесь можно устроить переход на любое расстояние, кратное 21. С другой стороны, и $a$, и $b$ делятся на 21, поэтому никакие другие переходы невозможны.
Заметим, что 21 — наибольший общий делитель чисел 819 и 357 (проверьте это!).
Рис. 3. Чтобы найти $\gcd(819,357)=21$ с помощью алгоритма Евклида, надо сделать четыре шага.
Упражнение 1.
Докажите, что если у покупателя и кассира есть (в неограниченном количестве) трёшки и пятёрки, то покупатель может заплатить любое число рублей.
Можно ли перейти от 0 к 1000, если $a=123$, $b=456$? если $a=589$, $b=1984$?
Какие переходы возможны при $a=18$, $b=81$?
Теперь сформулируем ответ к задаче 2 в общем виде. Пусть наибольший общий делитель (НОД) чисел $a$ и $b$ равен $d$. Тогда переход от $0$ к $c$ возможен в том и только том случае, когда число $c$ делится на $d$. Попробуйте доказать это.
В несколько иной форме мы получим этот результат в следующем пункте.
Упражнение 2. Докажите, что ответ к задаче 2 не изменится, если число $a$ разрешается только прибавлять, а $b$ — только вычитать.
Упражнение 3. Можно ли на чашечных весах с помощью гирь 36 г и 60 г (эти гири имеются в неограниченном количестве, и их можно класть на обе чашки весов) отвесить
150 г;
132 г?
3. Алгоритм Евклида
В следующей задаче позициями будут пары целых чисел.
Задача 3. Три автомата печатают на карточках пары целых чисел. Каждый автомат, прочитав карточку $(x;y)$, выдаёт новую карточку: первый автомат выдаёт $(x-y;y)$, второй автомат выдаёт $(x+y;y)$, третий автомат выдаёт $(y;x)$.
Пусть первоначально имеется одна карточка с парой чисел $(1;2)$. Можно ли, используя автоматы в любом порядке, получить карточку$(19;79)$? $(819;357)$?
Какие вообще карточки можно получить, если первоначально имеется карточка с парой чисел$(a;b)$?
Рис. 4. Каждый «марш» этой лестницы — один шаг алгоритма Евклида.
Обозначим операции, которые проделывают автоматы, соответственно, через $L$, $R$ и $S$. Начнём опять с числовых примеров.
Пару $(19;79)$ из пары $(1;2)$ операциями $L$, $R$, $S$ получить можно. Чтобы осуществить нужный переход, удобнее не подниматься от $(1;2)$ к $(19;79)$, а спускаться в обратном направлении (рис. 4).
Записав получившуюся цепочку в обратном порядке (и, конечно, меняя при этом $L$ и $R$), получим «подъём» от $(1;2)$ к $(19;79)$.
На рисунке 4 «спуск» от $(19;79)$ к $(1;2)$ мы продолжили до пары $(1;0)$; сокращённая запись этого «спуска» приведена на рисунке 2, в($L^k$ означает, что операция $L$ проделывается $k$ раз подряд). Собственно говоря, тот же спуск мы уже проделывали в соответствующем примере к предыдущей задаче (рис. 2, а).
Спуск, начинающийся с пары $(819;357)$, сокращённо записан на рисунке 3, в — запишите его подробно. Здесь пара $(1;2)$ (или $(1;0)$) не получается. И не удивительно — тому есть препятствие: все получаемые числа делятся на $21$. В каком бы порядке мы ни применяли операции $L$, $R$, $S$, избавиться от этого препятствия не удастся, поскольку, как нетрудно доказать, эти операции сохраняют общие делители чисел на карточке: $\gcd(x-y,x)=\gcd(x+y,y)=\gcd(x,y)$. Поэтому перейти от пары $(819;357)$ к паре $(1;2)$ или обратно нельзя.
Упражнение 4. Можно ли с помощью операций $L$, $R$, $S$ перейти
от пары $(1;10)$ к паре $(5;25)$?
от $(18;81)$ к $(36;63)$?
от $(589;1984)$ к $(31;1953)$?
Теперь мы можем сформулировать ответ на последний, общий вопрос задачи 3: пару $(a;b)$ можно перевести в пару $(p;q)$ в том и только в том случае, когда$\gcd(a;b)=\gcd(p;q)$. Это условие необходимо, поскольку, как мы уже говорили, наши операции сохраняют НОД. Но оно также и достаточно: если $\gcd(a,b)=\gcd(p,q)=d$, то каждую из этих пар операциями $L$, $R$, $S$ можно привести к паре $(d;0)$; проделав спуск от $(a;b)$ к $(d;0)$ и затем подъём от $(d;0)$ к $(p;q)$, мы получим цепочку от $(a;b)$ к $(p;q)$.
Покажем, почему от любой пары $(a;b)$ можно перейти к паре $(d;0)$. Заметим, что если один из элементов пары отрицателен, то его легко сделать положительным (рис. 5). А пару $(a;b)$ с натуральными$a$ и $b$ можно привести к паре $(d;0)$ тем же способом, который мы применили в примерах: на каждом шаге (кроме перестановок-симметрий) больший элемент пары уменьшается до тех пор, пока мы не придём к финалу $\to(d;d)\to(0;d)\to(d;0)$.
Рис. 5. Операциями $L$, $R$, $S$ можно поменять знак у одного числа на карточке.
Решая задачу 3, мы получили удобный способ отыскания наибольшего общего делителя двух чисел: от пары $(a;b)$, где $a\gt b\gt0$, переходим к паре $(b;r)$, где $r$ — остаток от деления $a$ на $b$, и повторяем эту операцию до тех пор, пока не получим пару $(d;0)$. Последний не равный нулю остаток $d$ и есть$\gcd(a;b)$ (рис. 2, б, 3, б). Этот способ называется алгоритмом Евклида.
Упражнение 5. Докажите, что из пары $(1357;2468)$ нельзя получить пару $(1234;5678)$; из пары $(123;457)$ нельзя получить $(7890;1979)$.
Упражнение 6. Приведите примеры, показывающие, что операции задачи 3 не перестановочны: $LS\ne SL$, $RS\ne SR$ (разумеется, $LR=RL$).
Упражнение 7. Найдите с помощью алгоритма Евклида $\gcd(589,1984)$, $\gcd(123456789,987654321)$.
Целочисленной решёткой$\Z^2$ называется множество всех точек плоскости с целыми координатами.
Следующее упражнение и рисунок 6 проясняют геометрический смысл задачи 3:
Упражнение 8. Докажите, что если отрезок $OA$, где $O$ — начало координат, $A$ — узел целочисленной решётки $\Z^2$, разбивается другими узлами на $d$ частей, то операциями $L$, $R$ и $S$ узел $A$ можно перевести в узлы $(d;0)$ и $(-d;0)$ и нельзя перевести ни в какие другие точки оси $Ox$.
Упражнения 9 и 10 обобщают задачи 1 и 2:
Упражнение 9*. Пусть заданы $n$ натуральных чисел $a_1$, $a_2$, $\ldots$, $a_n$. Докажите, что целое число $c$ можно получить из 0 ходами $\pm a_1$, $\pm a_2$, $\ldots$, $\pm a_n$ тогда и только тогда, когда $c$ делится на $\gcd(a_1,a_2,{\ldots},a_n)$.
Упражнение 10*.
Пусть на плоскости $Oxy$ заданы $n$ векторов $\overrightarrow{v_1}$, $\overrightarrow{v_2}$, $\ldots$, $\overrightarrow{v_n}$ целочисленными координатами. Докажите, что множество точек $D$ плоскости, в которые можно попасть из точки $O$ ходами $\pm\overrightarrow{v_1}$, $\pm\overrightarrow{v_2}$, $\ldots$, $\pm\overrightarrow{v_n}$, представляет собой множество вершин некоторой косоугольной решётки (так называется множество вершин параллелограммов, на которые два семейства равноотстоящих параллельных прямых разрезают плоскость).
Пусть вместе с каждым вектором $\overrightarrow{v_i}$ в семействе векторов $\overrightarrow{v_1}$, $\overrightarrow{v_2}$, $\ldots$, $\overrightarrow{v_n}$ имеется равный ему по длине и перпендикулярный. Тогда множество «достижимых» точек $D$ будет множеством вершин некоторой квадратной решётки.
Теперь уже нетрудно найти ответ к задаче 1: пусть $m=dm_1$, $n=dn_1$, где $d=\gcd(m,n)$; тогда, если $m_1+n_1$ нечётно, достижимы все поля $(dx;dy)$, где $x$ и $y$ — произвольные целые числа (решётка с шагом $d$); если же $m_1+n_1$ чётно — поля $(dx;dy)$, где $x\in\Z$, $y\in\Z$ и $x+y$ чётно (решётка с шагом $d\sqrt2$, повёрнутая на угол $45^\circ$ по отношению к линиям доски).
4. Некоторые итоги
В заключительной части статьи мы познакомим вас ещё с двумя довольно трудными задачами. Но прежде, оглянувшись назад, попробуем высказать общие соображения, которые помогли нам — и помогут в дальнейшем — выяснять, возможен ли переход от одной «позиции» к другой, и назовём математические «имена» тех понятий, которые встретились нам в задачах.
1°. Чтобы доказать невозможность того или иного перехода, мы обнаруживали некоторое препятствие — характеристику позиции, сохраняющуюся (как говорят, инвариантную) при всех допустимых ходах, но различную для начальной и конечной позиций; таким образом, доказательство невозможности того или иного перехода сводилось к отысканию подходящего инварианта. Таким инвариантом в задаче о $\{1;3\}$-коне является цвет поля, в задаче 2 — остаток от деления числа на $\gcd(a,b)$, в задаче 3 — НОД пары чисел на карточках. Подробнее об этом можно прочесть в «Кванте»
1974, №2 (с. 26),
1976, №2 (с. 32) и 1976, №12 (с. 19).
2°. Чтобы построить цепочку переходов на решётке, часто бывает полезно найти какой-то элементарный «ключевой» ход (или комбинацию ходов), либо свести дело к какой-то простейшей канонической позиции, — а затем уже сформулировать общее правило (алгоритм) отыскания переходов. Так, в задаче о $\{1;3\}$-коне достаточно научиться делать ход по диагонали, в задаче 2 — сдвиг на $d=\gcd(a,b)$, в задаче 3 — «спуск» к канонической позиции $(d;0)$.
3°. Во всех рассмотренных пока задачах переходы были обратимы: если от позиции $A$ можно было перейти к позиции $B$, то можно было вернуться и обратно — от $B$ к $A$. В таких задачах всё множество позиций разбивается на классы эквивалентности: внутри одного класса от каждой позиции можно перейти к любой другой, а никакие переходы между позициями из различных классов невозможны.
Сейчас мы рассмотрим задачу, в которой такой обратимости нет, но зато в ней прекрасно работают соображения 1° и 2°.
5. Избавление от двоек
Задача 4. Три автомата печатают на карточках пары натуральных чисел. Автоматы работают следующим образом: первый автомат, прочитав карточку $(a;b),$ выдаёт карточку $(a+1;b+1);$ второй автомат, прочитав карточку $(a;b),$ выдаёт карточку$\left(\dfrac a2;\dfrac b2\right)$ (он работает только в том случае, когда оба числа $a$ и $b$ чётны); третий автомат по двум карточкам $(a;b)$ и $(b;c)$ выдаёт карточку$(a;c)$.
Пусть первоначально имеется карточка с парой чисел $(5;19)$. Можно ли, используя автоматы в любом порядке, получить карточку
$(1;50)$?
$(1;100)$?
Пусть первоначально имеется карточка $(a;b)$, $a\lt b$, a мы хотим получить карточку $(1;n)$. При каких $n$ это можно сделать?
Эта задача предлагалась на XII Всесоюзной математической олимпиаде ученикам 8—10 классов. Впрочем, даже пятиклассникам хватит знаний, чтобы решать её.
Обозначим операции, которые выполняют наши новые автоматы, соответственно, через $I$, $H$ и $T$. На рисунке 7 показано, как из карточки $(5;19)$ получить «простейшую» Kapточку $(1;8)$ и затем — карточку $(1;50)$ (вместо «$k$ раз применить операцию $I$» мы снова пишем $I^k$). Таким образом, в задаче а) ответ утвердительный.
А вот карточку $(1;100)$, про которую спрашивается в задаче б), из карточки $(5;19)$ получить не удастся. Препятствие можно обнаружить, внимательно изучив тот же рисунок 7: разность чисел на каждой карточке делится на 7. В каком бы порядке мы ни применяли автоматы, избавиться от этого свойства не удастся — его сохраняют операции $I$, $H$ и $T$. (Для $I$ это очевидно. Для $H$: если $a$ и $b$ — чётные и $b-a$ делится на 7, то и $\dfrac b2-\dfrac a2$ делится на 7. Для $T$: если разности $b-a$ и $c-b$ делятся на 7, то и $c-a=(c-b)+(b-a)$ делится на 7.) Но разность $100-1=99$ на 7 не делится, так что ответ к б) отрицательный.
Рис. 7. С помощью операций $I^q$ (увеличение на $q$), $H$ (деление пополам), $T$ («транзитивный» переход) из $\fbox{\(\displaystyle{5\atop19}\)}$ получаем $\fbox{\(\displaystyle{1\atop50}\)}$.Рис. 8. Большее число $b$ на карточке $\fbox{\(\displaystyle{a\atop b}\)}$ можно уменьшить ($d=b-a$; $a\gt1$ или $a=1$, $b$ нечётно).
Упражнение 11. Можно ли, используя автоматы $I$, $H$ и $T$,
из карточки $(3;33)$ получить карточки $(5;29)$, $(1;101)$, $(1;1978)$?
Из карточки $(5;29)$ получить $(3;33)$, $(1;100)$, $(1;1979)$?
Сформулируем теперь ответ на последний, общий вопрос в) задачи 4: из карточки $(a;b)$, в которой $b-a=2^md$, где $d\gt0$ и нечётно, можно получть те и только те карточки $(p;q)$, в которых разность $p-q\gt0$ делится на$d$. Таким образом, можно избавиться от всех двоек в разложении $b-a$, но нечётный делитель разности $b-a$ служит непреодолимым препятствием.
В самом деле, как мы уже говорили (для $d=7$), из карточек, у которых разность делится на нечётное число $d$, с помощью операций $I$, $H$, $T$ получаются только карточки, обладающие тем же свойством. С другой стороны, от карточки $(a;b)$, где $b-a=2^md$ ($d$ нечётно), можно перейти к карточке $(1;d+1)$. (Один шаг такого перехода показан на рисунке 8.) Получив карточку $(1;d+1)$, легко изготовить любую карточку $(1;kd+1)$ (как в задаче а) — из карточки $(1;8)$) и затем — любую карточку $(l;kd+l)$ с разностью чисел, кратной $d$.
Упражнение 12.
Предположим, что автомат, выполняющий операцию $T$, сломался. Какие карточки можно получить из $(5;19)$? $(5;29)$?
Пусть сломался автомат, выполняющий операцию $H$. Какие карточки можно получить из карточки $(a;b)$?
Упражнение 13*. Какие карточки можно получить операциями $I$, $H$, $T$ из $n$ данных карточек $(a_1;b_1)$, $(a_2;b_2)$, $\ldots$, $(a_n;b_n)$?
Задача 4 выглядит довольно искусственной. Поэтому, возможно, вам будет интересно узнать, что она возникла из леммы в одной серьёзной математической книге (С. Улам, «Нерешённые математические задачи», М., Наука, 1964, с. 60).
6. Пары векторов
Следующая задача продолжает задачу 3. Здесь фигурируют те же три операции $L$, $R$ и $S$, но в задаче 3 они применялись к парам целых чисел, а теперь «позициями» будут пары векторов$(a;b)$ и $(c;d)$ с целыми координатами, и эти операции будут применяться одновременно к обоим векторам пары. Координаты обоих векторов удобно записывать в два столбика — получится табличка $\colsep{2pt}{\begin{pmatrix}a&c\\b&d\end{pmatrix}}$ из четырёх чисел; такие таблички в математике называются матрицами.
Задача 5. С матрицей $\colsep{2pt}{\begin{pmatrix}a&c\\b&d\end{pmatrix}}$ разрешается проделывать следующие операции:
$$
\def\t#1#2#3#4{\colsep{3pt}{\begin{pmatrix}#1 & #2\\#3 & #4\end{pmatrix}}}
\begin{aligned}
L&\colon\t acbd\to\t{a-b}{c-d}bd,\\
R&\colon\t acbd\to\t{a+b}{c+d}bd,\\
S&\colon\t acbd\to\t bdac.
\end{aligned}
$$
Можно ли этими операциями из матрицы $\colsep{2pt}{\begin{pmatrix}1&5\\2&7\end{pmatrix}}$ получить следующие матрицы:
а) $\colsep{2pt}{\begin{pmatrix}1&3\\2&9\end{pmatrix}}$;б) $\colsep{2pt}{\begin{pmatrix}1&1\\2&2\end{pmatrix}}$;в) $\colsep{2pt}{\begin{pmatrix}1&0\\0&1\end{pmatrix}}$;г) $\colsep{2pt}{\begin{pmatrix}1&2\\0&3\end{pmatrix}}$;д) $\colsep{2pt}{\begin{pmatrix}1&1\\0&3\end{pmatrix}}$?
Какие вообще матрицы можно получить из данной матрицы$\colsep{2pt}{\begin{pmatrix}a&c\\b&d\end{pmatrix}}$?
Будем называть две матрицы эквивалентными, если одну из них операциями $L$, $R$ и $S$ можно перевести в другую (здесь переходы обратимы, так что все матрицы разбиваются на классы эквивалентных).
В решении очень трудной задачи 5 нам встретится несколько препятствий. Будем преодолевать их последовательно.
а) Матрицы $\colsep{2pt}{\begin{pmatrix}1&5\\2&7\end{pmatrix}}$ и $\colsep{2pt}{\begin{pmatrix}1&3\\2&9\end{pmatrix}}$ не эквивалентны; второй вектор $\colsep{2pt}{\begin{pmatrix}5\\7\end{pmatrix}}$ никак нельзя перевести в $\colsep{2pt}{\begin{pmatrix}4\\9\end{pmatrix}}$, поскольку $\gcd(5,7)\ne\gcd(3,9)$. Вообще, из результата задачи 3 сразу вытекает условие, необходимое для эквивалентности двух матриц $\colsep{2pt}{\begin{pmatrix}a&c\\b&d\end{pmatrix}}$ и $\colsep{2pt}{\begin{pmatrix}p&r\\q&s\end{pmatrix}}$:
$$
\left\{\begin{array}{l}
\gcd(a,b)=\gcd(p,q),\\
\gcd(c,d)=\gcd(r,s).
\end{array}\right.\tag{*}
$$
Однако, как мы сейчас увидим, это условие не достаточно для эквивалентности матриц. Во всяком случае, если это условие выполнено, мы можем разделить каждый столбец матрицы на его НОД и далее рассматривать такие сокращённые матрицы (ведь НОД каждого столбца сохраняется при всех операциях).
б) Матрицы $\colsep{2pt}{\begin{pmatrix}1&5\\2&7\end{pmatrix}}$ и $\colsep{2pt}{\begin{pmatrix}1&1\\2&2\end{pmatrix}}$ не эквивалентны, потому что при любом преобразовании $L$, $R$, $S$ из матрицы $\colsep{2pt}{\begin{pmatrix}1&1\\2&2\end{pmatrix}}$ получится матрица с одинаковыми столбцами $\colsep{2pt}{\begin{pmatrix}p&p\\q&q\end{pmatrix}}$.
в) Матрицы $\colsep{2pt}{\begin{pmatrix}1&5\\2&7\end{pmatrix}}$ и $\colsep{2pt}{\begin{pmatrix}1&0\\0&1\end{pmatrix}}$ тоже не эквивалентны; тут возникает новое препятствие: величина
$$
\Delta=\Delta\colsep{2pt}{\begin{pmatrix}a&c\\b&d\end{pmatrix}}=|ad-bc|.
$$
Она сохраняется при всех преобразованиях $L$, $R$, $S$ матрицы $\colsep{2pt}{\begin{pmatrix}a&c\\b&d\end{pmatrix}}$. Проверим это для $L$:
$$
(a-b)d-b(c-d)=ad-bc.
$$
(для $R$ и $S$ проведите проверку сами.) Поскольку $\Delta\colsep{2pt}{\begin{pmatrix}1&5\\2&7\end{pmatrix}}=3$, а $\Delta\colsep{2pt}{\begin{pmatrix}1&0\\0&1\end{pmatrix}}=1$, эти матрицы не эквивалентны. Заметим, что $$
\Delta\colsep{2pt}{\begin{pmatrix}p&p\\q&q\end{pmatrix}}=0.
$$
Величина $ad-bc$ очень часто возникает в разных задачах про матрицы и называется определителем матрицы $\colsep{2pt}{\begin{pmatrix}a&c\\b&d\end{pmatrix}}$.
Рис. 9. Приведение к каноническому виду. При всех преобразованиях $L$, $R$, $S$ сохраняется площадь параллелограмма и расположение узлов целочисленной решётки внутри него.
г) Матрицы $\colsep{2pt}{\begin{pmatrix}1&5\\2&7\end{pmatrix}}$ и $\colsep{2pt}{\begin{pmatrix}1&2\\0&3\end{pmatrix}}$ эквивалентны: цепочка преобразований, приводящих первый вектор $\colsep{2pt}{\begin{pmatrix}1\\2\end{pmatrix}}$ к каноническому виду $\colsep{2pt}{\begin{pmatrix}1\\0\end{pmatrix}}$, и небольшие дополнительные ухищрения приводят к цели (рис. 9). На рисунке 9 хорошо виден и наш инвариант $\Delta$: это — площадь параллелограмма, построенного на векторах $\colsep{2pt}{\begin{pmatrix}a\\b\end{pmatrix}}$ и $\colsep{2pt}{\begin{pmatrix}c\\d\end{pmatrix}}$.
Рис. 10. В параллелограммах для матриц $\colsep{2pt}{\begin{pmatrix}1&1\\0&3\end{pmatrix}}$ и $\colsep{2pt}{\begin{pmatrix}1&2\\0&3\end{pmatrix}}$ расположение узлов целочисленной решётки различно.
Осталось ещё выяснить, д) эквивалентны ли матрицы $\colsep{2pt}{\begin{pmatrix}1&1\\0&3\end{pmatrix}}$ и $\colsep{2pt}{\begin{pmatrix}1&2\\0&3\end{pmatrix}}$. Оказывается, нет, хотя указать препятствие здесь не так просто. Его геометрический смысл ясен из рисунков 9 и 10.
Теперь мы можем дать ответ на общий вопрос задачи 5. Любую сокращённую матрицу операциями $L$, $R$, $S$ можно преобразовать к каноническому виду
$$
{\colsep{2pt}{\begin{pmatrix}1&r\\0&\Delta\end{pmatrix}}},\quad\text{где}\enspace
0\le r\lt\Delta{,}\enspace\gcd(r,\Delta)=1,\tag1
$$
или $$
\colsep{2pt}{\begin{pmatrix}1&1\\0&0\end{pmatrix}}\quad(\text{если}\enspace\Delta=0).\tag2
$$
Две матрицы эквивалентны тогда и только тогда, когда выполнены условия (*) и соответствующие сокращённые матрицы имеют один и тот же канонический вид. (Несколько иначе критерий эквивалентности сформулирован в упражнении 20.)
В самом деле, любую сокращённую матрицу можно преобразовать к каноническому виду так же, как раньше мы преобразовали матрицу $\colsep{2pt}{\begin{pmatrix}1&5\\2&7\end{pmatrix}}$ (см. рис. 9). Тот факт, что $r$ является инвариантом, вытекает из упражнений 14, 15.
Упражнение 14*. Пусть матрица $\colsep{2pt}{\begin{pmatrix}a&c\\b&d\end{pmatrix}}$ имеет канонический вид (1). Тогда внутри параллелограмма $OABC$, построенного на векторах $\overrightarrow{OA}=(a;b)$ и $\overrightarrow{OC}=(c;d)$, лежит $\Delta-1$ целых точек. Все эти точки $M_1$, $M_2$, $\ldots$, $M_{\Delta-1}$ могут быть получены при помощи векторных равенств:
$$
\overrightarrow{OM_j}=\left\{\dfrac j\Delta\right\}\overrightarrow{OC}+\left\{j\left(1-\dfrac r\Delta\right)\vphantom{\dfrac j\Delta}\right\}\overrightarrow{OA},
$$
где $\{x\}$ — дробная часть числа $x$.
Упражнение 15. Пусть $\gcd(a,b)=\gcd(c,d)=1$, $\Delta=|ad-bc|\ne0$. Тогда существует единственное $r$ такое, что $0\le r\lt\Delta$, $\gcd(r,\Delta)=1$ и оба числа $ra-c$, $rb-d$ делятся на $\Delta$, причём это $r$ сохраняется при преобразованиях $L$, $R$, $S$ матрицы $\colsep{2pt}{\begin{pmatrix}a&c\\b&d\end{pmatrix}}$.
Это упражнение удобно для конкретных вычислений числа $r$, если $\Delta$ невелико.
Упражнение 16. Какие матрицы среди следующих эквивалентны, а какие — нет:
$$
\def\p#1#2{\hphantom{#2}\mathllap{#1}}
\begin{gather*}
{\colsep{2pt}{\begin{pmatrix}5&1\\7&2\end{pmatrix}}},\enspace
{\colsep{2pt}{\begin{pmatrix}1&-5\\2&\hphantom-7\end{pmatrix}}},\enspace
{\colsep{2pt}{\begin{pmatrix}1&2\\3&9\end{pmatrix}}},\enspace
{\colsep{2pt}{\begin{pmatrix}1&3\\4&8\end{pmatrix}}},\enspace
{\colsep{2pt}{\begin{pmatrix}4&7\\5&8\end{pmatrix}}},\\
{\colsep{2pt}{\begin{pmatrix}\p6{17}&\p{14}{39}\\17&39\end{pmatrix}}},\enspace
{\colsep{2pt}{\begin{pmatrix}\p5{19}&\p{13}{50}\\19&50\end{pmatrix}}},\enspace
{\colsep{2pt}{\begin{pmatrix}\p{19}{79}&1\\79&4\end{pmatrix}}},\enspace
{\colsep{2pt}{\begin{pmatrix}39&60\\50&77\end{pmatrix}}}?
\end{gather*}
$$
Упражнение 17. Выше мы не рассматривали матрицы, у которых один из столбцов нулевой. В каком случае такие матрицы эквивалентны?
Упражнение 18. Докажите, что любые две матрицы, у которых $\Delta=1$, эквивалентны.
Упражнение 19*. Сколько существует всего классов неэквивалентных матриц с $\Delta=3$, $\Delta=4$, $\Delta=5$, $\Delta=10$, $\Delta=12$? Сколько среди них сокращённых? Нарисуйте для каждого класса матриц расположение узлов в соответствующем параллелограмме (как на рисунке 10).
Упражнение 20. Докажите, что для любой матрицы существует единственная эквивалентная ей матрица $\colsep{2pt}{\begin{pmatrix}k&l\\0&m\end{pmatrix}}$, где $k\ge0$, $m\ge0$, $l\ge0$ и $l\lt m$ при $m\ne0$.
Другой возможный подход к задачам 3 и 5 — выяснить, какие вообще преобразования целочисленной решётки можно получить композициями операций $L$, $R$, $S$ (подобно тому, как в задаче 2 мы выяснили, какие вообще сдвиги можно получить композициями сдвигов $\pm a$, $\pm b$). Оказывается, все эти преобразования решётки имеют вид $(x;y)\to(ax+by;cx+dy)$, где $a$, $b$, $c$, $d$ — целые числа и $|ad-bc|=1$. Но это уже — тема отдельной статьи, посвящённой линейной алгебре.
