Разделы 
Дополнительно
Задача по математике - 10427
2023-02-17 
На выпускном балу каждый юноша танцевал по крайней мере с одной девушкой, но никто из юношей не танцевал со всеми девушками, а каждая девушка танцевала по крайней мере с одним юношей, но никто из девушек не танцевал со всеми юношами.
Доказать, что среди присутствовавших на балу можно найти двух юношей и двух девушек так, что каждый из двух юношей танцевал лишь с одной из двух девушек, а каждая из этих двух девушек танцевала лишь с одним из этих двух юношей.
Решение:
Первое решение. Разобьем всех юношей на группы в зависимости от того, со сколькими девушками успел протанцевать каждый из них на выпускном балу (все юноши, входящие в одну группу, танцевали с одним и тем же числом партнерш). Пусть $F_{1}$ - один из тех юношей, который протанцевал с наибольшим числом девушек. Поскольку $F_{1}$ танцевал не со всеми девушками, то найдется по крайней мере одна девушка $L_{1}$ с которой $F_{1}$ не танцевал. Но поскольку с каждой девушкой танцевал по крайней мере один юноша, то заведомо найдется юноша $F_{2}$, танцевавший с $L_{1}$.
Юноша $F_{1}$ выбран так, что число девушек, с которыми не танцевал $F_{2}$, не меньше числа девушек, с которыми танцевал $F_{1}$. Отсюда следует, что $F_{2}$ танцевал не со всеми девушками, с которыми танцевал $F_{1}$: в противном случае, число партнерш у $F_{2}$ было бы больше, чем у $F_{1}$, поскольку $F_{2}$ танцевал с $L_l$, a $F_l$ не танцевал с ней. Итак, существует девушка $L_{2}$, с которой $F_{1}$ танцевал, а $F_{2}$ не танцевал.
Юноши $F_{1}$, $F_{2}$ и девушки $L_{1}$, $L_{2}$ образуют четверку участников бала, удовлетворяющих всем условиям задачи, поскольку $F_{1}, L_{1}$, так же как и $F_{2}$, $L_{2}$, не танцевали друг с другом, хотя $F_{1}$ танцевал с $L_{2}$, a $F_{2}$ - с $L_{1}$.
В приведенном решении использована лишь та часть условий задачи, в которой говорится о том, что ни один юноша не танцевал со всеми девушками и с каждой девушкой танцевал по крайней мере один юноша. Отсюда тотчас же следует другое решение, использующее ту часть условий, где говорится о том, что ни одна девушка не танцевала со всеми юношами и с каждым юношей танцевала по крайней мере одна девушка, поскольку юноши и девушки входят в условия задачи симметрично (они «взаимозаменяемы»). Таким образом, каждое из таких решений использует лишь половину условий задачи.
Хотя решения, полностью использующие условия задачи, отнюдь не проще и не короче приведенного выше, мы все же приведем три Таких решения, поскольку они позволяют показать обобщения задачи и ее связь с другими задачами.
Второе решение. Выберем среди участников выпускного бала какого-нибудь юношу $F_{1}$ и девушку $L_{1}$ с которой $F_{1}$ не танцевал. Пусть $F_{2}$ - юноша, танцевавший с $L_{1}$, a $L_{2}$ - девушка, с которой $F_{2}$ не танцевал. Условимся и далее поступать аналогичным образом: выбрав юношу $F_{i}$ ($i = 2, 3, \cdots$), искать девушку $L_{i}$, с которой он не танцевал, а затем - юношу $F_{i+1}$, танцевавшего с $L_{i}$. Этот процесс будем продолжать до тех пор, пока не дойдем до юноши, на которого наш выбор уже пал раньше. Поскольку число участников выпускного бала конечно, такой момент рано или поздно непременно наступит.
Итак, из числа присутствовавших на балу всегда можно выбрать $k$ юношей и $k$ девушек и выстроить их по кругу так, чтобы каждый юноша оказался в окружении двух девушек: с соседкой слева он танцевал на балу, а с соседкой справа не танцевал. Осталось еще доказать, что такой кружок можно выстроить всего лишь из двух юношей и двух девушек.
Предположим, что $k$ юношей и $k$ девушек выстроены в круг в следующем порядке:
$F_{1}, L_{1}, L_{2}, \cdots , F_{k}, L_{k}$ (
поскольку при такой записи круг «разорван», следует иметь в виду, что $L_{k}$ находится слева от $F_{1}$, то есть $F_{1}$ танцевал с $L_{1}$ на балу). Покажем, что если $k > 2$, го такой круг можно выстроить из меньшего числа юношей и девушек.
Действительно, если $F_{1}$ танцевал с $L_{2}$, то достаточно взять
$F_{1}, L_{1}, F_{2}, L_{2}$.
Если же $F_{1}$ не танцевал с $L_{2}$, то цепочка
$F_{1}, L_{2}, \cdots, F_{k}, L_{k}$
удовлетворяет требуемому условию. Таким образом, число выстроенных по кругу юношей и девушек всегда можно уменьшать до тех пор, пока в круге не останутся двое юношей и две девушки.
Третье решение. Предположим, что среди присутствовавших на выпускном балу юношей и девушек нельзя выбрать четверку, удовлетворяющую условиям задачи. Покажем, что такое предположение приводит к противоречию, а именно к тому, что число участников выпускного бала становится неограниченно большим. Правильность утверждения задачи будет следовать из полученного противоречия.
Пусть $L_{1}$ - одна из девушек, $F_{1}$ - танцевавший с ней юноша, $L_{2}$ - девушка, с которой не танцевал $F_{1}$ и $F_{2}$ - юноша, танцевавший с $L_{2}$. Относительно $F_{2}$ можно утверждать, что он танцевал с $L_{1}$, ибо в противном случае четверка $L_{1}$, $F_{1}$, $L_{2}$, $F_{2}$ вопреки предположению обладала бы всеми требуемыми свойствами. Итак, среди двух отобранных юношей и девушек лишь $L_{2}$ и $F_{1}$ не танцевали друг с другом.
Предположим, что мы уже отобрали среди участников выпускного бала группу
$L_{1}, F_{1}, L_{2}, F_{2}, \cdots, L_{k}, F_{k}$,
в которой юноша $F_{i}$ и девушка $L_{j}$ танцевали друг с другом (или нет), если $j \leq i$ (или $j > i$). При $k = 2$ существование такой группы уже было доказано. Убедимся теперь в том, что к группе отобранных участников бала всегда можно присоединить еще одну пару $L_{k+1}, F_{k+1}$ так, чтобы расширенная группа обладала свойствами исходной группы. Поскольку такой процесс можно повторить неограниченно, то отсюда и следует, что число участников бала бесконечно.
Поскольку $F_{k}$ танцевал с каждой из девушек $L_{1}, \cdots, L_{k}$, то существует по крайней мере еще одна девушка $Z_{k+1}$, с которой он не танцевал. Девушка $L_{k+1}$ не танцевала ни с одним из юношей $F_{1}, \cdots, F_{k-1}$, ибо, если предположить, что она танцевала, например, с юношей $F_{i}$, то четверка $L_{k}, F_{k}, L_{k+1}, F_{i}$ вопреки предположению обладала бы всеми необходимыми свойствами. Поскольку $L_{k+1}$ не танцевала ни с одним из юношей $F_{1}, \cdots, F_{k}$, то среди участников бала найдется по крайней мере один юноша $F_{k+1}$, танцевавший с $L_{k+1}$. Нетрудно видеть, что $F_{k+1}$ танцевал с $L_{1}, \cdots, L_{k}$: если бы он не танцевал, например, с $L_{i}$, то четверка $L_{i}, F_{i}, L_{k+1}, F_{k+1}$ вопреки предположению обладала бы требуемыми свойствами.
Итак, мы построили расширенную последовательность
$L_{1}, F_{1}, L_{2}, F_{2}, \cdots, L_{k}, F_{k}, L_{k+1}, F_{k+1}$,
обладающую тем свойством, что любой из юношей $F_{1}$ и любая девушка $L_{j}$ ($1 \leq i \leq k + 1$, $1 \leq j \leq k + 1)$, не танцевали друг с другом, если $j > i$, и танцевали, если $j \leq i$.
Полученное противоречие доказывает правильность утверждения задачи.
Из приведенного решения следует, что утверждение задачи перестает быть верным, если множество участников бала бесконечно (точнее говоря, если бесконечны множества юношей и девушек в отдельности),
Четвертое решение. Из условий задачи известно, что для каждого юноши можно указать девушку, с которой он не танцевал. Возможно, что для любых двух юношей найдется девушка, с которой ни один из них не танцевал. Не исключено также, что для любых трех и даже большего числа юношей можно указать девушку, с которой ни один из них не танцевал. Во всяком случае существует наибольшее число $k$, такое, что для любых $k$ юношей можно найти девушку, с которой ни один из них не танцевал. Поскольку с каждой девушкой танцевал по крайней мере один юноша, то $k$ заведомо меньше числа юношей, присутствовавших на выпускном балу.
Поскольку число $k + 1$ уже не обладает указанным свойством числа $k$, то можно выбрать $k + 1$ юношей
$F_{1}, F_{2}, \cdots, F_{k+1}$,
с которыми танцевали все девушки (каждая девушка танцевала с какими-то из $F_{1}, F_{2}, \cdots, F_{k+1}$, но, разумеется, не со всеми). Если какого-нибудь одного юношу, например $F_{1}$, исключить, то для оставшихся $k$ юношей (по определению числа $k$) найдется такая девушка $L_{1}$, с которой ни один из них не танцевал. Следовательно, из отобранных $k + 1$ юношей с $L_{1}$ танцевал лишь $F_{1}$. Исключая по порядку $F_{2}, F_3, \cdots, F_{k+1}$ и проводя аналогичные рассуждения, мы получим упорядоченный набор девушек
$L_{1}, L_{2}, \cdots, L_{k+1}$.
Каждая из них танцевала лишь с одним из выбранных нами $k + 1$ юношей, а именно с юношей, имеющим тот же индекс, что и у нее самой.
Поскольку $k \geq 1$, то всегда можно выбрать юношей $F_{1}, F_{2}$ и девушек $L_{1}, L_{2}$, для которых это утверждение верно, что и требовалось доказать.
Решение задачи можно было бы несколько сократить, ограничившись лишь самым необходимым: доказательством существования $L_{1}$ и $L_{2}$. Приведенное выше решение по существу служит доказательством более общего утверждения: если на выпускном балу каждая девушка танцевала по крайней мере с одним юношей и для любых $k-1$ (но не больше) из юношей найдется девушка, с которой не танцевал ни один из них, то среди участников бала можно выбрать $k$ юношей и $k$ девушек так, что каждый из юношей танцевал сводной и только одной из этих девушек.
На выпускном балу каждый юноша танцевал по крайней мере с одной девушкой, но никто из юношей не танцевал со всеми девушками, а каждая девушка танцевала по крайней мере с одним юношей, но никто из девушек не танцевал со всеми юношами.
Доказать, что среди присутствовавших на балу можно найти двух юношей и двух девушек так, что каждый из двух юношей танцевал лишь с одной из двух девушек, а каждая из этих двух девушек танцевала лишь с одним из этих двух юношей.
Решение:
Первое решение. Разобьем всех юношей на группы в зависимости от того, со сколькими девушками успел протанцевать каждый из них на выпускном балу (все юноши, входящие в одну группу, танцевали с одним и тем же числом партнерш). Пусть $F_{1}$ - один из тех юношей, который протанцевал с наибольшим числом девушек. Поскольку $F_{1}$ танцевал не со всеми девушками, то найдется по крайней мере одна девушка $L_{1}$ с которой $F_{1}$ не танцевал. Но поскольку с каждой девушкой танцевал по крайней мере один юноша, то заведомо найдется юноша $F_{2}$, танцевавший с $L_{1}$.
Юноша $F_{1}$ выбран так, что число девушек, с которыми не танцевал $F_{2}$, не меньше числа девушек, с которыми танцевал $F_{1}$. Отсюда следует, что $F_{2}$ танцевал не со всеми девушками, с которыми танцевал $F_{1}$: в противном случае, число партнерш у $F_{2}$ было бы больше, чем у $F_{1}$, поскольку $F_{2}$ танцевал с $L_l$, a $F_l$ не танцевал с ней. Итак, существует девушка $L_{2}$, с которой $F_{1}$ танцевал, а $F_{2}$ не танцевал.
Юноши $F_{1}$, $F_{2}$ и девушки $L_{1}$, $L_{2}$ образуют четверку участников бала, удовлетворяющих всем условиям задачи, поскольку $F_{1}, L_{1}$, так же как и $F_{2}$, $L_{2}$, не танцевали друг с другом, хотя $F_{1}$ танцевал с $L_{2}$, a $F_{2}$ - с $L_{1}$.
В приведенном решении использована лишь та часть условий задачи, в которой говорится о том, что ни один юноша не танцевал со всеми девушками и с каждой девушкой танцевал по крайней мере один юноша. Отсюда тотчас же следует другое решение, использующее ту часть условий, где говорится о том, что ни одна девушка не танцевала со всеми юношами и с каждым юношей танцевала по крайней мере одна девушка, поскольку юноши и девушки входят в условия задачи симметрично (они «взаимозаменяемы»). Таким образом, каждое из таких решений использует лишь половину условий задачи.
Хотя решения, полностью использующие условия задачи, отнюдь не проще и не короче приведенного выше, мы все же приведем три Таких решения, поскольку они позволяют показать обобщения задачи и ее связь с другими задачами.
Второе решение. Выберем среди участников выпускного бала какого-нибудь юношу $F_{1}$ и девушку $L_{1}$ с которой $F_{1}$ не танцевал. Пусть $F_{2}$ - юноша, танцевавший с $L_{1}$, a $L_{2}$ - девушка, с которой $F_{2}$ не танцевал. Условимся и далее поступать аналогичным образом: выбрав юношу $F_{i}$ ($i = 2, 3, \cdots$), искать девушку $L_{i}$, с которой он не танцевал, а затем - юношу $F_{i+1}$, танцевавшего с $L_{i}$. Этот процесс будем продолжать до тех пор, пока не дойдем до юноши, на которого наш выбор уже пал раньше. Поскольку число участников выпускного бала конечно, такой момент рано или поздно непременно наступит.
Итак, из числа присутствовавших на балу всегда можно выбрать $k$ юношей и $k$ девушек и выстроить их по кругу так, чтобы каждый юноша оказался в окружении двух девушек: с соседкой слева он танцевал на балу, а с соседкой справа не танцевал. Осталось еще доказать, что такой кружок можно выстроить всего лишь из двух юношей и двух девушек.
Предположим, что $k$ юношей и $k$ девушек выстроены в круг в следующем порядке:
$F_{1}, L_{1}, L_{2}, \cdots , F_{k}, L_{k}$ (
поскольку при такой записи круг «разорван», следует иметь в виду, что $L_{k}$ находится слева от $F_{1}$, то есть $F_{1}$ танцевал с $L_{1}$ на балу). Покажем, что если $k > 2$, го такой круг можно выстроить из меньшего числа юношей и девушек.
Действительно, если $F_{1}$ танцевал с $L_{2}$, то достаточно взять
$F_{1}, L_{1}, F_{2}, L_{2}$.
Если же $F_{1}$ не танцевал с $L_{2}$, то цепочка
$F_{1}, L_{2}, \cdots, F_{k}, L_{k}$
удовлетворяет требуемому условию. Таким образом, число выстроенных по кругу юношей и девушек всегда можно уменьшать до тех пор, пока в круге не останутся двое юношей и две девушки.
Третье решение. Предположим, что среди присутствовавших на выпускном балу юношей и девушек нельзя выбрать четверку, удовлетворяющую условиям задачи. Покажем, что такое предположение приводит к противоречию, а именно к тому, что число участников выпускного бала становится неограниченно большим. Правильность утверждения задачи будет следовать из полученного противоречия.
Пусть $L_{1}$ - одна из девушек, $F_{1}$ - танцевавший с ней юноша, $L_{2}$ - девушка, с которой не танцевал $F_{1}$ и $F_{2}$ - юноша, танцевавший с $L_{2}$. Относительно $F_{2}$ можно утверждать, что он танцевал с $L_{1}$, ибо в противном случае четверка $L_{1}$, $F_{1}$, $L_{2}$, $F_{2}$ вопреки предположению обладала бы всеми требуемыми свойствами. Итак, среди двух отобранных юношей и девушек лишь $L_{2}$ и $F_{1}$ не танцевали друг с другом.
Предположим, что мы уже отобрали среди участников выпускного бала группу
$L_{1}, F_{1}, L_{2}, F_{2}, \cdots, L_{k}, F_{k}$,
в которой юноша $F_{i}$ и девушка $L_{j}$ танцевали друг с другом (или нет), если $j \leq i$ (или $j > i$). При $k = 2$ существование такой группы уже было доказано. Убедимся теперь в том, что к группе отобранных участников бала всегда можно присоединить еще одну пару $L_{k+1}, F_{k+1}$ так, чтобы расширенная группа обладала свойствами исходной группы. Поскольку такой процесс можно повторить неограниченно, то отсюда и следует, что число участников бала бесконечно.
Поскольку $F_{k}$ танцевал с каждой из девушек $L_{1}, \cdots, L_{k}$, то существует по крайней мере еще одна девушка $Z_{k+1}$, с которой он не танцевал. Девушка $L_{k+1}$ не танцевала ни с одним из юношей $F_{1}, \cdots, F_{k-1}$, ибо, если предположить, что она танцевала, например, с юношей $F_{i}$, то четверка $L_{k}, F_{k}, L_{k+1}, F_{i}$ вопреки предположению обладала бы всеми необходимыми свойствами. Поскольку $L_{k+1}$ не танцевала ни с одним из юношей $F_{1}, \cdots, F_{k}$, то среди участников бала найдется по крайней мере один юноша $F_{k+1}$, танцевавший с $L_{k+1}$. Нетрудно видеть, что $F_{k+1}$ танцевал с $L_{1}, \cdots, L_{k}$: если бы он не танцевал, например, с $L_{i}$, то четверка $L_{i}, F_{i}, L_{k+1}, F_{k+1}$ вопреки предположению обладала бы требуемыми свойствами.
Итак, мы построили расширенную последовательность
$L_{1}, F_{1}, L_{2}, F_{2}, \cdots, L_{k}, F_{k}, L_{k+1}, F_{k+1}$,
обладающую тем свойством, что любой из юношей $F_{1}$ и любая девушка $L_{j}$ ($1 \leq i \leq k + 1$, $1 \leq j \leq k + 1)$, не танцевали друг с другом, если $j > i$, и танцевали, если $j \leq i$.
Полученное противоречие доказывает правильность утверждения задачи.
Из приведенного решения следует, что утверждение задачи перестает быть верным, если множество участников бала бесконечно (точнее говоря, если бесконечны множества юношей и девушек в отдельности),
Четвертое решение. Из условий задачи известно, что для каждого юноши можно указать девушку, с которой он не танцевал. Возможно, что для любых двух юношей найдется девушка, с которой ни один из них не танцевал. Не исключено также, что для любых трех и даже большего числа юношей можно указать девушку, с которой ни один из них не танцевал. Во всяком случае существует наибольшее число $k$, такое, что для любых $k$ юношей можно найти девушку, с которой ни один из них не танцевал. Поскольку с каждой девушкой танцевал по крайней мере один юноша, то $k$ заведомо меньше числа юношей, присутствовавших на выпускном балу.
Поскольку число $k + 1$ уже не обладает указанным свойством числа $k$, то можно выбрать $k + 1$ юношей
$F_{1}, F_{2}, \cdots, F_{k+1}$,
с которыми танцевали все девушки (каждая девушка танцевала с какими-то из $F_{1}, F_{2}, \cdots, F_{k+1}$, но, разумеется, не со всеми). Если какого-нибудь одного юношу, например $F_{1}$, исключить, то для оставшихся $k$ юношей (по определению числа $k$) найдется такая девушка $L_{1}$, с которой ни один из них не танцевал. Следовательно, из отобранных $k + 1$ юношей с $L_{1}$ танцевал лишь $F_{1}$. Исключая по порядку $F_{2}, F_3, \cdots, F_{k+1}$ и проводя аналогичные рассуждения, мы получим упорядоченный набор девушек
$L_{1}, L_{2}, \cdots, L_{k+1}$.
Каждая из них танцевала лишь с одним из выбранных нами $k + 1$ юношей, а именно с юношей, имеющим тот же индекс, что и у нее самой.
Поскольку $k \geq 1$, то всегда можно выбрать юношей $F_{1}, F_{2}$ и девушек $L_{1}, L_{2}$, для которых это утверждение верно, что и требовалось доказать.
Решение задачи можно было бы несколько сократить, ограничившись лишь самым необходимым: доказательством существования $L_{1}$ и $L_{2}$. Приведенное выше решение по существу служит доказательством более общего утверждения: если на выпускном балу каждая девушка танцевала по крайней мере с одним юношей и для любых $k-1$ (но не больше) из юношей найдется девушка, с которой не танцевал ни один из них, то среди участников бала можно выбрать $k$ юношей и $k$ девушек так, что каждый из юношей танцевал сводной и только одной из этих девушек.
