Арифметические препятствия

Квант 1979, №3 с. 22, 23, 24, 25, 26, 27, 29, 30 Тег 9DYL

Во многих математических теории и прикладных задачах, а также в математических играх и головоломках возникают вопросы такого рода: можно ли перейти от одной позиции к другой с помощью некоторых «допустимых» операций (ходов)? Как найти нужную целочкухход, если она существует, или доказать, что переход невозможен? В этой статье мы разберем несколько задач такого типа. Их обединият еще и внешнее состояние: в каждой из них фигурируют целые числа, а «препятствия» переходам, как правило, имеют арфметические природу.

Примеры, с которых начинается обсуждение каждой задачи, волне доступны даже ученикам младших классов. Упражнения «созвездкой» и доказательства общих результатов требуют от читателя сервезных размышлений. Заканчивается статья трудными олимпидными задачими, последняя из которых применяет к неэлементарной, бурно развивающейся сейчас теории arфметических групп.

Задча о коне

Задча 1. Даны натуральные числа m и n. На одном из полей бесконечной шахматной точки фигуря, которая ходит «буквой Γ» на m полей в одном из направлений и на n в перепendlкулярном; называем ее {m; n}-конem. На какое поля ходи этом конь может попасть?

Объичный шахматный конь ({1; 2}-конь) может из любого начального поля O попасть на любое другое: за три хода он может попасть на соседнее с O поле, а также элементарными шагами можно, конецно, прийти куда угодно.

А вот {1; 3}-конь, несколько ходов которого показаны на рисунке 1, никак не может попасть на соседнее (по горизонтали) с начальным поле. На шахматной доске очень легко объяснить, что препятствует такому переходу: {1; 3}-конь всегда ходит по полям одного цвета. С другой стороны, нетрудно показать, что {1; 3}-конь может обойти все поля одного цвета: за три хода он может сливнуться по диагонали на соседнее поле того же цвета (рис. 1), а также элементарными шагами уже легко обойти все однозвесные поля.

Попробуйте решить задачу 1 для чисел a) 2 и 5; b) 10 и 25; г) 19 и 79.

Оказывается, {m; n}-конь может попасть на любое том случae, когда m и n имеют разную четность и их наиболее общий делитель равен 1.

Полный ответ к задаче 1 приведен в конце пункта 3 (упражнение 10). Сейчас мы займемся более простым вопросом. Результат, который мы получим, полезен и для задачи о коне, и для более серверных математических задач.

Рис. 1. {1; 3}-конь может попасть на соседнее (по диагонали) поле того же цвета; таким шагами он может обойти все однозвесные поля.

Представление НОД
З адач а 2. Даны намуральные числа a и b. За один ход разрезается прибавить к некоторому целому числу одно из чисел a, b или вычесть из него одно из этих чисел. Можно ли максим образом из числа 0 получить число c?

В этой задаче можноесто «позиций» — это множество Z всех целых точек числовой прямой.

Начнем с конкретного примера. Предположим, что у покупателя и кассира есть только купюры в 10 и 25 рублей, причем (чero не бывают в математических задачах!) в неограниченном количестве. Ясно, что покупатель может запланить кассиру c рублей в том и только том случае, когда c кратно 5.

Еще пример. Пусть на множество Z разрешены ходы ±19 и ±79. С помощью этих ходов можно получить любое целое число: их комбинация позволяет свиниться на расстояние 3, а затем и на расстояние 1 (рис. 2, a).

Более сложный пример: a=819, b=357. В этом случае тем же прием удается найти кратчайший сдигг — на 21 (рис. 3, a). Таким образом, здесь можно устроить переход на любое расстояние, кратное 21. С другой стороны, и a, и b делятся на 21, поэтому никакие другие переходы невозможны.

Заметим, что 21 — наиболее общий делитель чисел 819 и 357 (проверьте это!).

У разнение 1. a) Докажите, что если у покупателя и кассира есть (в неограниченном количестве) трешки и пятерки, то покупатель может запланить любое число рублей.

Можно ли перейти от 0 к 1000, если a=123, b=456? если a=589, b=1984?

b) Какие переходы возможны при a=18, b=81?

Теперь сформируем ответ к задаче 2 в общем виде. Пусть наиболее

ший общий делимель (НОД) чисел а и b равен d. Тогда переход от 0 к с возможен в том и molъко том слуае, коеда число с делимся на d. Попробуйте доказать это.

В несколько иной форме мы получим этот результат в следующем пункте.

У разженняя
2. Докажите, что ответ к задаче 2 не изменится, если число a разрешается только прибавлять, а b — только вычитать.
3. Можно ли на чашечных весах с помощью гирь 36 г и 60 г (эти грии имеются в неограниченном количестве, и их можно класть на обе чашки весов) отвечать a) 150 г; b) 132 г?

Алгоритм Евклида
В следующей задаче позициями будут пары целых чисел.

Задача 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ᵉ означает, что операция L продельвается k раз подряд). Собственно говоря, тот же спуск мы уже продельвали в соответствии примере к предыдущей задаче (рис. 2, a).

Спуск, начинающийся с пары (819; 357), сокращенно записан на рисунке 3, в запишите его подробно. Здесь пара (1; 2) (или 1; 0) не получается. И не удивительно — тому есть преяя тствие: все получаемые числа делятся на 21. В каком бы порядке мы ни применяли операции L, R, S, избавиться от этого преяятствия неудоступа, поскольку, как нетрудно доказать, эти операции сохраняют общие делители чисел на карточеке: НОД (x—y, x) = НОД (x+y, y) = НОД (x, y). Поэтому ответ от пары = (819; 357) к паре (1; 2) или обратно нельзя.

У разженне 4. Можно ли с помощью операций L, R, S перейти a) от пары (1; 10) к паре (5; 25)? 6) от (18; 81) к (36; 63)? в от (589; 1984) к (31; 1953)?

Теперь мы можем сформировать ответ на последний, общий вопрос задачи 3: пару (a; b) можно перевести в пару (p; q) в том и molъко в том слуае, коеда НОД (a; b) = НОД (p; q). Это условие не обходимо, поскольку как мы уже говорили, наш операция сохраняет НОД. Но оно также и достаточно: если НОД (a, b) = НОД (p, q) = d, то каждую из этих пар операции L, R, S можно привести к паре (d; 0); проделав с пус к от (a; b) к (d; 0) и затем подъем от (d; 0) к (p; q), мы получим целочкув от (a; b) к (p; q).

Рис. 5. Операциями L, R, S можно поменять знак у одного числа на карточке.

Покажем, почему от любой пары $(a; b)$ можно перейти к паре $(d; 0)$ . Заметим, что если один из элементов пары отрицательен, то его легко сделать положительным (рис. 5). А пару $(a; b)$ с натуральными и $b$ можно привести к паре $(d; 0)$ тем же способом, который мы применили в примерах: на каждом шаге (кроме перестановок-симметрий) больше элемент пары уменьшается до тех пор, пока мы не придем к финалу $\rightarrow (d; d) \rightarrow (0; d) \rightarrow (d; 0)$ .

Решая задачу 3, мы получили удобный способ отыскания наиболее общого делителя двух чисел: от пары $(a; b)$ , где $a > b > 0$ , переходим к паре $(b; r)$ , где $r$ — остаток от деления $a$ на $b$ , и повторяем эту операцию до тех пор, пока не получим пару $(d; 0)$ . Последний не равный нулю остаток $d$ и есть НОД $(a; b)$ (рис. 2, б, 3, б). Этот способ называется алгоритмом Евклида.

У праванения
5. Докажите, что из пары (1357; 2468) нельзя получить пару (1234; 5678); из пары (123; 457) нельзя получить (7890; 1979).

Приведите примеры, показывающие, что операция задачи 3 не перестановочные: $LS \neq SL, RS \neq SR$ (разумеется, $LR=RL$ ).
Найдите с помощью алгоритма Евклида НОД (589, 1984), НОД (123456789, 987654321).

Целочисленной решеткой $Z^2$ называется множество всех точек плоскости с целыми координатами.

Рис. 6. «Левый переок» $L(x; b) \rightarrow (x-b; b)$ , «правый переок» $R(x; b) \rightarrow (x+b; b)$ , «симметрия» $S(x; b) \rightarrow (b; x)$ — линейные преобразования плоскости, осуществляющие взаимно однозначные отображения целочисленной решетки $Z^2$ на себя.

Следующие упражнения и рисунок 6 проясляют геометрический смысл задачи 3:

Докажите, что если отрезок $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, \dots, a_n$ . Докажите, что целое число $c$ можно получить из 0 ходами $\pm a_1, \pm a_2, \dots, \pm a_n$ тогда и только тогда, когда $c$ делится на $HOД$ ( $a_1, a_2, \dots, a_n$ ).

10*. а) Пусть на плоскости $Oxy$ заданы $n$ векторов $v_1, v_2, \dots, v_n$ с целочисленными координатами. Докажите, что множество точки $D$ плоскости, в которых можно попасть из точки $O$ ходами $\pm v_1, \pm v_2, \dots, \pm v_n$ , представляет собой множество вершин некоторой косугульной решетки (так называется множество вершин параллелограммов, на которых два семейства равносторских параллельных прямых разрезают плоскость).

Пусть вместе с каждой вектором $v_i$ в семействе векторов $v_1, v_2, \dots, v_n$ имеется равный ему по длине и перpendикулярный. Тогда множество «достижимых» точки $D$ будет множество вершин некоторой квадратной решетки.

Теперь уже нетрудно найти ответ к задаче 1: пусть $m=dm_1, n=dn_1$ , где $d=HOД(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\sqrt{2}$ , повернуть на угол $45^\circ$ по отношению к линейным доки).

Некоторые итоги

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

1°. Чтобы доказать невозможность того или иного перехода, мы обнаружили некоторое решение — характеристку позиции, сохраняющийшую (как говорят, инвариантную) при всех допустимых ходах, но различную для начальной и конечной позиций; таким образом, доказательство невозможности того или иного перехода сводилось к отрицанию инварианта. Таким инвариантом в задаче o {1; 3}-коне является цвет поля, в задаче 2 — остаток от деления числа на $HOД(a, b)$ , в задаче 3 — НОД пары чисел на карточках. Подробнее об этом можно прочесть в «Кванте» 1974, № 2 (с. 26), 1976, № 2 (с. 32) и 1976, № 12 (с. 19).

2°. Чтобы построить целочкум переход на решетке, часто бывают полезно найти какой-то элементарный «ключевой» ход (или комбинацию ходов), либо свести до к какой-то простейшей кanonчесной позиции, — а затем уже формулировать общее правило (алгоритм) отискания переходов. Так, в задаче o {1; 3}-коне достаточно научиться делать ход по диагонали, в задаче 2 — сдвиг на $d=HOД(a, b)$ , в задаче 3 — «спуск» кanonчесной позиции (d; 0).

3°. Во всех рассмотренных показах переходы были обратили к позиции $A$ можно было перейти к позиции $B$ , то можно было вернуть и обратно — от $B$ к $A$ . В таких задачах все множество позиций разбивается на классы эквивалентности: внутри одного класса от каждой позиции можно перейти к любоЙ другой, а никакие переходы между позициями из различных классов неозможно.

Сейчас мы рассмотрим задачу, в которой такой обратимость сообжения $1^\circ$ и $2^\circ$ .

Избавление от двоеки

Задача 4. Три автората печатают на карточках пары натуральных чисел. Автоматы работыются следующим образом: первый авторат, прочитав карточку $(a; b)$ , выдает карточку $(a+1; b+1)$ ; второй авторат, прочитав карточку $(a; b)$ , выдает карточку $(a/2; b/2)$ (он работает только в том случае, когда она числа а и b четны); третьий авторат по двум карточкам $(a; b)$ и $(b; c)$ выдает карточку $(a; c)$ .

Пусть первоначально имеет карточка $c$ парой чисел (5; 19). Можно ли, используя автораты в

лобом порядке, получить карточку a) (1; 50)? б) (1; 100)?

в) Пусть первоначально имеется карточка (a; b), a < b, а мы хотим получить карточку (1; n). При каких п его можно сделать?

Эта задача предлагалась на XII Всеюозной математической оптимизации ученикам 8—10 классов*. Впрочем, даже пятиклассик хватит знаний, чтобы решать ее.

Обозначим операции, которые выполняют наши новые автоматы, соответствующего через I, H и T. На рисунке 7 показано, как из карточки (5; 19) получить «простейшую» карточку (1; 8) и затем — карточку (1; 50) (вместо «k раз применить операцию I» мы снова пишем I^k). Таким образом, в задаче a) ответ утеверил те льный.

А вот карточку (1; 100), про которую спрашивает в задаче 6), из карточки (5; 19) получить неудается. Препятствие можно обнаружить, вымательно изучив тот же рисунок 7: разность чисел на каждой карточке делится на 7. В каком бы порядке мы ни применяли автоматы, избавиться от этого свойства не удалось — его сохраняют операции I, H и T. (Для I это оченьindo. Для H: если a и b — четные и b—a делится на 7, то и b/2—a/2 делится на 7. Для T: если разности b—a и c—a делится на 7, то и c—a=(c-b)+(b—a) делится на 7.) Но разность 100—1=99 на 7 не делится, так что ответ к 6) отрицательный.

Уражнение 11. Можно ли, использую автоматы I, H и T, a) из карточки (3; 33) получить карточки (5; 29), (1; 101), (1; 1978)?

Из карточки (5; 29) получить (3; 33), (1; 100), (1; 1979)?

Сформируем теперь ответ на последний, общий вопрос в) задачи 4: из карточки (a; b), в котором b—a=2^md, где d>0 и нечетно, можно получить me и только me карточки (p; q), в которых разность p—q>0 делится на d. Таким образом, можно избавиться от всех двое в разложении b—a, но нечетный делитель разности b—a служит непреодолимым прействием.

*) См. также задачу М516 из Задачника «Кванта» («Квант», 1978, № 8).

Рис. 7. С помощью операций I^q (увеличение на q), H (деление пополам), T («транзитивный» переход) из 519 получаем 150

Рис. 8. Большое число b на карточке можно уменьшить (d=b—a; a>1 или a=1, b нечетно).

В самом деле, как мы уже говорили (для d=7), из карточки, у которых разность делится на нечетное число d, с помощью операций I, H, T получаются только карточки, обладающие тем же свойствам. С другой стороны, от карточки (a; b), где b—a=2^md (d нечетно), можно перейти к карточке (1; d+1). (Один шаг такого перехода показан на рисунке 8.) Получив карточку (1; d+1), легко изготовить любую карточку (1; kd+1) (как

Рис. 9. Приведение к канонческому виду. При всех преобразованиях $L, R, S$ сохраняется площадь параллелограмма и расположение узлов целочисленной решетки внутри него.

$\begin{pmatrix} 1 & 1 \\ 2 & 2 \end{pmatrix}$ получится матрица с одинаковыми столбцами $\begin{pmatrix} p & p \\ q & q \end{pmatrix}$ .

в) Матрицы $\begin{pmatrix} 1 & 5 \\ 2 & 7 \end{pmatrix}$ и $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ тоже не эквивалентны; тут возникает новое препятствие: величина

$\Delta = \Delta \begin{pmatrix} a & c \\ b & d \end{pmatrix} = |ad - bc|.$

Она сохраняется при всех преобразованиях $L, R, S$ матрицы $\begin{pmatrix} a & c \\ b & d \end{pmatrix}$ . Проверим это для $L: (a-b)d-b(c-d) = ad-bc$ . (Для $R$ и $S$ проверите проверку сам.) Поскольку $\Delta \begin{pmatrix} 1 & 5 \\ 2 & 7 \end{pmatrix} = 3,$ а $\Delta \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = 1$ , эти матрицы не эквивалентны. Заметим, что

$\Delta \begin{pmatrix} p & p \\ q & q \end{pmatrix} = 0.$

Величина $ad-bc$ очень часто возникает в разных задачах про матрицы и называется определенем матрицы $\begin{pmatrix} a & c \\ b & d \end{pmatrix}$ .

г) Матрицы $\begin{pmatrix} 1 & 5 \\ 2 & 7 \end{pmatrix}$ и $\begin{pmatrix} 1 & 2 \\ 0 & 3 \end{pmatrix}$ эквивалентны: целочка преобразования, приводящих первый вектор $\begin{pmatrix} 1 \\ 2 \end{pmatrix}$ к канонческому виду $\begin{pmatrix} 1 \\ 0 \end{pmatrix}$ , и небольшие дополнительные ихшренения приводят к целии (рис. 9). На рисунке 9 хорошо виден и наш инвариант $\Delta$ : это — плошадь параллелограмма, построенного на векторах $\begin{pmatrix} a \\ b \end{pmatrix}$ и $\begin{pmatrix} c \\ d \end{pmatrix}$ .

Рис. 10. В параллелограммах для матрицы $(\begin{matrix} 1 & 1 \\ 0 & 3 \end{matrix})$ и $(\begin{matrix} 1 & 2 \\ 0 & 3 \end{matrix})$ расположение узлов целочисленной решетки различно.

Осталось еще выяснить, д) эквивалентны ли матрицы $(\begin{matrix} 1 & 1 \\ 0 & 3 \end{matrix})$ и $(\begin{matrix} 1 & 2 \\ 0 & 3 \end{matrix})$ . Оказывается, не т, хотя указывать прейстствие здесь не так просто. Его геометрический смысл ясен из рисунков 9 и 10.

Теперь мы можем дать ответ на общий вопрос задачи 5. Любую сокращенную матрицу операции $L, R, S$ можно преобразовать к канонческому виду

$\begin{pmatrix} 1 & r \\ 0 & \Delta \end{pmatrix}, \quad \text{где } 0 \leq r < \Delta,$

(1)

$\text{НОД}(r, \Delta) = 1,$

или

$\begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix} \quad (\text{если } \Delta = 0).$

Две матрицы эквивалентны модели и молко модели, когда выполенены условия (*) и соответствующие сокращенные матрицы имеют один и тот же канонческий вид. (Несколько иначе критерий эквивалентности формулирован в упражнения 20.)

В самом деле, любую сокращенную матрицу можно преобразовать к канонческому виду так же, как равше мы преобразовали матрицу $(\begin{matrix} 1 & 5 \\ 2 & 7 \end{matrix})$ (см. рис. 9). Тот факт, что $r$ является инвариантом, вытекает из упражнения 14, 15.

Уражнения

14*. Пусть матрица $\begin{pmatrix} a & c \\ b & d \end{pmatrix}$ имеет канонческий вид (1). Тогда внутри параллелограмма $OABC$ , построенного на векторах $\overrightarrow{OA} = (a; b)$ и $\overrightarrow{OC} = (c; d)$ , лежит $\Delta-1$ целая точка. Все эти точки $M_1, M_2, \dots, M_{\Delta-1}$ могут быть получены при помощи векторных равенств:

$\overrightarrow{OM}_j = \{j/\Delta\} \overrightarrow{OC} + \{j(1-r/\Delta)\} \overrightarrow{OA},$

где $\{x\}$ — дробная часть числа $x$ .

Пусть $\text{НОД}(a, b) = \text{НОД}(c, d) = 1, \Delta = |ad-bc| \neq 0$ . Тогда существует единственное $r$ такое, что $0 \leq r < \Delta$ , $\text{НОД}(r, \Delta) = 1$ и она числа $ra-c, rb-d$ делятся на $\Delta$ , причем это $r$ сохраняет при преобразовании $L, R, S$ матрицы $(\begin{pmatrix} a & c \\ b & d \end{pmatrix})$ .

Это упражнение удобно для конкретных вычислений числа $r$ , если $\Delta$ не велико.

Какие матрицы среды следующих эквивалентны, а какие — нет:

$\begin{pmatrix} 5 & 1 \\ 7 & 2 \end{pmatrix}, \quad \begin{pmatrix} 1 & -5 \\ 2 & 7 \end{pmatrix}, \quad \begin{pmatrix} 1 & 3 \\ 3 & 9 \end{pmatrix}, \quad \begin{pmatrix} 4 & 7 \\ 5 & 8 \end{pmatrix},$

$\begin{pmatrix} 6 & 14 \\ 17 & 39 \end{pmatrix}, \quad \begin{pmatrix} 5 & 13 \\ 19 & 50 \end{pmatrix}, \quad \begin{pmatrix} 19 & 1 \\ 79 & 4 \end{pmatrix}, \quad \begin{pmatrix} 39 & 60 \\ 50 & 77 \end{pmatrix}?$

Выше мы не рассматривали матрицы, у которых один из столбцов нулевой. В каком случае матрицы эквивалентны?
Докажите, что любые матрицы, у которых $\Delta=1$ , эквивалентны.

19*. Сколько существует все классов нееквивалентных матриц с $\Delta=3, \Delta=4, \Delta=5, \Delta=10, \Delta=12$ ? Сколько средних сокращенных? Нарисуйте для каждой класса матрицы расположение узлов в соответствии со параллелограмме (как на рисунке 10).

Докажите, что для любой матрицы существенная эквивалентная ей матрица $(\begin{pmatrix} k & l \\ 0 & m \end{pmatrix})$ , где $k \geq 0, m \geq 0, l \geq 0$ и $l < m$ при $m \neq 0$ .

Другой возможный подход к задачам 3 и 5 — выяснить, какое вообще преобразование целочисленной решетки можно получить композициями операций $L, R, S$ (подобно тому, как в задаче 2 мы выяснили, какое вообще сdwги можно получить композициями сdwгов ±a, ±b). Оказывется, все эти преобразования решетки имеют вид $(x; y) \rightarrow (ax+by; cx+dy)$ , где $a, b, c, d$ — целые числа и $|ad-bc|=1$ . Но это уже — тема отдельной статьи, посвященной линейной алгебре.