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