Теория стабилизаторов

Данная статья не имеет существенного прикладного или теоретического значения, но с её помощью Вы можете почувствовать, чем является та или иная математическая теория. Речь пойдёт о небольшом объекте высшей арифметики, который сподвигнет нас ввести некоторые определения, доказать ряд лемм и теорем, выдвинуть гипотезы, в общем — мы проделаем всё то, что обычно и делается в математической теории, не выходя при этом за рамки одной статьи (согласитесь, неплохая поучительная задумка).

P.S. Ещё мы вспомним о признаках деления чисел на 2, 3, 4, 7, 8, 9 и 11.

Определения. Виновниками торжества будут такие натуральные числа (натуральные числа — 1, 2, 3, …), которые состоят из одинаковых цифр— например, 222, 77777, 4444 и т.д. Важно подчеркнуть, что нам нужны не просто периодические числа (какими могли бы быть 121212 или 567567), а именно те из них, в записи которых используется лишь одна цифра, а подходящих цифр (отличных от нуля), как известно, 9 (в десятичной системе счисления). Итак, числа вида 3333, 555555, 22 и др. мы будем называть стабильными, и это первое определение нашей теории. Общности ради стабильными будут считаться и однозначные числа — 1, 2, …, 9. Стабилизатором натурального числа a будем называть такое натуральное число b, что найдётся неотрицательное целое (возможно — 0) n, при котором число a+bn — стабильное. В этом случае мы будем говорить, что b стабилизирует а, называя подходящее n — временем стабилизации. Так, 12 стабилизирует 63, поскольку 63+12∙3 = 99.

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

Гипотеза 1. Любое натуральное число является тотальным стабилизатором.

Так, можно написать программное обеспечение, которое в качестве a и b использует числа 1, 2, …, 20. Для каждого из значений b мы будем варьировать значение n от 1 до 100000, проверяя является ли b стабилизатором каждого из a. Полученные таким образом результаты представлены в Таблице 1.

Таблица 1. Экспериментальные данные о стабилизации в ряду 1..20

Здесь, например, в ячейке, соответствующей a=18 и b =7, указано “10,8” — это говорит о том, что 7 стабилизирует 18 за минимальное время 10, причём полученное стабильное число состоит из восьмёрок: 18+7∙10 = 88. Мы действительно можем видеть, что почти все рассмотренные b стабилизируют все рассмотренные а. Но, кто знает, может, некоторые ячейки остались пустыми, поскольку времени в 100000 было мало для стабилизации в соответствующих парах (a,b)? Обратите внимание на выделенную в красный контур пару (14,14) — соответствующие числа стабилизируют друг друга аж при n = 15872, т.е. при 10000 итерациях данная ячейка пустовала бы. Неужели Гипотеза 1 верна (и почему мы не слыхали подобных утверждений прежде)? Не будем томить друг друга и, обратив внимание на ячейки, выделенные жёлтым цветом, докажем первую нашу теорему, ставящую всё на свои места.

Теорема 1. Числа, оканчивающиеся на 0, не стабилизируют числа, оканчивающиеся на 0.

Доказательство. Предположим противное, рассмотрев пару (a,b), в которой a = a(1)a(2)…0 (здесь и далее a(1)a(2)… и др. — не произведение чисел, а последовательность цифр, из которых состоит число)и b = b(1)b(2)…0. Пусть b стабилизирует a за время n, т.е. a(1)a(2)…0+b(1)b(2)…0∙n — стабильное число. С другой стороны a(1)a(2)…0+b(1)b(2)…0∙n = 10∙(a(1)a(2)+ b(1)b(2)∙n), т.е. оканчивается на 0 и стабильным быть не может. Полученное противоречие завершает доказательство. ∎

Ладно, пусть Гипотеза 1 неверна, но всё же — вдруг для тех пустых ячеек, которые окрашены в голубой, а не жёлтый цвет, стабилизация выполняется? Иными словами, нам хочется констатировать, что Гипотеза 1 “почти всегда” верна, за исключением тех случаев, когда оба числа оканчиваются на 0.

Гипотеза 2. Если хотя бы одно из чисел a, b не оканчивается на 0, то b стабилизирует a.

Увы, но и здесь нам предстоит разочароваться — перейдём к доказательству Теоремы 2, но перед этим, как и было обещано, вспомним о признаке деления числа на 11. Звучит данный признак просто — пусть наше число состоит из цифр a(1)a(2)a(3)a(4)…, тогда данное число делится на 11 в том и только том случае, если на 11 делится a(1)-a(2)+a(3)-a(4)+… В качестве примера рассмотрим 121, имеем 1–2+1 = 0, 0 делится на 11, значит, 121 делится на 11. Наоборот, 3561 даёт 3–5+6–1 = 3, 3 не делится на 11, значит, 3561 — не делится на 11.

Теорема 2. 11 не стабилизирует 10.

Доказательство. Предположим противное, т.е. пусть имеется такое n, что 10+11∙n = ccc. Отсюда 11∙n =cc…(c-1)c, т.е. cc…(c-1)c делится на 11. Пусть количество цифр с, стоящих перед (с-1) — чётное, тогда имеем: с-с+с-…+(с-1)-с = 0+(с-1)-с = -1. Поскольку -1 не делится на 11, то cc…(c-1)c тоже не делится на 11, что противоречит обозначенному. Значит, возможен лишь второй случай, когда количество цифр с, стоящих перед (с-1) — нечётное. Здесь мы получим: с-с+…-с+с-(с-1)+с = 0+с-(с-1)+с = с+1. Поскольку с — одно из чисел 1, 2, …, 9, то с+1 не может делиться на 11, и опять cc…(c-1)c — не делится на 11. Вновь полученное противоречие, говорит о том, что сделанное нами предположение ложно, т.е. 11 не может стабилизировать 10. ∎

Ну, какая-то плохая теория получается — что ни предположение, то “провал”. Однако не спешите огорчаться, поскольку следующей гипотезе суждено оказаться верной — именно её доказательству и посвящена основная часть нашей статьи.

Гипотеза 3. Числа 1, 2, …, 9 являются тотальными стабилизаторами.

Доказывать Гипотезу 3 мы будем частями, если угодно — леммами, в каждой из которых будут отдельно рассмотрены случаи для 1, 2, …, 9, что в результате и позволит говорить об утверждении как о теореме.

Самый простой случай, когда рассматривается 1— понятно, что, постепенно прибавляя 1 к любому a, мы рано или поздно застабилизируем a, например, до 11…1.

Казалось бы, далее надо последовательно рассматривать случаи 2, 3 и т.д. Однако мы поступим иначе, обратив внимание на утверждение, которое настолько просто, что называть его теоремой некрасиво. Напомним, что число с называется делителем числа b, если b — делится на c, т.е. существует такое d, при котором b = сd.

Утверждение 1. Если число b стабилизирует a и делится на с, то c также стабилизирует а.

Доказательство. Пусть a+bn — стабильное, тогда, если b = сd, то данное стабильное число может быть записано как a+(сd)∙n или как a+с∙(dn). Значит, с также стабилизирует а. ∎

Таким образом, ввиду Утверждения 1, нам выгодно сперва доказать то, что 6 является тотальным стабилизатором, откуда будет следовать, что тотальными стабилизаторами являются 2 и 3, на которые делится 6. Прежде чем перейти к доказательству соответствующей леммы, напомним об элементарных признаках делимости на 2, 3 и 9 . Итак, число делится на 2 в том и только том случае, если последняя его цифра чётная, например, 126 делится на 2 (6 — чётное), 123 не делится на 2 (3 — нечётное). Далее — число делится на 3 (9) в том и только том случае, если сумма его цифр делится на 3 (9). Например, 2568 делится на 3, так как 2+5+6+8 = 21 делится на 3. Число 257 не делится на 9 — 2+5+7 = 14 не делится на 9.

Лемма 1. Число 6 является тотальным стабилизатором.

Доказательство. Пусть a = a(1)a(2)…a(k) и x— минимальное число, такое что 3∙x+1 > k. Подберём далее такое число y, чтобы a+6∙y было равно (3∙x+1)-значному числу вида 11…1z, где окончание z равно какому-то из чисел 1, 2, …, 6 (отметим, что этого всегда можно добиться). Если z = 1, то 6 стабилизирует а. В других случаях — составим (3∙x+1)-значное число с вида (z-1)(z-1)…(z-1)0. Очевидно, прибавляя с к 11…1z, мы получим стабильное число s= zzz, содержащее 3∙x+1 цифр. Видим, что в с содержится 3∙x цифр (z-1), откуда сумма цифр равна 3∙x∙(z-1) и делится на 3. Значит, само с делится на 3. Видим также, что с оканчивается на 0, т.е. является чётным. Итак, с делится на 3 и на 2, значит, оно делится и на 3∙2 = 6, т.е. с = 6∙t. Таким образом, имеем a+6∙y+6∙t = s, где s — стабильно. Отсюда получаем, что a+6∙(y+t) = a+6∙w — стабильное число, то есть 6 стабилизирует а.

Доказательство для 9 осуществляется аналогичным образом, с той лишь разницей, что мы исходим из (9∙x+1)-значного числа 11…1z. Перейдём к случаям с 4 и 8, однако теперь нам не удастся воспользоваться прежним подходом (доказав для 8, автоматически получить утверждение для 4) — доказательство для 8 будет опираться на доказательство для 4. Нам понадобятся признаки делимости на 4 и 8. Известно, что если число х содержит хотя бы 2 знака, то оно делится на 4 в том и только том случае, если на 4 делится число, образованное последними 2 знаками х. Так, 544 делится на 4, так как 44 делится на 4 (соответственно, 546 — уже не делится на 4). Аналогичный признак справедлив для 8, с той лишь разницей, что рассматриваются последние 3 цифры. Мы также обратимся к ещё одному утверждению.

Утверждение 2. Число вида ck стабилизируется числом с, если с = 1, 2, …, 9.

Доказательство. Положим а = c∙k = a(1)a(2)…a(n), рассмотрев (n+1)-значное число ccc. Имеем: cc..cck = c∙(11…1-k) = cl, откуда a+cl = ccc. ∎

Лемма 2. Число 4 является тотальным стабилизатором.

Доказательство. Отметим, во-первых, что любое число представимо в виде 4∙k, 4∙k+1, 4∙k+2, либо 4∙k+3, в связи с чем возникает 4 возможности для а = a(1)a(2)…a(n):

a = 4∙k. Числа данного вида стабилизируются четвёркой — следствие Утверждения 2.

a = 4∙k+1 (2, 3). Рассмотрим (n+1)-значное число 33…3 = 33…32+1 (22…2 = 22…20+2, 55…5 = 55…52+3) . Так как 32 (20, 52) делится на 4, то 33…32 (22…20, 55…52) делится на 4, т.е. имеет вид 4∙l. Следовательно, 33…3 =4∙l+1 (22…2 =4∙l+2, 55…5 =4∙l+3). Отсюда 33…3–(4∙k+1) = 4∙l+1–4∙k–1 = 4∙(lk) = 4∙m (22…2–(4∙k+2) = 4∙l+2–4∙k–2 = 4∙(lk) = 4∙m, 55…5–(4∙k+3) = 4∙l+3–4∙k–3 = 4∙(lk) = 4∙m). Значит, a+4∙m = 33…3 (22…2, 55…5). ∎

При доказательстве следующей леммы мы поступим похожим образом, а именно — будем исходить из того, что число a должно иметь одну из 8 форм: 8∙k, 8∙k+1, …, 8∙k+7. Результат в случае a = 8∙k вновь следует из Утверждения 2, а случаи 8∙k+1 (2, 3, 4, 7) разбираются так же, как при доказательстве во втором пункте Леммы 2. Так, например, при a = 8∙k+1 рассматривается (n+2)-значное число 77…7, равное 77…76+1. Так как 776 делится на 8, то и 77…76 делится на 8, т.е. имеет вид 8∙l. Значит, 77…7 =8∙l+1, откуда 77…7–(8∙k+1) = 8∙l+1–4∙k–1 = 8∙(lk) = 8∙m. Отсюда a+8∙m = 77…7. При остатках 2, 3, 4, 7 число a будет стабилизироваться соответственно до 66…6, 55…5, 44…4, 99…9. Однако проделанный приём не подойдёт для случаев 8∙k+5 и 8∙k+6, поскольку ни одно из подходящих чисел 550, 772, 994 (для 5) и 660, 882 (для 6) не делится на 8. Здесь нам потребуется другой подход.

Лемма 3. Число 8 является тотальным стабилизатором.

Доказательство. Вновь представим а в виде a(1)a(2)…a(n), начав с более короткого случая:

a = 8∙k+6. Имеем: a = 4∙2∙k+4+2 = 4∙(2∙k+1)+2 = 4∙l+2. Обращаясь к доказательству Леммы 2, получаем: a+4∙m = 22…2 (здесь 22…2 также (n+1)-значное число). Если m — чётное (2∙x), то 8 стабилизирует a: a+4∙m = a+4∙2∙x = a+8∙x = 22…2. Если m — нечётное (2∙x+1), то 8∙k+6+4∙(2∙x+1) = 8∙k+8∙x+8+2 = 8∙(k+x+1)+2 = 8∙y+2 = 22…2, откуда 22…20 делится на 8. Получили противоречие, так как ни 20 (если n = 1), ни 220 (признак делимости при n > 1) не делятся на 8.

a = 8∙k+5. Имеем: a = 4∙2∙k+4+1 = 4∙(2∙k+1)+1 = 4∙l+1. Обращаясь к доказательству Леммы 2, получаем: a+4∙m = 33…3. Если m — чётное, то 8 стабилизирует a: a+4∙m = a+4∙2∙x = a+8∙x = 33…3. Если m — нечётное, то 8∙k+5+4∙(2∙x+1) = 8∙(k+x+1)+1 = 8∙y+1 = 33…3. Отсюда 33…32 делится на 8, что возможно лишь в том случае, если 33…32 = 32 (поскольку 332 не делится на 8). Следовательно, y = 4, откуда k принимает одно из значений 0, 1, 2, 3. Отсюда значение a равно 5, 13, 21, либо 29, а каждое из этих чисел можно стабилизировать 8: 5+8∙9 = 13+8∙8 = 21+8∙7 = 29+8∙6 = 77. ∎

Перед нами остаются два простых числа (натуральное число, большее 1, называется простым, если оно делится только на 1 и себя, например, 11, 13, 29 и др.) — 5 и 7. Данные числа не были делителями уже рассмотренных чисел (1, 2, 3, 4, 6, 8, 9), значит, придётся придумывать новые приёмы доказательств (такова участь математика, печальная или радостная — решать Вам). Начнём с простого (Вам понравится).

Лемма 4. Число 5 является тотальным стабилизатором.

Доказательство. Рассмотрим два случая.

Число a не оканчивается на 0. Отметим, что, если a = a(1)a(2)…a(n), то, прибавляя постепенно к a число 10, мы не будем менять последнего знака, a(n), в то время как каждый раз число, полученное отбрасыванием a(n), будет на 1 больше предыдущего такого числа. Рассмотрим в качестве примера результаты последовательного прибавления 10 к 73 — 83, 93, 103, 113, 123 и т.д. Мы видим, что последняя цифра остаётся неизменной, в то время как цифры, отличные от неё, образуют постепенно увеличивающиеся на 1 числа — 7, 8, 9, 10, 11, 12. Исходя из этого, последовательное прибавление 10 к a однажды приведёт к тому, что (n-1)-значное число a(1)a(2)…a(n-1), стоящее перед a(n) в записи а, увеличится до n-значного числа вида a(n)a(n)…a(n) (здесь важно, что a(n) отлично от 0). Таким образом, само а преобразуется до (n+1)-значного числа a(n)a(n)…a(n). Иными словами, существует такое k, что: a+10∙k = a(n)a(n)…a(n), где а(n) — последняя цифра а. С другой стороны, a+10∙k = a+5∙2∙k, значит, 5 стабилизирует а.

Пусть теперь число а оканчивается на 0, т.е. равно a(1)a(2)…a(n-1)0. Тогда, как это следует из предыдущего пункта, число а+5, равное a(1)a(2)…a(n-1)5, стабилизируется пятёркой, т.е. найдётся k, такое что (а+5)+5∙k — стабильное. Но (а+5)+5∙k = a+5∙(k+1) = a+5∙l, значит, пятёрка стабилизирует и а. ∎

Далее нами будет использован приём доказательства по индукции, который (если Вы не знаете) основан на следующем простом принципе. Положим, нам надо доказать, что каким-то свойством обладает каждый элемент бесконечного счётного множества (т.е. такого бесконечного множества, элементы которого можно занумеровать — 1, 2, 3, ...). Доказательство в этом случае выполняется в 2 шага. На первом шаге мы доказываем справедливость утверждения для 1-го элемента множества, т.е. наличие у 1-го элемента интересующего нас свойства. На втором шаге — доказываем то, что, если некоторый элемент с номером k обладает интересующим свойством, то данным свойством должен обладать и следующий элемент, с номером k+1. Разумеется, два этих шага в доказательстве гарантируют, что все элементы множества будут обладать нужным свойством. Непосредственно применим данный метод, обратившись к следующему утверждению.

Утверждение 3. Пусть с = 1, 2, …, 9, тогда (6∙k+1)-значное число С вида ссс0 делится на 7 (k — натуральное).

Доказательство. Пусть k = 1. Тогда С = 1111110, 2222220, …, 9999990. Убеждаемся, что каждое из этих чисел делится на 7. Пусть теперь утверждение верно для какого-то k — посмотрим, будет ли оно верным для k+1. Рассмотрим (6∙(k+1)+1)-, т.е. (6∙k+7)-значное число C* = ссс0 = А∙10000000+сссссс0 = А0∙1000000+сссссс0, где A является (6∙k)-значным ссс. Если наше утверждение верно для k, то А0 делится на 7 (равно некоторому 7∙l). С другой стороны, мы проверяли, что сссссс0 делится на 7 (7∙m), откуда C* = 7∙l∙1000000+7∙m. Таким образом, число С*, соответствующее случаю k+1, также делится на 7. ∎

Перед тем, как перейти к доказательству заключительной леммы, напомним о признаке делимости числа на 7: число делится на 7 в том и только том случае, если на 7 делится разница данного числа, записанного без последнего знака, и удвоенного значения этого знака. Например, 364 делится на 7, поскольку 36–2∙4 = 28 делится на 7.

Лемма 5. Число 7 является тотальным стабилизатором.

Доказательство. Вновь рассмотрим все формы, которыми может обладать число а, которое надо застабилизировать:

a = 7∙k. Числа данного вида стабилизируются семёркой — следствие Утверждения 2.

a = 7∙k+1 (2, 3, 4). Рассмотрим (6∙l+2)-значное число c, равное 22…21 (44…42, 66…63, 88…84), где l — натуральное. Вычитая из числа, образованного первыми 6∙l+1 цифрами c, удвоенную последнюю цифру, получим число, делящееся на 7 (Утверждение 3), откуда по признаку делимости — само с делится на 7. Подберём минимальное l, такое что 7∙k < с = 7∙m. Имеем: 7∙m-7∙k = 7∙(m-k) = 7∙n, откуда следует, что 7∙k+7∙n = 22…21 (44…42, 66…63, 88…84). Таким образом, 7∙k+1 (2, 3, 4) + 7∙n = 22…22 (44…44, 66…66, 88…88).

a = 7∙k+5 (6). Используя индукцию так же, как это делалось при доказательстве Утверждения 3, докажем, что (6∙l+2)-значное число 33…328 (55…549) делится на 7,где l — натуральное. Обозначим данное число как с. Подберём минимальное l, такое что 7∙k < с = 7∙m. Имеем: 7∙m-7∙k = 7∙(m-k) = 7∙n, откуда 7∙k+7∙n = 33…328 (55…549). Таким образом, 7∙k+5 (6) + 7∙n = 33…3 (55…5). ∎

Леммы 1–5 в совокупности с проделанными рассуждениями приводят нас к основной теореме данной статьи.

Теорема 3. Числа 1, 2, …, 9 являются тотальными стабилизаторами.

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

Гипотеза 4. В следующих парах первое число не стабилизируется вторым: (16,16), (17,17), (19,19), (16,20), (20,12), (20,14), (20,16), (20,18).

Дополнение. Отдельным предметом исследования является изучение стабильности как отношения на множестве натуральных чисел. Напомним, что отношением на некотором множестве А является подмножество множества всевозможных пар элементов, взятых из А. Важнейшими свойствами отношений являются рефлексивность, симметричность и транзитивность. Говорят, что отношение рефлексивно, если в него входят все пары вида (a,a), в которых а — произвольный элемент множества А (где и задано отношение). Отношение называют симметричным в том случае, если наряду с парой вида (a,b), входящей в него, оно непременно будет содержать и пару (b,a). Наконец, отношение называется транзитивным, если при наличии в нём пар (a,b) и (b,c) оно всегда будет содержать и пару вида (a,с). Если взять в качестве исходного множества натуральные числа и задать на нём отношение “больше”, то, например, пара (1,1) не войдёт в данное отношение, ведь неверно, что 1 > 1. Значит, отношение “больше”, заданное на натуральных числах, не является рефлексивным. Далее видим, что в это отношение входит пара (17,3), но не входит (3,17). Значит, наше отношение не является симметричным. Однако оно транзитивно — рассмотрим, например, пары (13,4) и (4,1), которые входят в него, разумеется, и (13,1) будет в нём содержаться (ведь 13 > 1). Примером рефлексивного, симметричного и нетранзитивного отношения является знакомство, заданное на некотором множестве людей — подумайте, почему.

Что же можно сказать об отношении стабильности среди натуральных чисел? Во-первых, оно не является рефлексивным. Действительно, согласно Теореме 1, 10 не стабилизирует 10, значит пара (10,10) не будет входить в отношение. Далее, понятно, что 10 стабилизирует 11 (11+10∙0 = 11), однако, согласно Теореме 2, 11 не стабилизирует 10. Таким образом, в наше отношение входит пара (11,10), но не входит (10,11) — значит, отношение не является симметричным. Наконец, нетрудно убедиться, что наше отношение также не является транзитивным — 11 стабилизирует 5, 5 стабилизирует 10 (Таблица 1), но 11 не стабилизирует 10.