Разделы 
Дополнительно
Задача по математике - 3841
2019-06-16 
В одном государстве король хочет построить $n$ городов и $n - 1$ дорог между ними так, чтобы из каждого города можно было проехать в любой другой. (Каждая дорога соединяет два города, дороги не пересекаются и не проходят через другие города.) Король хочет, чтобы кратчайшие расстояния по сети дорог между парами городов равнялись соответственно $1, 2, 3, \cdots, \frac {n(n-1)}{2}$ км. Возможно ли это, если а) $n = 6$; б) * $n = 1986$?
Решение:
Если требуемая сеть дорог существует, то одно из чисел - $n$ или $n - 2$ - является квадратом целого числа.
Выберем какой-нибудь город $A$ и назовем его «хорошим». Любой город называется «хорошим», если длина пути $A$ и $B$ - четное число, и «плохим» - если нечетное. Пусть $x$ - число «хороших» городов, $y$ - число «плохих» городов ($x + y = n$). Всего есть $xy$ пар городов, в которых один город хороший, а другой - плохой. Значит, среди чисел $1, 2, \cdots \frac {n(n-1)}{2}$ имеется $xy$ нечетных чисел. Если $n$ нечетно, то $n = n^2 - 4 xy = (x - y)^2$, если же четно, то $n = (x - y)^2 + 2$.
а) Можно (рис.). б) Нельзя.
В одном государстве король хочет построить $n$ городов и $n - 1$ дорог между ними так, чтобы из каждого города можно было проехать в любой другой. (Каждая дорога соединяет два города, дороги не пересекаются и не проходят через другие города.) Король хочет, чтобы кратчайшие расстояния по сети дорог между парами городов равнялись соответственно $1, 2, 3, \cdots, \frac {n(n-1)}{2}$ км. Возможно ли это, если а) $n = 6$; б) * $n = 1986$?
Решение:
Если требуемая сеть дорог существует, то одно из чисел - $n$ или $n - 2$ - является квадратом целого числа.
Выберем какой-нибудь город $A$ и назовем его «хорошим». Любой город называется «хорошим», если длина пути $A$ и $B$ - четное число, и «плохим» - если нечетное. Пусть $x$ - число «хороших» городов, $y$ - число «плохих» городов ($x + y = n$). Всего есть $xy$ пар городов, в которых один город хороший, а другой - плохой. Значит, среди чисел $1, 2, \cdots \frac {n(n-1)}{2}$ имеется $xy$ нечетных чисел. Если $n$ нечетно, то $n = n^2 - 4 xy = (x - y)^2$, если же четно, то $n = (x - y)^2 + 2$.
а) Можно (рис.). б) Нельзя.
