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

Глава 1. Про какие лотереи мы говорим?

Давайте представим ситуацию: вы решили участвовать в лотерее. Вы покупаете лотерейный билет и вписываете в него несколько каких то чисел. По окончании розыгрыша, организатор лотереи объявляет выигрышную комбинацию чисел. Вы смотрите на нее, на свой заполненный билет и сравнивайте сколько чисел совпало. Если количество совпадений равно какому то фиксированному числу, например, 2, то вы выиграли. В противном случае вы проиграли. Как всё же точно гарантировать выигрыш ? Какое минимальное количество билетов для этого стоит купить ? Переплачивать ведь не хочется ! Именно эти вопросы и были поставлены в задаче "The Lottery Problem", которая существует уже более 60 лет. Изначально задача пришла из области комбинаторики, но нашла своё применение и в области теории графов, а в частности- в области теории доминирования.

Если вы поняли простой принцип работы данной лотереи, можно переходить к математической постановке задачи. Итак, данную лотерею можно представить с помощью лотерейного графа. Лотерейный граф- это регулярный граф, который в свою очередь задаётся с помощью трех параметров: m,n,k. Давайте разберём каждый из них.

- это параметр, задающий множество всех чисел, которые мы можем вписать в билет.

- это какое-то конкретное ?-элементное подмножество в ?? = {1,2, … , ?}, которое организатор лотереи назначает как «выигрышный билет».

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

G<m,n,k> - обозначение графа

Представьте, что вы игрок в лотерею ⟨?, ?; ?⟩, и вы хотите сыграть так, чтобы гарантированно выиграть ?-приз. Какое число лотерейных билетов вам нужно купить? Один из вариантов - купить все возможные билеты (их количество равно числу способов выбора ? элементов из ?-элементного множества). Однако, скорее всего это будет слишком дорого, ведь число различных билетов может быть очень большим. Более выгодный вариант - найти наименьшее количество лотерейных билетов, которые необходимо купить для того, чтобы гарантированно получить ?-приз. Такая стратегия позволит вам максимизировать свою прибыль. Поэтому вам нужно выбрать наименьшее такое множество ? лотерейных билетов, чтобы среди них обязательно был хотя бы один билет, в котором есть по крайней мере ? чисел, совпадающих с числами выигрышного билета, независимо от того, какой выигрышный билет будет выбран. Такое множество ? называется ?-оптимальным игровым множеством. Количество элементов в этом множестве называется лотерейным числом и обозначается символом ?(?, ?; ?). Как вы уже могли догадаться, если говорить в терминах теории доминирования, то - это число доминирования в лотерейном графе, а - это степень вершины.

Глава 2. Что было сделано до нас?

1. Доказано, что любой лотерейный граф регулярен; найдена формула, выражающая степень вершины графа через m, n, k.

   2. Доказано, что некоторые лотерейные графы изоморфны, а именно:

   G<m, n, k> ≅ G<m, m - n, m + k - 2n>

   Очевидно, что числа доминирования в изоморфных графах равны.

   3. Установлена зависимость роста или убывания L от изменения параметров m, n, k:

   • L(m↑, n, k)↑

   • L(m, n↑, k)↓

   • L(m, n, k↑)↑

   • L(m↑, n↑, k)↓

   • L(m, n↑, k↑)↑

   • L(m↑, n↑, k↑)↑

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

     5. Определены числа доминирования для частных случаев лотерейных графов.

     6. Выведены формулы, позволяющие вычислить L для определенных видов графов:

   • L(m, 3, 2) = (формула, где С с нижней чертой) 

   • L(m, n, 1) = ⌊m / n⌋

   • L(m, n, n) = C из m по n 

   7. Найдены условия для m, n, k, необходимые и достаточные для того, чтобы L(m, n, k) было равно 1; 2; 3.

Глава 3. Что сделала наша команда?

1. Независимо от уже существующих статей самостоятельно доказали необходимость и достаточность для фиксированного L=1 и L=2.

• : если выполняются данные условия, то число доминирования = 2.

2. Также независимо получили формулу нахождения степени вершины графа:

3. Вывели общую зависимость для частных наборов m,n,k, при которых L строго определено.

   Формулировка утверждения:

   Если

Доказательство:

Рассмотрим

Если х билетами мы покрываем числа от a1 до axn, то для формирования верхней оценки на k необходимо распределить (n-t) элементов по х билетам,

Так как для формирования верхней оценки на k требуется множества выигрышных чисел Cj 1 ≤ j ≤ n, распределить n- элементов Cj по всем билетам.

4. Постановка новой задачи:

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

   Гипотеза 1:

   Если при параметре m, удовлетворяющему условию :

существует разбиение множества чисел (множество чисел) на x билетов по n чисел, то L численно равно x. Однако если k не удовлетворяет ограничению, то L>x

Гипотеза 2:

Из гипотезы 1 следует, что если при

то найдётся такое x’>x, при котором

что x'=L, где F(x',n) это некоторое ограничение на параметр k.

Математическая формулировка:

Если в первом случае требовалось подтвердить разбиение m чисел на x билетов, так что оставалось t непокрытых чисел:

то теперь, мы разбиваем m чисел на x’ билетов, так что t чисел покрыты более чем одним билетом:

Основная проблема:

Рассмотрим задачу разбиения ? чисел на подмножества по ? билетов. Предположим, что параметр ? не делится нацело на ?. В этом случае в двух билетах (исключая два) может быть разное количество чисел, покрытых не более чем одним билетом.

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

Однако, конкретное значения ?, при которых это утверждение выполняется, зависят от конкретных условий задачи и могут быть определены только после анализа всех возможных случаев. Таким образом, на данным момент наша команда не смогла определить p для ограничения на m:

Глава 4. Частные случаи столото

1. Лотерея 7 из 49

Выигрывают билеты, в которых 2, 3, 4, 5, 6 или 7 чисел из 49 совпали с выпавшими числами.

Если вы угадали 7 чисел, вы выиграли многомиллионный суперприз.

Выигрыши за 2, 3, 4, 5 и 6 угаданных чисел являются фиксированными.

2. Лотерея 6 из 45

Выигрывают комбинации, в которых 2, 3, 4, 5 или 6 чисел из 45 совпали с выпавшими числами.

Если вы угадали 6 чисел из 45, вы выиграли многомиллионный суперприз.

Выигрыши за 2, 3, 4 и 5 угаданных чисел являются фиксированными

С каждой дополнительной цифрой в билете его стоимость увеличивается

3. Лотерея 5 из 36

В лотерее предусмотрено пять выигрышных категорий: три с фиксированными выигрышами и две с накапливаемыми суперпризом и призом. Угадав 5 чисел в поле 1 и 1 число в поле 2, вы получаете суперприз. Угадав только 5 чисел в поле 1 и ни одного числа в поле 2, вы получаете приз.

Призовой фонд лотереи — 50% с каждого проданного билета.

Сначала начисляются фиксированные выигрыши за 2, 3 и 4 угаданных числа в первом поле:

4. 4 из 20 x2

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

Если вы угадали 4 числа из 20 в первом поле и 4 числа из 20 — во втором, вы выиграли многомиллионный суперприз.

Если в текущем тираже никто не угадает 4 + 4 числа, накопленная сумма переходит на следующий тираж. Если суперприз разыгран, то в следующем тираже будет разыгрываться минимальный гарантированный суперприз, составляющий 100 000 000 рублей.

Если суперприз накопится до 300.000.000, то возможно выиграть +54.975.000!

5. Проще, чем 2×2

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

6. Всё, или ничего

Название говорит само за себя, можно выиграть либо джекпот, либо ничего. Если вы угадываете все числа или ни одного, то получаете джекпот в размере 5000000 руб.

7. Рапидо

В лотерее есть 2 поля. Для того, чтобы участвовать в лотерее, необходимо выбрать 8 чисел в первом поле и 1 число во втором. Минимальная стоимость 1 билета = 700 рублей. Для того, что бы окупить билет (выиграть 700 рублей), нужно что бы совпало 4 числа из 1 поля и 1 число из второго. Далее- аналогично. Минимальный суперприз = 10.000.000.

Лотерей «Рапидо» существует 4 вида, различаются они только стоимостью одного билета и минимальным выигрышем.

Общий вывод:

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

Возникает ситуация, при которых участие в лотерее действительно может быть эффективно. Например, в расчетах, приведённых для лотереи "4 из 20 x2", описанной в 4 пункте, на момент рассмотрения, (июль 2024) суперприз составлял более 300.000.000. Из этого следует то, что при минимальных затратах в размере 245.000.000, мы получим гарантированный профит.

Глава 5. О работе на БММ

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

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

Особую благодарность хотим выразить куратору проекта Захарову Алексею Евгеньевичу, а также научному специалисту по дискретной математике и комбинаторике Тахонову Ивану Ивановичу, который не только помог углубиться в задачу, но и оказал неоценимую помощь в её решении. Также мы благодарим организаторов потока, которые не только обеспечили комфортные условия для работы, но и стали настоящими друзьями для всех участников Мастерской.

Благодаря БММ мы смогли реализовать наш проект и внести вклад в решение задачи «The lottery problem». Мы выражаем благодарность всем участникам и организаторам, которые сделали это возможным. Мы уверены, что полученные результаты будут полезны для дальнейшего развития науки и образования в области математики.

Команда проекта:

• Коньшина Софья Павловна, sofia.konshina1@yandex.ru

• Бычков Иван Александрович, r3ngoky@yandex.ru , tg: @cupermush

• Емельянов Роман Иванович, emelroman7@gmail.com

• Штерн Богдан Игоревич, bogdan_stern@mail.ru

• Долгополов Кирилл Владимирович.

• Куратор: Захаров Алексей Евгеньевич.