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

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

Условие.

14. На окружности отметили $n$ точек, каждую соединили хордой хотя бы с одной из других отмеченных точек. Оказалось, что из первой точки выходит одна хорда, из второй — две, ..., из $(n-1)$-й точки выходит $(n-1)$ хорда. Сколько хорд выходит из $n$-й точки?

Решите задачу для:
а) $n = 5$;
б) нечётных $n \ge 3$.

Решение 1.

Решение 2.

Решение 4.

Решение 5.

Решение 7.

a) n = 5;

Пусть точки на окружности являются вершинами графа, а хорды — его рёбрами. Количество хорд, выходящих из точки, является степенью соответствующей вершины.По условию, у нас есть 5 вершин $v_1, v_2, v_3, v_4, v_5$.Их степени равны: $d(v_1) = 1$, $d(v_2) = 2$, $d(v_3) = 3$, $d(v_4) = 4$.Нам нужно найти степень пятой вершины, обозначим её $d(v_5) = k$.

Согласно лемме о рукопожатиях, сумма степеней всех вершин в любом графе должна быть чётным числом (так как она равна удвоенному числу рёбер).Сумма степеней в нашем случае равна:$S = d(v_1) + d(v_2) + d(v_3) + d(v_4) + d(v_5) = 1 + 2 + 3 + 4 + k = 10 + k$.

Так как $S$ должно быть чётным, и 10 — чётное число, то $k$ также должно быть чётным.Максимально возможная степень вершины в графе с $n=5$ вершинами равна $n-1 = 4$. Также по условию каждая точка соединена хотя бы с одной другой, значит $k \ge 1$.Таким образом, $k$ — это чётное число в диапазоне $1 \le k \le 4$. Возможные значения для $k$: 2 или 4.

Рассмотрим случай $k=4$. Тогда в графе две вершины имеют степень 4: $v_4$ и $v_5$. Вершина со степенью $n-1=4$ должна быть соединена со всеми остальными вершинами.Значит, $v_4$ соединена с $v_1, v_2, v_3, v_5$.И $v_5$ соединена с $v_1, v_2, v_3, v_4$.Из этого следует, что вершина $v_1$ соединена как минимум с двумя вершинами ($v_4$ и $v_5$), поэтому её степень должна быть $d(v_1) \ge 2$.Однако по условию $d(v_1) = 1$. Мы получили противоречие.Следовательно, случай $k=4$ невозможен.

Единственный оставшийся вариант — $k=2$. Этот случай не приводит к противоречию. Например, можно построить такой граф: $v_4$ соединена со всеми ($v_1, v_2, v_3, v_5$). $v_1$ соединена только с $v_4$. $v_3$ соединена с $v_4, v_2, v_5$. Тогда степени будут: $d(v_4)=4, d(v_1)=1, d(v_3)=3, d(v_2)=2$ (соединена с $v_4, v_3$), $d(v_5)=2$ (соединена с $v_4, v_3$). Это соответствует условию, если считать, что вторая точка из условия это та, у которой степень 2 (наша $v_5$ или $v_2$), третья - та, у которой степень 3 (наша $v_3$), и так далее.

Ответ: 2

б) нечётных n ≥ 3.

Рассуждаем аналогично, используя теорию графов. У нас есть $n$ вершин $v_1, ..., v_n$, где $n$ — нечётное число, $n \ge 3$.Степени вершин $v_1, ..., v_{n-1}$ заданы как $d(v_i) = i$ для $i=1, ..., n-1$.Степень вершины $v_n$ неизвестна, обозначим её $d(v_n)=k$.

Рассмотрим сумму степеней всех вершин:$S = \sum_{i=1}^{n-1} d(v_i) + d(v_n) = \sum_{i=1}^{n-1} i + k$.Сумма первых $n-1$ натуральных чисел равна $\frac{(n-1)n}{2}$.Значит, $S = \frac{n(n-1)}{2} + k$.

Сумма степеней $S$ должна быть чётной. Проанализируем чётность первого слагаемого.Так как $n$ — нечётное, то $n-1$ — чётное. Пусть $n=2m+1$ для некоторого целого $m \ge 1$.Тогда $\frac{n(n-1)}{2} = \frac{(2m+1)(2m)}{2} = m(2m+1)$.Чётность этого выражения зависит от чётности $m = \frac{n-1}{2}$.

Другой подход — использовать следствие из леммы о рукопожатиях: число вершин с нечётной степенью в любом графе должно быть чётным.Посчитаем количество нечётных степеней в известной последовательности $1, 2, 3, ..., n-1$.Так как $n$ нечётно, $n-1$ чётно. Нечётные числа в этой последовательности — это $1, 3, 5, ..., n-2$.Их количество равно $\frac{(n-2)-1}{2} + 1 = \frac{n-1}{2}$.

Пусть $N_{odd}$ — общее число вершин с нечётной степенью. $N_{odd}$ должно быть чётным.Количество нечётных степеней среди первых $n-1$ вершин равно $\frac{n-1}{2}$.Если $k$ — чётное, то $N_{odd} = \frac{n-1}{2}$.Если $k$ — нечётное, то $N_{odd} = \frac{n-1}{2} + 1$.

Рассмотрим два случая для нечётного $n$:1. $n = 4j+1$ для $j \ge 1$. Тогда $\frac{n-1}{2} = \frac{4j}{2}=2j$ (чётно). Чтобы $N_{odd}$ было чётным, $k$ должно быть чётным.2. $n = 4j+3$ для $j \ge 0$. Тогда $\frac{n-1}{2} = \frac{4j+2}{2}=2j+1$ (нечётно). Чтобы $N_{odd}$ было чётным, $k$ должно быть нечётным.

В обоих случаях чётность $k$ должна совпадать с чётностью числа $\frac{n-1}{2}$.

Теперь воспользуемся структурными свойствами графа. Максимальная степень вершины $d(v_{n-1}) = n-1$. Это означает, что вершина $v_{n-1}$ соединена со всеми остальными $n-1$ вершинами.Минимальная степень $d(v_1)=1$. Так как $v_{n-1}$ соединена со всеми, единственное ребро из $v_1$ должно вести в $v_{n-1}$.

Рассмотрим, может ли $k=n-1$. Если $k=n-1$, то в графе две вершины ($v_{n-1}$ и $v_n$) имеют степень $n-1$ и должны быть соединены со всеми остальными. В частности, обе должны быть соединены с $v_1$. Тогда степень $v_1$ была бы не меньше 2, что противоречит условию $d(v_1)=1$. Значит, $k \ne n-1$.

Рассмотрим $k=1$ (для $n \ge 5$). Этот вариант удовлетворяет условию чётности для $n=4j+3$. Однако можно показать, что такой граф не существует. Аргумент строится на рассмотрении дополнения графа и приводит к противоречию (в некотором подграфе возникает вершина со степенью, большей максимально возможной).

Единственным решением, удовлетворяющим всем условиям для любого нечётного $n \ge 3$, является $k = \frac{n-1}{2}$.Проверим это решение:

• Для $n=3$, $k=\frac{3-1}{2}=1$. Степени: 1, 2, 1. Сумма 4 (чётная). Граф: $v_2$ соединена с $v_1$ и $v_3$. Это возможно.
• Для $n=5$, $k=\frac{5-1}{2}=2$. Степени: 1, 2, 3, 4, 2. Сумма 12 (чётная). Это совпадает с ответом в пункте а).
• Для $n=7$, $k=\frac{7-1}{2}=3$. Степени: 1, 2, 3, 4, 5, 6, 3. $n=7$ имеет вид $4j+3$, $k=3$ нечётно, $\frac{n-1}{2}=3$ нечётно, условие на число нечётных степеней выполняется.

Этот результат является общим для всех нечётных $n \ge 3$.

Ответ: $\frac{n-1}{2}$