Джордан Элленберг - Как не ошибаться. Сила математического мышления

Код Хэмминга прекрасно подходит для трансильванской лотереи, но он неэффективен в случае лотереи Cash WinFall. В трансильванской лотерее всего семь чисел, в лотерее штата Массачусетс их сорок шесть. Следовательно, нам понадобится код побольше. Лучший код, который мне удалось найти для этой цели, открыл в 1976 году Ральф Деннистон из Лестерского университета {199}. И это очень красивый код.

Деннистон составил список из 285 384 комбинаций шести чисел из сорока восьми. Этот список начинается так:

1 2 48 3 4 8

2 3 48 4 5 9

1 2 48 3 6 32

В первых двух билетах четыре общие числа: 2, 3, 4 и 48. Однако (в этом и заключается поразительная особенность системы Деннистона) среди всех этих 285 384 лотерейных билетов вы не найдете пяти совпадающих чисел. Систему Деннистона можно перевести в код, как мы сделали это с плоскостью Фано, – заменив числа каждого билета строкой из 48 единиц и нулей, в которой 0 стоит на позициях, соответствующих числам вашего билета, а 1 – на позициях, соответствующих числам, которых в билете нет. Таким образом, первый билет из приведенных выше можно представить в виде такого кодового слова:

000011101111111111111111111111111111111111111110

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

Это можно сформулировать так: каждая комбинация из пяти чисел присутствует в максимум одном из билетов Деннистона. На самом деле все даже лучше: по существу, каждая комбинация из пяти чисел присутствует ровно в одном билете [242].

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

В лотерее Cash WinFall всего сорок шесть чисел, поэтому, чтобы сыграть в нее по методу Деннистона, придется немного нарушить красивую симметрию его системы, выбросив из его списка все билеты с числами 47 и 48. После этого у вас все еще останется 217 833 лотерейных билета. Предположим, вы достанете из тайника 435 666 долларов и решите поиграть в числа. Что произойдет?

В розыгрыше лотереи выпадает по шесть чисел – скажем, 4, 7, 10, 11, 34 и 46. Если произойдет маловероятное событие, эти числа совпадут с числами в одном из ваших лотерейных билетов – и вы получаете джекпот. Но даже если этого не произойдет, вы все равно сможете выиграть кучу денег по тем лотерейным билетам, в которых совпадут пять из шести чисел. Есть ли у вас билет с числами 4, 7, 10, 11, 34? В одном из билетов Деннистона такие числа есть, а значит, единственный случай, когда у вас не окажется такого билета, – если в нем были числа 4, 7, 10, 11, 34, 47 или 4, 7, 10, 11, 34, 48, поэтому вы его выбросили.

Но как насчет другой комбинации из пяти чисел, скажем 4, 7, 10, 11, 46? Может быть, вам не повезло в первый раз, потому что билет с числами 4, 7, 10, 11, 34, 47 был одним из билетов Деннистона. Но в таком случае билет 4, 7, 10, 11, 46, 47 не может быть в списке Деннистона, поскольку пять чисел этого билета совпадают с пятью числами билета, который, как вам известно, входит в этот список. Другими словами, если из-за злополучного числа 47 вы упустите один из призов за пять угаданных чисел, это не приведет к тому, что вы упустите и все остальные призы. То же самое можно сказать и о числе 48. Вот список возможных выигрышных билетов в категории «Пять угаданных чисел из шести»:

4, 7, 10, 11, 34

4, 7, 10, 11, 46

4, 7, 10, 34, 46

4, 7, 11, 34, 46

4, 10, 11, 34, 46

7, 10, 11, 34, 46

Минимум четыре из этих билетов гарантированно окажутся среди ваших. В действительности, если вы купите 217 833 лотерейных билета Деннистона, у вас будет такая вероятность выигрыша:

вероятность выиграть джекпот составляет 2 %;

вероятность выиграть шесть призов в категории «Пять из шести» составляет 72 %;

вероятность выиграть пять призов в категории «Пять из шести» составляет 24 %;

вероятность выиграть четыре приза в категории «Пять из шести» составляет 2 %.