Question

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

Answer 1

Ответ: 4

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

Если 3, то максимальное количество вариантов списков равно 16, а всего получается 19 учеников. Если же их 4, то вариантов 32 и этого хватает для всех

Answer 2

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

1. Если первый мальчик составил список из 0 девочек, второй мальчик - из 1, третий - из 2, и так далее, то общее количество девочек будет x + 0 + 1 + 2 + ... + 28.

2. Если первый мальчик составил список из 1 девочки, второй - из 2, третий - из 3, и так далее, то общее количество девочек будет x + 1 + 2 + 3 + ... + 28.

Теперь мы знаем, что не существует трёх мальчиков, у которых списки совпадают по количеству девочек. Это означает, что оба варианта, описанные выше, должны быть разными. То есть:

x + 0 + 1 + 2 + ... + 28 ≠ x + 1 + 2 + 3 + ... + 28.

Упростим оба выражения:

0 + 1 + 2 + ... + 28 ≠ 1 + 2 + 3 + ... + 28.

Теперь вычтем второе выражение из первого:

0 ≠ 1.

Это неверное утверждение, следовательно, наше предположение о наименьшем количестве девочек в классе было неверным.

Следовательно, невозможно, чтобы каждый мальчик имел разное количество девочек в своем списке. Таким образом, не существует такого распределения, и задача не имеет решения.