Номер 15, страница 270 - гдз по алгебре 7 класс учебник Никольский, Потапов

Задания на исследование. Глава 3. Линейные уравнения - номер 15, страница 270.

Условие.

15. Встретились $n$ друзей. Первый пожал руку одному из друзей, второй — двум, третий — трём, ..., $(n - 1)$-й пожал руку $(n - 1)$ другу (в любой паре друзей не более одного рукопожатия). Сколько рук пожал $n$-й друг?

Решите задачу для:

а) $n = 6$;

б) чётных $n \ge 4$.

Решение 1.

Решение 2.

Решение 4.

Решение 5.

Решение 7.

Для решения этой задачи представим друзей в виде вершин графа, а рукопожатия — в виде рёбер, соединяющих эти вершины. Количество рукопожатий каждого друга — это степень соответствующей вершины. Обозначим друзей как $F_1, F_2, \ldots, F_n$, а количество их рукопожатий (степени вершин) как $d_1, d_2, \ldots, d_n$.

По условию задачи мы знаем степени для первых $n-1$ друзей: $d_1 = 1$, $d_2 = 2$, $d_3 = 3$, $\ldots$, $d_{n-1} = n-1$. Нам нужно найти $d_n$.

a) n = 6;

В случае, когда $n=6$, у нас есть 6 друзей: $F_1, F_2, F_3, F_4, F_5, F_6$. Количества их рукопожатий известны для первых пяти: $d_1 = 1, d_2 = 2, d_3 = 3, d_4 = 4, d_5 = 5$. Нужно найти $d_6$.

Рассмотрим друга $F_5$. Он пожал руку 5 друзьям. Поскольку всего друзей 6 (включая его самого), это означает, что $F_5$ пожал руку всем остальным: $F_1, F_2, F_3, F_4$ и $F_6$.

Теперь рассмотрим друга $F_1$. Он пожал руку только одному другу. Так как мы уже знаем, что он пожал руку $F_5$, это и есть его единственное рукопожатие.

Теперь мы можем мысленно удалить из рассмотрения друзей $F_1$ и $F_5$ и проанализировать рукопожатия оставшихся друзей между собой. Остались 4 друга: $F_2, F_3, F_4, F_6$. Поскольку каждый из них уже совершил одно рукопожатие с $F_5$ (а $F_1$ ни с кем из них руки не жал), количество их рукопожатий внутри этой новой группы из 4 человек будет на единицу меньше первоначального. Новое количество рукопожатий для $F_2$ станет $d'_2 = d_2 - 1 = 2 - 1 = 1$; для $F_3$ — $d'_3 = d_3 - 1 = 3 - 1 = 2$; для $F_4$ — $d'_4 = d_4 - 1 = 4 - 1 = 3$; а для $F_6$ — $d'_6 = d_6 - 1$.

Мы получили аналогичную задачу, но для 4 друзей. В этой группе ($F_2, F_3, F_4, F_6$) друг $F_4$ имеет 3 рукопожатия, что означает, что он пожал руки всем остальным в группе: $F_2, F_3$ и $F_6$.

Друг $F_2$ в этой группе имеет всего одно рукопожатие. Поскольку мы знаем, что он пожал руку $F_4$, это его единственное рукопожатие в данной группе.

Снова применим метод редукции: удалим из рассмотрения $F_2$ и $F_4$. Остаются всего два друга: $F_3$ и $F_6$. Посчитаем количество их рукопожатий между собой. Каждый из них совершил рукопожатие с $F_4$, поэтому их счётчики рукопожатий в новой группе из двух человек снова уменьшатся на единицу. Новое количество рукопожатий для $F_3$ станет $d''_3 = d'_3 - 1 = 2 - 1 = 1$; а для $F_6$ — $d''_6 = d'_6 - 1 = (d_6 - 1) - 1 = d_6 - 2$.

В группе из двух человек ($F_3$ и $F_6$), если $F_3$ совершил одно рукопожатие, то это могло быть только с $F_6$. Следовательно, $F_6$ тоже должен был совершить одно рукопожатие (с $F_3$). Таким образом, $d''_6 = 1$.

Из уравнения $d_6 - 2 = 1$ находим $d_6$. $d_6 = 1 + 2 = 3$.

Ответ: 3.

б) чётных n ≥ 4

Рассмотрим общий случай для чётного числа друзей $n \ge 4$. Обозначим количество рукопожатий $n$-го друга как $D(n)$. Нам даны степени вершин $d_1=1, d_2=2, \ldots, d_{n-1}=n-1$.

Как и в частном случае, друг $F_{n-1}$ пожал руку $n-1$ другу, то есть всем остальным. Друг $F_1$ пожал руку только одному, и это должен быть $F_{n-1}$.

Удалим из рассмотрения $F_1$ и $F_{n-1}$. Мы останемся с группой из $n-2$ друзей: $F_2, F_3, \ldots, F_{n-2}, F_n$. У каждого из этих друзей было рукопожатие с $F_{n-1}$, поэтому количество их рукопожатий внутри новой группы уменьшится на 1.

Новые степени вершин в группе из $n-2$ человек будут: для $F_2$ — $d'_2 = d_2 - 1 = 1$; для $F_3$ — $d'_3 = d_3 - 1 = 2$; и так далее до $F_{n-2}$, у которого будет $d'_{n-2} = d_{n-2} - 1 = n-3$ рукопожатий. Для $F_n$ новое количество рукопожатий будет $d'_n = d_n - 1$.

Мы получили задачу того же типа, но для $n-2$ друзей. Количество рукопожатий "последнего" друга в этой новой задаче ($F_n$) по определению равно $D(n-2)$. То есть, $d'_n = D(n-2)$.

Таким образом, мы имеем рекуррентное соотношение, связывающее количество рукопожатий $n$-го друга в задаче с $n$ друзьями и в задаче с $n-2$ друзьями: $D(n) - 1 = D(n-2)$, что эквивалентно $D(n) = D(n-2) + 1$.

Это соотношение показывает, что для каждого шага, уменьшающего число друзей на 2, искомое количество рукопожатий увеличивается на 1. Поскольку $n$ — чётное, мы можем рекурсивно спускаться до базового случая. Выберем в качестве базового случая $n=4$.

Найдём $D(4)$. В группе из 4 друзей ($F_1, F_2, F_3, F_4$) известны степени: $d_1=1, d_2=2, d_3=3$. Нужно найти $d_4=D(4)$. Друг $F_3$ пожал руки всем остальным ($F_1, F_2, F_4$). Друг $F_1$ пожал руку только одному, и это $F_3$. У друга $F_2$ всего 2 рукопожатия: одно с $F_3$, значит, второе должно быть с $F_4$. Таким образом, $F_4$ пожал руки $F_3$ и $F_2$. Следовательно, $d_4=2$. Итак, $D(4)=2$.

Теперь решим рекуррентное соотношение для $n=2m$ (где $m \ge 2$ целое), используя базовый случай $D(4)=2$: $D(n) = D(2m) = D(2m-2) + 1 = D(2m-4) + 2 = \ldots$. Продолжая этот процесс $m-2$ раз, получим: $D(2m) = D(2m - 2(m-2)) + (m-2) = D(4) + m-2$. Подставляя значение $D(4)=2$, получаем: $D(2m) = 2 + m - 2 = m$.

Так как $n = 2m$, то $m = n/2$. Следовательно, искомое количество рукопожатий $n$-го друга равно $n/2$.

Ответ: $n/2$.