|
|
 |
Условие
30 учеников одного класса решили побывать друг у друга в гостях. Известно, что ученик за вечер может сделать несколько посещений, и что в тот вечер, когда к нему кто-нибудь должен прийти, он сам никуда не уходит. Покажите, что для того, чтобы все побывали в гостях у всех,
а) четырёх вечеров недостаточно,
б) пяти вечеров также недостаточно,
в) а десяти вечеров достаточно,
г) и даже семи вечеров тоже достаточно.
Решение 1
Пусть S – множество дней, в которые происходят события, описанные в условия. Каждому ученику соответствует некоторое подмножество множества S – дни, в которые этот ученик посещает одноклассников. Ученики смогут добиться цели тогда и только тогда, когда ни одно из этих подмножеств не содержится в другом подмножестве.
в), г) Пусть S состоит из семи дней. Очевидно, что одно трёхэлементное подмножество множества S не может содержаться в другом трёхэлементном подмножестве. Всего у S ровно трёхэлементных подмножеств. Таким образом, семи дней достаточно.
а), б) Докажем, что даже шести дней недостаточно. Пусть S состоит из шести дней. Будем рассматривать "цепочки" подмножеств вида где Si состоит из i дней. Докажем, что из любых тридцати подмножеств множества S можно выбрать два, принадлежащие одной цепочке. Каждое подмножество Si из i дней входит в i!·(6 – i)! цепочек. А поскольку минимальное значение
i!·(6 – i)! равно 3!·3! = 36, то каждое подмножество множества S принадлежит по крайней мере 36 цепочкам. Допустим, что нам удалось выбрать 30 подмножеств множества S, каждые два из которых не принадлежат одной цепочке. Тогда мы получаем не менее 30·36 различных цепочек. Но общее количество цепочек меньше – их всего 6! = 720. Противоречие.
Решение 2
Приведём более простые решения а), б) и в).
а), б) Поставим в соответствие ученику четырёхзначное двоичное число: 0 в i-м разряде означает, что в i-й день он сидит дома, 1 – ходит в гости. Чисел 16, значит, у каких-то двух учеников они совпадают. Следовательно, они не встречались в первые 4 дня. Не смогут они посетить друг друга и за один оставшийся день.
в) Произвольно занумеруем учеников пятизначными двоичными числами. В первый день ходят в гости те, у кого в первом разряде стоит 1, во второй день – те, у кого в первом разряде стоит 0. Таким образом, за два дня посетят друг друга все пары, отличающиеся в первом разряде. За следующие два дня аналогично посетят друг друга пары, отличающиеся во втором разряде, и т. д.
Замечания
баллы: 7-8 кл. – 3 + 3 + 3 + 3, 9-10 кл. – 3 + 2 + 2 + 3
