# Generalized Pigeonhole Principle

Can somebody explain this to me? I am very confused.

I have a question that says "What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades, A, B, C, D, and F?"

and the solution is:

The minimum number of students needed to ensure that at least six students receive the same grade is the smallest integer N such that [N/5] = 6. The smallest such integer is N = 5* 5 + 1 = 26. If you have only 25 students, it is possible for there to be five who have received each grade so that no six students have received the same grade. Thus, 26 is the minimum number of students needed to ensure that at least six students will receive the same grade. The bolded part is the part that confuses me the most. Unless I haven't understood math in the past 20 years, N/5 = 6 would mean that N would have to be 30. So how exactly am I supposed to approach this question to understand what it is I'm trying to understand?

• I suppose they must be taking $[-]$ to be the ceiling function. – Casteels Nov 24 '13 at 6:55

## 3 Answers

When there are 25 people, clearly the required condition is not met as it is possible for 5 groups of 5 people each to have gotten each of the different grades. (this is the only case with 25 people when no 6 people have got a common grade)

When you have one person extra, irrespective of his grade, there will be a grade now that is repeated 6 times. Hence, the minimum number of people is is 26.

We can use the Pigeonhole Principle (Strong form). That is $q_1+q_2+\cdots+q_n-n+1$ where $q_i$ is the number of desired test scores of a certain type, ($6$) and $n$ is the number of score types in general, ($5$). So $6+6+6+6+6-5+1=26$.

Are you sure that it doesn’t say $\lceil N/5\rceil$ or $\left\lceil\frac{N}5\right\rceil$ and not $[N/5]$ or $\left[\frac{N}5\right]$?

By definition $\lceil x\rceil$, the ceiling of $x$, is the smallest integer $n$ such that $x\le n$. This means that it’s the unique integer $n$ such that $n-1<x\le n$. Thus, $\lceil N/5\rceil=6$ if and only if

$$5<\frac{N}5\le 6\;,$$

which is true if and only if $25<N\le 30$. Since $N$ here is an integer, this means that $\lceil N/5\rceil=6$ if and only if $N$ is $26,27,28,29$, or $30$. With fewer than $26$ students, it’s possible that no more than $5$ received each grade; with more than $30$ students, at least one of the grades must have been obtained by $7$ or more students.