На трибуне стадиона ровно 2020 болельщиков. Каждый из этих болельщиков плеснул водой ровно в одного другого болельщика.
а) Можно ли гарантированно найти на этой трибуне ровно 672 болельщика таких, что никто из них не обливал другого из этих 672 болельщиков водой?
б) Можно ли гарантированно найти на этой трибуне ровно 676 болельщиков таких, что никто из них не обливал другого из этих 676 болельщиков водой?
в) Какое наибольшее количество болельщиков можно гарантированно найти на этой трибуне таких, что никто из них не обливал другого из этой группы болельщиков водой?
а), б) Выберем произвольного болельщика и выгоним тех, в кого плеснул он и кто плеснул в него. Выберем любого из оставшихся болельщиков и выгоним тех, в кого плеснул он и кто плеснул в него (если они все еще есть). Будем повторять эти действия, пока еще останутся болельщики. За каждое действие их число уменьшается максимум на 3, поэтому после 673 действий еще останется минимум один болельщик, и его тоже можно будет взять. Итого можно выбрать 674 болельщика.
в) Выше показано, что можно найти 674 болельщика. Покажем, что найти больше не получится. Разобьем болельщиков на 672 группы по 3 человека и две группы по 2 человека. Пусть в каждой группе они выстроятся по кругу и каждый обольет следующего. Тогда из каждой группы можно будет взять не более одного, а всего не более 674.
Ответ: а) да, б) нет, в) 674.