ЧТО ЕСТЬ ФОРТУНА, или Как не проиграть в «Спортпрогноз»

Журнал "Квант", Выпуск №9, 1990 год.

Учитель тайн заповедных!
Что есть Фортуна, счастье всех племён
Держащая в когтях своих победных?
Данте. Божественная комедия.
Ад. VII, 67-69

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

Как правило, со «Спортлото» и «Спортпрогнозом» связывают задачи подсчёта вероятности угадывания некоторого количества верных номеров (результатов). Мы не будем возвращаться к этим хорошо известным вопросам, а лишь скажем, что вероятность угадывания шести номеров из сорока девяти (сейчас в карточке «Спортлото» 45 номеров. Когда авторы были моложе и увлекались «Спортлото», карточка содержала 49 номеров.) p(49,6)~7*10^-8; в тех же обозначениях p(49,5)~2*10^-5, p(49,4)~10^-3, p(36,5)~3*10^-6 (вы можете доказать это самостоятельно).

Правила игры

В «Спортпрогноз» играют следующим образом. Из календаря спортивных соревнований выбираются 13 матчей, исход которых, по мнению организаторов лотереи, трудно предсказуем. Игрок должен сделать прогноз результатов этих матчей, ставя в каждой из 13 клеточек таблицы знак «1», если он считает, что победит команда хозяев, «2» - команда гостей и «0» в случае ничьей. После того как результаты матчей становятся известными, определяются выигравшие карточки. Премии делятся между угадавшими не меньше 11 результатов и растут с увеличением числа верных предсказаний в карточке. Каждый прогноз будем представлять 13-мерным вектором (т.е. строкой из 13 цифр) с компонентами 0, 1 и 2. Например, вектор х=(1,1,0,2,2,1,2,0,0,0,1,1,2) отвечает выигрышу гостей в 4, 5, 7 и 13 матчах, хозяев - в 1, 2, 6, 11 и 12 матчах и ничьим - в остальных встречах.

В игре «Спортлото» требуется угадать 6 из 49 или 5 из 36 номеров. Выигравшими считаются карточки, в которых указано не менее 3 из выпавших в результате случайного розыгрыша номеров. Прогноз в этом случае можно описать 49- (36-) мерным вектором, содержащим «0» в 43 (31) позициях и «1» в 6 (5) оставшихся позициях. Номера единичных позиций соответствуют предсказываемым номерам.

В каждом из тиражей один игрок может предложить несколько вариантов прогноза. Назовем набор этих вариантов l-системой, если независимо от исхода тиража среди них найдется хотя бы один, в котором верно угаданы не менее l результатов. Для нас интерес представляют только l-системы с 11<=l<=13 для «Спортпрогноза» и с 3<=l<=6 (5) для «Спортлото». Очевидные примеры l-систем с максимальным l получаются при заполнении всех возможных вариантов прогноза. Эти системы не очень интересны хотя бы потому, что количество заполняемых при этом карточек «Спортпрогноза» равно 1 594 323, т.е. нужно затратить около полумиллиона рублей и около двух лет непрерывной (по полминуты на карточку) работы. Для «Спортлото» соответствующие числа ещё больше. Плохо и то, что, даже справившись с заполнением, нельзя быть уверенным в том, что сумма выигрыша превзойдет сделанные затраты. Для меньших l мы будем стараться придумать такие системы, в которых общее число вариантов было бы как можно меньше.

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

Структура пространства E⁴₃. На верхнем рисунке показаны 9 точек пространства E²₃, пронумерованные числами от 0 до 8 в троичной системе счисления. Рёбрами соединены точки, «троичные» номера которых отличаются друг от друга ровно в одном символе (точки находятся на расстоянии 1). E⁴₃ получается из E²₃ заменой каждой точки на 9 точек пространства E²₃; различные пространства также нумеруются «троичными» числами от 0 до 8. Пронумеруем точки в каждом из этих пространств так же, как на верхнем рисунке. Тогда «троичный» номер каждой точки из E⁴₃ получается приписыванием номера точки к номеру того пространства E²₃, в котором она лежит. На рисунке отмечены девять точек, принадлежащих линейной системе C₀^-.

«Спортпрогноз» на 4 матча

Нам будет проще объяснить идею построения l-систем на примере игры в «Спортпрогноз-4», в которой предлагается угадать результаты лишь четырёх матчей. Обозначим множество всех 4-мерных векторов из трёх символов - нулей, единиц и двоек - через E⁴₃. Размер 4-системы при этом равен числу элементов множества E⁴₃ (=81). Случай 3-системы уже заставляет задуматься. Наша задача сводится к выбору из E⁴₃ такого подмножества C из минимального количества векторов, что для любого вектора e € E⁴₃ в C можно указать хотя бы один вектор c, отличающийся от e не более, чем в одной позиции.

Определение. Расстоянием Хэмминга между векторами a и b называется количество различающихся компонент этих векторов.

Например, расстояние между векторами a=(0,1,2,0) и b=(0,2,0,0) равно d(a, b)=2.

Упражнение 1. Проверьте, что расстояние Хэмминга удовлетворяет неравенству треугольника

d(a, b)+d(b, c)>=(a, c).

Рассмотрим следующую систему С₀: (0,0,0,0); (1,0,1,1); (2,0,2,2); (0,1,1,2); (0,2,2,1); (1,1,2,0); (2,1,0,1); (1,2,0,2); (2,2,1,0).

Докажем, что С₀ является 3-системой. Прямая проверка показывает, что расстояние между любой парой векторов из С₀ равно 3. В силу неравенства треугольника для расстояния Хэмминга не существует вектора e € E⁴₃, находящегося на расстоянии 1 одновременно от двух векторов a и b из С₀ (иначе d(a, b)=2). Множество векторов из E⁴₃, находящихся на расстоянии <=1 от любого вектора из С₀, содержит 9 элементов (докажите!). Поскольку эти множества не пересекаются, их объединение содержит 9*9=81 вектор. Но в E⁴₃ всего 81 вектор! Значит, любой вектор из E⁴₃ принадлежит одному из таких множеств, что и требовалось доказать.

Пример 1. Вектор (2,1,2,1) принадлежит множеству векторов, находящихся на расстоянии <=1 от вектора (2,1,0,1) € С₀.

Итак, построена 3-система игры в мини-«Спортпрогноз». Эта система замечательна тем, что любой вектор из E⁴₃ находится на расстоянии <=1 только от одного вектора из С₀ (в общем случае это может и не выполняться, а в большинстве случаев и не может выполняться). Системы с таким свойством называются совершенными. Мы к ним ещё вернемся.

Операции по модулю 3 и l-системы

Построенная в предыдущем параграфе 3-система обладает ещё рядом красивых свойств (открытых в 40-х годах американским ученым Ричардом Хэммингом), для объяснения которых потребуется небольшое отступление.

Мы имеем дело с векторами, компоненты которых могут принимать значения из множества Z₃={0,1,2}. Элементы Z₃ можно складывать и умножать так, что в результате будут снова получаться элементы из этого же множества. Для этого достаточно, выполнив обычное сложение или умножение, найти остаток от деления полученного результата на 3 (как говорят, привести его по модулю 3). Например, 5=2(mod 3), -2=1(mod 3).

Используя эти операции, можно определить сложение троичных векторов. Назовем суммой векторов a и b вектор c, каждая координата которого является суммой по модулю 3 соответствующих координат векторов a и b. Например, (0,1,1,2)+(1,2,1,1)=(1,0,2,0). Определим произведение вектора на троичное число v€Z₃ как вектор, координаты которого получены умножением координат вектора на v по модулю 3. Например, 2*(1,0,2,2)=(2,0,1,1). В математике такие совокупности векторов с определёнными на них операциями сложения и умножения на число называются векторными пространствами.

Упражнение 2. Проверьте, что введённая в предыдущем параграфе 3-система C₀ обладает следующими свойствами: для любых вектора a€C₀ и константы v€Z₃ произведение va также принадлежит C₀; для любых двух векторов a. b€C₀ их сумма - тоже вектор из Co. Такие системы называются линейными.

Операции по модулю 3 позволяют дать краткое описание 3-системы C₀. Во-первых, заметим, что первые две координаты (x₁, x₂) векторов из C₀ могут быть любой парой троичных чисел. Назовем эту пару троичным номером вектора. Значения двух оставшихся координат x₃ и x₄ можно вычислить по следующему правилу (действия по модулю 3):

x₃=x₁+x₂, x₄=x₁+2x₂ (1)

(проверьте!).

Упражнения

3. Можно ли в качестве номера выбрать другие координаты вектора? Какой вид будет тогда иметь правило (1)?

4. Покажите, что если ко всем векторам системы C₀ добавить произвольный (один и тот же) вектор, то ее свойства как l-системы не изменятся.

5. Воспользовавшись результатом упражнения 4, покажите, что в систему C₀ можно включить любой наперед заданный вектор (прогноз, кажущийся вам наиболее правдоподобным).

Предположим, что вы заполнили карточки в соответствии с системой C₀. В утренней газете опубликованы результаты матчей, включенных в тираж (вектор y). Как быстрее найти выигравшую карточку (то, что она есть, следует из свойств системы)? Очевидный, но иногда далеко не лучший способ - сравнить результаты тиража со всеми заполненными карточками и найти наименее отличающуюся.

Для описания более быстрого способа перепишем уравнения (1) в эквивалентном виде:

x₁+x₂+2x₃=0, x₁+2x₂+2x₄=0. (2)

Наш способ будет основан на том, что координаты каждого вектора системы C₀ удовлетворяют уравнениям (2). Если у удовлетворяет (2), он принадлежит системе C₀, и соответствующая ему карточка может быть найдена по её троичному номеру. В противном случае у отличается от какого-нибудь вектора c=(c₁, c₂, c₃, c₄)€C₀ в одной координате. Пусть её номер равен j. Найдём S₁=y₁+y₂+2y₃ и S₂=y₁+2y₂+2y₄.

Упражнение 6. Покажите, что выигравшую карточку с можно найти следующим образом:

а)если S₁=0 и S₂<>0, то j=4; если S₂=0 и S₁<>0, то j=3 (в обоих случаях c_i=y_i+S_i где i=1 или 2 - индекс отличного от нуля S₀);

б)если S₁<>0, и S₂<>0, то при S₁S₂=1 j=1, а c₁=y₁+2S_i, (i-любое). При S₁S₂=2 j=2, а C₂=y₂+2S₁=y₂+S₂.

Продолжение примера 1. Воспользуемся предыдущим упражнением для определения ближайшей карточки, если результаты матчей представлены вектором y=(2,1,2,1). Тогда S₁=1, S₂=0. Обращаясь к случаю а), получаем j=3, а c₃=y₃+S₁=0. Вновь найден вектор c=(2,1,0,1)€C₀, находящийся от y на расстоянии 1.

Для «Спортпрогноза» на 4 матча этот способ определения выигравшей карточки выглядит (и является) чересчур громоздким, особенно в сравнении с простым перебором всех девяти карточек системы. Его преимущества выяснятся ниже.

Отметим еще одно применение описанной системы. Пусть, заполняя карточку большого «Спортпрогноза», вы полагаете, что точно знаете результаты 9 из 13 матчей. Вам хотелось бы знать наверняка, что в прогнозе исходов остальных четырех матчей вы ошибетесь не более, чем однажды. Тогда следует заполнить 9 карточек с фиксированной комбинацией на известных 9 позициях и всеми векторами 3-системы C₀ на оставшихся четырех позициях.

Коды, исправляющие ошибки

Не следует думать, что l-системы изобретены и изучались для получения крупных выигрышей в лотерее - у математиков есть и более интересные занятия. Оказывается, очень похожие конструкции появляются, например, в теории передачи сообщений. Представим себе, что по линии связи с помехами требуется передать вектор из k букв, каждая буква которого может принимать одно из q значений (для сообщений на русском языке q=34 - буквы алфавита и промежуток между словами). Будем считать, что непосредственная передача с большой вероятностью исказит хотя бы одну букву сообщения, поэтому хотелось бы иметь способ исправления ошибок после приеёма.

Поступим следующим образом. Добавим к передаваемому вектору несколько букв, зависящих от букв исходного сообщения. Такой набор расширенных сообщений назовем кодом, а число букв в расширенном сообщении (кодовом векторе) обозначим через n и назовем длиной кода. Если при передаче кодового вектора в канале связи произошло искажение t букв, то принятый вектор находится на расстоянии Хэмминга t от переданного вектора. По принятому вектору требуется однозначно восстановить переданный вектор. Для этого код должен удовлетворять определенным свойствам.

Утверждение. Код C исправляет любые t или менее ошибок, если множества векторов из E_qⁿ, находящихся на расстоянии <=t от кодовых векторов, попарно не пересекаются.

Упражнения

7. Докажите, что каждое такое множество из утверждения содержит V(n, t)=SUM_i=0^j C_nⁱ*(q-1)ⁱ векторов (C_nⁱ - биномиальный коэффициент, равный n!/((n-i)!*i!).

8 (граница Хэмминга). Докажите, что для любого кода

k<=Log_q[qⁿ/V(n,t)]
([x] - целая часть x).     (3)

Если для параметров кода в (3) имеет место равенство, то код называется совершенным.

Возникшая около сорока лет назад математическая теория кодирования ныне является развитой и весьма глубокой наукой. У ее истоков стояли Клод Шеннон, уже упоминавшийся Ричард Хэмминг, Марсель Голей и другие ученые. Более подробно о кодах, исправляющих ошибки, вы можете прочитать в книгах Аршинова М. Н., Садовского Л. Е. «Коды и математика» (М., «Наука», 1983, Библиотечка «Квант», вып. 30), Яглома А. М., Яглома И. М. «Вероятность и информация» (М., «Наука», 1973).

Несложно видеть, что совершенные l-системы совпадают с совершенными кодами. В частности, 3-система для игры в мини-«Спортпрогноз» - это код с q=3, k=2 и n=4, исправляющий одну ошибку. Из сказанного выше следует, что этот код является линейным (в смысле упражнения 2) и совершенным и содержит, как ему и положено, q^k=9 векторов.

«Спортпрогноз-13»

Предложенная выше 3-система для тиража из четырёх матчей допускает обобщение на «реальный» случай 13 матчей; при этом получается 12-система C₁ состоящая из 3¹⁰=59049 карточек. Будем считать, что вектор x€E₃¹³ принадлежит системе C₁, если его координаты удовлетворяют следующим уравнениям (вновь операции по модулю 3):

x11=x3 +x4+x5+x6+x7+x8+x9+x10,

x12=x1+x2+x5+x6+x7+2x8+2x9+2x10, (4)

x13=x1+2x2+x3+2x4+x6+2x7+x9+2x10.

Как и выше, номером вектора будем называть набор из его первых девяти координат.

Упражнение 9. Пусть номер вектора x=(x1,...,x13)€C₁ равен (x1,...x10)=(0,1,1,1,2,0,2,1,2,1). Найдите x.

Утверждение. Построенная 12-система является линейной и совершенной.

Действительно, пусть векторы x и y удовлетворяют (4), тогда и x+y и 2x удовлетворяют этой системе уравнений. Несколько сложнее доказывается то, что расстояние между любыми двумя векторами системы C₁ не меньше трёх. Рассмотрим 2 вектора x, y€C₁. Если их номера совпадают, то x=y. Если номера различаются в трёх или более позициях, то все доказано. Пусть номера различаются в одной позиции, скажем, i-й. Тогда заметим, что любое x_i (1<=i<=10) входит с ненулевыми коэффициентами в правые части по меньшей мере двух уравнений системы (4), т. е. по меньшей мере две из трёх последних координат векторов x и y будут различными. Если же номера векторов x и y различаются в двух позициях, скажем, i-й и j-к, то для доказательства достаточно показать, что они различаются ещё по крайней мере в одной позиции. Этого может не быть только в случае, когда i-я и j-я переменные в правые части всех уравнений (4) входят с одинаковыми коэффициентами. Проверка показывает, что таких переменных не существует. Итак, доказано, что расстояние между двумя любыми векторами x, y€C₁ не меньше трёх. Тогда множества векторов из E₃¹³, находящихся от x и y на расстоянии <=1, не пересекаются. В соответствии с упражнением 7 каждое такое множество содержит 27 = 3³ векторов. Общее же количество векторов в системе равно числу различных номеров, т. е. 3¹⁰, а общий объём соответствующих им непересекающихся множеств равен 3¹⁰*3³=3¹³, что совпадает с числом всех возможных карточек. Что и требовалось доказать.

Упражнение 10 (трудное). Придумайте быстрый способ нахождения выигравшей карточки для системы C₁ по результату тиража (сравните с упражнением 6). Этот способ позволит найти выигравшую карточку значительно быстрее, чем при полном переборе.

Построенная 12-система является кодом с q=3, n=13, k=10, исправляющим одну ошибку. Этот код - представитель семейства совершенных кодов Хэмминга с q=3, n=(3^m-1)/2, k=n-m.

Нелинейные системы

Вернёмся на время к системе C₀ для мини-«Спортпрогноза». Выпишем все её девять векторов в строки таблицы. Вычеркивая из этой таблицы любой столбец, получим линейную систему из девяти векторов для «Спортпрогноза-3». Можно показать, что эта система является наилучшей среди линейных, т. е. содержит наименьшее возможное число карточек. Оказывается, отказ от условия линейности позволяет улучшить эту систему. Наилучшая нелинейная 2-система длины 3 состоит всего из пяти векторов. Вот она:

(0,0,0), (0,1,1), (1,0,1), (1,1,0), (2,2,2).

В таблице приведены рекорды построения l-систем для l=n-3, n-2 и n-1 при n<=13. Для игры «Спортпрогноз» понадобятся только первые два столбца, но для математиков интерес представляет и более общий случай. Заметим, что любое улучшение таблицы достойно статьи в солидных международных математических журналах. Разумеется, системы из этой таблицы строились их авторами не простым перебором на ЭВМ (кстати, как это сделать? Ответ в общем случае неизвестен), а применением общих конструкций, приводящих к семействам систем различных длин. Так что если кому-то из читателей посчастливится улучшить таблицу, авторы готовы оказать помощь по подготовке статьи. Поиск лучше начать с длин n>=3, т.е. улучшение при меньших длинах маловероятно.

Таблица

n	l=n-1	l=n-2	l=n-3
1	1*	1*	1*
2	3*	1*	1*
3	5*	3*	1*
4	9*	3*	3*
5	27	8	3*
6	73	17	6*
7	186	34	12
8	486	81	27
9	1458	219	54
10	3645	558	108
11	10935	729*	243
12	29889	2187	729
13	59049*	6561	1215

* - известно, что улучшить нельзя.

Замечательная 9-система длины 11

При внимательном наблюдении за таблицей бросается в глаза звёздочка, одиноко мерцающая в её середине. Здесь находится замечательная 9-система C₂ длины 11. Её история и применения могли бы послужить сюжетом для увлекательного математического романа. Но прежде несколько слов о самой героине. Это линейная совершенная система. Совершенность доказать несложно, если знать, что любые два вектора системы находятся на расстоянии не менее пяти. Тогда, как и раньше, множества (их 729= 3⁶) векторов из E₃¹¹ находящихся на расстоянии <=2 от некоторой точки системы, не пересекаются. Поскольку в каждом из этих множеств 243=3⁵ векторов, суммарный объём этих множеств совпадает с общим числом векторов в E₃¹¹.

Приведём уравнения, связывающие троичный номер (x₁, x₂,...,x₆) любого вектора x, принадлежащего системе C₂, с остальными пятью его координатами:

x₇=x₁+      x₃+2x₄+2x₅+x₆,

x₈=x₁+x₂+      x₄+2x₅+2x₆,

x₉=х₁+2x₂+x₃+      x₅+2x₆,      (5)

x₁₀=x₁+2x₂+2x₃+x₄+      x₆,

x₁₁=x+x₂+2x₃+2x₄+x₅      .

Эта система совпадает с совершенным кодом с параметрами q=3, n=11, k=6, исправляющим две ошибки. Он называется кодом Голея в честь открывшего и опубликовавшего его в 1949 году математика. Для задания кода с помощью системы уравнений (5) Голею пришлось использовать теорию так называемых квадратичных вычетов. Однако летом 1989 года выяснилось, что этот код (как хорошая система для игры «Спортпрогноз») открыт и опубликован в 1947 г. в финской спортивной газете «Вейкаайя» ( В Финляндии при заполнении карточки «Спорт-прогноза» в 1947 году требовалось предсказать результаты 12 матчей (теперь - 13). Карточка считалась выигравшей, если в ней было верно угадано не менее 10 результатов. Поэтому систему C2 можно было использовать, если результаты одного матча игрок знал наверное.). Автор этого открытия Юхани Виртакаллио - не математик и, наверное, не знал, что для построения кода необходимо использовать квадратичные вычеты. Он писал: «Эта система из 729 столбцов пришла мне в голову в дни небывало низких выигрышей в «Спортпрогноз». Видимо, мы имеем дело с примером истинно рамануджановского озарения (см. статью С Г. Гиндикина в «Кванте» № 10 за 1987 год).

Помимо этой троичной системы, М. Голей в своей работе 1949 года описал еще одну линейную совершенную систему - 20-систему C₃ длины 23 с векторами из нулей и единиц - код с параметрами q=2, n=23, k=12, исправляющий 3 ошибки. Эта система содержит 2¹²=4096 векторов и могла бы оказаться полезной для «Спортпрогноза» на 23 поединка в игре без ничьих.

Упражнение 11. Используя результаты упражнений 7 и 8, покажите, что система C₃ совершенна (и следовательно, содержит наименьшее возможное число карточек среди систем с такими параметрами).

Открытие, сделанное Виртакаллио, тем более удивительно, что при q=3 других нетривиальных совершенных l-систем с l<=n-2 ни для каких значений n не существует. При l=n-1 существуют еще системы с параметрами, приведёнными в конце предыдущего параграфа. При q=2 список нетривиальных совершенных систем с l<=n-1 исчерпывается 20-системой C₃ и семейством (n-1)-систем с n=2^m-1 и k=n-m. Эти два утверждения следуют из глубокой теоремы о совершенных кодах, доказанной только в начале 70-х гг.

Возникающие в связи с кодами Голея C₂ и C₃ математические задачи, как правило, довольно трудны. Даже задача быстрого (непереборного) нахождения выигравшей карточки системы C₂ по известному результату тиража весьма непроста. Желающие попробовать свои силы в этой трудной (хотя и решенной) проблеме должны воспользоваться системой уравнений (5) и действовать в духе упражнений 6 и 9. Может быть, вам удастся открыть какой-нибудь новый способ решения этой задачи?

Последняя задача, которой мы хотим здесь коснуться в связи со «Спортпрогнозом», возникает в случае, когда игрок предполагает, что в t из n матчей возможен любой из трёх исходов - ничья, выигрыш и проигрыш одной из команд, а в b=n-t матчах её выигрыш практически невероятен. (Например, в футбольном матче «Барселона» (Мадрид) - «Звезда» (Пермь) одна из команд может в лучшем случае рассчитывать на ничью.) Обозначим через E_2,3(b,t) множество векторов длины b+t, у которых первые b координат принимают значения 0 или 1, а последние t - значения 0, 1 или 2. l-система C для смешанного «Спортпрогноза» должна состоять из таких векторов из E_2,3(b,t), что для любого вектора a€E_2,3(b,t) найдется вектор c€C, находящийся от a на расстоянии Хэмминга не более l.

Упражнения

12. Покажите, что на расстоянии <=l от фиксированного вектора a€E_2,3(b, t) находится SUM_i=0^l 2^l-iC_bⁱ C_t^l-i векторов.

13. Постройте 3-систему при t, b=2, состоящую из шести карточек.

«Спортлото»

Уже понятно, что построение систем для игры «Спортлото» связано с рассмотрением множества всех векторов из множества E₂^n,w двоичных векторов длины n, содержащих ровно w единиц. Нам неизвестны хорошие системы для «Спортлото», однако можно получить простое неравенство, показывающее, что любая такая система должна содержать довольно много карточек. Их количество, разумеется,

зависит от того, насколько высоки наши требования к ожидаемому выигрышу. Как и выше, назовем множество карточек m-системой D, если при любом результате тиража у хотя бы одна из этих карточек выиграет не менее m номеров. Рассмотрим «Спортлото - 6 из 49». 6-система D₀ содержит C₄₉⁶=13983816 карточек - все векторы из множества E₂^49,6 двоичных векторов длины 49 с шестью единицами. В любой 5-системе D₁ найдутся 2 вектора c₁ и c₂ с d(c₁,c₂)=2. В самом деле, любые два вектора, содержащие одинаковое число единиц, находятся один от другого на чётном расстоянии. Поэтому если не существует векторов c₁ и c₂ таких, что d(c₁,c₂)=2, то min_c1,c2d(c₁,c₂)= 4, и найдется такой вектор y€E₂^49,6, что ближайший к нему вектор системы находится от y на расстоянии 2. Тогда, если y будет результатом тиража, в D₁ не найдётся карточки с пятью выигравшими номерами.

Упражнение 14 (граница Хэммиига для векторов с одинаковым числом единиц).

а) Докажите, что число векторов из E₂^49,6, находящихся на расстоянии <=2s от данного вектора c€E₂^49,6, равно
M(s)=SUM_i=0^s C₆ⁱ C₄₃ⁱ=SUM_i=6-s⁶ C₆ⁱC₄₃^6-i

б) Докажите, что |D1|-количество карточек в 5-системе D1 - не меньше, чем [C₄₉⁶/M(1)]=53992
([х] - наименьшее целое, большее или равное х).

Аналогично показывается, что любая 4-система D₂ не может содержать меньше, чем 1014 карточек, любая 3-система D₆ - меньше, чем 54 карточки. Для «Спортлото - 5 из 36» |D₁|>=2417, |D₂|>=79, |D₆|>=8.

В заключение приведём пример 2-системы D для мини-«Спортлото», в котором требуется угадать 6 из 8 номеров:

D=	11111100 11110011 11001111 00111111.

Поскольку любой результат тиража у содержит два нуля, найдется такой вектор C€D, что в некоторой координате векторы y и c оба содержат нуль. Тогда расстояние между y и c не больше двух, т.е. D - действительно 2-система. Покажем, что 2-системы с меньшим числом векторов не существует. Действительно, три вектора вместе содержат всего шесть нулей, и даже если все они находятся на разных позициях, все же остаются две позиции, не содержащие нулей. Помещая на эти позиции нули вектора y, мы видим, что он находится на расстоянии 4 от каждого из трёх векторов системы. Значит, 2-система D длины 8 оптимальна.

Кандидат технических наук А. БАРГ,
кандидат технических наук С. ЛИЦЫН