0
$\begingroup$

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?

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .