Разделы 
Дополнительно
Задача по математике - 10375
2023-02-17 
Доказать, что в любой компании число тех, кто знаком с нечетным числом членов компании, четно.
Решение:
Первое решение. Для доказательства утверждения задачи воспользуемся методом полной математической индукции по числу знакомств (пар людей, знакомых друг с другом).
Если в компании имеется лишь двое людей, знакомых друг с другом (то есть если число знакомств равно 1), то утверждение задачи очевидно. Предположим, что оно выполняется в том случае, если число знакомств равно $k$. Что произойдет, если число знакомств увеличится на 1, то есть если двое людей, не знавших друг друга ранее, познакомятся? Если один из них был до этого знаком с нечетным, а другой - с четным числом членов компании, то число тех членов компании, кто имел нечетное число знакомых, не изменилось (изменился лишь состав этой группы). Если же до того, как состоялось знакомство, оба имели либо четное, либо нечетное число знакомых, то число членов компании, имеющих нечетное число знакомых, либо увеличилось на 2, либо уменьшилось на 2 и, следовательно, осталось четным, что и требовалось доказать.
Второе решение. Спросим у каждого члена компании, сколько у него знакомых, а все названные в ответ числа сложим. Полученная сумма заведомо четна,
поскольку каждое знакомство означает, что два чето-века знают друг друга. Следовательно, сумма нечетных чисел, названных при опросе членами компании, четна, ибо в противном случае общая сумма не могла бы быть четной. Но из четности суммы нечетных чисел следует, что число нечетных слагаемых четно. Следовательно, число членов компании, имеющих нечетное число знакомых, четно, что и требовалось доказать.
Задача встречается и во многих других формулировках. Приведем лишь некоторые из них.
Доказать, что число всех когда-либо живших на Земле людей, которые обменялись нечетным числом рукопожатий, четно.
Доказать, что у любого многогранника число граней с нечетным числом ребер четно.
Доказать, что у любого многогранника число вершин, в которых сходится нечетное число ребер, четно.
По существу все эти задачи сводятся к одной и той же задаче из теории графов.
В любом конечном графе число вершин, в которых сходится нечетное число ребер, четно.
В случае последней задачи вершинами графа являются вершины многогранника, а ребрами графа - ребра многогранника.
В случае исходной олимпиадной задачи и задачи о числе людей, обменявшихся нечетным числом рукопожатий, вершины графа обозначают людей, о которых идет речь, а ребра соединяют те вершины, которые соответствуют знакомым или обменявшимся между собой рукопожатиями. В задаче о числе граней произвольного многогранника, обладающих нечетным числом ребер, каждой грани многогранника сопоставим по одной вершине графа и соединим ребрами те вершины, которые соответствуют граням, имеющим общее ребро.
Решения задачи по существу содержат доказательство приведенной выше теоремы из теории графов.
Доказать, что в любой компании число тех, кто знаком с нечетным числом членов компании, четно.
Решение:
Первое решение. Для доказательства утверждения задачи воспользуемся методом полной математической индукции по числу знакомств (пар людей, знакомых друг с другом).
Если в компании имеется лишь двое людей, знакомых друг с другом (то есть если число знакомств равно 1), то утверждение задачи очевидно. Предположим, что оно выполняется в том случае, если число знакомств равно $k$. Что произойдет, если число знакомств увеличится на 1, то есть если двое людей, не знавших друг друга ранее, познакомятся? Если один из них был до этого знаком с нечетным, а другой - с четным числом членов компании, то число тех членов компании, кто имел нечетное число знакомых, не изменилось (изменился лишь состав этой группы). Если же до того, как состоялось знакомство, оба имели либо четное, либо нечетное число знакомых, то число членов компании, имеющих нечетное число знакомых, либо увеличилось на 2, либо уменьшилось на 2 и, следовательно, осталось четным, что и требовалось доказать.
Второе решение. Спросим у каждого члена компании, сколько у него знакомых, а все названные в ответ числа сложим. Полученная сумма заведомо четна,
поскольку каждое знакомство означает, что два чето-века знают друг друга. Следовательно, сумма нечетных чисел, названных при опросе членами компании, четна, ибо в противном случае общая сумма не могла бы быть четной. Но из четности суммы нечетных чисел следует, что число нечетных слагаемых четно. Следовательно, число членов компании, имеющих нечетное число знакомых, четно, что и требовалось доказать.
Задача встречается и во многих других формулировках. Приведем лишь некоторые из них.
Доказать, что число всех когда-либо живших на Земле людей, которые обменялись нечетным числом рукопожатий, четно.
Доказать, что у любого многогранника число граней с нечетным числом ребер четно.
Доказать, что у любого многогранника число вершин, в которых сходится нечетное число ребер, четно.
По существу все эти задачи сводятся к одной и той же задаче из теории графов.
В любом конечном графе число вершин, в которых сходится нечетное число ребер, четно.
В случае последней задачи вершинами графа являются вершины многогранника, а ребрами графа - ребра многогранника.
В случае исходной олимпиадной задачи и задачи о числе людей, обменявшихся нечетным числом рукопожатий, вершины графа обозначают людей, о которых идет речь, а ребра соединяют те вершины, которые соответствуют знакомым или обменявшимся между собой рукопожатиями. В задаче о числе граней произвольного многогранника, обладающих нечетным числом ребер, каждой грани многогранника сопоставим по одной вершине графа и соединим ребрами те вершины, которые соответствуют граням, имеющим общее ребро.
Решения задачи по существу содержат доказательство приведенной выше теоремы из теории графов.
