Pigeon Hole Principle - Minimum customers needed such that at least one is a winner

Question

I was reading about pigeon-hole principle from this paper.

If n items are put into m pigeonholes with n > m ( m,n ∈ N ∗ ), then at least one pigeonhole must contain more than one item.

One of the applications of the principle is stated as:

Pitter is the boss of a lotto games company, the lottery is a number which contains 5 digits. Every month, the machine picks up 1 number randomly and the owner of the lottery ticket with the same number will win one million dollars. In order to demonstrate the justice of the lottery, there must be at least one winner every month.

Based on the former condition, calculate the minimum number of customers should this ticket be sold to.

which has the solution as:

Since every digit of the number varies from 0 to 9, there are 10⁵ numbers in total. As a result of it, according to the Pigeonhole Principle, the number of customers should be at least 10⁵ + 1 = 100001.

So, as far as I understand the question and try to relate it with the basics of the principle:

1. The possible lottery tickets are holes here.
2. Customers are pigeon here.
3. We need to find the minimum pigeons (customers) required such that one hole (ticket) is occupied by more than one pigeon.

This evaluates to: $100001$ customer required such that two of them share the same ticket. But I cannot understand the solution as it tries to evaluate minimum number of customer required to make the game "justified" or "such that there is at least one winner".

1. The machine can pickup any random number (of $5$ digits) and if a lottery number can be assigned only to a single customer, then $10^5$ is least number of customers required such that at least one wins. And in this case, there are no ticket left so $10^5+1$ ($1$ extra customer) is out of question.
2. If more than one customer is allowed to pick up same tickets, then $10^5+1$ customers can also pickup the same ticket (obviously, very low probability) and there could be no winner.

I'm sure I'm missing something here.

Answer 1

Just so this question has an answer:

• Yes, you are correct saying that if $10^5$ different numbers tickets are bought then the probability of somebody winning is $100\%$

• Yes, you are correct saying that if $10^5+1$ or more tickets are bought then the pigeonhole principle means that at least two tickets have the same numbers, since there are only $10^5$ possible numbers

• Yes, you are correct saying that if different tickets can have the same numbers and the purchasers choose the numbers or they are generated at random then it is possible that some numbers may not appear on any tickets and so the probability of there being at least one winning ticket may be less than $100\%$ no matter how many tickets are sold

• There might be a different answer to this last point if Pitter (the ticket seller) decides which numbers appear on each ticket, but that could take you back to the first point of $10^5$ rather than $10^5+1$ as the minimum number of tickets needed to be sold to be able to ensure a $100\%$ probability of a winner

• If $n$ tickets are sold, and the winning number is picked uniformly at random from the $10^5$ possibilities independently of the numbers on the sold tickets, then the expected number of winners is $\frac{n}{10^5}$; this reaches $1$ when $n=10^5$ but the expectation of at least one winner is not equivalent to there being a $100\%$ probability of at least one winner

• If $n$ tickets are sold, with each sold ticket and the winning pick chosen independently uniformly at random from the $10^5$ possibilities, then the probability of at least one winner is $1-\left(1-\frac1{10^5}\right)^n \approx 1-e^{-n/10^5}$, which is about $50\%$ for $n=69315$, about $63.2\%$ for $n=10^5$, and about $99.995\%$ for $n=10^6$