Олимпиадная задача: распределение тысяч билетов по ящикам и принцип Дирихле
Задача
Есть тысяча билетов с номерами 000, 001, ..., 999 и сто ящиков с номерами 00, 01, ..., 99. Билет разрешается опустить в ящик, если номер ящика может быть получен из номера билета вычеркиванием одной из цифр. Можно ли разложить все билеты в 50 ящиков?
Решение
Выделим две группы ящиков: в группу А войдут все ящики, номера которых содержат только цифры 0, 1, 2, 3 и 4; а в группу B – все ящики, номера которых содержат только цифры 5, 6, 7, 8 и 9. В каждой группе будет по 25 ящиков: в А войдёт половина ящиков из первых пяти десятков (по 5 из каждого), а в B – половина ящиков из последних пяти десятков.
Докажем, что любой билет можно положить в один из пятидесяти выделенных ящиков. Действительно, номер билета состоит из трёх цифр, поэтому среди них найдутся две цифры, которые попадают в одну из групп. Зафиксируем эти две цифры и вычеркнем оставшуюся. Тем самым мы получим номер ящика, который присутствует в одной из рассматриваемых групп. В этот ящик мы и положим билет.
Ответ
Можно.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь