Числовые головоломки

шero простого числа, откуда следует бесконечность множества простых чисел и, разумется, множество натуральных чисел. Вот остроимное доказательство этого факта. Пусть $p$ — простое число. Перменожим все простые числа до $p$, включая само $p$, и к этому произведению прибавим единицу. Получим число $2 \cdot 3 \cdot 5 \cdot 7 \cdot \dots \cdot p + 1$. Это число, большее $p$, будет или простым, или составным. Если оно простое, то тем самым доказано, что существует простое число, большее $p$. Если же оно состоит из простых чисел 2, 3, 5, …, $p$ оно не делится — при делении на эти числа в остатке получается 1. Значит, оно должно делиться на простое число, большее, чем $p$. Итак, и в этом случае мы должны признать, что существует простое число, большее $p$. Но это и означает, что не существует наиболее простого числа.

Сам термин «натуральное число» впервые был употреблен римским филиософом Боэцием (ок. 480—524), но стал общеупотребительным после того, как был включен французским математиком Д’Аlamбером (1717—1783) в «Энциклопедию».
В XIX веке математики

$$1 + 3 + 5 + \dots + (2n - 1) = n^2$$
$$1^2 + 3^2 + 5^2 + \dots + (2n - 1)^2 = \frac{1}{3} n (2n - 1)(2n + 1)$$
$$1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \dots + n (n + 1) = \frac{1}{3} n (n + 1)(n + 2)$$

Числовые головоломки

Кроссамбер
По горизонтали:
a) Число, цифры которого является последовательными и расположены в порядке возрастания; b) число, кратное 9; d) полный квадрат; e) число, кратное 36.
По вертикали:
a) Число, цифры которого является последовательными и расположены в порядке убывания; b) квадрат простого числа; c) полный куб; e) степени числа 2.

Н. К. Антонович
Одинаковые цифры при умножении
Может ли при переменении двух двух значных чисел получить четпрежзнаное число, все цифры которого одинаковы?

Ф. К. Кадиров
Одинаковые цифры при сложении
Может ли подобрать такое натуральное число $A$, а затем так переста-

вить в нем цифры, чтобы при сложении полученного числа с числом $A$ суммой оказалось число, записываемое 1985 девятками: 99…999?

М. Байрамов, десятиклассник из Баку

Арифметические ребцы

ЛЮБА
ЛЮБИТ
АРБУЗЫ

СПОРТ

• ПОРТ
  ОРТ
  РРРР

Н. К. Антонович

34

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

Не ясно, почему отсутствие разделения текста на отдельные слова каждая судье непредодолимым препятствием. На самом деле оно только увеличивает объем необходимого перебора. Манозль возвращает судьbe: «Ну, что же! Если имя Дакости упоминается, тогда, принимая одну другой каждую букву этих строк за первый из тех семи, что составляют его имя, мы в конце концов найдем его».

Вот он — прямой путь к решению задачи! Перебор не так уж велик. Текст состоит из 252 букв. Следовательно, необходимо перебрать максимум 246 вариантов. В один прекрасный момент, записав над фрагментом ИБНТФЕ слова ДАКОСТА, мы определяли бы последовательность цифр 5134325. Естественно предположить, что последняя цифра 5 — начало следующого периода:

ДАКОСТА
… 5 1 3 4 3 2 5 1 3 4 3 2 5 1 3 4 …
… Т Г О И БНТ Ф Е О И X …

Вместо ключа 432513 мы нашли его циклическую перестановку 513432, что ни в коей мере не мешает расшифровке текста.

И, наконец, обсуудим следующий вопрос. Мы имеем представление о содержании документа и поэтому смогли угадать слова, в него входящие. По этому слову и была проведена расшифровка. А как быть, когда содержание документа неизвестно?

Есть несколько путей. Можно как и раныше, пытается отладать какоеибудь слова (либо часть слова), входящие в документ. (В текстах часто встречаются слова «который», «тогда», «если», «что» и т. д.; присутствки «при», «пре», «под».) Такой поиск может значительно увеличить объем перебора, однako шансов на успех достагоно много. По-видимому, болеерациональный путем является проведение анализа частоты использования различных букв в криптографме. Но как же так?! Ведь Жаррикс прямо говорит, что если ключом к шифру служит число, такой путь неприменем: «Что же из этого следует? Что значение каждой буквы определяется случайно поставленной под ней цифрой, и буква в криптографме никака не обозначает одной и той же буквы текста.»

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

35

(i=1, 2, 3; k=0, 1, 2, …) буквы текста — соответствующее ей букву i-го круга.

Из самого процесса кодирования следует, что если разница между номерами мест, на которых стоит любые буквы текста, кратна 3, то при их кодировании используется одна и та же цифра. Поэтому утверждение Жаррикаса о том, что буква в криптографме никакого не обозначает одной и той же буквы текста — ошибочно.

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

Остается выяснить вопрос: как быть, когда неизвестно, из какого количества цифр состоит ключ? Здесь уже не обойтись без перебора. Сначала предполагаем, что ключ — двухначенное число, затем — трехзначное и т. д., — до тех пор, пока текст не будет расшифрован.

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

Весь текст криптографмы разбиваем на шесть наборов букв по правилам, описанному выше*), и подсчитываем, сколько раз буквы алфавита входят в каждый из наборов. Результаты подсчетов приведены в таблице 1.

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

Возьемем четыре наиболее употребительные буквы: A, E, И, O — и подсчитаем общее число их входений в первоначальный текст при различных величины сдигага от 0 до 9. Результаты приведены в таблице 2.

| № набора | Величина сдигага |
| :— | :— |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 5 | 1 | 1 | 9 | 13 | 1 | 6 | 4 | 7 | 6 |
| 2 | 6 | 2 | 2 | 19 | 3 | 4 | 9 | 5 | 4 | 5 |
| 3 | 8 | 8 | 11 | 3 | 5 | 12 | 11 | 5 | 5 | 5 |
| 4 | 5 | 4 | 6 | 3 | 8 | 15 | 1 | 4 | 6 | 8 |
| 5 | 6 | 17 | 3 | 7 | 6 | 1 | 9 | 7 | 2 | 8 |
| 6 | 9 | 4 | 6 | 12 | 3 | 10 | 7 | 8 | 7 | 4 |

Поскольку мы выбрали наиболее часто встречающиеся буквы, естественно предположить, что первая цифра ключа — 4, вторая — 3, четвертая — 5, пятая — 1, шестая — 3. Что касется третьей цифры, то ее следует выбирать из цифры 2, 5, 6. Окончательная расшифровка криптографмы теперь уже не представляется никакой трудности.

К нашим читателем
Продолжается подписка на журнал «Квант» на 1986 год. Индекс журнала в каталоге Союзечати 70465. Подписая цена на год 4 рублей 80 копеек, Подписа принимается без ограничений всем почтовыми отделениями в течение всего года.