В классе 33 человека. У каждого ученика спросили, сколько у него в классе тёзок и сколько однофамильцев (включая родственников). Оказалось, что среди названных чисел встретились все целые от 0 до 10 включительно. Докажите, что в классе есть два ученика с одинаковыми именем и фамилией.
Это задача 9.6 с Всероссийской олимпиады школьников 1997 года. Автор задачи - А.В. Шаповалов.
Будем объединять в группы людей с одинаковыми именами и одинаковыми фамилиями. Каждый школьник при этом попадёт в две группы.
Давайте поймём, что групп ровно 11. (Могло ведь быть и больше, из условия задачи не следует, что не получено других ответов.)
В тех одиннадцати группах, о которых мы знаем, всего
1+2+...+10+11=66 школьников.
Но 66=2*33. Т.е. уже каждый школьник оказался записанным в двух группах! Следовательно, других групп нет.
Рассмотрим теперь группу А из 11 человек. Остальных групп ровно 10.
Но каждый школьник из группы А должен попасть ещё в какую-нибудь группу (ведь каждый школьник в двух группах; по имени и по фамилии).
По принципу Дирихле найдутся минимум два школьника из группы А, которые попадут в одну из оставшихся групп. А, значит, у них одинаковые и имя, и фамилия!