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?

  • $\begingroup$ You think the pigeonhole principle means you only need 5+1 students? $\endgroup$ – almagest May 19 '16 at 19:51
  • $\begingroup$ That's what I was thinking, but not sure how and why 5.5+1? $\endgroup$ – Surdz May 19 '16 at 19:53
  • $\begingroup$ 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. $\endgroup$ – almagest May 19 '16 at 19:57
  • 2
    $\begingroup$ 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.) $\endgroup$ – 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.

  • $\begingroup$ What exactly does that add to the solution given by the OP? [which he is evidently unhappy with] $\endgroup$ – almagest May 19 '16 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.