стр. 1
(всего 2)

СОДЕРЖАНИЕ

>>

Н а у ч н о - р е д а к ц и о н н ы й с о в е т с е р и и:
В. В. Прасолов, А. Б. Сосинский (гл. ред.),
А. В. Спивак, В. М. Тихомиров, И. В. Ященко.



Серия основана в 1999 году.
Библиотека
<Математическое просвещение>
Выпуск 29




С. Б. Гашков



СИСТЕМЫ СЧИСЛЕНИЯ
И ИХ ПРИМЕНЕНИЕ




Издательство Московского центра
непрерывного математического образования
Москва • 2004
УДК 511.1
ББК 22.130
Г12

Аннотация
Различные системы счисления используются всегда, когда
появляется потребность в числовых расчётах, начиная с вычи-
слений младшеклассника, выполняемых карандашом на бумаге,
кончая вычислениями, выполняемыми на суперкомпьютерах.
В книжке кратко изложены и занимательно описаны не-
которые из наиболее популярных систем счисления, история их
возникновения, а также их применения, как старые, так и но-
вые, как забавные, так и серьёзные.
?
Большая её часть доступна школьникам 7—8 классов,
но и опытный читатель может найти в ней кое-что новое для себя.
Текст книжки написан на основе лекций, прочитанных
автором в школе им. А. Н. Колмогорова при МГУ и на Малом
мехмате МГУ.
Книжка рассчитана на широкий круг читателей, интересу-
ющихся математикой: школьников, учителей.


Издание осуществлено при поддержке
Московской городской Думы
и Департамента образования г. Москвы.


ISBN 5-94057-146-8 © Гашков С. Б., 2004.
© МЦНМО, 2004.


Сергей Борисович Гашков.
Системы счисления и их применение.
(Серия: <Библиотека ,,Математическое просвещение“>).
М.: МЦНМО, 2004. — 52 с.: ил.
Редакторы Е. В. Корицкая, Ю. Г. Кудряшов.
Художник Т. И. Котова.
Техн. редактор М. Ю. Панов. Корректор Т. Л. Коробкова.

Лицензия ИД № 01335 от 24/III 2000 года. Подписано к печати 25/II 2004 года.
Формат бумаги 60?88 116 . Офсетная бумага № 1. Офсетная печать. Физ. печ. л. 3,25.
/
Усл. печ. л. 3,18. Уч.-изд. л. 3,62. Тираж 5000 экз. Заказ 6709.

Книга соответствует гигиеническим требованиям к учебным изданиям для обще-
го и начального профессионального образования (заключение государственной са-
нитарно-эпидемиологической службы Российской Федерации № 77.99.02.953.Д.
002797.04.03 от 18/IV 2003 года).

Издательство Московского центра непрерывного математического образования.
119002, Москва, Г-2, Бол. Власьевский пер., 11. Тел. 241 72 85, 241 05 00.

Отпечатано с готовых диапозитивов
в ФГУП <Производственно-издательский комбинат ВИНИТИ>.
140010, г. Люберцы Московской обл., Октябрьский пр-т, 403. Тел. 554 21 86.
§ 1. ДЕНЬГИ В КОНВЕРТАХ И ЗЁРНА НА ШАХМАТНОЙ ДОСКЕ
Представьте себе, дорогой читатель, что вы банкир, занимаю-
щийся отмыванием грязных денег, и завтра ждёте важного клиен-
та, которому вы должны выдать круглую или не очень круглую,
но заранее вам неизвестную сумму от 1 до 1 000 000 000 у. е. Что-
бы не пачкать руки о грязные деньги, вы заранее дали указание
своим кассирам заготовить некоторое количество конвертов с день-
гами, на которых написаны содержащиеся в них суммы, и собира-
етесь просто отдать клиенту один или несколько конвертов, в ко-
торых и будет содержаться требуемая им сумма. Какое наимень-
шее количество конвертов необходимо иметь?
Конечно, можно просто заготовить конверты со всеми суммами
от 1 до 1 000 000 000. Но где взять столько денег на конверты?
1. А какова будет в этом случае полная сумма во всех конвер-
тах? Попробуйте оценить также массу бумаги, предполагая, что
использованы не более чем сотенные купюры*).
Есть более рациональный подход к нашему делу. Надо положить
в первый конверт 1 у. е., а в каждый следующий класть вдвое боль-
шую сумму, чем в предыдущий. Тогда, например, в 5-м конверте
будет 16 у. е., в 10-м — 512 у. е., в 11-м — 1024 у. е., в 21-м —
10242 =1 048 576 у. е., в 31-м — 10243 =1 073 741 824 у. е., но он
нам, очевидно, уже не понадобится, а вот 30-й с 1 073 741 824/2=
=536 870 912 у. е. может и пригодиться. В общем случае сумма
в (n+1)-м конверте будет равна произведению n двоек, это чи-
сло принято обозначать 2n и называть n-й степенью двойки. Усло-
вимся считать, что 20 =1. Проведённые выше вычисления основы-
вались на следующих свойствах операции возведения в степень:
2n 2m =2n+m , 2n /2m =2n?m , (2n )m =2nm .
Экспериментально легко проверить, что любое число можно пред-
ставить единственным образом в виде суммы различных меньших
степеней двойки, и поэтому наша задача почти решена. Например,
30 000=214 +213 +212 +210 +28 +25 +24 .
Но для реального применения нужен алгоритм построения тако-
го разложения. Далее будут приведены несколько разных алгорит-
мов, но вначале мы рассмотрим самый простой. В сущности, это
алгоритм выдачи сдачи клиенту, записанный некогда даже в ин-
струкции для работников торговли, но очень редко ими выполняю-
щийся. А он очень прост — сдачу надо выдавать, начиная с самых
больших купюр. В нашем случае нужно найти конверт с наиболь-
шей суммой денег, не превосходящей требуемую, т. е. наибольшую
степень двойки, не превосходящую требуемого количества денег.
*) Двумя чертами слева выделены тексты задач для самостоятельного решения.
3
Если требуемая сумма равна этой степени, то алгоритм заканчивает
работу. В противном случае опять выбирается конверт с наиболь-
шей суммой денег, не превосходящей оставшуюся, и т. д. Алго-
ритм закончит работу, когда останется сумма, в точности равная
степени двойки, и она будет выдана последним конвертом.
Ниже мы докажем, что, имея набор конвертов с суммами
в 1 у. е., 2 у. е., 4 у. е., ..., 2n у. е., любую сумму денег от 1 у. е.
до 2n+1 ?1 у. е. можно выдать единственным способом. Также
будет доказано, что, действуя по описанному алгоритму, мы всегда
получим этот способ выдачи требуемой суммы.
Вначале рассмотрим пример работы алгоритма с числом 2n ?1.
Ясно, что на первом шаге будет выбрано число 2n?1 , останется
число 2n ?1?2n?1 =2n?1 ?1, потом будет выбрано число 2n?2 ,
и т. д., и в результате получится разложение
2n ?1=2n?1 +2n?2 +...+22 +21 +20 .
Но оно не показалось бы очевидным, если, не зная заранее ответа,
пришлось бы вычислять сумму
1+2+4+8+...+2n?2 +2n?1 ,
называемую суммой геометрической прогрессии со знаменателем 2.
Ведь для этого пришлось бы выдумать какой-нибудь трюк наподо-
бие следующего:
1+2+4+8+...+2n?2 +2n?1 =2?1+2+4+8+...+2n?2 +2n?1 =
=4?1+4+8+...+2n?2 +2n?1 =8?1+8+16+...+2n?2 +2n?1 =...
...=2n?2 ?1+2n?2 +2n?1 =2n?1 ?1+2n?1 =2n ?1.
2. Используя подобный трюк, вычислите произведение
n
(2+1)(22 +1)·...·(22 +1).
Докажем теперь существование и единственность представле-
ния числа N в виде суммы меньших степеней двойки. Доказатель-
ство будем проводить индукцией по N.
Для N=1 утверждение очевидно.
Пусть оно верно для всех N<N0. Пусть 2n — максимальная
степень двойки, не превосходящая N, т. е. 2n ?N0 <2n+1 . Тогда
по предположению индукции число N0 ?2n ?2n представимо в ви-
де суммы степеней двойки, меньших N0 ?2n <2n . Следовательно,
число N0 тоже представимо в виде суммы меньших степеней двой-
ки (достаточно к представлению числа N0 ?2n добавить 2n ). Кроме
того, так как 1+2+...+2n?1 =2n ?1<2n , то не существует пред-
ставления числа N0 , не исползующего 2n . Таким образом, доказа-
на единственность такого представления.
Заметим, что для быстрого применения этого алгоритма удобно
заранее вычислить все степени двойки, не превосходящие данного
числа.
4
Заметим ещё, что, в отличие от первого варианта решения,
полная сумма во всех конвертах менее чем в два раза превосходит
верхнюю границу подлежащей выплате суммы.
Для краткой записи результата работы алгоритма над данным
числом a можно вместо разложения
a=2n1 +...+2nk ,
которое и записать-то в общем виде без использования трёхэтаж-
ных обозначений затруднительно, использовать последовательность
показателей степеней (n1 , ..., nk ), или, что ещё удобнее (но не все-
гда короче), написать последовательность (am , ..., a1 ) чисел 0 и 1,
в которой ai =1, если число 2i?1 входит в указанное выше разло-
жение, и ai =0 в противном случае. Тогда это разложение можно
будет переписать в виде
а=a1 +2a2 +4a3 +...+2m?1 am .
Ясно, что приведённый выше алгоритм позволяет строить такое
представление, причём оно определяется однозначно, если предпо-
лагать, что старший его разряд am ненулевой. Это представление
и называется двоичной записью числа a.
Читатель увидит, что понятие двоичной записи очень похоже
на понятие десятичной записи и в каком-то смысле даже проще.
Остался вопрос о минимальности найденной системы конвер-
тов. В общем виде указанный выше приём предлагает для уплаты
любой суммы от 1 до n использовать m конвертов с суммами 1,
2, 4, 8, ..., 2m?1 , где 2m?1 ?n<2m . Меньшего количества кон-
вертов может не хватить, потому что с помощью k<m конвер-
тов можно уплатить не более чем 2k ?1<2m?1 ?n разных сумм,
так как каждая сумма однозначно определяется ненулевым набо-
ром (a1 , ..., ak ), в котором каждое число ai равно 1, если i-й кон-
верт входит в эту сумму, и равно 0 в противном случае, а всего
наборов длины k из нулей и единиц можно составить ровно 2k .
3. Докажите последнее утверждение.
4. Докажите, что если n=2m ?1, то минимальная система
конвертов определяется однозначно, в противном случае — нет.
После упоминания десятичной системы сразу возникает идея
на первый взгляд даже более простого решения задачи о конвер-
тах. Надо просто заготовить конверты с суммами 1, 2, ..., 9, 10,
20, 30, ..., 90, 100, 200, 300, ..., 100 000 000, 200 000 000, ...
..., 900 000 000. Тогда для выплаты любой требуемой суммы
не нужно искать её двоичную запись, так как для выплаты, напри-
мер, 123 456 789 у. е. нужно просто взять конверт с суммой 9, кон-
верт с суммой 80, конверт с суммой 700 и т. д. Это действительно
проще, но исключительно потому, что мы привыкли пользоваться
десятичной системой и все расчёты ведутся с её помощью. Если бы
мы использовали в повседневной жизни только двоичную систему,
5
то этот способ был бы сложнее, так как приходилось бы перево-
дить данную сумму из двоичной системы в десятичную*). Поэтому
простота десятичного способа решения задачи скорее мнимая.
На самом деле указанный выше двоичный метод имеет пре-
имущество перед десятичным (и любым другим). Оно заключается
в меньшем числе используемых конвертов, что было показано выше.
Хотя длина двоичной записи числа в три с лишним раза больше
длины его десятичной записи, на каждую цифру десятичной запи-
си приходится девять конвертов, т. е. число конвертов в двоичном
методе почти в три раза меньше, чем в десятичном.
Идея, лежащая в основе изложенной задачи, видимо, очень древ-
няя, и происходит, вероятно, из Индии. Об этом свидетельствует ле-
генда об изобретателе шахмат, который скромно попросил (после
настояний магараджи, которому очень понравилась игра) себе в на-
граду положить одно зерно на угловую клетку шахматной доски
и удваивать количество зёрен на каждой следующей клетке. Магарад-
жа, подивившись скудоумию казавшегося таким мудрым человека,
распорядился отсыпать ему запрошенные несколько мешков зерна.
5. Оцените приблизительно, во сколько миллионов тонн зерна
обойдётся магарадже его щедрость.
Из сказанного выше видно, что если бы на каждое поле шах-
матной доски не всегда класть столько зерна, сколько просил му-
дрец, а иногда вообще не класть зёрен, то можно получить таким
образом любое число от 0 до 264 ?1. Поэтому, вероятно, таким
образом можно представить любое число, которое может встретить-
ся в каких либо конкретных прикладных вычислениях.
Индийская легенда обращает наше внимание на одну особен-
ность двоичной (и любой позиционной) системы — возможность
представить колоссальные числа в виде короткой записи. Разуме-
ется, в качестве такой записи не надо использовать совокупность
количеств зёрен, лежащих на клетках доски в точности так как
указано выше — ведь эти числа могут быть очень велики, и реаль-
но такое количество зёрен на большей части клеток доски поме-
стится не может. Вместо этого, как и принято в двоичной системе,
на каждую клетку или не кладётся зёрен вообще, или кладётся од-
но зерно, которое символизирует соответствующую степень двой-
ки. Тогда шахматная доска превращается по существу в то, что
на Востоке называют абак, а в России — счёты.
Конечно, реально используемые счёты всегда были десятичны-
ми, но проведённые выше рассуждения показывают, что, хотя дво-
ичная запись в три раза длиннее десятичной (и вообще, из всех
позиционных систем в этом смысле двоичная — самая плохая),

*) Иногда это приходится делать и в реальной жизни. Различные алгоритмы
такого перевода будет изложены далее.
6
но изготовление счёт с применением двоичной системы могло бы
дать определённую (правда, лишь теоретическую) экономию (см.
приложение, с. 49).
6. Пусть на каждой из n спиц счётов находится по b костяшек
(т. е. счёты представляют числа в системе счисления с основани-
ем b+1) и поэтому они позволяют записать в этой системе любое
число от 0 до N=(b+1)n ?1 (число N характеризует <вмести-
мость> счётов). Каким нужно выбрать b, чтобы суммарное коли-
чество костяшек на счётах (<сложность> счётов) было минималь-
ным при условии возможности указанного представления на счё-
тах любого числа от 1 до N (т. е. при заданной вместимости)?
Для прочитавших этот параграф, ответ, конечно очевиден. Для
знающих логарифмы продолжение этой задачи: сравните слож-
ности десятичных и двоичных счёт одинаковой вместимости.
Приведённый выше алгоритм перевода из десятичной системы
в двоичную вычислял цифры двоичной записи, начиная со стар-
ших цифр. Опишем теперь кратко, возможно более удобный, ал-
горитм, в котором цифры двоичной записи вычисляются, начиная
с младших*).
Очевидно, самая младшая цифра равна нулю, если число чёт-
ное, и единице, если оно нечётное. Для нахождения остальных
двоичных цифр надо от исходного числа отнять найденную млад-
шую цифру, поделить разность пополам и к полученному числу
применить описанный выше шаг алгоритма.
Например, у числа 300 последние две цифры нули, а для нахож-
дения остальных цифр надо иметь дело с числом 300/4=75, поэто-
му следующая цифра 1, и получаем промежуточный результат 37.
Следующая далее цифра опять 1, и промежуточный результат 18,
поэтому следующая цифра 0, а промежуточный результат 9, сле-
дующая цифра 1, а потом три нуля подряд, а старший разряд, как
всегда 1. В результате получается двоичная запись 1000101100.
Преимущество этого алгоритма в том, что не требуется предва-
рительного вычисления степеней двойки, но зато приходится не-
однократно выполнять операцию деления пополам.
§ 2. ВЗВЕШИВАНИЕ С ПОМОЩЬЮ ГИРЬ И ВОЗВЕДЕНИЕ В СТЕПЕНЬ
Предлагаем читателю самому убедиться в том, что точно так же,
как и предыдущем разделе, можно доказать, что для отвешивания
любого числа граммов песка от 1 г до n г за одно взвешивание,
достаточно иметь гири 1 г, 2 г, 4 г, ..., 2m г, где 2m ?n<2m+1,
и меньшего числа гирь недостаточно, если песок лежит на одной чаш-
ке весов, а гири разрешается ставить на вторую чашку. На самом
*) Кстати, кассиры в магазинах и на рынках предпочитают выдавать сдачу
начиная с мелких купюр, вопреки инструкции. Причина понятная — надеются,
что покупатель, получив мелочь, уйдёт, забыв взять крупные.
7
деле с математической точки зрения эта задача, известная со сред-
невековых времён, ничем не отличается от рассмотренной выше
задачи о конвертах с деньгами.
Часто новые и интересные задачи получаются, если в старой
задаче наложить какие-нибудь естественные ограничения. Напри-
мер, можно задать следующий вопрос: за какое наименьшее коли-
чество взвешиваний на чашечных весах можно отвесить килограмм
сахарного песка, если имеется лишь одна однограммовая гирька?
На первый взгляд кажется, что единственный способ решения
этой задачи — отвесить один грамм, положить в эту же чашку
гирьку, отвесить в другой чашке два грамма, переложить гирьку
в неё и т. д., добавляя по одному грамму, после тысячного взве-
шивания отмерить наконец-то килограмм.
Но есть и более быстрый способ. Нужно лишь заметить, что если
мы научились отвешивать за n взвешиваний m г песка, то, сделав
ещё одно взвешивание, можно даже не используя гирьку отвесить
ещё m г, и, ссыпав обе порции вместе, получить 2m г за n+1 взве-
шивание. А если при этом взвешивании положить на одну из чашек
гирьку, то за n+1 взвешивание можно отмерить 2m±1 г песка.
Теперь воспользуемся двоичной записью числа 1000. Применяя
любой из указанных выше алгоритмов, получаем равенство
1000=29 +28 +27 +26 +25 +23 .
Так как
29 +28 +27 +26 +25 +23 =(((((2+1)2+1)2+1)2+1)22 +1)23 ,
то, последовательно отвешивая 1, 2+1=3, 2·3+1=7, 2·7+1=
=15, 2·15+1=31, 2·31=62, 2·62+1=125, 2·125=250, 2·250=
=500, получаем на десятом взвешивании 2·500=1000 г. Девяти
взвешиваний не хватит, потому что за два взвешивания можно
отмерить массу не более 3=22 ?1, за три — не более 7=2·3+
+1=23 ?1, за четыре — не более 15=2·7+1=24 ?1, и за девять
взвешиваний — не более 511=29 ?1.
Если нужно отмерить n г песка, то надо записать n в двоичном
виде am ...a1 , где 2m?1 ?n<2m, am =1, и воспользоваться формулой
n=am 2m?1 +...+a22+a1 =(...((2am +am?1 )2+am?2 )...)2+a1,
последовательно отвешивая по b1 =am , b2 =2b1 +am?1 , b3 =2b2 +
+am?2 , ..., bm =bm?1 2+a1 =n г.
В используемой формуле знающие читатели увидят так назы-
ваемую схему Горнера. К ней мы ещё вернёмся в дальнейшем.
Идея, лежащая в основе этого метода взвешивания, стара как сама
математика. Её применяли и древние египтяне, и древние индусы,
но, конечно, не для взвешивания, а для умножения. Ведь алгоритм
умножения столбиком был придуман не сразу, а до этого умножение
сводилось к сложению. Например, чтобы умножить какое-нибудь
8
число a на 1000, можно, используя только операции сложения после-
довательно вычислить a+a+a=3a, 3a+3a+a=7a, 7a+7a+a=
=15a, 15a+15a+a=31a, 31a+31a=62a, 62a+62a+a=125a,
125a+125a=250a, 250a+250a=500a, 500a+500a=1000a. Та-
кой метод умножения дожил почти до нашего времени, он удобен
при вычислениях на счётах. Сейчас он никому не нужен, так как
все используют калькуляторы. Но как возвести на калькуляторе
число a, например, в тысячную степень, если у него нет специ-
альной операции возведения в произвольную степень? Умножать
999 раз не нужно, а можно применить тот же приём, последо-
вательно вычисляя a3 =a2 a, a7 =(a3 )2 a, a15 =(a7 )2 a, a31 =(a15 )2 a,
a62 =(a31 )2 , a125 =(a62 )2 a, a250 =(a125 )2 , a500 =(a250 )2 , a1000 =(a500)2 .
Если вспомнить, что 1000 имеет двоичную запись 1111101000,
то можно заметить, что если отбросить старший бит (всегда равный
единице), то каждому следующему биту соответствует операция воз-
ведения в квадрат, если он нулевой, или, если он ненулевой, возве-
дение в квадрат с последующим умножением на число a — основа-
ние степени (т. е. делается две операции). Кстати, число a не нуж-
но каждый раз заново набирать на клавиатуре. Нужно в самом на-
чале вычислений занести его в память калькулятора, и когда нуж-
но, после нажатия кнопки для умножения, просто вызывать его
из памяти и потом нажимать кнопку <равно>. Таким образом, воз-
ведение в квадрат требует двукратного нажатия кнопок, а возведе-
ние в квадрат и последующее умножение на основание степени —
пятикратного. Для того чтобы не запутаться в операциях, можно
перед началом вычислений составить мнемоническое правило. Воз-
ведение в квадрат обозначим символом К, а возведение в квадрат
и последующее умножение — символом КУ. Тогда, заменяя в дво-
ичной записи единицы (кроме старшей) на КУ, а нули — на К,
получим правило КУКУКУКУККУККК, или короче КУ4 ККУК3 .
Посчитаем общее число операций умножения в рассмотрен-
ном вычислении. Число возведений в квадрат на единицу меньше
длины двоичной записи показателя степени, а число умножений
общего вида на единицу меньше суммы цифр двоичной записи.
Для любого n обозначим ?(n) уменьшенную на единицу дли-
ну двоичной записи числа n, a ?(n) — её сумму цифр (другими
словами, число единиц в ней). Тогда в общем случае число опера-
ций умножения, использованных в этом методе возведения в сте-
пень n, будет равно ?(n)+?(n)?1. Далее будет показано, что мень-
шим числом операций обойтись нельзя, если только не обновлять
содержимое ячейки памяти.
Очевидно, что ?(n)+?(n)?1?2?(n). Те, кто знают логарифмы,
сообразят, что ?(n)= log2 n , где знак x означает целую часть
числа x. Но можно вычислить обе введённые функции даже
не упоминая о двоичной записи. Для этого надо воспользоваться
9
следующими правилами:
?(1)=1, ?(2n)=?(n), ?(2n+1)=?(n)+1,
?(1)=0, ?(2n)=?(2n+1)=?(n)+1.
Однако для доказательства справедливости этих правил полезно,
конечно, воспользоваться двоичной системой, после чего они ста-
новятся почти очевидными.
Докажем полезное и простое неравенство ?(n+1)??(n)+1. Оно
очевидно превращается в равенство, если n чётно, так как тогда
его двоичная запись заканчивается нулём. Если же эта двоичная
запись заканчивается k единицами, перед которыми стоит нуль,
то двоичная запись числа n+1 заканчивается k нулями, перед ко-
торыми стоит единица (а старшие биты остаются без изменения,
если они есть). Для того, чтобы в этом убедиться, достаточно вы-
полнить прибавление 1 к n в двоичной системе. В обоих рассмо-
тренных случаях ?(n+1)??(n)+1.
Из доказанного неравенства следует, что
?(n+1)+?(n+1)??(n)+?(n)+1.
Действительно, если 2k?1 <n+1<2k, то ?(n+1)=k?1=?(n),
и из неравенства ?(n+1)??(n)+1 следует нужная нам оценка.
Если же n+1=2k , то ?(n+1)=k=?(n)+1, ?(n+1)=1, ?(n)=k,
откуда следует, что ?(n+1)+?(n+1)=k+1?2k=?(n)+?(n)+1.
Справедливо также равенство
?(2n)+?(2n)=?(n)+?(n)+1,
которое сразу следует из равенств ?(2n)=?(n), ?(2n)=?(n)+1.
Выше было показано, что число операций умножения, исполь-
зованных для возведения в степень n на калькуляторе с одной
ячейкой памяти, не больше чем ?(n)+?(n)?1. При n=1, 2 оче-
видно, что меньшим числом операций обойтись нельзя. Покажем,
что и в общем случае это так, если только не обновлять содержи-
мое ячейки памяти, т. е. кроме возведения в квадрат всегда ис-
пользовать только умножение на основание степени.
Допустим противное, а именно, что для вычисления указан-
ным образом xn при некотором n оказалось достаточно l<?(n)+
+?(n)?1 операций. Выберем среди таких чисел n наименьшее чи-
сло и обозначим его также n. Если последняя операция в рас-
сматриваемом вычислении была возведение в квадрат, то n чётно,
и для вычисления xn/2 достаточно l?1<?(n)+?(n)?2=?(n/2)+
+?(n/2)?1 операций, поэтому минимальным числом с рассматри-
ваемым свойством не может быть n, что ведёт к противоречию.
Аналогично получается противоречие и в случае, когда последней
операцией было умножение на x. Действительно, тогда согласно
доказанному выше неравенству для вычисления xn?1 достаточно
l?1<?(n)+?(n)?2??(n?1)+?(n?1)?1 операций.
10
Но если обновлять содержимое ячейки памяти, то указанный
выше метод вычисления x1000 можно улучшить. Для этого можно
применить так называемый метод множителей. Идея этого метода
заключается в следующем. Заметим, что если мы умеем возводить
в степень n за l(n) операций и возводить в степень m за l(m)
операций, то можно после того, как закончено вычисление xn ,
занести его в ячейку памяти и далее вычислить xnm =(xn )m за l(m)
операций, используя тот же метод, что и для вычисления xm .
Тогда общее число операций будет равно l(nm)=l(n)+l(m).
Вычисляя x5 старым методом за ?(5)+?(5)?1=3 операции
(с помощью последовательности x, x2 , x4 =(x2 )2 , x5 =(x4 )x) и при-
меняя два раза метод множителей, получаем, что l(125)=3l(5)=
=9. Выполняя ещё три возведения в квадрат, получаем l(1000)=
=l(125)+3=12. Старый же метод требовал ?(1000)+?(1000)?1=
=9+6?1=14 операций.
Читателю может показаться, что мы слишком много внима-
ния уделили такому специальному и не слишком важному вопро-
су, как быстрое выполнение возведения в степень. Лет тридцать
назад это замечание было бы справедливым. Но в середине 1970-x
годов почти одновременно и независимо группой американских ма-
тематиков (У. Диффи, М. Хеллман, Р. Ривест, А. Шамир, П. Ад-
леман) и группой английских криптографов (К. Кокс, М. Вильям-
сон, Д. Эллис) были открыты первые алгоритмы криптографии
с открытым ключом*). Благодаря этим алгоритмам теперь частные
лица могут обмениваться секретной информацией по общедоступ-
ным каналам связи (например, по Интернету) без боязни, что их
сообщения прочтут не только конкуренты, но и спецслужбы. Воз-
никшее направление в криптографии быстро превратилось в по-
пулярную область математических исследований, которой уже по-
священы многочисленные журналы и книги. И во многих самых
распространённых алгоритмах важную роль играет операция воз-
ведения в степень.
§ 3. АДДИТИВНЫЕ ЦЕПОЧКИ И ФЛЯГИ С МОЛОКОМ
Назовём аддитивной цепочкой любую начинающуюся с 1 по-
следовательность натуральных чисел a0 =1, a1 , ..., am , в которой
каждое число является суммой каких-то двух предыдущих чисел
(или удвоением какого-то предыдущего числа). Обозначим l(n) наи-
меньшую длину аддитивной цепочки, заканчивающейся числом n
(длиной цепочки a0 =1, a1 , ..., am называем число m).
Например, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 — адди-
тивная цепочка, 1, 2, 3, 5, 7, 14 — минимальная цепочка для 14,
*) Англичане сделали это раньше, но им, как сотрудникам секретной крипто-
графической службы, было запрещено опубликовать свои результаты в открытой
печати.
11
т. е. l(14)=5. Аддитивные цепоч-
ки можно изображать в виде ори-
ентированного графа, в котором
1 2 3 5 7 14 в вершину a идут рёбра от вершин
i
aj , ak , если ai =aj +ak (в случае,
Рис. 1
если такое представление неод-
нозначно, выбираем любое из них и рисуем только два ребра).
Если из какой-то вершины выходит только одно ребро, то для крат-
кости можно <склеить> эту вершину с той вершиной, в которую
ведёт это ребро. Граф для предыдущего примера показан на рис. 1.
Можно считать, что все числа в цепочке разные, так как этого
легко достичь просто удаляя из неё повторяющиеся числа, и что
эти числа расположены в цепочке в порядке возрастания.
Очевидно, что наименьшее число умножений, необходимое для
возведения в n-ю степень, равно l(n).
Приведённый выше метод построения аддитивных цепочек на-
зывается двоичным (или бинарным). Фактически этим методом бы-
ло доказано, что справедливо неравенство l(n)??(n)+?(n)?1. Ме-
тодом множителей легко доказать неравенство l(nm)?l(n)+l(m).
7. Докажите нижнюю оценку: l(n)??(n).
Из этой оценки следует, что l(2n )=n.
Интересно, что бинарный метод был по существу известен
древним индусам, потом был переоткрыт арабскими математиками,
задача о точном вычислении функции l(n) появилась в одном
французском журнале в 1894 году, потом заново была переоткрыта
в 1930-е годы и неоднократно переоткрывалась в дальнейшем,
но до сих пор в общем случае не решена.
По существу, наилучшая из известных общих верхних оценок
была доказана в 1930-е годы А. Брауэром и имеет вид
# A
C ?(?(?(n))) !
!,
1 !
l(n)??(n) 1+
(?(?(n)))2 
+
?(?(n))
где C>0 — некоторая константа.
Не каждую аддитивную цепочку можно вычислить на кальку-
ляторе с одной ячейкой памяти, не используя для запоминания
промежуточных результатов собственную голову (фактически, такие
калькуляторы имеют две ячейки памяти, так одна из них содер-
жит число, изображаемое в данный момент на дисплее). Укажем,
как можно определить необходимое число ячеек памяти для вы-
числения данной аддитивной цепочки. Для этого введём понятия
ширины (а заодно и глубины) аддитивной цепочки.
Пусть дана произвольная цепочка a0 =1, a1 , ..., aL =n. Сопо-
ставим каждому её элементу два числа. Первое из них назовём
глубиной элемента, а второе — номером ячейки, хранящей это чи-
сло. Для элемента a0 первое число положим равным нулю, а вто-
12
рое — единице. Будем далее последовательно вычислять эти числа
для элементов цепочки. Пусть они уже вычислены для всех эле-
ментов от a0 до ak . Составим список номеров ячеек, содержащих
те элементы цепочки, которые ещё могут быть использованы для
вычисления последующих элементов. Найдём наименьшее число,
не входящее в этот список, и присвоим его элементу ak+1 в каче-
стве номера ячейки (возможно, она использовалась ранее, но те-
перь уже свободна). Пусть ak+1 =ai +aj , i, j?k. Если D(ai ), D(aj ) —
значения глубины элементов ai , aj , то положим D(ak+1 ) на едини-
цу большим максимального из чисел D(ai ), D(aj ). Шириной S це-
почки назовём число использованных ячеек (равное наибольшему
из использованных номеров ячеек). Глубиной D цепочки назовём
глубину её последнего элемента.
8. Докажите, что ak ?2D(ak ) и D??(n). Докажите, что бинар-
ный метод можно модифицировать так, чтобы длина цепочки
не изменилась, а глубина стала бы равна ?(n).
Если цепочка имеет ширину S, то её можно представить в виде
вычисления на калькуляторе с S?1 ячейками памяти (кроме основ-
ной, содержащей число, изображаемое в данный момент на дисплее)
или в виде компьютерной программы, использующей S ячеек памяти.
Можно ещё представить эту цепочку в виде способа, как налить
в данную флягу n литров молока из цистерны, если первоначально
в ней был один литр и кроме неё имеется S таких же пустых фляг
и весы, способные только сравнивать веса двух фляг между собой.
Для этого сопоставим S фляг ячейкам памяти рассматриваемой
цепочки, а одну флягу оставим запасной. Тогда любую операцию
с ячейками памяти вида xk =xi +xj можно выполнить, выливая
в случае необходимости k-ю флягу в цистерну, потом наливая
запасную флягу до уровня i-й фляги и сливая её содержимое в k-ю
флягу, если k=i, и делая аналогичную процедуру для индекса j.
Естественно, что аналогичным образом на языке <переливаний>
можно представить и программу с командами, использующими не толь-
ко сложение, но и вычитание xk =xi ?xj . Поэтому понятие аддитив-
ной цепочки можно обобщить, разрешив использовать вычитание.
Для вычисления степеней такие цепочки также можно выпол-
нять на калькуляторе, если кроме умножения использовать и де-
ление. Известно, что в среднем это не даёт существенной выгоды,
но в некоторых случаях число используемых операций уменьшается.
Например, вычислить x1000 можно с помощью следующей
цепочки: 1, 2, 4, 8, 16, 32, 31, 62, 124, 125, 250, 500, 1000.

§ 4. КРАТКАЯ ИСТОРИЯ ДВОИЧНОЙ СИСТЕМЫ
Некоторые идеи, лежащие в основе двоичной системы, по су-
ществу были известны в Древнем Китае. Об этом свидетельствует
13
классическая книга <И-цзин> (<Книга Перемен>), о которой речь
пойдёт позже.
Идея двоичной системы была известна и древним индусам.
В Европе двоичная система, видимо, появилась уже в новое время.
Об этом свидетельствует система объёмных мер, применяемая англий-
скими виноторговцами: два джилла = полуштоф, два полуштофа =
пинта, две пинты = кварта, две кварты = потл, два потла = галлон,
два галлона = пек, два пека = полубушель, два полубушеля =
= бушель, два бушеля = килдеркин, два килдеркина = баррель,
два барреля = хогзхед, два хогзхеда = пайп, два пайпа = тан.
Читатели исторических романов, видимо, знакомы с пинтами
и квартами. Частично эта система дожила и до нашего времени
(нефть и бензин до сих пор меряют галлонами и баррелями).
И в английских мерах веса можно увидеть двоичный принцип.
Так, фунт (обычный, не тройский) содержит 16 унций, а унция —
16 дрэмов. Тройский фунт содержит 12 тройских унций. В английских
аптекарских мерах веса, однако, унция содержит восемь дрэмов.
Пропагандистом двоичной системы был знаменитый Г. В. Лейб-
ниц (получивший, кстати, от Петра I звание тайного советника).
Он отмечал особую простоту алгоритмов арифметических действий
в двоичной арифметике в сравнении с другими системами и при-
давал ей определённый философский смысл. Говорят, что по его
предложению была выбита медаль с надписью <Для того, чтобы
вывести из ничтожества всё, достаточно единицы>. Известный со-
временный математик Т. Данциг о нынешнем положении дел ска-
зал: <Увы! То, что некогда возвышалось как монумент монотеиз-
му, очутилось в чреве компьютера>. Причина такой метаморфозы
не только уникальная простота таблицы умножения в двоичной
системе, но и особенности физических принципов, на основе кото-
рых работает элементная база современных ЭВМ (впрочем, за по-
следние 40 лет она неоднократно менялась, но двоичная система
и булева алгебра по-прежнему вне конкуренции).

§ 5. ПОЧЕМУ ДВОИЧНАЯ СИСТЕМА УДОБНА?
Главное достоинство двоичной системы — простота алгорит-
мов сложения, вычитания умножения и деления. Таблица умноже-
ния в ней совсем не требует ничего запоминать: ведь любое число,
умноженное на нуль равно нулю, а умноженное на единицу рав-
но самому себе. И при этом никаких переносов в следующие раз-
ряды, а они есть даже в троичной системе. Таблица деления сво-
дится к двум равенствам 0/1=0, 1/1=1, благодаря чему деление
столбиком многозначных двоичных чисел делается гораздо проще,
чем в десятичной системе, и по-существу сводится к многократно-
му вычитанию.
14
Таблица сложения как ни странно чуть сложнее, потому что
1+1=10 и возникает перенос в следующий разряд. В общем ви-
де операцию сложения однобитовых чисел можно записать в виде
x+y=2w+v, где w, v — биты результата. Внимательно посмотрев
на таблицу сложения, можно заметить, что бит переноса w — это
просто произведение xy, потому что он равен единице лишь когда
x и y равны единице. А вот бит v равен x+y, за исключением
случая x=y=1, когда он равен не 2, а 0. Операцию, с помощью
которой по битам x, y вычисляют бит v, называют по-разному.
Мы будем использовать для неё название <сложение по модулю 2>
и символ ?. Таким образом, сложение битов выполняется факти-
чески не одной, а двумя операциями.
Если отвлечься от технических деталей, то именно с помощью
этих операций и выполняются все операции в компьютере.
Для выполнения сложения однобитовых чисел делают обыч-
но даже специальный логический элемент с двумя входами x, y
и двумя выходами w, v, как бы составленный из элемента умно-
жения (его часто называют конъюнкцией, чтобы не путать с умно-
жением многозначных чисел) и элемента сложения по модулю 2.
Этот элемент часто называют полусумматором.

§ 6. ХАНОЙСКАЯ БАШНЯ, КОД ГРЕЯ И ДВОИЧНЫЙ n-МЕРНЫЙ КУБ
Далее мы рассмотрим несколько интересных задач, в решении
которых помогает знание двоичной системы. Начнём мы с задач,
в которых используется только одна, самая простая, из лежащих
в её основе идей — идея чисто комбинаторная и почти не связанная
с арифметикой.
Первая из них — это <Ханойская башня>. Головоломку под
таким названием придумал французский математик Эдуард Люка
в XIX веке.
На столбик нанизаны в порядке убывания размеров n круглых
дисков с дырками в центре в виде детской игрушечной пирамидки.
Требуется перенести эту пирамидку на другой столбик, пользуясь
третьим вспомогательным столбиком (рис. 2). За один ход разре-
шается переносить со столбика на столбик один диск, но класть
больший диск на меньший
нельзя. Спрашивается,
за какое наименьшее ко-
личество ходов это можно
сделать. Ответом в этой за-
даче служит уже извест-
ное нам <индийское число>
2n ?1. Люка в своей книге
Рис. 2
приводит якобы известную
15
легенду о том, что монахи в одном из монастырей Ханоя зани-
маются перенесением на другой столбик пирамидки, состоящей
из 64 дисков. Когда они закончат работу, кончится жизнь Брах-
мы*). Видно, ждать придётся долго.
Решение этой головоломки сильно облегчается, если знать, что
такое код Грея. Кодом Грея порядка n называется любая цикличе-
ская последовательность всех наборов из нулей и единиц длины n,
в которой два соседних набора отличаются ровно в одной компо-
ненте. Примером кода Грея порядка 3 является последовательность
трёхразрядных наборов 000, 001, 011, 010, 110, 111, 101, 100.
9. Докажите, что длина кода Грея порядка n равна 2n .
Если занумеровать компоненты каждого набора справа налево
(при этом последняя, т. е. самая правая компонента получит но-
мер 1), и начинать код Грея с нулевого набора, то его можно за-
писать короче, если вместо очередного набора писать только номер
компоненты, в которой он отличается от предшествующего набо-
ра. Например, указанный выше код Грея можно коротко записать
в виде последовательности семи чисел 1, 2, 1, 3, 1, 2, 1. В общем
случае длина подобной последовательности равна 2n ?1. Указан-
ная краткая запись позволяет догадаться, как можно строить коды
Грея дальше. Например, Грея порядка 4 можно задать последова-
тельностью 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1. Она получается,
если мы повторим два раза последовательность, определяющую код
Грея порядка 3, разделив оба экземпляра этой последовательности
числом 4. Далее поступаем аналогично, т. е. последовательность
длины 2n ?1, определяющую код Грея порядка n, дублируем, раз-
делив оба дубля числом n+1. Полученная последовательность дли-
ны 2(2n ?1)+1=2n+1 ?1 будет определять код Грея порядка n+1.
Легко видеть, что эта последовательность, так же, как и пре-
дыдущая, не изменяется, если её выписать в обратном порядке.
Последовательности (или слова) с таким свойством называются
палиндромами. Например, одним из самых известных русских па-
линдромов является предложение (символы пробела, естественно,
игнорируются)
А РОЗА УПАЛА НА ЛАПУ АЗОРА.
Нам понадобится это свойство кода Грея порядка n+1, а также
то обстоятельство, что все числа этой последовательности, кроме
среднего, не больше n. Это означает, что если с её помощью мы
начнём выписывать последовательность наборов длины n+1, на-
чиная с нулевого, то первые 2n ?1 наборов будут начинаться с нуля,
так как (n+1)-я компонента никогда в них не будет меняться.
*) Приблизительный западный аналог — это конец света, но на Востоке считают,
что после этого рождается новый Брахма, и всё циклически повторяется сначала,
от золотого века до нашей Кали-Юги, которой и заканчивается цикл.
16
Остальные же компоненты будут образовывать наборы длины n,
и они будут чередоваться в том же порядке, что и в коде Грея
порядка n, поэтому получится некоторая перестановка всех 2n на-
боров длины n+1, начинающихся с нуля. Потом в её последнем
наборе этот нуль будет заменён на единицу (это определяется тем,
что в середине последовательности стоит число n+1), далее эта
единица меняться не будет, а будет меняться в каждом очередном
наборе длины n+1 только одна из последних n компонент, и эти
компоненты образуют код Грея порядка n, выписанный в обратном
порядке, и закончится он нулевым набором. Сама же построенная при
этом последовательность наборов длины n+1 будет образовывать
перестановку всех наборов длины n+1, начинающихся с единицы, а её
последним набором будет набор 10...0. Таким образом, построенная
последовательность состоит из 2n различных наборов и может быть
превращена в циклическую, т. е. является кодом Грея порядка n+1.
Код Грея можно наглядно изобразить на n-мерном двоичном
кубе. Сам этот куб служит для наглядного представления множества
всех наборов длины n из нулей и единиц. Наборы изображаются
точками и называются вершинами куба. Два набора, отличающие-
ся только в одной компоненте, называются соседними и образуют
ребро куба. Номер этой компоненты называется направлением ре-
бра. Куб можно нарисовать на плоскости так, что все рёбра будут
изображены отрезками, соединяющими их вершины, причём рёбра
одного направления будут изображены равными и параллельны-
ми отрезками (поэтому такие рёбра называют тоже параллельны-
ми). Например, четырёхмерный куб можно изобразить на плоско-
сти так, как показано на рис. 3.
Код Грея на многомерном кубе можно изобразить в виде последова-
тельности вершин, в которой каждые две соседние вершины соединя-
ются рёбрами. Такие последовательности вершин принято называть
путями. Но код Грея изобра-
жается путём, у которого пер-
вая и последняя вершина тоже
соединяются ребром. Такие пу-
ти естественно называть цикла-
ми. Однако код Грея — не про-
сто цикл, а цикл проходящий
через все вершины куба. Такие
циклы (а их можно искать
не только на многомерном ку-
бе, но и на любом графе*))
называются гамильтоновыми
*) Граф — это произвольное множе-
ство вершин, некоторые из которых
Рис. 3
соединены рёбрами.
17
циклами*), а графы, у которых они есть — гамильтоновыми гра-
фами. Вопрос о том, какие графы гамильтоновы, а какие нет, ока-
зался чрезвычайно трудным и не решён удовлетворительно по сей
день. Ему можно посвятить отдельную книгу, и такие книги уже
написаны, поэтому мы прекращаем разговор на эту тему и возвра-
щаемся к многомерному кубу.
Для того, чтобы изобразить код Грея на приведённом на рис. 3
изображении n-мерного куба рядом с вершинами следует написать
их имена — соответствующие им наборы из нулей и единиц. Сделать
это можно, например, таким образом. Самой нижней вершине сопо-
ставим набор из одних нулей. Рёбрам сопоставим номера их направ-
лений, например, направлению самого правого ребра, выходящего
из <нулевой> вершины, сопоставим номер 1, и т. д., а направлению
самого левого такого ребра — номер n. Далее сопоставляем остав-
шимся вершинам куба имена с помощью следующего алгоритма.
Если какой-то вершине имя уже присвоено и, поднимаясь из неё
вверх по какому-нибудь ребру, скажем, направления k, попадаем
в новую, пока безымянную, вершину, то ей присваиваем имя, кото-
рое получается из имени прежней вершины заменой k-й компо-
ненты (которая была нулём) на противоположную (т. е. единицу).
Если же мы попали в вершину, имя которой уже было присвоено
ранее, то можно ничего не делать, так как если мы попробуем
всё же сопоставить ей имя согласно указанному правилу, то оно
совпадёт с уже присвоенным именем. Очевидно, самой верхней
вершине будет присвоен набор из одних единиц. Результат работы
описанного алгоритма для четырёхмерного куба показан на рис. 4.
Читателю предоставляется возможность самому решить голо-
воломку Люка и обнаружить её связь с кодом Грея, а мы займём-
ся другим вопросом.
Бросается в глаза на изображениях многомерного куба, что все
вершины, имена которых содержат заданное число единиц, ска-
жем k, лежат на одной прямой (рис. 5). Говорят, что эти вершины
лежат на k-м слое куба. Очевидно, нулевой слой состоит из одной
вершины — <нулевой>, а n-й слой состоит только из <единичной>
вершины.
10. Сколько различных <возрастающих> путей ведут из <ну-
левой> вершины в данную вершину k-го слоя?
О т в е т: k(k?1)(k?2)·...·2·1. Это число называют <k факто-
риал> и кратко обозначают k!.

*) В честь ирландского математика, механика, физика и астронома У. Р. Га-
мильтона, подсказавшего одному книготорговцу идею головоломки — как обойти
по рёбрам все вершины правильного многогранника (например, додекаэдра) и вер-
нуться в исходную вершину. Полученные от книготорговца десять фунтов были,
вероятно, единственным гонораром знаменитого учёного за многочисленные науч-
ные труды, если не считать оклада профессора Дублинского университета.
18
1)
(111

1) 0)
1) 1)
(011 (111
(101 (110

0)
1) 0) (110
(100 (101
)
1 0)
(010
11) (011
(00

0) 0)
1) (001 (010 0)
(000 (100

0)
(000
Рис. 4

Для того чтобы решить эту задачу, достаточно <закодировать>
любой такой путь последовательностью k различных чисел, нуме-
рующих направления составляющих этот путь рёбер.
В частности, число возрастающих путей от нулевой вершины
до единичной равно n!. На любом таком пути есть единственная
вершина, принадлежащая k-му слою, и она разбивает его на две
части. Нижняя часть соединяет её с нулевой вершиной, и этот
путь — один из множества возможных путей, соединяющих её
с нулевой вершиной, которых, как мы уже знаем, ровно k!. Верх-
няя часть соединяет её с единичной вершиной, и этот путь — один
из множества возможных, которых, как легко понять по анало-
гии, в точности (n?k)!.
Поэтому множество всех возрастающих путей от нулевой верши-
ны до единичной, проходящих при этом через заданную вершину
k-го слоя, равно k! (n?k)!. Но всего возрастающих путей от нулевой
1)) 4-й слой
1))
(1 111
1111
((111
(1 11

11) 0)
11)) 10))
1) 0)
1) 1)
1)) 1)) (111 0
(011 1 ) )
01 3-й слой
111
1011 1101
((01 1 ((11 1
(1 011 (1 101
(01 (1 1
((101 ((110
(101 (110

0)
00)))
1) 0) 1100
1)) 0)) (1 10 0
) ) 2-й слой
((11 0
(1 001 (1 010
100 101
1) ((100 1 ((101 0 (11
01)) (100 (101
0)
) 0))
0101
(0 10 1
) 0)
1) (0 11 0
((01 0 0 11
1)
) ((011
(01
0011
(0 011 ( 011
((00 1
(00 1

1-й слой
0) 0)
0)) 0))
1) ) )
01)) 0010 0100
(0 010 (0 100 0)
0))
) ((001 ((010
0001 (001 (010 0)
(000 1 (1 00 0
1 00
((00 0 ((100
( 100
(00

0-й слой
0)
0))
0)
(0 00 0
0 00
((000
(000

Рис. 5
19
вершины до единичной n!, поэтому число вершин в k-м слое рав-
n!
но . Это число называется k-м биномиальным коэффици-
k! (n?k)!
ентом и обозначается кратко Ck . Далее оно нам понадобится.
n
На этом мы заканчиваем рассказ о n-мерном кубе и возвраща-
емся в заключение опять к коду Грея. Очевидно, что в нём несо-
седние вершины могут быть соседними на кубе, т. е. соединяться
в нём ребром. В некоторых приложениях, как теоретических, так
и практических, представляет интерес построение цепи или цикла
в n-мерном кубе, в которой несоседние вершины никогда не явля-
ются соседними в этом кубе. Такая цепь максимальной возможной
длины называется <змеёй в ящике>. Какова её длина, до сих пор
неизвестно. Наилучшие известные её оценки принадлежат ново-
сибирским математикам А. А. Евдокимову и А. Д. Коршунову.
Другой задачей, связанной с кодом Грея, но более простой,
является его недвоичное обобщение. Например, как построить ци-
клическую последовательность всех трёхзначных десятичных чисел
от 000 до 999, в которой каждые два соседних числа были бы
соседними ещё и в том смысле, что отличались бы ровно в одном
разряде и ровно на единицу? Несколько проще построить такую
последовательность, если считать цифры 0 и 9 также соседними,
хотя разность между ними и не равна 1. Ещё проще построить
нециклическую последовательность с теми же свойствами.
Эта задача имеет приложение к алгоритму быстрейшего вскрытия
кодового замка на дипломате, поэтому мы не приводим её решения.
Заметим, что этим методом можно вскрыть, конечно, дипломат
не только с десятичным, но и с любым k-ичным кодовым замком.
Однако при нечётном k аналога циклического кода Грея не суще-
ствует, а существует только <цепной> код Грея. Читателю предо-
ставляется возможность самому это проверить.

§ 7. КНИГА ПЕРЕМЕН, АЗБУКА МОРЗЕ, ШРИФТ БРАЙЛЯ
И АЛФАВИТНЫЕ КОДЫ
Двоичная система, по крайней мере в своей комбинаторной
ипостаси, по существу была известна в Древнем Китае. В клас-
сической книге <И-цзин> (<Книга Перемен>) приведены так на-
зываемые гексаграммы Фу-си, первая из которых имеет вид ,
а последняя (64-я) — вид , причём они расположены по кругу
и занумерованы в точном соответствии с двоичной системой (ну-
лям и единицам соответствуют сплошные и прерывистые линии).
Китайцы не поленились придумать для этих диаграмм специаль-
ные иероглифы и названия (например, первая из них называлась
<кунь>, а последняя — <цянь>, сплошной линии сопоставляется
мужское начало янь, а прерывистой линии — женское начало инь).
20
Каждая гексаграмма состоит из двух триграмм (верхней и ниж-
ней), им тоже соответствуют определённые иероглифы и названия.
Например, триграмме из трёх сплошных линий сопоставлен образ-ат-
рибут <небо, творчество>, а триграмме из трёх прерывистых линий
сопоставлен образ-атрибут <земля, податливость, восприимчивость>.
Их также принято располагать циклически, но этот цикл не явля-
ется кодом Грея.
Книга Перемен очень древняя, возможно, одна из древнейших
в мире, и кто её написал — неизвестно. Она использовалась ранее,
и используется в настоящее время, в том числе и на Западе,
для гадания. В Европе с аналогичной целью используются карты
Таро. В чём-то обе эти системы схожи, но Таро никак не связаны
с двоичной системой, поэтому о них мы говорить не будем.
Способ гадания по Книге Перемен в кратком изложении таков.
Бросается шесть раз монета (или лучше пуговица, деньги в гадании
применять не рекомендуется) и по полученным результатам (орёл
или решка) разыскивается подходящая гексаграмма (для этого на-
до заранее сопоставить орлу и решке янь или инь). По гексаграм-
ме разыскиваете соответствующий раздел Книги Перемен (имеется
перевод выдающегося синолога Ю. К. Шуцкого, неоднократно пе-
реиздававшийся в последнее время) и читаете, что там написано.
Конечно, перевод текста книги в предсказание требует опыта
и мастерства. И заниматься этим надо после соответствующей под-
готовки, в подходящем настроении, в подходящее время и в подхо-
дящем месте. Говорят, тогда предсказания почти всегда сбываются.
А может быть, просто магическим образом из множества вариантов
будущего выбирается тот, который соответствует предсказанию?
Заинтересованного читателя отсылаем к книгам Дж. Х. Брен-
нана <Таинственный И-цзин>, М.: Гранд, 2001; В. Фирсова <Кни-
га Перемен. Мистика и магия древнего Китая>, М.: Центрполи-
граф, 2002, и переходим к другой теме — азбуке для слепых.
На этом примере, в частности, хорошо видно, что многие
на первый взгляд простые идеи рождались не сразу, и своим по-
явлением обязаны усилиям многих людей. Идею использовать ре-
льефные буквы для печатания книг для слепых первым предло-
жил француз Валентен Ойи. Но выпущенные им книги успехом
не пользовались, так как слепым трудно было на ощупь отличать
сложные начертания букв друг от друга.
Капитан французской армии Шарль Барбье в 1819 году пред-
ложил печатать выпуклыми не буквы, а точки и тире (или просто
продавливать их на бумаге) и ими уже записывать буквы. Эту
систему он назвал <ночное письмо> и предлагал вовсе не для сле-
пых, а для использования в военно-полевых условиях. С появлени-
ем электрических фонариков военное значение этого изобретения
упало до нуля.
21
Слепой мальчик Луи Брайль познакомился с этой системой
в 12 лет. Она ему понравилась тем, что позволяла не только читать,
но и писать. В течение трёх лет он её усовершенствовал и создал
так называемый шрифт Брайля. В нём символы языка (буквы,
знаки препинания и цифры) кодируются комбинациями от одной
до шести выпуклых точек, расположенных в виде таблицы стан-
дартного размера с тремя строчками и двумя столбцами. Элементы
(точки) таблицы нумеруются числами 1, 2, 3 в первом столбце
сверху вниз и 4, 5, 6 во втором столбце сверху вниз. Каждая точка
либо продавливается специальной машинкой (или даже шилом)
или остаётся целой. Всего различных способов продавить выпуклые
точки в этой таблице 64 (в том числе и тот, в котором ни одна
из точек не вдавлена). При желании теперь читатель может со-
поставить каждому символу алфавита Брайля одну из гексаграмм
Книги Перемен. Вряд ли, конечно, Брайль знал об этой книге.
Вероятно, не имеет смысла описывать все символы шрифта
Брайля, тем более что после его смерти в 1852 году шрифт допол-
нялся и совершенствовался. Но несколько слов сказать, видимо,
стоит. Буква <а>, например, изображается одной выпуклой точкой
в 1-м элементе таблицы, буква <б> изображается выпуклыми точ-
ками в 1-м и 2-м элементах таблицы и т. д. Для сокращения тек-
стов некоторые часто встречающиеся слова или комбинации букв
кодируются специальными таблицами. Для того чтобы отличать
заглавную букву от строчной, перед ней ставят специальную табли-
цу, изображающую то, что сейчас называют эскейп-символом. Мно-
гие таблицы имеют несколько значений (например, буква и какой-
нибудь специальный знак или знак препинания), выбор из которых
делается в соответствии с контекстом. Цифры кодируются так же,
как и первые буквы алфавита, и, чтобы их отличать, перед по-
следовательностью цифр ставится специальный символ — признак
числа, а заканчивается число символом отмены признака числа.
Азбука Брайля по известности уступает азбуке Морзе, хотя
и применяется до сих пор в отличие от последней. Сэмюэль Морзе
известен однако не только изобретением азбуки. Он был и худож-
ником-портретистом (его картина <Генерал Лафайет> до сих пор
висит в нью-йоркском Сити-Холле*)), и одним из первых фотогра-
фов в Америке (учился делать дагерротипные фотографии у са-
мого Луи Дагерра), и политиком (он баллотировался в 1836 го-
ду на пост мэра Нью-Йорка), но самое главное его достижение —
изобретение телеграфа (а азбука Морзе понадобилась ему для ис-
пользования телеграфа). Заодно он изобрёл устройство, которое на-
зывается реле. Именно из реле спустя сто лет после Морзе были
построены первые компьютеры.
*) Известна также его картина <Человек в предсмертной агонии>, после просмо-
тра которой его приятель, известный врач, сказал: <По-моему, малярия>.
22
Начал свои работы в этом направлении он в 1832 году, запа-
тентовал своё изобретение в 1836 году, но публичная демонстрация
телеграфа произошла только 24 мая 1844 года. По телеграфной
линии, соединяющей Вашингтон с Балтимором, была успешно
передана фраза из Библии.
Точки и тире оказались самыми элементарными символами,
которые мог передавать его телеграф. Они соответствовали корот-
ким и длинным импульсам электрического тока, передаваемым
по телеграфным проводам. Длина импульса определялась нажатием
руки телеграфиста на ключ телеграфа. Приём сигнала осуществля-
ло реле, которое после появления в нём импульса тока включало
электромагнит, который либо заставлял стучать молоточек, либо
прижимал колёсико с красящей лентой к бумажной ленте, на ко-
торой отпечатывалась либо точка, либо тире в зависимости от дли-
ны импульса.
Азбука Морзе сопоставляет каждой букве алфавита последо-
вательность из точек и тире. Естественней всего использовать такие
последовательности длины 6, их всего 64 и хватит даже на русский
алфавит. Но Морзе понимал, что длину сообщения желательно
уменьшить, насколько возможно, поэтому он решил использовать
последовательности длины не более 4, их всего 2+4+8+16=30.
В русском алфавите пришлось не использовать буквы <э> и <ё>
и отождествить мягкий и твёрдый знаки. Кроме того, наиболее
часто используемым буквам он предложил давать самые короткие
коды, чтобы уменьшить среднюю длину передаваемого сообщения.
Эту идею в наше время используют с той же целью в алфавитном
кодировании.
Здесь имеет смысл ввести терминологию теории кодирования.
Определение алфавитного кодирования очень просто. Пусть, на-
пример, кодирующим алфавитом является двухбуквенный алфа-
вит, например, состоящий из символов 0, 1. Схемой алфавитного
кодирования называется отображение каждой буквы кодируемого
алфавита в некоторое слово в кодирующем алфавите (называемое
элементарным кодом), в рассматриваемом случае — последователь-
ность нулей или единиц. Пользуясь этой схемой, можно закодиро-
вать любое слово в кодируемом алфавите, заменяя в нём каждую
букву на соответствующий ей элементарный код, и превратить
исходное слово в более длинное слово в кодирующем алфавите.
Таким образом, и код Брайля, и азбука Морзе являются алфавит-
ными кодами.
Удобнее всего задать код Морзе в виде четырёхярусного двоич-
ного дерева. Из корня дерева выходят два ребра, из которых пра-
вому соответствует тире, а левому — точка. Это — рёбра первого
яруса. Из их концов тоже аналогичным образом выходят по два
ребра. Это — рёбра второго яруса. Дерево рисуем до четвёртого
23
Ш Ч Щ З Ы Ц Ь Б Й П Я Л Ю Ф Ж Х


О Г К Д В Р У С


М Н А И

Т Е


Рис. 6


яруса. Вершинам дерева (за исключением корня) приписываем
буквы алфавита (рис. 6). Тогда каждой букве можно сопоставить
последовательность точек или тире, получающуюся, если выпи-
сать друг за другом последовательность символов, сопоставленных
рёбрам дерева, образующим путь, идущий из корня к вершине
дерева, соответствующей данной букве.
Очевидно, что алфавитный код должен обладать свойством од-
нозначной декодируемости, т. е. разные слова в исходном алфавите
не могут иметь одинаковые коды. А так как процедуру деко-
дирования можно представлять как поиск разбиения закодиро-
ванного слова на элементарные коды, то это разделение должно
быть однозначным. Поэтому однозначно декодируемые коды иногда
называют разделимыми кодами. Ясно, что если все элементарные
коды имеют одинаковую длину, то код разделим и алгоритм деко-
дирования очень прост. Но если это не так, то код может и не быть
разделимым. Например, таким является код Морзе. Но между
словами телеграфисты всегда делали промежутки, поэтому никаких
проблем не возникало. Однако если промежутки между словами
выделять невозможно, приходится использовать только раздели-
мые коды. А пустую букву, изображающую промежуток между
словами, часто включают в состав алфавита, что даёт возможность
всегда иметь дело не с предложениями, а только со словами.
Понять по достаточно сложному алфавитному коду, являет-
ся ли он разделимым, бывает не просто. Известны несколько разных
алгоритмов для проверки разделимости кода. Наиболее наглядный
из них принадлежит А. А. Маркову*).
Не вдаваясь в подробности, ограничимся замечанием, что код,
у которого ни один из элементарных кодов не является началом
другого (такие коды принято называть префиксными), несомненно
является разделимым. Предоставим доказательство этой теоремы
читателю. Очевидным примером префиксного кода является лю-

*) Заинтересовавшегося этими вопросами читателя мы отсылаем к книге
А. А. Маркова <Теория алгорифмов>, М.: Наука, 1984; М.: Фазис, 1996.
24
бой код с равными длинами кодовых слов. Код Морзе префиксным
не является, что также предоставляется проверить читателю. Лю-
бой двоичный префиксный код можно задать подобно коду Морзе
с помощью двоичного дерева, не обязательно такого равномерно-
го, как у него, но при этом буквы кодируемого алфавита должны
сопоставляться только <листьям> дерева, но никак не внутренним
вершинам.
Возвращаясь к истории алфавитного кодирования, заметим,
что его корни уходят в глубь веков. Фактически первый при-
мер применения алфавитного кодирования был описан древнегре-
ческим историком Полибием. Алфавит записывался в квадратную
таблицу 5?5 и каждая буква шифровалась парой своих коорди-
нат (i, j) (номерами строки и столбца), а передаваться сообщения
могли в то время с помощью факелов — i факелов в левой руке
и j факелов в правой означали пару (i, j).
Дальнейшее развитие идеи алфавитного кодирования принад-
лежит знаменитому английскому философу, эзотерику и писателю
сэру Френсису Бэкону, который первым начал использовать двоич-
ный алфавит в качестве шифроалфавита. В криптографии, правда,
это не нашло особого применения, главным образом из-за пяти-
кратного удлинения шифртекста в сравнении с открытым текстом.
Но сам Бэкон предложил использовать его как метод, сочетающий
криптографию со стеганографией (так называется скрытие самого
факта передачи секретного сообщения).
Вместо двоичных цифр он использовал обычный алфавит,
но со шрифтами двух типов. Таким методом можно было в любом
тексте спрятать шифровку, если, конечно, шрифты были достаточно
мало различимы. Желательно при этом использовать разделимый
код. Длина зашифрованного сообщения будет в несколько раз ко-
роче, чем длина содержащего его (и одновременно маскирующего
его) текста, но если для передачи шифровки использовать книгу,
то в ней можно таким образом незаметно разместить ещё целую
книгу. Но эта красивая идея из-за дороговизны её реализации так
и не нашла применения. В наше же время её нельзя рассматривать
как серьёзный метод.
Интересно, что в XIX веке, главным образом в кругах, инте-
ресующихся наследием возникшего в средневековье тайного ми-
стического ордена розенкрейцеров, появилась идея, что Френсис
Бэкон, которого считали розенкрейцером, является настоящим
автором пьес Шекспира. Начали искать подтверждение этого
в шифрах, которые мог оставить Бэкон в своих книгах, а также
в первом знаменитом издании пьес Шекспира. Было, естественно,
найдено много таких, якобы зашифрованных фрагментов. Серьёзные
исследователи, правда, замечали, что в любом длинном тексте можно
при желании и некоторых натяжках найти короткие фрагменты,
25
напоминающие шифры. Но у сторонников авторства Бэкона стрем-
ление доказать это криптографическим методом приняло форму мании.
Американский миллионер Фабиан даже создал в начале XX века
на свои деньги лабораторию криптоанализа, которая занималась
только подобными исследованиями.
Фабиан нанял на работу дипломированного генетика Уильяма
Фридмана, сына эмигрантов из России. Через некоторое время
Фридман уже возглавлял у Фабиана и лабораторию генетики,
и лабораторию криптоанализа. Доказать авторство Бэкона он не смог,
более того, он впоследствии опубликовал книгу, где опровергал
возможность такого криптографического доказательства. Но он
не на шутку увлёкся криптографией и своей подчинённой Элизабет
Смит, с которой обвенчался в 1917 году. Они стали самой знаменитой
супружеской парой в истории криптографии. После вступления
Америки в войну у него с супругой появилась серьёзная работа
по правительственным заказам. После войны он ушёл от Фабиана,
и стал главным криптографом войск связи.

§ 8. ФОТОПЛЁНКА И ШТРИХ-КОД
Рассмотрим теперь некоторые примеры реального применения
двоичного кодирования в современной технике.
Как автоматические фотоаппараты узнают светочувствительность
заправленной в них плёнки? Её измеряют в некоторых единицах, и вся
выпускаемая сейчас в мире плёнка имеет одно из 24 стандартных
значений светочувствительности. Эти значения кодируются некото-
рым стандартным образом наборами из нулей и единиц, естественно,
длины 5. На поверхности кассеты для плёнки нанесены 12 квадратиков
чёрного или серебристого цвета, образующих прямоугольник 2?6.
Квадратики его верхней части мысленно занумеруем от 1 до 6,
начиная слева. Квадратики нижней части аналогично занумеруем
от 7 до 12. Серебристые квадратики — это просто металлическая
поверхность кассеты, она проводит ток, который с контакта внутри
аппарата подаётся на первый квадрат (он всегда серебристый).
Чёрные квадраты покрыты краской, не проводящей ток.
Когда плёнка вставляется в аппарат, шесть его контактов со-
прикасаются с шестью первыми квадратиками, и с квадратиков
со 2-го по 6-й снимается информация — нуль, если квадратик
чёрный и ток по соответствующему контакту не идёт, и единица
в противном случае. Вся информация о светочувствительности
плёнки заключена в квадратиках со 2-го по 6-й. В остальных ква-
дратиках заключена информация о числе кадров в плёнке и т. п.
Ещё на поверхности кассеты можно увидеть штрих-код. Это так
называемый универсальный код продукта, он сейчас ставится на всех
продаваемых товарах. Для чего он нужен и как его прочитать?
26
Нужен он только для автоматического занесения информации
в кассовый аппарат. Сам штрих-код состоит из тридцати чёрных
полос переменной толщины, разделённой промежутками тоже
переменной толщины. Толщина полос может принимать четыре
значения от самой тонкой до самой толстой. Такую же толщину
могут иметь и промежутки. Когда по сканеру проводят штрих-кодом,
он воспринимает каждую чёрную полоску как последовательность
единиц длины от одной до четырёх, и также воспринимает проме-
жутки между полосами, но при этом вместо единиц сканер видит
нули. Полностью весь штрих-код сканер воспринимает как после-
довательность из 95 цифр 0 или 1 (их давно уже принято назы-
вать битами). Что же содержит этот код? Он кодирует 13-разряд-
ное десятичное число, совершенно открыто написанное под самим
штрих-кодом. Если сканер не смог распознать штрих-код, то это
число кассир вводит в аппарат вручную. Штрих-код нужен лишь
для облегчения распознавания сканером изображения. Распозна-
вать цифры, к тому же повёрнутые боком, может только сложная
программа распознавания на универсальном компьютере, да и то
не очень надёжно, а не кассовый аппарат.
Какую же информацию содержит это 13-значное число? Этот
вопрос к математике никакого отношения не имеет. Первая цифра
задаёт тип товара, например, у товаров переменного веса она равна 2.
Следующие пять цифр — это код производителя, а следующие
пять цифр — код самого продукта в принятой этим производителем
кодировке. Последняя цифра — это код проверки. Он однозначно
вычисляется по предыдущим 12 цифрам следующим образом. Нужно
сложить все цифры с нечётными номерами, утроить сумму, к ней
прибавить сумму оставшихся цифр, а полученный результат вычесть
из ближайшего (большего) кратного 10 числа.
А вот 95-битный код, соответствующий штрих-коду, более
интересен. Он содержит в себе только указанное 12-значное число
(контрольная цифра в самом штрих-коде не содержится), но с боль-
шой избыточностью. Первые три бита в нём, так же, как и по-
следние — это всегда 101. Они нужны только для того, чтобы ска-
нер смог определить ширину полосы, соответствующей одному би-
ту (ведь размеры штрих-кода на разных упаковках могут быть раз-
ными) и настроиться на распознавание. В центре кода всегда стоит
комбинация 01010, а левая и правая части кода состоят каждая
из шести блоков по семь битов и содержат информацию о левых
шести и правых шести из данных 12 десятичных цифр. Централь-
ная комбинация позволяет, в частности, отличать поддельные или
плохо напечатанные коды.
Цифры 13-значного кода кодируются в левой и правой частях
штрих-кода по-разному. В левой половине каждая цифра коди-
руется семёркой битов, начинающейся с 0 и заканчивающейся 1
27
согласно следующей таблице:
=0001101=0, =0111101=3, =0111011=7,
=0011001=1, =0100011=4, =0110111=8,
=0010011=2, =0110001=5, =0001011=9.
=0101111=6,
В правой половине каждая цифра кодируется семёркой битов, на-
чинающейся с 1 и заканчивающейся 0 согласно таблице, кото-
рая получается из вышеприведённой, если в ней нули заменить
на единицы и единицы на нули (это переход к дополнительному
коду). Можно заметить, что каждый из кодов в таблице содержит
нечётное число единиц и ровно две группы рядом стоящих единиц
и ровно две группы рядом стоящих нулей. Это означает, что каж-
дая цифра соответствует двум соседним полосам на штрих-коде.
Но более важно то обстоятельство, что все десять кодов таблицы,
будучи прочитанными не слева направо, а справа налево, будут от-
личаться от любого из кодов таблицы, прочитанного правильным
образом. Очевидно, таблица для правой половины кода обладает
теми же свойствами, только число единиц в каждом коде чётное.
Такая избыточная (не четырёхбитовая, а семибитовая) табли-
ца кодов нужна для того, чтобы сканер мог правильно прочитать
штрих-код и в случае, когда код направляют в него <вверх но-
гами>. Как сканер может отличать одно направление от другого?
По чётности или нечётности числа единиц в первом же прочитан-
ном семибитовом блоке, идущем после комбинации 101. При пра-
вильном направлении оно будет нечётным, а при обратном напра-
влении — чётным. Перепутать же коды, прочитанные слева, и ко-
ды, прочитанные справа, согласно свойству таблицы, невозможно.
Если же в каком-то из семибитовых блоков нарушено правиль-
ное чередование нулей и единиц в первом и последнем битах или
ему не соответствует чётность числа единиц, то штрих-код при-
знаётся поддельным или плохо пропечатанным.

§ 9. ЗАДАЧИ О ПЕРЕЛИВАНИЯХ
На одной из Всесоюзных математических олимпиад была пред-
ложена следующая задача. В три сосуда налито по целому числу
литров воды. В любой сосуд разрешается перелить столько воды,
сколько в нём уже содержится, из любого другого сосуда. Каждый
из сосудов может вместить всю имеющуюся в них воду. Докажите,
что можно несколькими переливаниями освободить один из сосудов.
В её решении неожиданно на первый взгляд применяется дво-
ичная система. Так как задача оказалась очень трудной (на олим-
пиаде её никто не решил), мы приведём здесь это решение. В нём
используются две идеи. Первая из них заключается в том, что если
будет найден алгоритм переливания, после применения которого ми-
28
нимальный объём воды, содержащейся в одном из сосудов, умень-
шается, то, повторяя многократно этот алгоритм, мы опорожним
один из сосудов. Эта идея не такая простая, как может показать-
ся. Ведь это не что иное, как метод бесконечного спуска П. Ферма.
Идея применения двоичной системы лежит в основе этого алго-
ритма уменьшения минимума. Пусть в сосудах A, B, C находится
a?b?c литров воды. Разделим b на a с остатком, b=aq+r,
0?r<a и предложим алгоритм, после применения которого в со-
суде B останется r литров. Для этого представим q в виде суммы
различных степеней двойки: q=2d1 +...+2dk . Выливая из сосуда C
воду d1 раз подряд в сосуд A, получим в нём 2d1 a литров, а вы-
ливая после этого в него 2d1 a литров из сосуда B, получаем в нём
b?2d1 a=a(q?2d1 )+r=a(2d2 +...+2dk )+r литров. Аналогично,
выливая из сосуда C воду d2 ?d1 ?1 раз подряд в сосуд A, а потом
выливая в него воду из сосуда B, получаем в нём a(2d2 +...+2dk )+
+r?2d2 a=a(2d3 +...+2dk )+r литров. Повторяя эту процедуру, по-
лучим, что в конце концов в сосуде B окажется r литров воды.
Нужно ещё заметить, что во время каждой процедуры из сосу-
да C выливалось меньше воды, чем из сосуда B, так как 2+22 +...
...+2l?1 <2l . Поэтому всего из сосуда C вылито воды меньше, чем
из B, значит оба они не опорожнятся раньше времени, и алгоритм
работает корректно.
Приведённую выше задачу можно обобщить и на большее
количество сосудов. Применив к любым трём из них указанный
алгоритм, один из сосудов опорожним. Повторяя эту процедуру
ещё раз, опорожним ещё один сосуд и т. д., пока не останутся
заполненными только два сосуда.
Предоставляем читателю самостоятельно выяснить, что будет
происходить, если продолжить переливания с двумя оставшимися
сосудами.
Выше указывалось, что при решении некоторых задач о пе-
реливаниях можно использовать аддитивные цепочки. Предлага-
ем читателю для самостоятельного решения одну из таких задач.
11. Как быстрее всего наполнить флягу 85 литрами моло-
ка, пользуясь однолитровым черпаком, если есть ещё одна та-
кая же фляга и весы, способные только сравнивать массы фляг?
Классические задачи о переливаниях выглядят несколько по-
другому, и метод их решения не связан с двоичной системой.
Примером такой задачи, решение которой по преданию послу-
жило знаменитому французскому математику Пуассону толчком
к выбору его профессии, является вопрос о том, как, имея полные
сосуды в 3 и 5 литров и пустой 8-литровый сосуд, отмерить ров-
но 4 литра. Читателю предоставляется возможность самостоятель-
но придумать метод решения подобных задач за наименьшее ко-
личество переливаний.
29
§ 10. ИГРА <НИМ>
Двоичная система находит неожиданное применение при ана-
лизе известной игры <Ним>. Происхождение её, так же, как и шах-
мат, покрыто туманом. Возможно, она была изобретена в Китае.
Состоит она в следующем: на столе лежит несколько кучек спи-
чек, и два игрока по очереди выбирают одну из кучек и забирают
из неё сколько угодно спичек (хоть все); выигрывает тот, кто заби-
рает последнюю (есть вариант игры, в котором забравший послед-
нюю проигрывает). Эпизод с этой игрой неоднократно повторяется
в известном французском фильме <Прошлым летом в Мариенбаде>.

стр. 1
(всего 2)

СОДЕРЖАНИЕ

>>