Системы счисления и их применение

§ 7. Книга Перемен, азбука Морзе, шрифт Брайля и алфавитные коды

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

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

Книга Перемен очень древняя, возможно, одна из древнейших в мире, и кто ее написал — неизвестно. Она использовалась ранее и используется в настоящее время, в том числе и на Западе, для гадания. В Европе с аналогичной целью используются карты Таро. В чем-то обе эти системы похожи, но Таро никак не связаны с двоичной системой, поэтому о них мы говорить не будем.

Способ гадания по Книге Перемен в кратком изложении таков. Бросается шесть раз монета (или лучше пуговица, деньги в гадании применять не рекомендуется) и по полученным результатам (орел или решка) разыскивается подходящая гексаграмма (для этого надо заранее сопоставить орлу и решке янь или инь). По гексаграмме разыскиваете соответствующий раздел Книги Перемен (имеется перевод выдающегося синолога Ю.К. Шуцкого, неоднократно переиздававшийся в последнее время) и читаете, что там написано.

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

Заинтересованного читателя отсылаем к книгам Дж.Х. Бреннана «Таинственный И-цзин» (М.: Гранд, 2001); В. Фирсова «Книга Перемен. Мистика и магия древнего Китая» (М.: Центрполиграф, 2002) и переходим к другой теме — азбуке для слепых.

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

Капитан французской армии Шарль Барбье в 1819 году предложил печатать выпуклыми не буквы, а точки и тире (или просто продавливать их на бумаге) и ими уже записывать буквы. Эту систему он назвал «ночное письмо» и предлагал вовсе не для слепых, а для использования в военно-полевых условиях. С появлением электрических фонариков военное значение этого изобретения упало до нуля.

Слепой мальчик Луи Брайль познакомился с этой системой в 12 лет. Она ему понравилась тем, что позволяла не только читать, но и писать. В течение трех лет он ее усовершенствовал и создал так называемый шрифт Брайля. В нем символы языка (буквы, знаки препинания и цифры) кодируются комбинациями от одной до шести выпуклых точек, расположенных в виде таблицы стандартного размера с тремя строчками и двумя столбцами. Элементы (точки) таблицы нумеруются числами 1, 2, 3 в первом столбце сверху вниз и 4, 5, 6 во втором столбце сверху вниз. Каждая точка либо продавливается специальной машинкой (или даже шилом) или остается целой. Всего различных способов продавить выпуклые точки в этой таблице 64 (в том числе и тот, в котором ни одна из точек не продавлена). При желании теперь читатель может сопоставить каждому символу алфавита Брайля одну из гексаграмм Книги Перемен. Вряд ли, конечно, Брайль знал об этой книге.

Вероятно, не имеет смысла описывать все символы шрифта Брайля, тем более что после его смерти в 1852 году шрифт дополнялся и совершенствовался. Но несколько слов сказать, видимо, стоит. Буква «а», например, изображается одной выпуклой точкой в 1-м элементе таблицы, буква «б» изображается выпуклыми точками в 1-м и 2-м элементах таблицы и т.д. Для сокращения текстов некоторые часто встречающиеся слова или комбинации букв кодируются специальными таблицами. Для того чтобы отличать заглавную букву от строчной, перед ней ставят специальную таблицу, изображающую то, что сейчас называют эскейп-символом. Многие таблицы имеют несколько значений (например, буква и какой-нибудь специальный знак или знак препинания), выбор из которых делается в соответствии с контекстом. Цифры кодируются так же, как и первые буквы алфавита, чтобы их отличать, перед последовательностью цифр ставится специальный символ — признак числа, и заканчивается число символом отмены признака числа.

Азбука Брайля по известности уступает азбуке Морзе, хотя и применяется до сих пор в отличие от последней. Сэмюэль Морзе известен, однако, не только изобретением азбуки. Он был и художником-портретистом (его картина «Генерал Лафайет» до сих пор висит в нью-йоркском Сити-Холле ¹) и одним из первых фотографов в Америке (учился делать дагерротипные фотографии у самого Луи Дагерра), и политиком (он баллотировался в 1836 году на пост мэра Нью-Йорка), но самое главное его достижение — изобретение телеграфа (а азбука Морзе понадобилась ему для использования телеграфа). Заодно он изобрел устройство, которое называется реле. Именно из реле спустя сто лет после Морзе были построены первые компьютеры.

Начал свои работы в этом направлении он в 1832 году, запатентовал свое изобретение в 1836 году, но публичная демонстрация телеграфа произошла только 24 мая 1844 года. По телеграфной линии, соединяющей Вашингтон с Балтимором, была успешно передана фраза из Библии.

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

Азбука Морзе сопоставляет каждой букве алфавита последовательность из точек и тире. Естественней всего использовать такие последовательности длины 6, их всего 64 и хватит даже на русский алфавит. Но Морзе понимал, что длину сообщения желательно уменьшить, насколько возможно, поэтому он решил использовать последовательности длины не более 4, их всего 2 + 4 + 8 + 16 = 30. В русском алфавите пришлось не использовать буквы «э» и «ё» и отождествить мягкий и твердый знаки. Кроме того, наиболее часто используемым буквам он предложил давать самые короткие коды, чтобы уменьшить среднюю длину передаваемого сообщения. Эту идею в наше время используют с той же целью в алфавитном кодировании.

Здесь имеет смысл ввести терминологию теории кодирования. Определение алфавитного кодирования очень просто. Пусть, например, кодирующим алфавитом является двухбуквенный алфавит, например, состоящий из символов 0, 1. Схемой алфавитного кодирования называется отображение каждой буквы кодируемого алфавита в некоторое слово в кодирующем алфавите (называемое элементарным кодом), в рассматриваемом случае — последовательность нулей или единиц. Пользуясь этой схемой, можно закодировать любое слово в кодируемом алфавите, заменяя в нем каждую букву на соответствующий ей элементарный код, и превратить исходное слово в более длинное слово в кодирующем алфавите. Таким образом, и код Брайля, и азбука Морзе являются алфавитными кодами.

Удобнее всего задавать код Морзе в виде четырехярусного двоичного дерева. Из корня дерева выходят два ребра, из которых правому соответствует тире, а левому — точка. Это — ребра первого яруса. Из их концов тоже аналогичным образом выходят по два ребра. Это — ребра второго яруса. Дерево рисуем до четвертого яруса. Вершинам дерева (за исключением корня) приписываем буквы алфавита (рис. 6). Тогда каждой букве можно сопоставить последовательность точек или тире, получающуюся, если выписать друг за другом последовательность символов, сопоставленных ребрам дерева, образующим путь, идущий из корня к вершине дерева, соответствующей данной букве.

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

Понять по достаточно сложному алфавитному коду, является ли он разделимым, бывает непросто. Известны несколько разных алгоритмов для проверки разделимости кода. Наиболее наглядный из них принадлежит А.А. Маркову ².

Не вдаваясь в подробности, ограничимся замечанием, что код, у которого ни один из элементарных кодов не является началом другого (такие коды принято называть префиксными), несомненно, является разделимым. Предоставим доказательство этой теоремы читателю. Очевидным примером префиксного кода является любой код с равными длинами кодовых слов. Код Морзе префиксным не является, что также предоставляется проверить читателю. Любой двоичный префиксный код можно задать подобно коду Морзе с помощью двоичного дерева, не обязательно такого равномерного, как у него, но при этом буквы кодируемого алфавита должны сопоставляться только «листьям» дерева, но никак не внутренним вершинам.

Возвращаясь к истории алфавитного кодирования, заметим, что его корни уходят в глубь веков. Фактически первый пример применения алфавитного кодирования был описан древнегреческим историком Полибием. Алфавит записывался в квадратную таблицу 5 ´ 5 и каждая буква шифровалась парой своих координат (i; j) (номерами строки и столбца), а передаваться сообщения могли в то время с помощью факелов — i факелов в левой руке и j факелов в правой означали пару (i; j).

Дальнейшее развитие идеи алфавитного кодирования принадлежит знаменитому английскому философу, эзотерику и писателю сэру Френсису Бэкону, который первым начал использовать двоичный алфавит в качестве шифроалфавита. В криптографии, правда, это не нашло особого применения, главным образом из-за пятикратного удлинения шифротекста в сравнении с открытым текстом. Но сам Бэкон предложил использовать его как метод, сочетающий криптографию со стеганографией (так называется сокрытие самого факта передачи секретного сообщения).

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

Интересно, что в XIX веке, главный образом в кругах, интересующихся наследием возникшего в средневековье тайного мистического Ордена розенкрейцеров, появилась идея, что Френсис Бэкон, которого считали розенкрейцером, является настоящим автором пьес Шекспира. Начали искать подтверждение этого в шифрах, которые мог оставить Бэкон в своих книгах, а также в первом знаменитом издании пьес Шекспира. Было, естественно, найдено много таких, якобы зашифрованных, фрагментов. Серьезные исследователи, правда, замечали, что в любом длинном тексте можно при желании и некоторых натяжках найти короткие фрагменты, напоминающие шифры. Но у сторонников авторства Бэкона стремление доказать это криптографическим методом приняло форму мании. Американский миллионер Фабиан даже создал в начале XX века на свои деньги лабораторию криптоанализа, которая занималась только подобными исследованиями.

Фабиан нанял на работу дипломированного генетика Уильяма Фридмана, сына эмигрантов из России. Через некоторое время Фридман уже возглавлял у Фабиана и лабораторию генетики, и лабораторию криптоанализа. Доказать авторство Бэкона он не смог, более того, он впоследствии опубликовал книгу, где опровергал возможность такого криптографического доказательства. Но он не на шутку увлекся криптографией и своей подчиненной Элизабет Смит, с которой обвенчался в 1917 году. Они стали самой знаменитой супружеской парой в истории криптографии. После вступления Америки в войну у него с супругой появилась серьезная работа по правительственным заказам. После войны он ушел от Фабиана и стал главным криптографом войск связи.

§ 8. Фотопленка и штрих-код

Рассмотрим теперь некоторые примеры реального применения двоичного кодирования в современной технике.

Как автоматические фотоаппараты узнают светочувствительность заправленной в них пленки? Ее измеряют в некоторых единицах, и вся выпускаемая сейчас в мире пленка имеет одно из 24 стандартных значений светочувствительности. Эти значения кодируются некоторым стандартным образом наборами из нулей и единиц, естественно, длины 5. На поверхности кассеты для пленки нанесены 12 квадратиков черного или серебристого цвета, образующих прямоугольник 2x6. Квадратики его верхней части мысленно занумеруем от 1 до 6, начиная слева. Квадратики нижней части аналогично занумеруем от 7 до 12. Серебристые квадратики — это просто металлическая поверхность кассеты, она проводит ток, который с контакта внутри аппарата подается на первый квадрат (он всегда серебристый). Черные квадраты покрыты краской, не проводящей ток.

Когда пленка вставляется в аппарат, шесть его контактов соприкасаются с шестью первыми квадратиками, и с квадратиков со 2-го по 6-й снимается информация — нуль, если квадратик черный и ток по соответствующему контакту не идет, и единица в противном случае. Вся информация о светочувствительности пленки заключена в квадратиках со 2-го по 6-й. В остальных квадратиках заключена информация о числе кадров в пленке и т.п.

Еще на поверхности кассеты можно увидеть штрих-код. Это так называемый универсальный код продукта, он сейчас ставится на всех продаваемых товарах. Для чего он нужен и как его прочитать?

Нужен он только для автоматического занесения информации в кассовый аппарат. Сам штрих-код состоит из тридцати черных полос переменной толщины, разделенных промежутками тоже переменной толщины. Толщина полос (от самой тонкой до самой толстой) может принимать четыре значения. Такую же толщину могут иметь и промежутки. Когда по сканеру проводят штрих-кодом, он воспринимает каждую черную полоску как последовательность единиц длины от одной до четырех, и также воспринимает промежутки между полосками, но при этом вместо единиц сканер видит нули. Полностью весь штрих-код сканер воспринимает как последовательность из 95 цифр 0 или 1 (их давно уже принято называть битами). Что же содержит этот код? Он кодирует 13-разрядное десятичное число, совершенно открыто написанное под самим штрих-кодом. Если сканер не смог распознать штрих-код, то это число кассир вводит в аппарат вручную. Штрих-код нужен лишь для облегчения распознавания сканером изображения. Распознавать цифры, у тому же повернутые боком, может только сложная программа распознавания на универсальном компьютере, да и то не очень надежно, а не кассовый аппарат.

Какую же информацию содержит это 13-значное число? Этот вопрос к математике никакого отношения не имеет. Первая цифра задает тип товара, например, у товаров переменного веса она равна 2. Следующие пять цифр — это код производителя, а следующие пять цифр — код самого продукта в принятой этим производителем кодировке. Последняя цифра — это код проверки. Он однозначно вычисляется по предыдущем 12 цифрам следующим образом. Нужно сложить все цифры с нечетными номерами, утроить сумму, к ней прибавить сумму оставшихся цифр, а полученный результат вычесть из ближайшего (большего) кратного 10 числа.

А вот 95-битный код, соответствующий штрих-коду, более интересен. Он содержит в себе только указанное 12-значное число (контрольная цифра в самом штрих-коде не содержится), но с большой избыточностью. Первые три бита в нем, так же как и последние, — это всегда 101. Они нужны только для того, чтобы сканер мог определить ширину полосы, соответствующей одному биту (ведь размеры штрих-кода на разных упаковках могут быть разными) и настроиться на распознавание. В центре кода всегда стоит комбинация 01010, а левая и правая части кода состоят каждая из шести блоков по семь битов и содержат информацию о левых шести и правых шести из данных 12 десятичных цифр. Центральная комбинация позволяет, в частности, отличать поддельные или плохо напечатанные коды.

Цифры 13-значного кода кодируются в левой и правой частях штрих-кода по-разному. В левой половине каждая цифра кодируется семеркой битов, начинающейся с 0 и заканчивающейся 1 согласно следующей таблице:

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

Такая избыточная (не четырехбитовая, а семибитовая) таблица кодов нужна для того, чтобы сканер мог правильно прочитать штрих-код и в случае, когда код направляют в него «вверх ногами». Как сканер может отличать одно направление от другого? По четности или нечетности числа единиц в первом же прочитанном семибитовом блоке, идущем после комбинации 101. При правильном направлении оно будет нечетным, а при обратном направлении — четным. Перепутать же коды, прочитанные слева, и коды, прочитанные справа, согласно свойству таблицы, невозможно.

Если же в каком-то из семибитовых блоков нарушено правильное чередование нулей и единиц в первом и последнем битах или ему не соответствует четность числа единиц, то штрих-код признается поддельным или плохо пропечатанным.

§ 9. Задачи о переливаниях

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

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

Идея применения двоичной системы лежит в основе этого алгоритма уменьшения минимума. Пусть в сосудах A, B, C находится a ≤ b ≤ c литров воды. Разделим b на a
с остатком, b = aq + r, 0 ≤ r < a, и предложим алгоритм, после применения которого в сосуде B останется r литров воды. Для этого представим q в виде суммы различных степеней двойки: Выливая из сосуда C воду d₁ раз подряд в сосуд A, получим в нем литров, а выливая после этого в него литров из сосуда B, получаем в нем

литров. Аналогично, выливая из сосуда C воду d₂ – d₁ – 1 раз подряд в сосуд A, а потом выливая в него воду из сосуда B, получаем в нем

литров. Повторяя эту процедуру, получим, что в конце концов в сосуде B окажется r литров воды. Нужно еще заметить, что во время каждой процедуры из сосуда C выливалось меньше воды, чем из сосуда B, так как 2 + 2² + ... + 2^l – 1 < 2^l. Поэтому всего из сосуда C вылито воды меньше, чем из B, значит, оба они не опорожнятся раньше времени, и алгоритм работает корректно.

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

Предоставим читателю самостоятельно выяснить, что будет происходить, если продолжить переливания с двумя оставшимися сосудами.

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

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

Классические задачи о переливаниях выглядят несколько по-другому, и метод их решения не связан с двоичной системой.

Примером такой задачи, решение которой, по преданию, послужило знаменитому французскому математику Пуассону толчком к выбору его профессии, является вопрос о том, как, имея полные сосуды в 3 и 5 литров и пустой 8-литровый сосуд, отмерить ровно 4 литра. Читателю предоставляется возможность самостоятельно придумать метод решения подобных задач за наименьшее количество переливаний.

§ 10. Игра «Ним»

Двоичная система находит неожиданное применение при анализе известной игры «Ним». Происхождение ее, так же как и шахмат, покрыто туманом. Возможно, она была изобретена в Китае.

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

Игра «Ним» являлась излюбленной темой математических кружков в МГУ. Иногда она представлялась в виде гонки нескольких пешек от одного края доски до другого. Читатель сам сможет сформулировать правила игры в таком ее представлении.

При игре с одной кучкой, очевидно, побеждает начинающий.

При игре с двумя кучками начинающий побеждает не всегда.

12. Докажите, что выигрывающей позицией является позиция с двумя равными кучками. Игрок, сумевший после своего хода попасть в такую позицию, всегда сможет выиграть.

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

Например, если в кучках было 3, 7, 12, 17 спичек, то покомпонентно складывать придется наборы

Ним-сумма равна 11001, поэтому позиция является проигрышной для того, кто в нее попал после своего хода. Причина в том, что противник может сделать ход, которым он попадет в позицию с нулевой ним-суммой. Для этого он может оставить в последней кучке число спичек, равное в двоичной записи ним-суммы наборов 10001 и 11001, то есть 01000. Тогда ним-сумма чисел, образующих новую позицию, будет равна ненулевому набору, так как эта сумма будет отличаться от прежней суммы 11001 прибавлением к ней по модулю 2 набора 11001, что дает в результате, очевидно, нулевой набор. Поскольку 01000 = 8, из последней кучки надо взять 17 – 8 = 9 спичек.

13. Докажите в общем случае, что из позиции с ненулевой ним-суммой за один ход можно попасть в позицию с нулевой ним-суммой, а из позиции с нулевой ним-суммой любой ход ведет к позиции с ненулевой ним-суммой.

Теперь ясно, что тот, что первым попал в позицию с нулевой ним-суммой, дальше, при любой игре противника, при своем ходе опять сможет попасть в такую же позицию, и в конце концов он возьмет последнюю спичку.

Указанная выигрышная стратегия поддается для реализации даже на специализированных машинах. Одна из таких машин была выставлена после войны в Берлине на английской выставке и с успехом конкурировала с находящимся рядом бесплатным пивным залом. Знаменитый английский математик Алан Тьюринг вспоминал о том, как популярность этой машины повысилась еще больше после победы над тогдашним бундесминистром экономики Л. Эрхардом.

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

Более интересная модификация игры ним получается, если ограничить число спичек, которые можно взять за один раз, например, числом 10. Тогда интерес представляет даже игра с одной кучкой спичек. Эту игру изобрел в XVII веке французский математик Баше де Мезириак, написавший, кстати, одну из первых в Европе книг по занимательной математике. Читатель может попробовать сам придумать для нее выигрышную стратегию.

---

¹  Известна также его картина «Человек в предсмертной агонии», после просмотра которой его приятель, известный врач, сказал: «По-моему, малярия».
² Заинтересовавшегося этим вопросом читателя мы отсылаем к книге А.А. Маркова «Теория логарифмов» (М.: Наука, 1984; М.: Фазис, 1996).

Гашков С.