What is the minimum number of students, each of whom comes from one of the 50 states, who must be enrolled in a university to guarantee that there are at least 100 who come from the same state?

Let’s start with definitions.

THE PIGEONHOLE PRINCIPLE: “If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.” Discrete Mathematics and its applications by Rosen.

Like in previous exercises, let’s find the boxes and the objects. In other words, let’s write our problem in the same way that principle is written.

Seeing that we must guarantee that at least 100 students come from the same state, we can be sure that the 50 states are the boxes.

So, the answer to this exercise is the same as calculating how many objects we need to put in 50 boxes, to guarantee that at least 1 box has 100 students.

As you can see from the previous statement, the pigeonhole principle doesn’t show how to do this calculation.

Fortunately, we have the generalized pigeonhole principle to use in this type of situations. The type of situation is when we need to prove that at least k+n objects are in one box, instead of k+1 objects.

THE GENERALIZED PIGEONHOLE PRINCIPLE: “If N objects are placed into k boxes, then there is at least one box containing at least ⌈N/k⌉ objects.” Discrete Mathematics and its applications by Rosen.

In our case, we need to proof that at least 100 students come from the same state. In other words, that at least 1 of the 50 boxes has 100 students.

So, we know that ⌈N/k⌉ = 100. We also know that k=50, the number of states (boxes if we write it in terms of the principle).

Therefore,

⌈N/50⌉ = 100

So, what number N, divided by 50, and rounded to the next integer, gives us 100?

The answer is 4951.

4951 / 50 = 99.02, therefore, ⌈4951/50⌉ = 100.

By the generalized pigeonhole principle, a minimum of 4951 students must be enrolled in the university to guarantee that at least 100 comes from the same state.

Related posts: