Minimum 10K Runners

Probability Level 4

A 10 km race has 5 water stations set up around the course. What is the minimum number of people that must run in the race in order to guarantee that 10 people stop at the same set of water stations?

Details and assumptions

A racer may stop at none of the water stations. (The set of water stations such a racer stops at is called the null set.)

The answer is 289.

2 solutions

Calvin Lin Staff
May 13, 2014

There are $2^5= 32$ possible sets of water stations that a racer could stop at. If 9 people stopped at each possible set then there would be 288 people in the race. If there are $288 + 1 = 289$ people in the race, then by the pigeonhole principle, at least $\left \lceil \frac {289}{32} \right \rceil =10$ people must stop at the same set of water stations.

Fang Ting Goh
May 20, 2014

There are altogether 32 sets of water station, this is derived from $5C0+5C1+5C2+5C3+5C4+5C5=32$ . The minimum number of runners to ensure that there are already 9 runners that has stopped at the same set of water station is 32x9=288. Hence when one more person enters the run, he will be the 10th person that has stopped at one set of water station. Thus the minimum number of runners is 288+1=289

This is a common mistake made in solutions. They give a descriptive construction, and then assume that all other constructions must use their base case. For example, we could have 288 runners, but with a set of water stations that do not have 9 people who stopped at that set.

How would you fix this solution?

Calvin Lin Staff - 7 years ago

Minimum 10K Runners

The answer is 289.

2 solutions

0 pending reports