Question

В классе учатся 26 человек. Размышляя, каким девочкам отправить валентинку на 14 февраля, каждый мальчик составил список из всех симпатичных ему девочек-одноклассниц (возможно, пустой). Известно, что не существует трёх мальчиков, у которых списки совпадают по количеству девочек. Какое наименьшее количество девочек может быть в классе?

Answer 1

Ответ:

8 девочек.

Пошаговое объяснение:

Нам нужно найти, наименьшее возможное количество девочек. Но нет 3 мальчиков, которые написали бы в списке одно и то же количество симпатичных ему девочек. Значит предположим что по 2 мальчиков написали количеству девочек 0,1,2,3,4...( И так далее смотря сколько человек в классе). Предположим что самое большое количество девочек в списке 8. Поскольку нам нужно найти минимально возможное количество девочек, мы можем считать что все девочки были упомянуты хотя бы по разу, а также что любая девочка упомянутая в списке , была упомянута также во всех списках с большим количеством человек.Тогда мальчиков было 2*9=18. (На 9 потому что ещё у двоих были пустые списки) 18+8=26. Значит все сходится.

Answer 2

Давайте рассмотрим эту задачу:

Предположим, что в классе всего 2 девочки. Тогда у каждого мальчика может быть только два варианта: он симпатизирует одной из них или другой. Следовательно, у всех мальчиков будет по два разных списка девочек, и задача выполнена.

Теперь давайте рассмотрим случай, когда в классе 3 девочки. Пусть у первого мальчика есть список A, у второго - список B, а у третьего - список C. Если ни один из списков не совпадает по количеству с другими, это означает, что у первого мальчика в списке A одна девочка, у второго в списке B - две девочки, и у третьего в списке C - три девочки. Но так как у нас всего 3 девочки, то это невозможно. Следовательно, необходимо, чтобы хотя бы два из списков совпадали по количеству девочек.

Теперь мы знаем, что у нас два списка, которые содержат одинаковое количество девочек. Предположим, что у первых двух мальчиков списки A и B содержат по одной девочке каждый, и у третьего мальчика список C содержит две девочки. Тогда у нас есть две девочки, которые есть в списках двух мальчиков, и одна девочка, которая есть только в списке третьего мальчика.

Теперь рассмотрим случай, когда в классе 4 девочки. Мы уже видели, что в случае трех девочек это невозможно, так как два списка должны совпадать по количеству девочек. Теперь, если у нас 4 девочки, то как минимум два мальчика должны иметь по две девочки в своих списках (потому что 4 = 2 + 2).

Таким образом, наименьшее количество девочек в классе, при котором не существует трех мальчиков с одинаковыми списками по количеству девочек, это 4.