На психологический тренинг пришли m человек. В начале работы психолог попросил каждого пришедшего написать записку с вопросом к любому одному из других участников. После этого в группу А были отобраны те, кто получил не более 1 вопроса.
а) Какое наибольшее число участников могло оказаться в группе А, если m = 100?
б) Какое наименьшее число участников могло оказаться в группе А, если m = 144?
в) Какое наименьшее число участников могло оказаться в группе А, если m = 97, а в группу А вошли те, кто не получил ни одного вопроса, и половина тех, кто получил ровно один вопрос? (Если ровно один вопрос получило нечетное число человек, то берется наибольшее число, не превосходящее половину.)
а) Пусть все люди выстроятся в круг и каждый задаст вопрос следующему за ним. Тогда каждый получит ровно один вопрос, а в группу А будут отобраны все 100 человек.
б) Участник не попадает в группу А, если он получил минимум два вопроса. Всего было задано 144 вопроса, значит, таких участников не более половины от 144, а оставшаяся половина участников попадет в группу А. Пример строится, скажем, так: разобьем всех людей на группы по 4 человека. Первый и второй зададут вопрос третьему, а третий и четвертый — второму. Тогда из каждой группы будут выбраны первый и четвертый, всего 72 человека.
в) Если в группе есть два человека, получивших по одному вопросу, то можно переадресовать один из этих вопросов так, чтобы один из них получил два вопроса, а второй ни одного (возможно, при этом кто-то задаст вопрос сам себе — это неважно). Таким образом, любой пример, где есть больше одного такого человека, можно переделать, уменьшив количество таких людей и не изменив число людей в группе А. Будем так делать до тех пор, пока останется не более одного такого человека.
Теперь не более 97 вопросов распределены по людям так, что каждому достается либо 0, либо не менее двух. Тех, кому достается не менее двух, будет не более 97 : 2 = 48,5, то есть от попадания в группу А можно спасти максимум 48 человек и еще того одного, кому достался один вопрос. Значит, в группе А не менее 97 − 48 − 1 = 48 человек.
Построим пример. Разобьем всех людей на 24 группы по 4 человека и попросим во всех группах, кроме одной, обменяться вопросами так же, как в пункте б). В последнюю группу добавим последнего человека, еще не распределенного. Пусть теперь первый и второй спрашивают третьего, третий и четвертый — пятого, а пятый — первого. Тогда в группу А из каждой группы попадут ровно двое: второй и четвертый. Всего 48 человек.
Ответ: а) 100; б) 72; в) 48.
Приведем еще одно решение пункта в).
Если бы в группе А было меньше 48 человек, то не менее 50-и человек не вошли бы в группу. Пусть n из них получили по одному вопросу, тогда не менее n − 1 человека получили по одному вопросу и вошли в группу, а оставшиеся 50 − n человек получили не менее двух вопросов. Тогда на тренинг пришло бы не менее человек, что противоречит условию. Следовательно, в группе было не меньше 48 человек. Пример для 48 человек можно взять из пункта а), когда всё стоят по кругу и каждый получает по 1 вопросу: в группу А попадает целая часть числа [97/2], то есть 48.

