Ile naklejek potrzebuję, aby ukończyć album FIFA Panini?

Gram w FIFA Panini Online Sticker Album , który jest internetową adaptacją klasycznych albumów Panini, które są zwykle wydawane na mistrzostwa świata w piłce nożnej, mistrzostwa Europy i ewentualnie inne turnieje.

Album zawiera symbole zastępcze dla 424 różnych naklejek. Celem gry jest zebranie wszystkich 424. Naklejki są dostarczane w paczkach po 5, które można uzyskać za pomocą kodów znalezionych online (lub, w przypadku klasycznego drukowanego albumu, zakupionych w lokalnym kiosku).

Przyjmuję następujące założenia:

Wszystkie naklejki są publikowane w tej samej ilości.
Jedna paczka naklejek nie zawiera duplikatów.

Jak mogę dowiedzieć się, ile paczek naklejek muszę zdobyć, aby mieć pewność (powiedzmy 90%), że mam wszystkie 424 unikalne naklejki?

probability coupon-collector-problem

— Vidar S. Ramdal
źródło

Wiele pytań można uzyskać, czytając inne pytania dotyczące problemu kolekcjonera kuponów .

— Glen_b

Potrzebujesz 700 paczek; wówczas szansa na zdobycie wszystkich 424 naklejek wynosi 90,0024%. Potrzebnych jest 761, aby zwiększyć szansę na 95%, a 898 na 99%. (Średnio potrzeba prawie 560 paczek do ukończenia zestawu. Jest mało prawdopodobne (rzadziej niż raz na tysiąc), że potrzebnych byłoby mniej niż 352).

— whuber

Nie jestem pewien, czy można przyjąć pierwsze założenie. „Shinies” są rzadsze.

— James

Hmm, z tego, co mogłem przeczytać w dokumencie opublikowanym przez Asuranceturix, udowodnili, że nie było znaczącej różnicy.

— Vidar S. Ramdal

@ VidarS.Ramdal Stoję poprawiony.

— James

Odpowiedzi:

To piękny problem z kolekcjonerami kuponów, z niewielkim zdziwieniem wprowadzonym przez fakt, że naklejki są pakowane po 5 sztuk.

Jeśli naklejki zostały zakupione indywidualnie, wynik jest znany, jak widać tutaj .

Wszystkie szacunki 90% górnej granicy dla indywidualnie kupowanych naklejek są również górnymi granicami dla problemu z paczką 5, ale mniej bliską górną granicą.

Myślę, że uzyskanie lepszej górnej granicy prawdopodobieństwa 90%, przy użyciu pakietu 5 zależności, stałoby się znacznie trudniejsze i nie dałoby znacznie lepszego wyniku.

Tak więc, używając oszacowania ogona przy i , dojdziesz do dobra odpowiedź. $P[T>\beta n \log n] \leq n^{-\beta+1}$ $n=424$ $n^{-\beta+1} = 0.1$

EDYCJA :

Artykuł „Problem kolekcjonera z rysunkami grupowymi” (Wolfgang Stadje), odniesienie do artykułu autorstwa Assuranceturix, przedstawia dokładne analityczne rozwiązanie problemu kolekcjonerskiego kuponu z „pakietami naklejek”.

Przed napisaniem twierdzenia niektóre definicje notacji: będzie zbiorem wszystkich możliwych naklejek,. byłby podzbiorem, który Cię interesuje (w OP, ), a. Narysujemy z zamiennymi, losowymi podzbiorami różnych naklejek. będzie liczbą elementów pojawiających się w co najmniej jednym z tych podzbiorów. $S$ $s = |S|$ $A \subset S$ $A = S$ $l = |A|$ $k$ $m$ $X_{k}(A)$ $A$

Twierdzenie mówi, że:

P (X_{k} (A) = n) = (\binom{l}{n}) \sum_{j = 0}^{n} (- 1)^{j} (\binom{n}{j}) [(\binom{s + n - l - j}{m}) / (\binom{s}{m})]^{k}

$P(X_{k}(A) = n) = {l \choose n} \sum_{j=0}^{n}(-1)^j {n \choose j}[{s+n-l-j \choose m}/{s \choose m}]^k$

Tak więc, dla PO mamy i . Próbowałem z wartościami pobliżu oszacowania dla problemu klasycznego kolekcjonera kuponów (729 paczek) i uzyskałem prawdopodobieństwo 90,02% dla k równego 700 . $l=s=n=424$ $m=5$ $k$

Więc nie było tak daleko od górnej granicy :)

— Jundiaius
źródło

A ta dobra odpowiedź by?

— ziggystar

Około 3642 losowych naklejek. Zatem górna granica dla „pakietu 5 problemów” wynosiłaby mniej niż 729 paczek.

— Jundiaius

Pewnego dnia natknąłem się na artykuł, który porusza ściśle powiązane pytanie:

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

Jeśli dobrze to zrozumiałem, oczekiwana liczba paczek, które musiałbyś kupić, to:

$\binom{424}{5}\sum_{j=1}^{424}\left(-1\right)^{j+1}\frac{\binom{424}{j}}{\binom{424}{5}-\binom{424-j}{5}}$

Jednak, jak podkreślono w komentarzach, konkretne pytanie, które zadaje OP, zostało szczegółowo omówione w innym dokumencie, który nie jest otwartym dostępem.

Ich końcowy wniosek sugeruje następującą strategię (dla albumu z 660 naklejkami):

Kup pudełko zawierające 100 paczek po 5 naklejek (500 naklejek, które gwarantują, że wszystko będzie inne)
Kup 40 kolejnych paczek po 5 naklejek i zamieniaj duplikaty, aż pozostanie maksymalnie 50 brakujących naklejek.
Kup pozostałe naklejki bezpośrednio od Panini (kosztują one około 1,5 raza więcej).

Jest to łącznie 140 paczek + do 15 dodatkowych paczek o wartości naklejek (według kosztów) zakupionych w sposób ukierunkowany, co odpowiada najwyżej 155 paczkom .

— Asuranceturix
źródło

Świetny! Wydaje się, że głównym argumentem ich wyników byłby artykuł „Problem kolekcjonera z rysunkami grupowymi” , który niestety nie jest otwarty.

— Jundiaius

Haha, to świetnie! Zagłębiają się również w szczegóły, w jaki sposób zamiana wpływa na wynik (który pominąłem w pytaniu). Bardzo interesujące, dzięki!

— Vidar S. Ramdal,

Czy potrafisz streścić rozwiązanie problemu PO przedstawione w artykule? Linki czasem wygasają, a wtedy ta odpowiedź będzie mniej przydatna.

— Andy

@Andy: Zredagowałem odpowiedź, aby odpowiedzieć na twoje obawy, ale nie jest to dokładnie odpowiedź na pierwotne pytanie. Niestety, oryginalny artykuł, który zawiera tę odpowiedź, jest dla mnie zbyt trudny do odczytania, przepraszam.

— Asuranceturix

Mam wątpliwości co do pudełka zawierającego 100 paczek, które zawierają tylko wyraźne naklejki. Wydaje się, że spowodowałoby to ogromne i niepotrzebne komplikacje produkcyjne, przynosząc niewielkie korzyści.

— jwg