MathDB

(298) 5

Part of 1991 Tournament Of Towns

Problems(1)

TOT 298 1991 Spring A S5 system of roads fro 16 cities

Source:

6/9/2024
There are 1616 cities in a certain kingdom. The king wants to have a system of roads constructed so that one can go along those roads from any city to any other one without going through more than one intermediate city and so that no more than 55 roads go out of any city. (a) Prove that this is possible. (b) Prove that if we replace the number 55 by the number 44 in the statement of the problem the king’s desire will become unrealizable.
(D. Fomin, Leningrad)
combinatorics