APEC MEETING
UNIVERSITY OF TSUKUBA, TOKYO 2020, FEB 11—12

THE COLLECTOR’S PROBLEM
an example of inciting to thinking

Ivan Vysotskiy, Moscow, MCCME
http://ptlab.mccme.ru

HISTORICAL REVIEWAll parents meet a math problem given by their kid
having got first Kinder Surprise with a toy inside. Thecollection can contain 12 princesses or 10 hippos orsomething even more exiting.
The immediate question – how many eggs do we needto buy to complete the collection?
This leads to a curious statistical and probabilistic model
which is being originally simple grows to adisproportionally and offensively sophisticatedgeneralization as we need two collections for two kids.

HISTORICAL REVIEWThe problem was probably set in de Moivre’s De Mensura
Sortis (1712); mentioned by Laplace in his Théorie
analytique des probabilité (1812).
In 1930-s the American company Dixie Cup used a genial
marketing trick with a coupons inside bottle lids. Ofcourse, one who collects the entire collection waspromised to win a prize.
That’s why the problem is known not only as a Coupon
Collector's Problem, but also as the Dixie Cup Problem,and its generalization to two or more collections is called
the Double Dixie Cup Problem.

HISTORICAL REVIEWThe Classic (Single) Collector’s Problem is easy andcould be a support in teaching geometrics series for 9thgradersE ξ = nH n

And in high school as a support of integrating:E ξ » n ln n + 0,577
Solution of the Double Dixie Cup Problem was obtained
as an integral by Newman and Shepp in 1960. From theirsolution they also drew out an asymptotic formulaE ξ 2 = n ( ln n + ln ln n ) + O ( n )The nature of O ( n ) was examined by Paul ErdősHISTORICAL REVIEWIn 2019, the exact solution was obtained as adeterminant of a certain matrix.
At the same time, the upper estimatior
was proved.

E ξ 2 < nH n + nH H n

However, for many related tasks there is not yet
satisfactory solutions.

WHY THE COLLECTOR’S PROBLEM?
Many of you do think now ‘Why did Ivan decide to blow
the dust off a relic math problem and sell it here at theAPEC meeting?’
The deeper I immerse to the problem the clearer I see
that it is one of the rarest diamonds of math which
deserve not only to mentioned but still has unsolved
aspects and lot of didactical power.
The problem forces to work all mathematics taught inschool. It's various subproblems could serve as easily
apprehensible lifelike motivation for developing what wecall ‘Statistical Thinking’ for 7h-graders and higher.
The most precious feature is that the statistical thinking
here is scarcely working without some probabilitsitc
intuition and math knowledge.

INTRODUCTION
Use a die. When rolling the die, count how many casts
have you done to get all six faces (each at least once).

1 4 4 3 4

5 1 6 3 3

2This time I got it (the full collection of 1 to 6) with 11 trial

INTRODUCTION
Now use a RNG (Excel or any other) with 10 random
integers from 1 to 10.
Run it many times and find how many trials you havedone before you got all ten possible

INTRODUCTION
const n = 10; {the collection volume}
var a:array[1..n] of integer;
count, i,fl,hippo:integer;
begin
randomize;
for i:=1 to n do a[i]:=0;
count:=1; fl:=0;
while fl=0 do begin
hippo:= trunc(random(n+1));a[hippo]:=1;
fl:=1;
for i:=1 to n do fl:=fl*a[i];count:=count+1;
end;
write(count); write(' eggs bought');
end.

INTRODUCTION

45 eggs

INTRODUCTION
Find the average after many (let’ssay 100) such experiments.
You’ll likely get a number close to1ö
æ 1 1
10 × ç1 + + + ... + ÷ .» 29,3.
10 ø
è 2 3
In the two experiments above

12 + 45= 28,5.
2

HUNTING HIPPOS. GRADE 7 - 8You’ve got already 4 hippos out of 10. What is theprobability to get a new hippo (#5) in the next eggbought?
You and your friend decided to collect to entire sets ofhippos. The moment you totally harvested the firstcollection, some hippos still aren’t in the second one.
Prove:P (1 hippo ' s missing ) = P ( 2 hippos are )Show thatP (1) = P ( 2 ) > P ( 3) > P ( 4 ) > ... > P (10 )HUNTING HIPPOS. GRADE 9 – 12
Find the math expectation of the number of missing
hippos when the first collection is completed.
How many spare hippos # 1 in average will you haveafter the 1st collection is completed?
How many spare hippos # 3?
Solve the classic Collector’s problem: show that to holdthe full collection you need to buy in average

1ö
æ 1 1
E ξ = 10 × ç1 + + + ... + ÷ = 10 H1010 øè 2 3
chocolate eggs.

HOW MANY TAXI METER CABS IN KHON KAEN?
Russian doctor of math in Khon Kaen
Was of greatest sagacity man…
One mathematician uses to use taxi meter in Khon Kaenas he often visits this city.
Being incredibly observant and having a memory like anelephant, during the 22nd trip, he noticed that he hadalready used this car once with the same driver.
But the cars have not been repeated before. How many
Taxi Meters cars are there in Khon Kaen?
Can we model this problem using Python or Pascal?

HOW MANY TAXI METER CABS IN KHON KAEN?
For advanced ones, we can pose this task as a project ora mathematical study research. MM gives the equation

πx 1+ = 222 2from whichx » 294

CONCLUSION
To get the estimator 294 for the Khon Kaen Taxi problem
by the way we need to use combinatorics, calculus,
deep ideas about Poisson distribution and Euler gammafunction, Stirling formula, Taylor series, chain fractions
theory and something more.
That’s why I call such problems ‘generous’ anddidactically rich ones.
We saw only a small part of possible mathematicalconstructions connected to the Collector’s problem.
I think that it’s possible to built the whole mathematiccourse for 7 – 12 using exclusively questions being
arisen from the ‘Hunting Hippos’.
Don’t invent math problems.
Take them from the life. For free!

THANK YOU

What is it,Newman??

Shepp, old chap! It’sthe rarest one formy collection