\section*{Problem 2 - 261032}

In a domino game with the numbers \(0,1, \ldots, 6\), each tile is divided into two halves, each half bearing one of the numbers.

In a domino game, all combinations of two of the numbers \(0,1, \ldots, 6\) appear exactly once (including those where the same number appears on both halves of a tile). According to this, a domino game consists of exactly 28 tiles.

A chain is formed when multiple tiles are placed next to each other in a sequence such that adjacent halves of neighboring tiles always bear the same number (domino game rule).

A chain is called closed if the two outer halves at the free ends of the chain also bear the same number.

a) Determine the smallest number \(k>1\) of different tiles from a domino game that can form a closed chain!

b) From a domino game, closed chains consisting of \(k\) different tiles each are to be formed (\(k\) being the number mentioned in a)). Each tile of the domino game should be used in at most one of these chains.

Determine the maximum number \(g\) of chains that can be formed in this way!

c) Determine the number of all different closed chains consisting of \(k\) different tiles that can be formed! (Thus, each tile of the domino game can appear in any number of these chains.)

Two closed chains are considered the same if they show the same sequence of numbers when a suitable starting tile and direction are chosen.

For example, the chains \((2,4),(4,5),(5,5),(5,1),(1,2)\) and \((5,4),(4,2),(2,1),(1,5),(5,5)\) are considered the same.
}

(a) From two different stones of a domino game, one cannot form a closed chain, because in every closed chain \((a, b),(b, a)\) made of two stones, these are identical.

From three stones of a domino game, one can form a closed chain, e.g., \((0,1),(1,2),(2,0)\). Therefore, the smallest number \(k\) sought in (a) is \(k=3\).

(b) In every closed chain \((a, b),(b, c),(c, a)\) made of 3 different stones of a domino game, \(a, b\), and \(c\) are three pairwise different numbers; for if \(a=b\), then \((b, c)\) and \((c, a)\) would be two identical stones; similarly, one disproves \(a=c\) and \(b=c\).

The number of all those stones of a domino game that carry a pair of different numbers is \(28-7=21\). Since \(21: 3=7\), at most 7 chains can be formed in the required manner.

That 7 chains can be formed in this way is shown by the example

\[
\begin{aligned}
& (0,1),(1,2),(2,0) ; \quad(0,3),(3,4),(4,0) ; \quad(0,5),(5,6),(6,0) \\
& (1,3),(3,5),(5,1) ; \quad(1,4),(4,6),(5,2) ; \quad(2,3),(3,6),(6,2) ; \quad(2,4),(4,5),(5,2)
\end{aligned}
\]

Therefore, the number \(g\) sought in (b) is \(g=7\).

(c) As shown in (b), every closed chain made of three different stones of a domino game contains three pairwise different numbers. Conversely, for any three pairwise different numbers \(a, b, c\), there are exactly three stones with each pair of different numbers from these, and there is (according to the explanation of which closed chains are to be considered equal) exactly one closed chain from these three stones, namely the chain \((a, b),(b, c),(c, a)\).

Thus, there are exactly as many closed chains made of three different stones as there are sets of three pairwise different numbers from the numbers \(0, \ldots, 6\).

Selecting three elements from a set of six different numbers, without regard to the order of selection and without repeated selection of an element, corresponds to a combination of \(n\) elements of the \(k\)-th class with \(n=6\) and \(k=3\), i.e.,

\[
\binom{6}{3}=\frac{7 \cdot 6 \cdot 5}{1 \cdot 2 \cdot 3}=35
\]

The number of chains sought is 35.

Adapted from [5]