# Pigeon Hole Priciple and Genaralized Pigeon Hole Principle Question

Question: 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$?

Solution: The minimum number of students to ensure that at least six students receive the same grade is the smallest integer $N$ such that $⌈N/6⌉ = 6$. The smallest such integer is $N = 5 \cdot 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.

Doubt: Why we get $5.5+1$?

Can someone clearly explain?

I think because of $K+1$ on Pigeon Hole Principle, if so why $5$ multiply by $5$ again?

• You think the pigeonhole principle means you only need 5+1 students? – almagest May 19 '16 at 19:51
• That's what I was thinking, but not sure how and why 5.5+1? – Surdz May 19 '16 at 19:53
• The basic pigeonhole principle applies where you just want to be sure of getting 2 students having the same grade. But here you need 6 to get the same grade. It is the same idea. As the solution said, five students could get each grade and you would still not have 6 with the same grade, but whatever grade the 26th student got you would have 6 with the same grade. – almagest May 19 '16 at 19:57
• Names (generalized pigeonhole principle) and formulas (that ceiling function stuff) can interfere with clear thinking. It is obvious, as you pointed out, that with $25$ people we might end up with $5$ in each grade category. But with $26$, at least one grade category must have $6$ or more people. (If each had at most $5$, there would be at most $5\times 5$ people in the class.) – André Nicolas May 19 '16 at 19:58

Let's say we have $26=5\cdot 5+1$ students but suppose that no $6$ students get the same grade. Then at for each grade there are at most $5$ students getting that particular grade. But then that means there are at most $5\cdot 5$ students all together, which is a contradiction.