Baltic Way 1997 · Problem 19

Combinatorics

In a forest each of $n$ animals $(n \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 $n$ , the maximum possible number of campaign-making animals is $\frac{n-1}{2}$ ;

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

Change pool

When you’re ready

Review material becomes available with the next Daily.

Review

Topics

Graph theory

Solutions

Solution

Solution:

a) As each campaign-making animal uses exactly $n$ paths and the total number of paths is $\frac{n(n-1)}{2}$ , the number of campaign-making animals cannot exceed $\frac{n-1}{2}$ . Labeling the caves by integers $0,1,2, \ldots, n-1$ , we can construct $\frac{n-1}{2}$ non-intersecting campaign routes as follows:

\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 $\frac{n-1}{2}$ campaign-making animals can be chosen arbitrarily).

b) As noted above, the number of campaign-making animals cannot exceed $\frac{9-1}{2}=4$ . The 4 non-intersecting campaign routes can be constructed as follows:

\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}

Contest context

Results from Baltic Way 1997

11 teams

Mean score: 3.0 / 5
Scores of 4 or 5: 2 / 11
Estonia: 3 / 5

Score distribution

All team scores

Team	Score
Poland	3 / 5
Germany	3 / 5
Estonia	3 / 5
Sweden	3 / 5
Denmark	3 / 5
Latvia	1 / 5
Finland	2 / 5
Norway	3 / 5
St. Petersburg	2 / 5
Iceland	5 / 5
Lithuania	5 / 5

Review

Topics

Solutions

Contest context

Elsewhere