Учитель таємниць заповідних!
Що є Фортуна, щастя всіх племен
Держава, що тримає в пазурах своїх переможних?
Данте. Божественна комедія.
Пекло. VII, 67-69
Шкільний фольклор містить історію про людину, яка за допомогою ЕОМ розробив систему для гри «Спортлото» і виграв цілий статок. Цю людину ніхто не бачив, та й навряд чи він існує, так як свідомо виграшної стратегії для цієї гри немає. Іншими словами, не можна вказати такий спосіб гри, при якому виграна сума буде завжди більше витрачених на покупку карток грошей. Не є винятком і пропоновані нами стратегії. Проте, зі «Спортлото» і іншими подібними іграми пов'язано безліч цікавих математичних задач. Про деякі з них ми і розповімо.
7 * 10 -8; в тих же позначеннях p (49,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 4 3. На верхньому малюнку показані 9 точок простору E 2 3. пронумеровані числами від 0 до 8 в трійчастий системі числення. Ребрами з'єднані точки, «трійчастий» номери яких відрізняються один від одного рівно в одному символі (точки знаходяться на відстані 1). E 4 3 виходить з E 2 3 заміною кожної точки на 9 точок простору E 2 3, різні простору також нумеруються «трійковими» числами від 0 до 8. Пронумеруємо точки в кожному з цих просторів так само, як на верхньому малюнку. Тоді «трійчастий» номер кожної точки з E 4 3 виходить приписуванням номера точки до номера того простору E 2 3. в якому вона лежить. На малюнку відзначені дев'ять точок, що належать лінійної системі C0 -.
«Спортпрогноз» на 4 матчі
Нам буде простіше пояснити ідею побудови l-систем на прикладі гри в «Спортпрогноз-4», в якій пропонується вгадати результати лише чотирьох матчів. Позначимо множину всіх 4-мірних векторів з трьох символів - нулів, одиниць і двійок - через E 4 3. Розмір 4-системи при цьому дорівнює числу елементів безлічі E 4 3 (= 81). Випадок 3-системи вже змушує задуматися. Наше завдання зводиться до вибору з E 4 3 такого підмножини C з мінімальної кількості векторів, що для будь-якого вектора e € E 4 3 в C можна вказати хоча б один вектор c, що відрізняється від e не більше, ніж в одній позиції.
Визначення. Відстанню Хеммінга між векторами a і b називається кількість розрізняються компонент цих векторів.
Наприклад, відстань між векторами a = (0,1,2,0) і b = (0,2,0,0) одно d (a, b) = 2.
Вправа 1. Перевірте, що відстань Хеммінга задовольняє нерівності трикутника
Розглянемо наступну систему С0. (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).
Доведемо, що С0 є 3-системою. Пряма перевірка показує, що відстань між будь-якою парою векторів з С0 дорівнює 3. У силу нерівності трикутника для відстані Хеммінга не існує вектора e € E 4 3. знаходиться на відстані 1 одночасно від двох векторів a і b з С0 (інакше d (a, b) = 2). Безліч векторів з E 4 3. знаходяться на відстані 4 3 всього 81 вектор! Значить, будь-який вектор з E 4 3 належить одному з таких множин, що й треба було довести.
Приклад 1. Вектор (2,1,2,1) належить множині векторів, що знаходяться на відстані 4 3 знаходиться на відстані n. знаходяться на відстані j Cn i * (q-1) i векторів (Cn i - біноміальний коефіцієнт, що дорівнює n! / ((n-i)! * i!).
8 (межа Хеммінга). Доведіть, що для будь-якого коду
k<=Logq [q n /V(n,t)]
([X] - ціла частина x). (3)
Якщо для параметрів коду в (3) має місце рівність, то код називається досконалим.
Виникла близько сорока років тому математична теорія кодування нині є розвиненою та вельми глибокої наукою. Біля її витоків стояли Клод Шеннон, вже згадуваний Річард Хеммінга, Марсель Голей і інші вчені. Більш докладно про коди, що виправляють помилки, ви можете прочитати в книгах Аршинова М. М. Садовського Л. Є. «Коди та математика» (М. «Наука», 1983, Бібліотечка "Квант", вип. 30), Яглом А. М. Яглом І. М. «Імовірність і інформація» (М. «Наука», 1973).
Нескладно бачити, що вчинені l-системи збігаються з досконалими кодами. Зокрема, 3-система для гри в міні-«Спортпрогноз» - це код з q = 3, k = 2 і n = 4, що виправляє одну помилку. Зі сказаного вище випливає, що цей код є лінійним (в сенсі вправи 2) і досконалим і містить, як йому і належить, q k = 9 векторів.
Запропонована вище 3-система для тиражу з чотирьох матчів допускає узагальнення на «реальний» випадок 13 матчів; при цьому виходить 12-система C1 складається з 3 10 = 59049 карток. Будемо вважати, що вектор x € E3 13 належить системі C1. якщо його координати задовольняють наступним рівнянням (знову операції по модулю 3):
Як і вище, номером вектора будемо називати набір з його перших дев'яти координат.
Вправа 9. Нехай номер вектора x = (x1. X13) € C1 дорівнює (x1. X10) = (0,1,1,1,2,0,2,1,2,1). Знайдіть x.
Затвердження. Побудована 12-система є лінійною і досконалою.
Дійсно, нехай вектори x і y задовольняють (4), тоді і x + y і 2x задовольняють цій системі рівнянь. Дещо складніше доводиться те, що відстань між будь-якими двома векторами системи C1 не менше трьох. Розглянемо 2 вектора x, y € C1. Якщо їх номери збігаються, то x = y. Якщо номери різняться в трьох або більше позиціях, то все доведено. Нехай номера розрізняються в одній позиції, скажімо, i-й. Тоді зауважимо, що будь-який xi (1<=i<=10) входит с ненулевыми коэффициентами в правые части по меньшей мере двух уравнений системы (4), т. е. по меньшей мере две из трёх последних координат векторов x и y будут различными. Если же номера векторов x и y различаются в двух позициях, скажем, i-й и j-к, то для доказательства достаточно показать, что они различаются ещё по крайней мере в одной позиции. Этого может не быть только в случае, когда i-я и j-я переменные в правые части всех уравнений (4) входят с одинаковыми коэффициентами. Проверка показывает, что таких переменных не существует. Итак, доказано, что расстояние между двумя любыми векторами x, y€C1 не меньше трёх. Тогда множества векторов из E3 13. находящихся от x и y на расстоянии <=1, не пересекаются. В соответствии с упражнением 7 каждое такое множество содержит 27 = 3 3 векторов. Общее же количество векторов в системе равно числу различных номеров, т. е. 3 10. а общий объём соответствующих им непересекающихся множеств равен 3 10 *3 3 =3 13. что совпадает с числом всех возможных карточек. Что и требовалось доказать.
Побудована 12-система є кодом з q = 3, n = 13, k = 10, виконуючим одну помилку. Цей код - представник сімейства досконалих кодів Хеммінга з q = 3, n = (3 m -1) / 2, k = n-m.
Повернемося на час до системи C0 для міні- «Спортпрогноз». Випишемо всі її дев'ять векторів в рядки таблиці. Викреслюючи з цієї таблиці будь-стовпець, отримаємо лінійну систему з дев'яти векторів для «Спортпрогноз-3». Можна показати, що ця система є найкращою серед лінійних, т. Е. Містить найменше можливе число карток. Виявляється, відмова від умови лінійності дозволяє поліпшити цю систему. Найкраща нелінійна 2-система довжини 3 складається всього з п'яти векторів. Ось вона:
* - відомо, що поліпшити не можна.
Чудова 9-система довжини 11
При уважному спостереженні за таблицею кидається в очі зірочка, самотньо мерехтлива в її середині. Тут знаходиться чудова 9-система C2 довжини 11. Її історія і застосування могли б послужити сюжетом для захоплюючого математичного роману. Але перш кілька слів про саму героїню. Це лінійна досконала система. Досконалість довести нескладно, якщо знати, що будь-які два вектори системи знаходяться на відстані не менше п'яти. Тоді, як і раніше, безлічі (їх 729 = 3 6) векторів з E3 11 знаходяться на відстані <=2 от некоторой точки системы, не пересекаются. Поскольку в каждом из этих множеств 243=3 5 векторов, суммарный объём этих множеств совпадает с общим числом векторов в E3 11 .
Наведемо рівняння, що зв'язують трійчастий номер (x1. X2. X6) будь-якого вектора x, що належить системі C2. з іншими п'ятьма його координатами:
Крім цієї троичной системи, М. Голей в своїй роботі 1949 року описав ще одну лінійну досконалу систему - 20-систему C3 довжини 23 з векторами з нулів і одиниць - код з параметрами q = 2, n = 23, k = 12, що виправляє 3 помилки. Ця система містить 2 12 = 4096 векторів і могла б виявитися корисною для «Спортпрогноз» на 23 поєдинки в грі без нічиїх.
Вправа 11. Використовуючи результати вправ 7 і 8, покажіть, що система C3 досконала (і отже, містить найменше можливе число карток серед систем з такими параметрами).
Відкриття, зроблене Віртакалліо, тим більше дивно, що при q = 3 інших нетривіальних скоєних l-систем з l<=n-2 ни для каких значений n не существует. При l=n-1 существуют еще системы с параметрами, приведёнными в конце предыдущего параграфа. При q=2 список нетривиальных совершенных систем с l<=n-1 исчерпывается 20-системой C3 и семейством (n-1)-систем с n=2 m -1 и k=n-m. Эти два утверждения следуют из глубокой теоремы о совершенных кодах, доказанной только в начале 70-х гг.
Що виникають у зв'язку з кодами Голі C2 і C3 математичні завдання, як правило, досить важкі. Навіть завдання швидкого (непереборного) знаходження виграла картки системи C2 по відомому результату тиражу вельми непроста. Бажаючі спробувати свої сили в цій важкій (хоча і вирішеною) проблеми повинні скористатися системою рівнянь (5) і діяти в дусі вправ 6 і 9. Може бути, вам вдасться відкрити який-небудь новий спосіб вирішення цього завдання?
Останнє завдання, якої ми хочемо тут торкнутися в зв'язку зі «Спортпрогноз», виникає в разі, коли гравець припускає, що в t з n матчів можливий будь-який з трьох випадків - нічия, виграш і програш однієї з команд, а в b = nt матчах її виграш практично неймовірний. (Наприклад, в футбольному матчі «Барселона» (Мадрид) - «Зірка» (Перм) одна з команд може в кращому випадку розраховувати на нічию.) Позначимо через E2,3 (b, t) безліч векторів довжини b + t, у яких перші b координат приймають значення 0 або 1, а останні t - значення 0, 1 або 2. l-система C для змішаного «Спортпрогноз» повинна складатися з таких векторів з E2,3 (b, t), що для будь-якого вектора a € E2,3 (b, t) знайдеться вектор c € C, що знаходиться від a на відстані Хеммінга не більше l.
12. Покажіть, що на відстані <=l от фиксированного вектора a€E2,3 (b, t) находится SUMi=0 l 2 l-i Cb i Ct l-i векторов.
13. Побудуйте 3-систему при t, b = 2, що складається з шести карток.
Вже зрозуміло, що побудова систем для гри «Спортлото» пов'язане з розглядом безлічі всіх векторів з безлічі E2 n, w довічних векторів довжини n, що містять рівно w одиниць. Нам невідомі хороші системи для «Спортлото», проте можна отримати просте нерівність, що показує, що будь-яка така система повинна містити досить багато карток. Їх кількість, зрозуміло,
залежить від того, наскільки високі наші вимоги до очікуваного виграшу. Як і вище, назвемо безліч карток m-системою D, якщо при будь-якому результаті тиражу у хоча б одна з цих карток виграє не менше m номерів. Розглянемо «Спортлото - 6 з 49». 6-система D0 містить C49 6 = 13983816 карток - все вектори з безлічі E2 49,6 довічних векторів довжини 49 з шістьма одиницями. У будь-який 5-системі D1 знайдуться 2 вектора c1 і c2 з d (c1, c2) = 2. Справді, будь-які два вектори, що містять однакове число одиниць, знаходяться один від одного на парному відстані. Тому якщо не існує векторів c1 і c2 таких, що d (c1, c2) = 2, то minc1, c2 d (c1, c2) = 4, і знайдеться такий вектор y € E2 49,6. що найближчий до нього вектор системи перебуває від y на відстані 2. Тоді, якщо y буде результатом тиражу, в D1 не знайдеться картки з п'ятьма виграли номерами.
Вправа 14 (межа Хеммііга для векторів з однаковим числом одиниць).
а) Доведіть, що число векторів з E2 49,6. знаходяться на відстані <=2s от данного вектора c€E2 49,6. равно
M (s) = SUMi = 0 s C6 i C43 i = SUMi = 6-s 6 C6 i C43 6-i
б) Доведіть, що | D1 | -кількість карток в 5-системі D1 - не менш, ніж [C49 6 / M (1)] = 53992
([Х] - найменше ціле, більше або рівне х).
Аналогічно показується, що будь-яка 4-система D2 не може містити менше, ніж 1014 карток, будь-яка 3-система D6 - менше, ніж 54 картки. Для «Спортлото - 5 з 36» | D1 |> = 2417, | D2 |> = 79, | D6 |> = 8.
На закінчення наведемо приклад 2-системи D для міні- «Спортлото», в якому потрібно вгадати 6 з 8 номерів:
Оскільки будь-який результат тиражу у містить два нуля, знайдеться такий вектор C € D, що в деякій координаті вектори y і c обидва містять нуль. Тоді відстань між y і c не більш двох, тобто D - дійсно 2-система. Покажемо, що 2-системи з меншим числом векторів не існує. Дійсно, три вектора разом містять всього шість нулів, і навіть якщо всі вони знаходяться на різних позиціях, все ж залишаються дві позиції, що не містять нулів. Помістивши на ці позиції нулі вектора y, ми бачимо, що він знаходиться на відстані 4 від кожного з трьох векторів системи. Значить, 2-система D довжини 8 оптимальна.
Кандидат технічних наук А. Барг,
кандидат технічних наук С. ЛІЦИН