Думаю, все когда-нибудь хоть раз задумывались над тем, как же всё таки выиграть в лотерею. В мире существует огромное количество различных лотерей, но сегодня мы рассмотрим только один, из ее видов, доступный и понятный.
Глава 1. Про какие лотереи мы говорим?
Давайте представим ситуацию: вы решили участвовать в лотерее. Вы покупаете лотерейный билет и вписываете в него несколько каких то чисел. По окончании розыгрыша, организатор лотереи объявляет выигрышную комбинацию чисел. Вы смотрите на нее, на свой заполненный билет и сравнивайте сколько чисел совпало. Если количество совпадений равно какому то фиксированному числу, например, 2, то вы выиграли. В противном случае вы проиграли. Как всё же точно гарантировать выигрыш ? Какое минимальное количество билетов для этого стоит купить ? Переплачивать ведь не хочется ! Именно эти вопросы и были поставлены в задаче "The Lottery Problem", которая существует уже более 60 лет. Изначально задача пришла из области комбинаторики, но нашла своё применение и в области теории графов, а в частности- в области теории доминирования.
Если вы поняли простой принцип работы данной лотереи, можно переходить к математической постановке задачи. Итак, данную лотерею можно представить с помощью лотерейного графа. Лотерейный граф- это регулярный граф, который в свою очередь задаётся с помощью трех параметров: m,n,k. Давайте разберём каждый из них.
- это параметр, задающий множество всех чисел, которые мы можем вписать в билет.
- это какое-то конкретное 𝑛-элементное подмножество в 𝑈𝑚 = {1,2, … , 𝑚}, которое организатор лотереи назначает как «выигрышный билет».
- участник выигрывает приз (так называемый 𝑘-приз), если хотя бы 𝑘 чисел в билете, который он купил, совпадают с числами в выигрышном билете.
G<m,n,k> - обозначение графа
Представьте, что вы игрок в лотерею ⟨𝑚, 𝑛; 𝑘⟩, и вы хотите сыграть так, чтобы гарантированно выиграть 𝑘-приз. Какое число лотерейных билетов вам нужно купить? Один из вариантов - купить все возможные билеты (их количество равно числу способов выбора 𝑛 элементов из 𝑚-элементного множества). Однако, скорее всего это будет слишком дорого, ведь число различных билетов может быть очень большим. Более выгодный вариант - найти наименьшее количество лотерейных билетов, которые необходимо купить для того, чтобы гарантированно получить 𝑘-приз. Такая стратегия позволит вам максимизировать свою прибыль. Поэтому вам нужно выбрать наименьшее такое множество 𝐿 лотерейных билетов, чтобы среди них обязательно был хотя бы один билет, в котором есть по крайней мере 𝑘 чисел, совпадающих с числами выигрышного билета, независимо от того, какой выигрышный билет будет выбран. Такое множество 𝐿 называется 𝑘-оптимальным игровым множеством. Количество элементов в этом множестве называется лотерейным числом и обозначается символом 𝐿(𝑚, 𝑛; 𝑘). Как вы уже могли догадаться, если говорить в терминах теории доминирования, то 
- это число доминирования в лотерейном графе, а 
- это степень вершины.
Глава 2. Что было сделано до нас?
Доказано, что любой лотерейный граф регулярен; найдена формула, выражающая степень вершины графа через m, n, k.
Доказано, что некоторые лотерейные графы изоморфны, а именно:
G<m, n, k> ≅ G<m, m - n, m + k - 2n>
Очевидно, что числа доминирования в изоморфных графах равны.
Установлена зависимость роста или убывания 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
Найдены условия для m, n, k, необходимые и достаточные для того, чтобы L(m, n, k) было равно 1; 2; 3.
Глава 3. Что сделала наша команда?
Независимо от уже существующих статей самостоятельно доказали необходимость и достаточность для фиксированного L=1 и L=2.
: если выполняются данные условия, то число доминирования = 2.
Также независимо получили формулу нахождения степени вершины графа:
Вывели общую зависимость для частных наборов m,n,k, при которых L строго определено.
Формулировка утверждения:
Если
Доказательство:
Рассмотрим
Если х билетами мы покрываем числа от a1 до axn, то для формирования верхней оценки на k необходимо распределить (n-t) элементов по х билетам,
Так как для формирования верхней оценки на k требуется множества выигрышных чисел Cj 1 ≤ j ≤ n, распределить n- элементов Cj по всем билетам.
Постановка новой задачи:
Основной целью текущей проблемы является расширение уже полученной закономерности путем преодоления границы на параметр 𝑘, что позволит нам получить более полное решение задачи.
Гипотеза 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. Частные случаи столото
Лотерея 7 из 49
Значение k, нижняя оценка на L | Убыток |
2, L≥ 4 | -150 |
3, L≥ 20 | -850 |
4, L≥ 205 | -9.900 |
5, L≥ 4675 | -464.550 |
6, L≥ 291189 | -14.409.450 |
7, L= 85900584 | -4.245.029.200 |
Выигрывают билеты, в которых 2, 3, 4, 5, 6 или 7 чисел из 49 совпали с выпавшими числами.
Если вы угадали 7 чисел, вы выиграли многомиллионный суперприз.
Выигрыши за 2, 3, 4, 5 и 6 угаданных чисел являются фиксированными.
Лотерея 6 из 45
Значение k, нижняя оценка на L | Убыток |
2, L=15 | -650 |
3, L ≥ 42 | -1.800 |
4, L = 946 | -45.800 |
5, L ≥ 39732 | -464.550 |
6, L = 8145060 | -392.253.000 |
Выигрывают комбинации, в которых 2, 3, 4, 5 или 6 чисел из 45 совпали с выпавшими числами.
Если вы угадали 6 чисел из 45, вы выиграли многомиллионный суперприз.
Выигрыши за 2, 3, 4 и 5 угаданных чисел являются фиксированными
С каждой дополнительной цифрой в билете его стоимость увеличивается
Лотерея 5 из 36
Значение k, нижняя оценка на L | Убыток |
2, L ≥ 15 | -840 |
3,L ≥ 112 | -6.120 |
4, L ≥ 2417 | -139.020 |
5, L ≥ 376992 | -2.169.520 |
5+1, L ≥ 376992 | -80.000.000 |
В лотерее предусмотрено пять выигрышных категорий: три с фиксированными выигрышами и две с накапливаемыми суперпризом и призом. Угадав 5 чисел в поле 1 и 1 число в поле 2, вы получаете суперприз. Угадав только 5 чисел в поле 1 и ни одного числа в поле 2, вы получаете приз.
Призовой фонд лотереи — 50% с каждого проданного билета.
Сначала начисляются фиксированные выигрыши за 2, 3 и 4 угаданных числа в первом поле:
4 из 20 x2
Значение k, значение L | Убыток |
4 и 4, L1 ×L2 = 4845×4845 | -5.568.506.250 |
5 и 4, L1 ×L2 = 4845×400 | -2.182.500.000 |
4 и 6, L1 ×L2 = 4845×66 | -899.137.500 |
5 и 5, L1 ×L2 = 400×400 | -700.000.000 |
5 и 6, L1 ×L2 = 66×400 | -195.000.000 |
6 и 6, L1 ×L2 = 66×66 | +54.975.000 |
После определения выигрышной комбинации проводится подсчет результатов. Лотерея имеет 12 выигрышных категорий.
Если вы угадали 4 числа из 20 в первом поле и 4 числа из 20 — во втором, вы выиграли многомиллионный суперприз.
Если в текущем тираже никто не угадает 4 + 4 числа, накопленная сумма переходит на следующий тираж. Если суперприз разыгран, то в следующем тираже будет разыгрываться минимальный гарантированный суперприз, составляющий 100 000 000 рублей.
Если суперприз накопится до 300.000.000, то возможно выиграть +54.975.000!
Проще, чем 2×2
Значение k, нижняя оценка на L | Убыток |
2×2, L×L ≥ 325 × 325 | -1.534.375 |
3×2, L×L ≥ 113 × 325 | -1.602.625 |
3×3, L×L ≥ 113 × 113 | -1.673.815 |
4×2, L×L ≥ 59 × 325 | -1.675.750 |
4×3, L×L ≥ 59 × 113 | -1.750.090 |
4×4, L×L ≥ 59 × 59 | -1.829.740 |
5×2, L×L ≥ 37 × 325 | -1.753.750 |
5×3, L×L ≥ 37 × 113 | -1.831.450 |
5×4, L×L ≥ 37 × 59 | -1.914.700 |
5×5, L×L ≥ 37 × 37 | -2.003.500 |
Есть два поля, в каждом из которых можно выбрать 2 или более чисел из 26. Для каждого поля существует пара выигрышных чисел - в зависимости от того, сколько из них вы угадаете, вы выиграете определённую сумму. В таблице (нашей) приведена нижняя оценка суммы, которую необходимо потратить, чтобы гарантированно выиграть суперприз.
Всё, или ничего
Значение k, значение L | Убыток |
12, L= 2.704.156 | -265.415.600 |
0, L= 2.704.156 | -265.415.600 |
Название говорит само за себя, можно выиграть либо джекпот, либо ничего. Если вы угадываете все числа или ни одного, то получаете джекпот в размере 5000000 руб.
Рапидо
Значение k, нижняя оценка на L | Убыток |
k = 4+1, L ≥ 3 | -7.700 |
k = 5+0, L ≥ 9 | -4.400 |
k = 5+1, L ≥ 9 | -21.700 |
k =6+0, L ≥ 65 | -38.500 |
k = 6+1, L ≥ 65 | -164.500 |
k = 7+0, L ≥ 1299 | -55.930 |
k = 7+1, L ≥ 1299 | -3.497.200 |
k = 8+0, L ≥ 125970 | -87.479.000 |
k = 8+1, L ≥ 125970 | -342.716.000 |
В лотерее есть 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
Долгополов Кирилл Владимирович.
Куратор: Захаров Алексей Евгеньевич.
