Иэн Стюарт - Математические головоломки профессора Стюарта
Правда, я так и не рассказал вам, что такое субфакториал. Ну, ничего, в следующий раз.
Серьезный беспорядок
Пора объяснить, что такое субфакториалы.
Предположим, что у каждой из n дам имеется шляпка. Все они складывают свои шляпки в одно место, затем каждая из них берет какую-нибудь случайную шляпку и надевает на себя. Сколькими способами можно это сделать, чтобы ни на одной из дам не оказалось ее собственной шляпки? Такое размещение называется беспорядком.
К примеру, если дам три – скажем, Александра, Бетани и Валерия, – то шляпки между ними можно распределить шестью способами:
АБВ АВБ БАВ БВА ВАБ ВБА.
Для АБВ и АВБ Александра получает свою собственную шляпку, так что беспорядка не возникает. Для БАВ собственную шляпку получает Валерия, а для ВБА – Бетани. Это оставляет нам два варианта беспорядка: БАВ и ВАБ.
Если дам четыре – предположим, к группе присоединилась еще Грейс – существует 24 варианта расстановки:
однако в 15 из них (вычеркнутые) кто-нибудь из дам получает свою собственную шляпку. (Убираем все с А в первой позиции, с Б во второй, с В в третьей и с Г в четвертой.) В результате получаем 9 вариантов беспорядка.
Число вариантов беспорядка из n объектов и есть субфакториал (обозначается! n или n ¡). У этого понятия множество определений. Простейшее из них, вероятно,
Первые значения этой величины
Бросание монетки – несправедливый жребий
Бросание монетки – фундамент теории вероятностей, поскольку орел или решка выпадают на ней с равной вероятностью. Бросание монетки считается живым воплощением случайности. С другой стороны, моделью монетки может служить простая механическая система, и ее поведение полностью определяется начальными условиями броска – в первую очередь вертикальной скоростью, начальной скоростью вращения и ориентацией оси вращения. Это, собственно говоря, делает движение монетки неслучайным. Так откуда же берется случайность в бросание монетки? Я вернусь к этому вопросу после описания открытия, имеющего ко всему этому непосредственное отношение.
Перси Диаконис, Сьюзен Холмс и Ричард Монтгомери показали, что на самом деле бросание монетки – не совсем «честная» жеребьевка. Существует небольшой, но заметный сдвиг вероятности: при бросании монетка с несколько большей вероятностью падает на ту же сторону, на которой она лежала на большом пальце. В реальности вероятность ее падения именно в таком положении составляет приблизительно 51 %. В своем исследовании ученые предполагали, что монетка при падении не подскакивает, что разумно при падении на землю, особенно в траву, или для того случая, когда ее ловят на лету, но не тогда, когда она падает на деревянный стол.
Вероятность 51 % становится статистически значимой только после примерно 250 000 бросков. Возникает этот сдвиг потому, что ось, вокруг которой вращается монетка, может и не быть горизонтальной. В предельном случае представьте, что ось располагается под прямым углом к монетке, так что монетка, вращаясь, всегда остается горизонтальной, как гончарный круг. В таком случае она всегда будет приземляться той же стороной, которой лежала, то есть вероятность ее непереворачивания составит 100 %. Другой предельный случай – ось горизонтальна, и монетка кувыркается в воздухе. Хотя в принципе конечное состояние монетки в этом случае определяется начальной вертикальной скоростью и скоростью вращения в воздухе, даже небольшие ошибки в этих параметрах приводят к тому, что монетка падает той же стороной кверху лишь в 50 % случаев. При таких бросках небольшие ошибки приводят к случайному взаимодействию механической системы и монетки.
Как правило, ось вращения монетки не находится ни в одном из крайних положений, а расположена в каком-то промежуточном, близком к горизонтали. Поэтому возникает легкий сдвиг вероятности в сторону падения той же стороной вверх. Подробные расчеты дали 51 % вероятности. Эксперименты с монеткобросательным автоматом подтвердили этот результат с разумной достоверностью.
На практике бросание настоящей монетки все-таки дает случайный результат с 50 % вероятностью, причем вовсе не по приведенным причинам. Дело в том, что начальная ориентация монетки на пальце тоже случайна. Если говорить о длинных сериях, то монетка в половине случаев взлетает орлом кверху, а в половине – решкой кверху. Это снимает сдвиг на 1 %, потому что при броске неизвестно, из какого именно положения стартует монетка.
Дополнительную информацию см. в главе «Загадки разгаданные».
Покер по почте
Предположим, что Алиса и Боб – традиционные участники криптографической переписки – хотят сыграть в покер, точнее, в пятикарточный стад. Но Алиса живет в Австралии, в Алис-Спрингс, а Боб – в Англии, в Боббингтоне. Но возможно, они могли бы пересылать друг другу карты по почте? Главная проблема – как раздать карты, то есть дать каждому игроку «в руки» по пять карт. Как могут при этом оба игрока быть уверены, что каждому из них достались карты из одной колоды и что второй игрок их не знает?
Если Боб просто отправит Алисе в конверте пять карт, она не сможет быть уверена, что он их не видел; более того, когда Боб выкладывает карты, которые будто бы находятся у него на руках, она не может быть уверена, действительно ли у него только пять карт, или в его распоряжении находится вся остальная колода и он только делает вид, что использует только законные пять карт, сданные ему в начале игры.
Как ни удивительно, способ играть в такие карточные игры, как покер, по переписке, по телефону или через Интернет существует, причем без всякой опасности, что кто-то из игроков при этом обманывает. Алиса и Боб могут создать шифр, воспользовавшись теорией чисел, и прибегнуть к сложному обмену посланиями. Такой метод известен как «протокол с нулевым разглашением» – способ убедить собеседника в том, что ты обладаешь каким-то конкретным знанием, не раскрывая, в чем это знание состоит. Так, вы могли бы убедить онлайновую банковскую систему в том, что знаете секретный код, записанный на обороте кредитной карты, не передавая при этом никакой полезной информации о самом коде.
Гостиницы часто хранят ценности гостей в небольших сейфовых ячейках в холле. Для обеспечения безопасности каждая такая ячейка снабжается двумя ключами: один хранится у администратора, другой выдается постояльцу. Чтобы открыть сейф, необходимы оба ключа. Алиса и Боб могут воспользоваться аналогичной схемой:
1. Алиса раскладывает карты по одной в 52 ящичка и запирает их на кодовые замки, ключи к которым известны только ей. Затем она почтой пересылает все ящички Бобу.
2. Боб (который не может отпереть ящички и посмотреть, что за карты в них лежат) выбирает пять ящичков и высылает обратно Алисе. Она отпирает их и получает свои пять карт.
3. Боб выбирает другие пять ящичков и накладывает на каждый из них дополнительный замок. Он знает коды этих замков, Алисе же они неизвестны. Боб высылает эти ящички Алисе.
4. Алиса отпирает свои замки и возвращает ящички Бобу. Теперь он может отпереть их и получить свои пять карт.
После этих предварительных действий может начаться собственно игра. Чтобы раскрыть карты, их пересылают второму игроку. Чтобы доказать, что никто не мошенничал, можно вскрыть все оставшиеся ящички после окончания игры.
Алиса и Боб перевели свою методику игры на язык математики, выделив ее существенные черты. Они представили карточную колоду согласованным набором из 52 чисел. Кодовые замки Алисы обозначаются шифром A, известным только ей. Это функция, математическое правило, превращающее число карты c в другое число Ac. (Я беру на себя вольность не писать всякий раз A (c), чтобы не пришлось говорить о «композиции» функций.) Алисе известен также обратный шифр A–1, который переводит Ac обратно в c. То есть
A−1Ac = c.
Боб не знает ни A, ни A–1.
Аналогично замки Боба соответствуют шифрам B и B–1, известным только ему, таким, что B–1Bc = c.
С учетом этих предварительных замечаний метод соответствует следующей процедуре:
1. Алиса пересылает все 52 числа Ac1, …, Ac52 Бобу. Он понятия не имеет, каким картам эти числа соответствуют; по существу, Алиса перетасовала колоду.
