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?

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ź. n = 424 n - β + 1 = $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 | A ⊂ S A = S l = | A | k m X k ( A ) $S$$s = |S|$$A \subset S$$A = S$$l = |A|$$k$$m$$X_{k}(A)$$A$

Twierdzenie mówi, że:

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 .m = 5 $l=s=n=424$$m=5$$k$

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

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 .