MathDB

(034) O3

Part of 1983 Tournament Of Towns

Problems(1)

TOT 034 1983 Spring J-O3 J-A3 S-O3 S-A3 N towns in Shvambrania

Source:

8/18/2019
In Shvambrania there are NN towns, every two of which are connected by a road. These roads do not intersect. If necessary, some of them pass over or under others via bridges. An evil magician establishes one-way rules along the roads in such a way that if someone goes out of a certain town he is unable to come back. Prove that
(a) It is possible to establish such rules. (b) There exists a town from which it is possible to reach any other town, and there exists a town from which it is not possible to go out. (c) There is one and only one route passing through all towns. (d) The magician can realise his intention in N!N! ways.
(LM Koganov, Moscow)
PS. (a),(b),(c) for Juniors, (a),(b),(d) for Seniors
combinatorics