There are $33$ children in a given class. Each child writes a number on the blackboard, which indicates how many other children possess the same forename as oneself. Afterwards, each child does the same thing with their surname. After they've finished, each of the numbers $0,1,2,\dots,10$ appear at least once on the blackboard. Prove that there are at least two children in this class that have the same forename and surname.
Problem
Source: Germany 2016 - BWM Round 1, #4
Tags: combinatorics, combinatorics unsolved, pigeonhole principle, graph theory, Germany, blackboard
Continuum
13.11.2016 06:03
we look at a student $A$ who have written number $n$ on the blackboard, we noticed that the other $n$ students that have been identified by $A$ must also have written the number $n$ on the blackboard as well. So we grouped the students who has written the same number together (note that each student may belong to atmost 2 groups). We also get that a group that have written the number $n$ must have atleast $n+1$ members this results in atleast $1+2+3+\dots+11=66=33*2$ members this let us know from equality case that each student belong to 2 groups and there are excactly 1 group for each number (that is, no surnames or forenames having the same number of students). We then look at the $10$ group consisting of $11$ members WLOG let them have the same forename. If all of them have different surnames then there must be atleast $11$ different surnames, which is impossible as indicated by having at most only $10$ group of surnames (actually it is only at most $7$ surnames, but nevermind that). So there will be a children having the same forename and surname.
roughlife
24.11.2016 15:28
Let the number of distinct forename be $f$, surname be $s$. now we consider $a_{i}$ which means the number of children have $i$-th forename. they write $a_{i}$ on the blackboard, so there are $a_{i}+1$ children who write $a_{i}$. now we sum the number of children for every forename, we can get $\sum_{i=1}^{f}(a_{i}+1)=\sum_{i=1}^{f}a_{i}+f=33$. in the same way, we can get $\sum_{j=1}^{s}b_{j}+s=33$ for $b_{j}$ which means the number of children posses $j$-th surname. so $f+s=66-(\sum_{i=1}^{f}a_{i}+\sum_{j=1}^{s}b_{j})$. by the condition, $\sum_{i=1}^{f}a_{i}+\sum_{j=1}^{s}b_{j}\ge55$, $f+s\le11$. so the number of combination of forename and surname is below $30$. by pigeon hole principle, $\lceil\frac{33}{30}\rceil=2$. it's done.