Balti Tee 1997 · Ülesanne 19

Kombinatoorika

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$ .

Muuda valikut

Kui oled valmis

Ülevaatematerjal muutub kättesaadavaks järgmise päevaülesannete komplektiga.

Ülevaade

Teemad

Graafiteooria

Lahendused

Lahendus

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}

Võistluse kontekst

Balti Tee tulemused 1997

11 võistkonda

Keskmine tulemus: 3,0 / 5
4 või 5 punkti: 2 / 11
Eesti: 3 / 5

Punktijaotus

Kõigi võistkondade punktid

Võistkond	Punktid
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

Ülevaade

Teemad

Lahendused

Võistluse kontekst

Mujal