91Ó°ÊÓ

We have 101 items to distribute uniformly and randomly among 10 boxes. We want to prove that at least one of the boxes contains at least 11 items.

Instead of proving that at least one box contains at least 11 items, we will look at the complementary situation: all boxes contain 10 or fewer items. If the probability of the complementary situation is less than 1, then it must be true that at least one box contains at least 11 items with positive probability.

There are \(10^{101}\) ways to distribute 101 items uniformly and randomly among 10 boxes since each item has a choice of 10 boxes.

We will calculate the number of ways to distribute 101 items among 10 boxes such that each box contains at most 10 items. For each box, let \(x_i\) denote the number of items in box i. We want to find all non-negative integer solutions for \(x_1 + x_2 + ... + x_{10} = 101\) such that \(0 \leq x_i \leq 10\) for all i. By using a stars and bars argument, we find that there are a total of \(\binom{101+10-1}{10-1} = \binom{110}{9}\) ways to distribute 101 items among 10 boxes without any restrictions. Now we need to subtract those cases where at least one box has more than 10 items. To do this, we will use the inclusion-exclusion principle. Let A_i be the event that box i contains more than 10 items. Then, we have: Number of ways with complementary criteria = \(\sum_{i=1}^{10}(-1)^{i+1} \cdot f(i)\) where f(i) is the total number of ways of selecting i disjoint events A_i. Notice that \(f(i) = {10 \choose i} \cdot \binom{101 - 11i + (10 - i)}{9}\) because we are first choosing i boxes from 10 that have more than 11 items and then distributing the remaining items. So, the number of ways with complementary criteria is: \(\sum_{i=1}^{10}(-1)^{i+1} \cdot {10 \choose i} \cdot \binom{101 - 11i + (10 - i)}{9}\)

Divide the number of ways with complementary criteria by the total number of ways to get the probability of the complementary situation: \(P(Complementary) = \frac{\sum_{i=1}^{10}(-1)^{i+1} \cdot {10 \choose i} \cdot \binom{101 - 11i + (10 - i)}{9}}{10^{101}}\)

Since the value of the numerator is less than \(10^{101}\) (as every term in the sum is less than the total number of ways), it's clear that: \(P(Complementary) < 1\)

Since the probability of the complementary situation occurring (all 10 boxes contain 10 or fewer items) is less than 1, it must be true with positive probability that at least one of the boxes contains at least 11 items. Hence, we have proved that when distributing 101 items into 10 boxes, at least one box must contain more than 10 items, using the probabilistic method.