9
$\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?

$\endgroup$
10
$\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.

$\endgroup$
  • $\begingroup$ Just beat me to it +1 :) $\endgroup$ – Paul Evans Feb 27 '16 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 Feb 27 '16 at 23:56
  • $\begingroup$ @Mophotla Yes, that is correct. There are at maximum 7 names in each group. $\endgroup$ – Tony Ruth Feb 27 '16 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 Feb 28 '16 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 Feb 28 '16 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.

$\endgroup$

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.