Problem

Source: Komal A. 722.

Tags: combinatorics



The Hawking Space Agency operates $n-1$ space flights between the $n$ habitable planets of the Local Galaxy Cluster. Each flight has a fixed price which is the same in both directions, and we know that using these flights, we can travel from any habitable planet to any habitable planet. In the headquarters of the Agency, there is a clearly visible board on a wall, with a portrait, containing all the pairs of different habitable planets with the total price of the cheapest possible sequence of flights connecting them. Suppose that these prices are precisely $1,2, ... , \binom{n}{2}$ monetary units in some order. prove that $n$ or $n-2$ is a square number.