Maths Olympiad Prep

Library / Baltic Way competition problems /40 of 45

Baltic Way competition problems, 1997

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Baltic Way

Problem:

In a forest each of nn animals (n⩾3n \geqslant 3) lives in its own cave, and there is exactly one separate path between any two of these caves. Before the election for King of the Forest some of the animals make an election campaign. Each campaign-making animal visits each of the other caves exactly once, uses only the paths for moving from cave to cave, never turns from one path to another between the caves and returns to its own cave in the end of its campaign. It is also known that no path between two caves is used by more than one campaign-making animal.

a) Prove that for any prime nn, the maximum possible number of campaign-making animals is n−12\frac{n-1}{2};

b) Find the maximum number of campaign-making animals for n=9n=9.

Solution

Solution:

a) As each campaign-making animal uses exactly nn paths and the total number of paths is n(n−1)2\frac{n(n-1)}{2}, the number of campaign-making animals cannot exceed n−12\frac{n-1}{2}. Labeling the caves by integers 0,1,2,…,n−10,1,2, \ldots, n-1, we can construct n−12\frac{n-1}{2} non-intersecting campaign routes as follows:
0→1→2→3→…→n→00→2→4→6→…→n−1→00→3→6→9→…→n−2→0………+⋯0→n−12→n−1→…→n+12→0 \begin{aligned} & 0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow \ldots \rightarrow n \rightarrow 0 \\ & 0 \rightarrow 2 \rightarrow 4 \rightarrow 6 \rightarrow \ldots \rightarrow n-1 \rightarrow 0 \\ & 0 \rightarrow 3 \rightarrow 6 \rightarrow 9 \rightarrow \ldots \rightarrow n-2 \rightarrow 0 \\ & \ldots \ldots \ldots+\cdots \\ & 0 \rightarrow \frac{n-1}{2} \rightarrow n-1 \rightarrow \ldots \rightarrow \frac{n+1}{2} \rightarrow 0 \end{aligned}
(As each of these cyclic routes passes through any cave, the n−12\frac{n-1}{2} campaign-making animals can be chosen arbitrarily).

b) As noted above, the number of campaign-making animals cannot exceed 9−12=4\frac{9-1}{2}=4. The 4 non-intersecting campaign routes can be constructed as follows:
0→1→2→8→3→7→4→6→5→00→2→3→1→4→8→5→7→6→00→3→4→2→5→1→6→8→7→00→4→5→3→6→2→7→1→8→0 \begin{aligned} & 0 \rightarrow 1 \rightarrow 2 \rightarrow 8 \rightarrow 3 \rightarrow 7 \rightarrow 4 \rightarrow 6 \rightarrow 5 \rightarrow 0 \\ & 0 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 4 \rightarrow 8 \rightarrow 5 \rightarrow 7 \rightarrow 6 \rightarrow 0 \\ & 0 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 1 \rightarrow 6 \rightarrow 8 \rightarrow 7 \rightarrow 0 \\ & 0 \rightarrow 4 \rightarrow 5 \rightarrow 3 \rightarrow 6 \rightarrow 2 \rightarrow 7 \rightarrow 1 \rightarrow 8 \rightarrow 0 \end{aligned}

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.