Думаю, все когда-нибудь хоть раз задумывались над тем, как же всё таки выиграть в лотерею. В мире существует огромное количество различных лотерей, но сегодня мы рассмотрим только один, из ее видов, доступный и понятный.
Глава 1. Про какие лотереи мы говорим?
Давайте представим ситуацию: вы решили участвовать в лотерее. Вы покупаете лотерейный билет и вписываете в него несколько каких то чисел. По окончании розыгрыша, организатор лотереи объявляет выигрышную комбинацию чисел. Вы смотрите на нее, на свой заполненный билет и сравнивайте сколько чисел совпало. Если количество совпадений равно какому то фиксированному числу, например, 2, то вы выиграли. В противном случае вы проиграли. Как всё же точно гарантировать выигрыш ? Какое минимальное количество билетов для этого стоит купить ? Переплачивать ведь не хочется ! Именно эти вопросы и были поставлены в задаче «The Lottery Problem», которая существует уже более 60 лет. Изначально задача пришла из области комбинаторики, но нашла своё применение и в области теории графов, а в частности- в области теории доминирования.
Если вы поняли простой принцип работы данной лотереи, можно переходить к математической постановке задачи. Итак, данную лотерею можно представить с помощью лотерейного графа. Лотерейный граф- это регулярный граф, который в свою очередь задаётся с помощью трех параметров: m,n,k. Давайте разберём каждый из них.
— это параметр, задающий множество всех чисел, которые мы можем вписать в билет.
— это какое-то конкретное 𝑛-элементное подмножество в 𝑈𝑚 = {1,2, … , 𝑚}, которое организатор лотереи назначает как «выигрышный билет».
— участник выигрывает приз (так называемый 𝑘-приз), если хотя бы 𝑘 чисел в билете, который он купил, совпадают с числами в выигрышном билете.
G
Представьте, что вы игрок в лотерею ⟨𝑚, 𝑛; 𝑘⟩, и вы хотите сыграть так, чтобы гарантированно выиграть 𝑘-приз. Какое число лотерейных билетов вам нужно купить? Один из вариантов — купить все возможные билеты (их количество равно числу способов выбора 𝑛 элементов из 𝑚-элементного множества). Однако, скорее всего это будет слишком дорого, ведь число различных билетов может быть очень большим. Более выгодный вариант — найти наименьшее количество лотерейных билетов, которые необходимо купить для того, чтобы гарантированно получить 𝑘-приз. Такая стратегия позволит вам максимизировать свою прибыль. Поэтому вам нужно выбрать наименьшее такое множество 𝐿 лотерейных билетов, чтобы среди них обязательно был хотя бы один билет, в котором есть по крайней мере 𝑘 чисел, совпадающих с числами выигрышного билета, независимо от того, какой выигрышный билет будет выбран. Такое множество 𝐿 называется 𝑘-оптимальным игровым множеством. Количество элементов в этом множестве называется лотерейным числом и обозначается символом 𝐿(𝑚, 𝑛; 𝑘). Как вы уже могли догадаться, если говорить в терминах теории доминирования, то 
— это число доминирования в лотерейном графе, а 
— это степень вершины.
Глава 2. Что было сделано до нас?
-
Доказано, что любой лотерейный граф регулярен; найдена формула, выражающая степень вершины графа через m, n, k.
-
Доказано, что некоторые лотерейные графы изоморфны, а именно:
G
Очевидно, что числа доминирования в изоморфных графах равны.
-
Установлена зависимость роста или убывания 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’=L, где F(x’,n) это некоторое ограничение на параметр k. Математическая формулировка: Если в первом случае требовалось подтвердить разбиение m чисел на x билетов, так что оставалось t непокрытых чисел: то теперь, мы разбиваем m чисел на x’ билетов, так что t чисел покрыты более чем одним билетом: Основная проблема: Рассмотрим задачу разбиения 𝑚 чисел на подмножества по 𝑛 билетов. Предположим, что параметр 𝑡 не делится нацело на 𝑛. В этом случае в двух билетах (исключая два) может быть разное количество чисел, покрытых не более чем одним билетом. Задача заключается в определении оптимального способа разделения чисел на подмножества таким образом, чтобы минимизировать различие в количестве чисел, покрываемых каждым билетом, а также в обобщении оценки на k для данного случая. Однако, конкретное значения 𝑚, при которых это утверждение выполняется, зависят от конкретных условий задачи и могут быть определены только после анализа всех возможных случаев. Таким образом, на данным момент наша команда не смогла определить p для ограничения на m: Лотерея 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, мы получим гарантированный профит. . Большая математическая мастерская (БММ) — это уникальное и важное мероприятие, которое предоставляет возможность молодым исследователям и студентам работать над открытыми математическими проблемами и развивать свои навыки презентации полученных результатов во множестве различных форматов. БММ — это место, где учат эффективно общаться с другими людьми, ведь здесь так много заинтересованных и эрудированных людей, которые могут научить новому, а главное- открыты для общения. Это двухнедельное мероприятие, которое помогает участникам из разных уголков России объединиться и работать над передовыми задачами в области математики. Это отличная возможность для тех, кто хочет попробовать себя в научной или околонаучной сфере, найти единомышленников и научного руководителя, наработать базу для грантов и исследований или написать первую публикацию. Во время работы над проектом мы получили много нового опыта и впечатлений. Мы познакомились с интересными экспертами, которые помогли нам проверить наши теории. Особую благодарность хотим выразить куратору проекта Захарову Алексею Евгеньевичу, а также научному специалисту по дискретной математике и комбинаторике Тахонову Ивану Ивановичу, который не только помог углубиться в задачу, но и оказал неоценимую помощь в её решении. Также мы благодарим организаторов потока, которые не только обеспечили комфортные условия для работы, но и стали настоящими друзьями для всех участников Мастерской. Благодаря БММ мы смогли реализовать наш проект и внести вклад в решение задачи «The lottery problem». Мы выражаем благодарность всем участникам и организаторам, которые сделали это возможным. Мы уверены, что полученные результаты будут полезны для дальнейшего развития науки и образования в области математики. Команда проекта. Коньшина Софья Павловна, sofia.konshina1@yandex.r. Бычков Иван Александрович, r3ngoky@yandex.ru , tg: @cupermush Емельянов Роман Иванович, emelroman7@gmail.com Штерн Богдан Игоревич, bogdan_stern@mail.ru Долгополов Кирилл Владимирович. Куратор: Захаров Алексей Евгеньевич.
Глава 4. Частные случаи столото
Глава 5. О работе на БММ
