Question

Помогите пожалуйста!1)Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно.2)У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей? Почему?

Answer 1

Ответ:

Пошаговое объяснение:

1) в рукопожатием принимают участие 2 человека, поэтому рукопожатие удваивается, т.е. умножается на 2

2)Под графом мы будем понимать множество точек (вершин), некоторые из которых соединены отрезками (ребрами).

Степень вершины графа — это количество выходящих из нее (или, что то же самое, входящих в нее) ребер (еще говорят: количество ребер, инцидентных данной вершине). Вершина графа называется четной, если ее степень четна, и нечетной в противном случае.

Некоторая часть вершин данного графа называется компонентой связности, если из любой ее вершины можно «дойти» до любой другой, двигаясь по ребрам.

В некоторых случаях на ребрах графа выбирается «направление движения» (например, когда на автомобильной дороге вводится одностороннее движение). При этом получается ориентированный граф. (Если направление движения по ребрам не определено, то граф называется неориентированным). В ориентированном графе различают положительную и отрицательную степень каждой вершины (то есть количество ребер, соответственно, входящих и выходящих из нее). Две вершины могут быть соединены и несколькими ребрами, направления движения по которым противоположны («дорога с двусторонним движением»). Изменяется понятие компоненты связности: теперь каждый «маршрут» от одной вершины до другой должен учитывать направление движения по ребрам.Теорема 2. Всякий (неориентированный) граф содержит четное число нечетных вершин. Ответ. Нет.

Решение. Сделаем вассалов вершинами графа; ребрами соединим тех из них, которые являются соседями. По условию все вершины этого графа нечетны, а всего их 19, то есть тоже нечетное число. Но по теореме 2 такого быть не может.

Answer 2

1. Давайте рассмотрим сумму всех рукопожатий в группе людей. Каждый человек вносит в эту сумму число рукопожатий, равное количеству его рукопожатий с другими людьми. Если мы посчитаем сумму рукопожатий всех людей в группе, получим общее число рукопожатий в этой группе.

Предположим, что есть некоторое число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий. Обозначим это число как N. Если мы рассмотрим сумму рукопожатий всех этих людей, то эта сумма также будет нечетной, так как сумма нечетного количества нечетных чисел также является нечетной.

Теперь предположим, что в этой группе есть ровно один человек, сделавший четное число рукопожатий. Тогда общая сумма рукопожатий в этой группе будет четной, так как сумма нечетного числа нечетных чисел плюс четное число равна четному числу.

Но это противоречит предыдущему утверждению о сумме рукопожатий в этой группе, которая должна быть нечетной. Получили противоречие, следовательно, предположение о том, что есть ровно один человек, сделавший четное число рукопожатий, неверно.

Из этого следует, что количество людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, должно быть четным.

2. Количество соседей каждого вассала определяется числом вассалов, находящихся рядом с ним. В данном случае, у короля есть 19 вассалов, и каждый из них должен иметь определенное количество соседей (1, 5 или 9). Однако, это невозможно.

Если каждый вассал имеет 1 соседа, то общее число соседей будет равно 19. Однако, каждый вассал имеет только 18 вассалов в качестве соседей (так как король не считается его соседом). Получается противоречие.

Точно так же, если каждый вассал имеет 5 соседей, общее число соседей будет равно 95. Опять же, каждый вассал имеет только 18 вассалов в качестве соседей, и это пр