MathDB

A. 722

Part of KoMaL A Problems 2017/2018

Problems(1)

The Hawking space

Source: Komal A. 722.

5/12/2018
The Hawking Space Agency operates n−1n-1 space flights between the nn 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,...,(n2)1,2, ... , \binom{n}{2} monetary units in some order. prove that nn or n−2n-2 is a square number.
combinatorics