Разделы 
Дополнительно
Задача по математике - 3184
2019-05-27 
Каждый из 1994 депутатов парламента дал пощечину ровно одному своему коллеге. Докажите, что можно составить парламентскую комиссию из 665 человек, члены которой не выясняли отношений между собой указанным выше способом.
Решение:
Первый способ. Назовем депутатов врагами, если один другого бил. Индукцией по $n$ докажем следующее утверждение: если в парламенте $M \geq 3n-2$ депутатов, и каждый дал пощечину ровно одному коллеге, то можно составить парламентскую комиссию из $n$ человек, в которой нет врагов. При $n=665$ из этого будет следовать утверждение задачи, так как $1994>1993=3 \cdot 665-2$.
База индукции $(n=1)$ очевидна.
Шаг индукции: Так как число депутатов равно числу пощечин (равно $M$), по принципу Дирихле найдется депутат, получивший не более одной пощечины. У него не более двух врагов (его враги - тот, кто его бил и тот, кого он бил). Отправим этого депутата в комиссию, а его врагов (которых не больше двух) выведем из парламента. В парламенте осталось $M-3 \geq 3(n-1)-2$ депутатов. По предположению индукции, из них можно создать комиссию из $n-1$ депутатов, не бивших друг друга. Вместе с уже выбранным депутатом они составят комиссию из $n$ депутатов. Ясно, что в этой комиссии никто никого не бил.
Второй способ. Рассмотрим ориентированный граф Г, вершины которого - депутаты, а ребра - пощечины (т. е. ребро, ведущее от одного депутата к другому, означает, что первый депутат дал второму пощечину).
Ориентированным деревом будем называть граф следующего вида: имеется одна вершина уровня 1 (корень), в нее ведут стрелки из вершин уровня 2, в вершины уровня 2 - стрелки из вершин уровня 3, причем из каждой вершины выходит ровно одна стрелка, и т. д. вплоть до вершин некоторого уровня $k$.
Мы утверждаем, что компоненты связности графа Г выглядят следующим образом: ориентированный цикл, к вершинам которого «подвешены» (попарно непересекающиеся) ориентированные деревья (рис.). Действительно, выйдем из произвольной вершины и будем двигаться по ребрам (в направлении стрелок), пока не придем в вершину, в которой мы уже были. Это обязательно произойдет, так как вершин конечное число (1994). Значит, в каждой компоненте графа есть цикл.
Возьмем любую вершину цикла. В нее входит стрелка из единственной вершины цикла, и, возможно, из других вершин. Назовем эти другие вершины вершинами уровня 2. В них могут входить стрелки из вершин, которые мы назовем вершинами уровня 3, и т. д.
Теперь раскрасим граф в 3 цвета так, чтобы концы любого ребра были разного цвета. В цикле четной длины покрасим депутатов через одного. Если цикл имеет нечетную длину, покрасим одного из депутатов в 3-й цвет, а остальных-через одного.
С деревьями поступим так. Пусть, например, корень покрашен в 1-й цвет. Тогда вершины второго уровня покрасим во 2-й цвет, 3-го уровня - снова в 1-й и т. д. Понятно, что граф Г будет раскрашен не более чем в 3 цвета.
Ясно, что вершин некоторого цвета не меньше трети, т. е. не меньше, чем 667. Достаточно создать комиссию из депутатов этого цвета.
Каждый из 1994 депутатов парламента дал пощечину ровно одному своему коллеге. Докажите, что можно составить парламентскую комиссию из 665 человек, члены которой не выясняли отношений между собой указанным выше способом.
Решение:
Первый способ. Назовем депутатов врагами, если один другого бил. Индукцией по $n$ докажем следующее утверждение: если в парламенте $M \geq 3n-2$ депутатов, и каждый дал пощечину ровно одному коллеге, то можно составить парламентскую комиссию из $n$ человек, в которой нет врагов. При $n=665$ из этого будет следовать утверждение задачи, так как $1994>1993=3 \cdot 665-2$.
База индукции $(n=1)$ очевидна.
Шаг индукции: Так как число депутатов равно числу пощечин (равно $M$), по принципу Дирихле найдется депутат, получивший не более одной пощечины. У него не более двух врагов (его враги - тот, кто его бил и тот, кого он бил). Отправим этого депутата в комиссию, а его врагов (которых не больше двух) выведем из парламента. В парламенте осталось $M-3 \geq 3(n-1)-2$ депутатов. По предположению индукции, из них можно создать комиссию из $n-1$ депутатов, не бивших друг друга. Вместе с уже выбранным депутатом они составят комиссию из $n$ депутатов. Ясно, что в этой комиссии никто никого не бил.
Второй способ. Рассмотрим ориентированный граф Г, вершины которого - депутаты, а ребра - пощечины (т. е. ребро, ведущее от одного депутата к другому, означает, что первый депутат дал второму пощечину).
Ориентированным деревом будем называть граф следующего вида: имеется одна вершина уровня 1 (корень), в нее ведут стрелки из вершин уровня 2, в вершины уровня 2 - стрелки из вершин уровня 3, причем из каждой вершины выходит ровно одна стрелка, и т. д. вплоть до вершин некоторого уровня $k$.
Мы утверждаем, что компоненты связности графа Г выглядят следующим образом: ориентированный цикл, к вершинам которого «подвешены» (попарно непересекающиеся) ориентированные деревья (рис.). Действительно, выйдем из произвольной вершины и будем двигаться по ребрам (в направлении стрелок), пока не придем в вершину, в которой мы уже были. Это обязательно произойдет, так как вершин конечное число (1994). Значит, в каждой компоненте графа есть цикл.
Возьмем любую вершину цикла. В нее входит стрелка из единственной вершины цикла, и, возможно, из других вершин. Назовем эти другие вершины вершинами уровня 2. В них могут входить стрелки из вершин, которые мы назовем вершинами уровня 3, и т. д.
Теперь раскрасим граф в 3 цвета так, чтобы концы любого ребра были разного цвета. В цикле четной длины покрасим депутатов через одного. Если цикл имеет нечетную длину, покрасим одного из депутатов в 3-й цвет, а остальных-через одного.
С деревьями поступим так. Пусть, например, корень покрашен в 1-й цвет. Тогда вершины второго уровня покрасим во 2-й цвет, 3-го уровня - снова в 1-й и т. д. Понятно, что граф Г будет раскрашен не более чем в 3 цвета.
Ясно, что вершин некоторого цвета не меньше трети, т. е. не меньше, чем 667. Достаточно создать комиссию из депутатов этого цвета.
