Способ заработать на лотерее?

Question

[vladimirovich]

Тут вот такая новость: джекпот на шведской лотерее 224.7 млн крон, стоимость одного билета 16 крон, соответственно, купить все варианты — 223.7 млн крон. Опуская вопрос с налогообложением, переведём его в плоскость программирования.


Заполнить 13 983 816 билетов сложно. Но правилами лотереи разрешается ставить до 17 крестиков в одном билете. Это в лучшем случае облегчит нам работу в 12376 раз — то есть до вполне реальных тысячи с чем-то билетов. Ура?


Вопрос — как купить и как заполнить минимальное количество билетов с минимальным (или вовсе отсутствующим) перекрытием, заведомо покрыв все комбинации?

Answer 1

[Anatole]

В российских условиях, возможность заработать есть только у владельца лотереи :)

Answer 2

[Виталий Желтяков]

Конечно, многое зависит от условий — внешний вид, бумага билета, возможность/законность печати на билете.
Но на в скидку, могу предложить написать макрос в MS Word, который сформирует заполнение ваших 12 тыс. билетов. Затем билеты помещаем в лоток принтера и печатать, печатать и ещё раз печатать.

Comments

[vladimirovich]

Блин, ребят. Вы вообще не поняли, о чём речь.

Речь о том, как сформировать номера на этих 12 тысячах билетов. Это матзадача!

Скажем, существуют не более четырех билетов с 17 зачеркнутыми числами каждый, у которых не перекрываются ни одни 6.

[Виталий Желтяков]

Чтобы получать правильные ответы, нужно задавать правильные вопросы…

Сначала перебираете все числа с одной цифрой, затем перебираете массив с другой цифрой, исключая предыдущую, затем перебираете массив со следующей цифрой, исключая предыдущие две, и т.д. Это простой алгоритм.

[vladimirovich]

В смысле — все числа с одной цифрой?

Выход вашего алгоритма:

Билет 1 — набор чисел 1
Билет 2 — набор чисел 2
… (и т.д.)

Задача — минимизировать общее количество билетов, покрыв все комбинации.

[Виталий Желтяков]

Мой ответ заминусовали?! Хабр ты уже не тот…

Объясню для не изучавших статистику на пальцах:
— Сначала перебираем все комбинации с цифрой 1;
— Затем перебираем все комбинации с цифрой 2, но без цифры 1;
— Затем перебираем все комбинации с цифрой 3, но без цифр 1 и 2;
— и т.д.
Так вы получите все возможные комбинации.

[vladimirovich]

Комбинации

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17 и
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18

— это возможные комбинации с цифрой 1. Но очевидно, покупка этих двух билетов будет бессмысленна — очень много пересечений. Скажем, если выпадают цифры с 1 по 6, то они есть в обоих билетах, значит за обе эти комбинации придётся заплатить при покупке билетов.

[Виталий Желтяков]

Мы платим не за комбинацию с 1 по 6, а за комбинацию с 1 и изменяемой цифрой.
В самом вашем примере, если мы исключим один из билетов то мы лишимся комбинации с 1 и либо 17, либо 18.

[vladimirovich]

Пожалуйста, напишите ваш алгоритм, например, на псевдокоде. Он всё равно непонятен мне (для меня сейчас это набор слов, честно). На выходе он должен печатать, повторюсь, номера билетов. Можно рассмотреть простой случай (что-т типа мини-лотереи 3 из 7, где разрешено зачеркивать до 5 чисел).

И да, мы платитм, очевидно, за количество покрываемых комбинаций в билете.

Скажем, билет в котором зачеркнуто только 6 чисел покрывает одну такую комбинацию.
Билет, в котором зачеркнуто 7 чисел покрывает 7 таких комбинаций, и стоит в 7 раз дороже.
Билет, в котором зачеркнуто 8 чисел — 28 комбинаций, и стоит в 28 раз дороже.
Это очевидные правила лотереи, где стоимость билета пропорциональна тому, какие шансы на выигрыш он даёт.
Но если вы покупаете билет 1, 2, 3, 4, 5, 6, 7 а за ним 1, 2, 3, 4, 5, 6 — то покупка второго билета не имеет смысла, а деньги за него всё равно нужно будет платить.

[Виталий Желтяков]

Алгоритм описан выше — элементарный перебор всех комбинаций каждого числа с исключением уже перебранных.

Допустим у нас 20 цифр. Нам нужно сначала перебрать все комбинации с единицей, чтобы покрыть все комбинации с единицей.
Мы заполняем первый билет цифрами 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17. Это нам даёт множество комбинаций с единицей.
Остаются цифры 18, 19, 20. Чтобы покрыть комбинации с ними мы заполняем второй билет цифрами 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20. Это нам даёт ещё некоторое множество комбинаций с единицей, но нам не хватает комбинаций с 1, 2, 3, 4, 18, 19, 20 в различных неучтённых ситуациях.
Чтобы учесть не перекрытые комбинации мы заполняем следующий следующий билет цифрами 1, 2, 3, 4, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20. Мы получаем ещё некоторое множество комбинаций с 1, но у нас опять не перекрывается часть комбинаций с 1, 2, 3, 4, 5, 6, 7, 18, 19, 20. Не перекрытых комбинаций стало ещё меньше, но они есть.
Мы будем продолжать так очень долго чтобы обеспечить полное перекрытие всех комбинаций с 1. А потом мы перейдём к двойке и т.д.

[vladimirovich]

Это неоптимально, вы плохо поняли условие задачи. Возвращаясь к исходным данным.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 и
1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

оба покрывают, например, вариант 5, 6, 7, 8, 9, 10 — то есть, за этот вариант вы платите сначала в составе первого билета, а потом в составе второго.

То есть, ваши билеты — каждый покрывает 12376 вариантов, но 3003 варианта у них общие. Получается, что вы платите за 12376*2, а получаете (2*12376-3003) варианта. Выходит, ваш КПД 0,878 — и с таким КПД вы не сможете уйти в выгоду.

[Виталий Желтяков]

Какое ещё КПД в комбинаторике? В данной сфере используется понятие «вероятность».

Чтобы получить 100% вероятность мы должны перебрать абсолютно все комбинации, даже есть придётся платить большие деньги за малые проценты вероятности выигрыша. Мы можем съэкономить деньги только понижая вероятность выигрыша, но тогда появляется вероятность проигрыша.

[vladimirovich]

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

Мы должны перебрать все комбинации, но только по одному разу. А вы перебираете некоторые комбинации по нескольку раз.

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

[Виталий Желтяков]

Повторения комбинаций появляются в случаях, если мы ставим больше крестиков, чем 6. Таким образом самым экономным способом будет покупка билетов с 6 крестиками.

[vladimirovich]

Нет, это не так.

Например, у комбинаций

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17 и
13,14,15,16,17,18,19, 20, 21, 22, 23, 24, 25, 26. 27, 28, 29, 30

Нет ни одной общей шестёрки чисел.

[Виталий Желтяков]

Вы что не можете допереть, что чтобы обеспечить 100% выигрыш нужно ещё обеспечить 0% проигрыш.

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

[vladimirovich]

Добейте оставшиеся шестичисловыми билетами (это всегда возможно для любого случая). И это всё равно получится лучше, чем выбирать всё пространство комбинаций шестичисловыми, верно же?

[Виталий Желтяков]

Единственный случай, когда удобно (но не выгодно — по деньгам тоже самое), это когда мы покупаем билеты с полностью разными цифрами, а остальное добиваем билетами с 6 крестиками.

[vladimirovich]

Не очевидно.

[Виталий Желтяков]

Что не очевидно?

[vladimirovich]

Знаете, по-моему вы меня просто троллите. Ну, я не знаю, зачем.

Вот допустим у вас есть задача — угадать 2 из 6, а разрешено покупать билеты в три цифры.

По вашему способу нужно купить 1,2,3 и 4,5,6, а оставшееся забить двойками.

Но очевидно выгоднее купить 1,2,3 и 3,4,5 и 5,6,1 и забить двойками оставшееся.

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

[Виталий Желтяков]

А по моему Вы троллите математику…

В последнем случае правда ваша. Но это Вам не особо поможет — посчитайте возможное число комбинаций.

[vladimirovich]

Так это вы троллите математику! Правда моя, но «не особо поможет». Ну, посчитайте.

Ещё раз — если вы сформулировали какое-то утверждение, то за ним должно следовать далее строгое мат доказательство. Если я на ваше утверждение нашел хотя бы один контрпример — оно уже не верное.

[Виталий Желтяков]

Чтобы посчитать, мне нужно хотя бы знать количество чисел.?

[vladimirovich]

Вот вам задача в самой общей постановке. Дано.

Лотерея "k из n".
В билетах разрешено зачеркивать любое число чисел от k до p. Стоимость такого билета с d зачеркнутыми цифрами пропорциональна числу сочетаний k из d.
Нужно написать алгоритм, который выдаёт оптимальный набор билетов, которые не перекрываются, и которые покрывают всё множество комбинаций.
Нужно доказать, что такой алгоритм — оптимальный. Что нет заведомо более лучшей комбинации. Доказать строго (т.к. алгоритм перебрал все варианты, а те которые не перебрал — мат доказательство, что они не оптимальные).
Тут что-то не понятно?

[Виталий Желтяков]

Загнули. Вы мне предлагаете Вам на пальцах доказать половину теорем комбинаторики, начиная с бинома Ньютона?
Я уже понял, что у Вас большие пробелы в этой области.

Просто назовите число чисел в вашей лотерее, а я посчитаю сколько билетов Вам понадобиться.

[vladimirovich]

И вы сможете доказать, что меньшим числом обойтись невозможно, верно?

[Виталий Желтяков]

А что там доказывать?
Количество комбинаций увеличивается геометрически (по факториалу), соответственно, нам, чтобы уменьшить количество билетов нужно взять сначала билеты с максимально возможным числом крестиков, без повторения комбинаций.

Почему число комбинаций увеличивается геометрически Вы можете прочитать в учебнике по комбинаторике.

[vladimirovich]

Я уже написал случай, когда ваше «без повторения» не оптимально, но вы как-будто этого не заметили. Вот простая задача: угадать 2 из 6. Разрешено зачеркивать до трёх цифр. Какой оптимальный набор билетов?

[Виталий Желтяков]

Я уже написал, что ваш вариант будет правильный, т.к. нет повторений комбинаций.

[vladimirovich]

В таком случае, почему вы настаиваете на своём варианте, если я привёл уже один пример когда он будет не оптимален?

[Виталий Желтяков]

Вы походу запутались. Что Вы имеете в виду под моим вариантом?

[vladimirovich]

«взять сначала билеты с максимально возможным числом крестиков, без повторения комбинаций». Что это значит, как минимум, уже непонятно (это не строгое объяснение). Я, повторюсь, вы же не пишите АЛГОРИТМ, ПРОГРАММУ, а просто выражаетесь на русском языке — а он не строгий.

Вот с программой уже можно иметь дело.

[Виталий Желтяков]

У вас условия задачи постепенны неправильно чтобы по ним делать алгоритм — нет ограничения на количество «крестиков». При вашей подаче самым оптимальным вариантом будет покупка билета с n «крестиками».

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

[vladimirovich]

Крупные перебрали, дальше?

Вы сможете доказать, что их нужно добивать только через самую мелочовку, или можно более крупными билетами?

[Виталий Желтяков]

Если мы будем добавлять не мелочовкой, то будут повторения комбинаций, что очевидно — множества пересекаются.

[vladimirovich]

(раздраженно) это тоже не так. Вы не приводите строго мат доказательства. Допустим, нужно угадать всего 1 число из 8. А разрешено зачеркивать 3 числа.

Тогда билеты
«1,2,3»
«4,5,6»

По вашему нужно добить мелочевкой, т.е. билетами «7» и «8».
А можно всего одним билетом
«7,8»

[Виталий Желтяков]

Строгого мат.доказательства я приводить не буду — если оно Вам нужно, то возьмите учебник по комбинаторике.

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

Сколько чисел в вашей лотерее? А то мне спать пора.

[vladimirovich]

Вы хотите сказать, что данная задача разбиралась — в том виде, котором я её поставил — где-то в учебнике? Если да, то просто дайте ссылку. А если нет, то и всё.

Я уже написал, что вы формулируете свои мысли не строго. Да, общая идея, видимо, «сначала крупными, потом мелкикими», но это вовсе не даёт нам строго алгоритма, как мне нужно.

[vladimirovich]

И да, задачу нужно решать для произвольных чисел (в этом и смысл решения задачи). Это как вы бы теорему ферма доказывали не для произвольных чисел, а для трёх конкретных. Смешно.

[Виталий Желтяков]

«то и всё»… Такому как Вы, я не собираюсь объяснять, как это доказывается — у Вас практический нулевой уровень.

Удачи.

[vladimirovich]

Вы мой нулевой уровень как определили? Тем, что я легко на ваши утверждения нашел контрпримеры, которые в признали?

Удачи :-)

[sl_bug]

Фух. Осил :) Самое прикольное что как бы правы оба. Попытаюсь я рассказать мысль VitaZheltyakov.
1. Набираем комбинации максимальным количеством цифр (пусть это будет — P) без единого повторения.
2. Остатки добиваем мелкими (вот тут и непонятки). Мелкими это не значит по 1 цифре. Это значит — (P — 1), потом (P — 2) и т.д.

Как-то так…

[vladimirovich]

1. Что значит без единого повторения? Я уже писал случай, когда повторения явно выгодны. habrahabr.ru/qa/36335/#comment_173837
2. Как сделать по (P-1) заведомо без пересечений с предыдущими?

[Виталий Желтяков]

1. Без единого повторения комбинации. Числа в «больших» (с максимальным числом крестиков) билетах могут перекрываться меньше, чем комбинация.
2. Внутрениий цикл с проверкой предыдущих комбинаций.

[vladimirovich]

1. Не приведён алгоритм получения комбинаций без повторений. Это можно, очевидно, сделать несколькими способами. Возможно, одни из них окажутся более оптимальными для будущих «добитий», чем другие.
2. Нет алгоритма этого внутреннего цикла без повторений, оценки сложности этого алгоритма (будет ли он работать полиномиальное от входа время или экспоненциальное).
3. Пока нет строгого доказательства, что начинать всегда нужно с максимума и «добивать» им до упора. Да, число комбинаций растёт быстро, ну и что? Есть функции, которые растут быстрее факториала. Возможно, взяв «большой кирпичик слишком неправильной формы» в начале, потом придётся добивать слишком большим числом мелких.

Вы, конечно, обвиняли меня в недостаточном уровне знаний. В таком случае, вы наверняка знаете, что "Задача о Рюкзаке", например, при всей своей простоте формулировки не имеет полиномиального точного решения, и простого приблеженного решения тоже не имеет.

[sl_bug]

А расскажите сколько всего чисел, сколько нужно угадать? Все билеты одинаковые? (последовательные числа от 1 до максимума).

[Виталий Желтяков]

1. Самый простой алгоритм приведён в моём втором комментарии — перебор всех комбинаций в лоб при помощи рекурсии. Проще просто не придумаете, т.к. число проходов равно числу возможных комбинаций.
2. Внутрений алгоритм представляет собой цикл с сравнением комбинаций. Самым простым способом будет проверка чисел комбинации на принадлеженость разным «большим билетам». Количество переборов будет увеличено на 6 — число цифр в комбинации.
3. Я уже вам его приводил — количество комбинаций увеличивается в геометрической прогрессии, поэтому самым выгодным будет взятие сначала самых «больших» билетов.

Задача о рюкзаке не в тему, т.к. условия другие — у нас комбинации все равновероятностны.

[sl_bug]

И еще по вычислению стоимости расскажите, а то может быть смысла нет покупать по 17 чисел?

[vladimirovich]

1. Не приведена оценка, как такая рекурсия будет работать, непонятно что такое «комбинация» в применении к данному вопросу. В данном случае нужно перебрать все возможные способы выбрать все билеты, и это число астрономическое. Но непонятно даже, как написать этот алгоритм. Если вы хотите — используйте псевдокод.
2. Как провести эту проверку? Вот есть список чисел билетов A, и B, и что?
3. Это утверждение не является точно математически сформулированным. "количество комбинаций увеличивается в геометрической прогрессии" — каких комбинаций и в зависимости от чего? Как это поможет в применении к нашей задаче? Строго математически, чтобы доказать теорему, вы должны сравнить две зависимости между собой, и доказать что одна больше. А не просто «видно, что одна очень большая и растёт быстро».

Пожалуйста. Используйте точные мат формулировки.

[vladimirovich]

Т.е. поясню. У вас есть число комбинаций, которое растёт экспоненциально, но есть и число оставшихся билетов которые мы должны будем заполнить чтобы было без перекрытия. Даже если число растёт экспоненциально, совсем не факт что число оставшихся билетов не будет расти быстрее, чем этот рост. Это требуется до-ка-зать.

[Виталий Желтяков]

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

[vladimirovich]

Фраза, «я не собираюсь Вам ничего доказывать, т.к. это уже давно доказано» — тут следует либо привести ссылку, на место где разбиралась ровно такая задача, а не на «учебник комбинаторики».

Ну и наконец. Википедия говорит, что экспоненциальный рост и геометрический рост — это одно и то же. А то, что вы попутали его с логарифмическим, ну это наверное я, нуб, виноват :-)

Кстати, если я недостоин вашего внимания, то мне можно просто не отвечать в этом треде. Боюсь, вы правда не удержитесь ещё рас сказать мне, какое я ничтожество :-)

[Виталий Желтяков]

Мне не обязательно что-то говорить — любой человек, который хоть когда-то изучал комбинаторику, встанет на мою сторону.

[vladimirovich]

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

[Виталий Желтяков]

Любой экспонентальный рост — это геометрический рост. Любой геометрический рост — это не обязательно экпонентальный рост. Ещё один прокол с вашей стороны. Если читаете Википедию, то читайте внимательнее.

[vladimirovich]

Экспоненциальный — это обобщение геометрического на область непрерывных величин. У нас величины дискретные. Так что в нашем случае это эквивалентно.

[Виталий Желтяков]

Я даже не знаю, как комментировать ваш ответ… Вы связываете вид функции роста с дискретностью множества.

[vladimirovich]

Кстати, рост числа комбинаций рассматривается — в зависимости от чего? От числа крестиков в билете?

Ну так он вообще не является ни геометрическим, ни экспоненциальным.

[Виталий Желтяков]

Вы так решили потому что этого нет в Википедии? А если своей головой подумать? Рост количества комбинаций происходит согласно факториалу, то есть геометрически.

[vladimirovich]

Рост числа комбинаций чего в зависимости от чего? Ещё раз: "чего в зависимости от чего" Вы правда, когда формулируете — формулируете настолько расплывчато, а когда вам предлагают уточнить, говорите что уточнения нужны для нубов, а всем и так всё понятно. Ну да, ну да.

Согласно факториалу — это количество комбинаций из n предметов.

Кроме того, факториал растёт значительно быстрее экспоненциальной функции. Формула Стирлинга, вот это всё.

[Виталий Желтяков]

Поимите одну важную вещь — я Вам ничего не должен (доказывать/писать/уточнять), но за то Вы должны обладать хотябы какими-то заниями.

[vladimirovich]

Я задал вопрос. Вы взялись отвечать. Я же вас силком не тянул :-) Но на полпути вы закрыли тему, потому что а) всем якобы всё очевидно б) раз мне не очевидно, то проблема во мне. Отлично. Эту вашу точку зрения я понял. У вас есть ещё что-то новое мне сообщить?

[Виталий Желтяков]

Нет, мне нечего Вам сообщать и так всё понятно.

[vladimirovich]

В таком случае, спасибо, до свидания, надеюсь больше вас в этом треде я не увижу.

Answer 3

[vsespb]

Помню в 90-х годах. На улице, у метро, происходила лотерея. Девушка громко призывала толпу купить билеты.
Через какое-то время оказывалось что выигрышный билет ещё никто не купил. А билетов осталось всего 3 по 10 рублей (например), и один из ниху гарантированно выигрышный (выигрыш 500 рублей, например).
О чём честно говорила девушка-продавец. Т.е. если купить все три билеты гарантированно будем в плюсе.

Незнаю покупал ли кто-то… Но эта история повторялась каждый день

Answer 4

[sl_bug]

gist.github.com/slbug/88b19f5b3f9e32961f46

Вот вам алгоритм. Оптимизируйте сами. Там два примера с ответами приведены.

Answer 5

[oleg1977]

а если второй умник найдется придется джекпот пополам делить

Comments

[vladimirovich]

Да.