Задача 4.
В классе учатся 20 человек. Размышляя, каким девочкам отправить валентинку на 14 февраля, каждый мальчик составил список из всех симпатичных ему девочекодноклассниц (возможно, пустой). Известно, что не существует трёх мальчиков, у которых списки совпадают по количеству девочек. Какое наименьшее количество девочек может быть в классе?
Ответ на Задачу 4.
Ответ: 6 девочек.
Решение:
Обозначим количество девочек в классе за 𝑑. По условию нет трёх мальчиков, у которых списки совпадают по количеству девочек, значит, может быть максимум 2 пустых списка, 2 списка с одной девочкой, 2 списка с двумя девочками, …, 2 списка с 𝑑 девочками. Получается, что списков, как и мальчиков, не больше 2(𝑑 + 1).
Общее количество детей в классе равно 20 и не превосходит 2(𝑑 + 1) + 𝑑 = 3𝑑 + 2, откуда получаем, что 𝑑 ≤ 6.
Несложно понять, что такое могло произойти, если всего было 6 девочек и 14 мальчиков. У двух мальчиков списки должны быть пустыми, у двух других в списках должна быть 1 девочка, ещё у двух — 2 девочки, …, у последних двух — 6 девочек (неважно, какие именно девочки присутствуют в списках, главное — их количество). Итого получается как раз 14 списков.
