11
$\begingroup$

There are 33 students in a class. Every pupil writes the number of other pupils in this class with the same first name as him- or herself onto the blackboard. This procedure is repeated, now with the number of students with the same surname.

In the end, of the 66 numbers on the blackboard, each of the numbers $0,1,2\ldots,9,10$ appears at least once.

Prove that at least two students in this class bear the same fore- and surname.

Remark: Every student in this class has exactly one first name and one last name (hence no middle name).

Update: I've thought about Tony's answer a bit, especially about the part "the only way this works is if there are 1 students with name A, 2 students with name B, 3 students with name C, etc up to 11 students with name K". I noticed that $1+2+\ldots+10+11=66=2\cdot33$ which means that these 1 to 11 students have to be equally distributed among first and last names (if you know what I mean). Is this just a coincidence or is this fact in any way relevant for solving the problem?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\begingroup$

Each of the numbers 0,1,2…,9,10 appears at least once.

In fact, the only way this works is if there are 1 students with name A, 2 students with name B, 3 students with name C, etc up to 11 students with name K

The names are distributed as 7 first names and 4 last names, or 5 first names and 6 last names or vice versa.

If we look at the group that has 11 people with same same first(last) name. Then they have at most 7 different last(first) names, and by the pigeon hole principle at least 2 of them are in the same hole, have the same last name and first name.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Just beat me to it +1 :) $\endgroup$
    – Paul Evans
    Commented Feb 27, 2016 at 23:51
  • $\begingroup$ "The names are distributed as 7 first names and 4 last names, or 5 first names and 6 last names or vice versa." Is that because $1+2+\ldots+6+7\leq33$, but $1+2+\ldots+7+8>33$? $\endgroup$
    – Mophotla
    Commented Feb 27, 2016 at 23:56
  • $\begingroup$ @Mophotla Yes, that is correct. There are at maximum 7 names in each group. $\endgroup$
    – Tony Ruth
    Commented Feb 27, 2016 at 23:59
  • $\begingroup$ Wouldn't this argument also hold if we had a number of students of up to 65, as $1+2+\ldots+10+11=66$? Or, if we stick to 33 students, shouldn't this also work if we only knew that the numbers 0 through 7 appear at least once? $\endgroup$
    – Mophotla
    Commented Feb 28, 2016 at 1:55
  • $\begingroup$ @Mophotla, It would not hold in either of those cases. In the first case, if there were 65 students, it would be possible for the 11 students with the same first (last) name to have different last (first) names. In the second case, the same thing happens, the name with 8 students could be split into 8 or more unique names. There definitely is some leeway here to reduce the constraints, but I think it cannot go as far as you have suggested. $\endgroup$
    – Tony Ruth
    Commented Feb 28, 2016 at 19:58
3
$\begingroup$

Let the number of same first names for each written number be $n_0,n_1,...,n_{32}$ and that of the same surnames $m_0,m_1,...,m_{32}$. $n_0$ or $m_0$ denotes the number of unique names, $n_x$ or $m_x$ denotes the number of names common to $x+1$ people, and so on. Therefore, $n_x$ and $m_x$ must be divisible by $x+1$.

The sum $n_0+m_0...+n_{10}+m_{10}$ can be 1+2+...+11=66 at a minimum, which is the total number of the written numbers. For there to be no full name overlap, the 11-strong group with the same first name/surname must all have different surnames/first names (if the first name is the same, the surnames must be different and vice versa), but adding up 11 existing same name/surname groups will give 66, which is greater than 33. In short, there IS at least one overlap.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I am trying to understand your answer. It is clear that 10 was written by exactly 11 people, 9 was written by exactly 10 people….. 0 was written by exactly 1 person. Let's say that the 11 people who wrote 10 had the same first names. How you are proving that at least 2 of these 11 people will have the same last name, is something that I cannot understand. $\endgroup$
    – Hemant Agarwal
    Commented Jun 28, 2023 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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