Сколько стикеров мне нужно, чтобы завершить мой альбом FIFA Panini?

30

Я играю на альбоме FIFA Panini Online Sticker Album , который представляет собой интернет-адаптацию классических альбомов Panini, которые обычно публикуются для чемпионата мира по футболу, чемпионата Европы и, возможно, других турниров.

Альбом имеет заполнители для 424 различных стикеров. Цель игры - собрать все 424. Стикеры поставляются в пачках по 5 штук, которые можно получить с помощью кодов, найденных в Интернете (или, в случае классического печатного альбома, купленного в местном газетном киоске).

Я делаю следующие предположения:

  • Все стикеры публикуются в одинаковом количестве.
  • Одна упаковка стикеров не содержит дубликатов.

Как я могу узнать, сколько пачек стикеров мне нужно приобрести, чтобы быть уверенным (скажем, на 90%), что у меня есть все 424 уникальных стикера?

Видар С. Рамдал
источник
2
Ряд идей можно почерпнуть, прочитав другие вопросы, связанные с проблемой сбора купонов .
Glen_b
3
Вам нужно 700 упаковок; тогда вероятность приобретения всех 424 стикеров равна 90,0024%. 761 необходимо, чтобы довести шанс до 95% и 898 за шанс 99%. (В среднем, почти 560 пачек необходимо для завершения набора. Маловероятно (менее одного раза в тысяче), что потребуется менее 352).
whuber
1
Я не уверен, что первое предположение может быть сделано. "Блестящие", как правило, реже.
Джеймс
2
Хм, из того, что я мог прочитать из документа, опубликованного Asuranceturix, они доказали, что существенной разницы не было.
Видар С. Рамдал
@ VidarS.Ramdal Я исправлен.
Джеймс

Ответы:

15

Это прекрасная проблема со сборщиком купонов, с небольшим поворотом в связи с тем, что наклейки поставляются в упаковках по 5 штук.

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

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

Я думаю, что получить лучшую верхнюю границу вероятности 90%, используя пакет из 5 зависимостей, будет намного сложнее и не даст вам гораздо лучшего результата.

Итак, используя оценку хвоста сn=424и n - β + 1 =0,1, вы получите хороший ответ.P[T>βnlogn]nβ+1n=424nβ+1=0.1

РЕДАКТИРОВАТЬ :

Статья «Проблема коллекционера с групповыми рисунками» (Вольфганг Стадже), ссылка на статью, предоставленную Assuranceturix, представляет точное аналитическое решение проблемы коллекционера купонов с «наклейками».

Прежде чем писать теорему, определим некоторые обозначения: будет набором всех возможных наклеек, s = | S | , A S будет подмножеством, которое вас интересует (в OP, A = S ), а l = | A |Ss=|S|ASA=Sl=|A|, Мы собираемся нарисовать, с заменой, случайных подмножеств m различных наклеек. X k ( A ) будет количеством элементов A, которые появляются хотя бы в одном из этих подмножеств.kmXk(A)A

Теорема говорит, что:

P(Xk(A)=n)=(ln)j=0n(1)j(nj)[(s+nljm)/(sm)]k

Итак, для ОП у нас есть и m = 5 . Я сделал несколько попыток со значениями k около оценки для классической задачи сборщика купонов (729 упаковок), и я получил вероятность 90,02% для k, равного700.l=s=n=424m=5k

Так что это было не так далеко от верхней границы :)

Jundiaius
источник
И этот хороший ответ будет?
Ziggystar
4
Около 3642 случайных стикеров. Таким образом, верхняя граница для «пакета из 5 проблем» будет меньше 729 пакетов.
Жундиаус
10

На днях я наткнулся на статью, в которой рассматривается тесно связанный вопрос:

http://www.unige.ch/math/folks/velenik/Vulg/Paninimania.pdf

Если я правильно понял, ожидаемое количество упаковок, которое вам нужно будет купить:

(4245)j=1424(1)j+1(424j)(4245)(424j5)

Однако, как отмечают в комментариях eqperes, конкретный вопрос, который задает ОП, на самом деле подробно рассматривается в другом документе, который не является открытым доступом.

Их окончательный вывод предполагает следующую стратегию (для альбома из 660 стикеров):

  • Купите коробку из 100 упаковок по 5 наклеек (500 наклеек, гарантированно все будет по-разному)
  • Купите еще 40 пачек из 5 стикеров и меняйте дубликаты, пока не наберете не более 50 стикеров.
  • Приобретите оставшиеся наклейки непосредственно у Panini (они стоят примерно в 1,5 раза дороже).

Это всего 140 упаковок + до 15 дополнительных упаковок наклеек (по стоимости), приобретенных целевым образом, что эквивалентно максимум 155 упаковкам .

Asuranceturix
источник
Большой! Кажется, что центральным аргументом их результатов будет статья «Проблема коллекционера с групповыми рисунками» , которая, к сожалению, не находится в открытом доступе.
Жундиаус
Хаха, это здорово! Они также подробно рассказывают о том, как свопинг влияет на результат (о котором я не говорил). Очень интересно, спасибо!
Видар С. Рамдал
3
Можете ли вы подвести итог решения проблемы ОП, представленной в документе? Ссылки иногда истекают, и тогда этот ответ станет менее полезным.
Энди
@ Энди: я отредактировал ответ, чтобы решить вашу проблему, но это не совсем ответ на первоначальный вопрос. К сожалению, оригинальная статья, которая дает такой ответ, слишком сложна для чтения, извините.
Asuranceturix
Я сомневаюсь в коробке из 100 упаковок, содержащих только отдельные наклейки. Похоже, что это приведет к огромным и ненужным производственным осложнениям за небольшую выгоду.
JWG