Question

На танцевальном вечере ни один мальчик не танцевал со всеми девочками, но каждая девочка танцевала по крайней мере с одним мальчиком. Докажите, что найдутся две такие пары A1, B1 и A2, B2, что мальчик A1 танцевал с девочкой B1, а A2 танцевал с B2, но A1 не танцевал с B2, а A2 с B1

Answer 1

Ответ:

Положим так. Если А1 танцевал с Б1, а А2 танцевал с Б2, то А1 танцевал с Б2, а А2 танцевал с Б1. Есть какое-то множество девочек М1, с которыми танцевал мальчик А1; и множество девочек М2, с которыми танцевал мальчик Б2. Оба множества непусты ввиду первых двух предложений.

Гипотеза указывает, что мальчик А1 танцевал с любой девочкой из М2. Множество М1 можно пополнять до тех пор, пока остаются другие нерассмотренные мальчики помимо А1; и если множество М1 ещё не включает всех девочек, то, ввиду предложения о наличии затанцованного мальчика для каждой девочки, такие мальчики остаются. Значит, А1 танцевал со всеми девочками, противоречие.

Answer 2

Давайте докажем это утверждение методом противоречия.

Предположим, что такие пары A1, B1 и A2, B2 не существуют, то есть для любой пары мальчик-девочка (Ai, Bi) мальчик Ai танцевал с девочкой Bi, и также мальчик Ai танцевал с девочкой Bj только если Bj ≠ Bi.

Рассмотрим одного из мальчиков, скажем, A1. Поскольку каждая девочка танцевала по крайней мере с одним мальчиком, пусть Bk будет девочкой, с которой танцевал мальчик A1. Но мы предположили, что для любой пары мальчик-девочка (Ai, Bi) мальчик Ai танцевал с девочкой Bi исключительно с ней. Это противоречие — мальчик A1 не может танцевать и с другой девочкой, например, с B2.

Таким образом, наше предположение оказывается неверным, и существуют две пары A1, B1 и A2, B2, такие что мальчик A1 танцевал с девочкой B1, мальчик A2 танцевал с девочкой B2, и при этом A1 не танцевал с B2, а A2 не танцевал с B1.