\section*{Problem 5 - 261045}

In a domino game with the numbers \(0,1,2, \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, 2, .. , 6 occur exactly once.

A chain is formed when several tiles are placed next to each other in a sequence such that adjacent halves of neighboring tiles always bear the same number.

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

A closed chain of three different tiles is briefly called a triplet chain. Two triplet chains are considered the same if and only if they consist of the same tiles.

Determine the number of all sets \(\left\{K_{1}, \ldots, K_{7}\right\}\) consisting of exactly 7 different triplet chains \(K_{1}, \ldots, K_{7}\), where each tile of the domino game appears in at most one of the chains \(K_{1}, \ldots, K_{7}\)!

(As usual, two sets \(\mathrm{M}=\left\{K_{1}, \ldots, K_{7}\right\}\) and \(M^{\prime}=\left\{K_{1}^{\prime}, \ldots, K_{7}^{\prime}\right\}\) are considered equal if and only if every chain \(K_{i}\) contained in the set \(M\) is also contained in \(M^{\prime}\) and vice versa every chain contained in \(M^{\prime}\) is also contained in \(M\).)
}

In every triplet chain \((a, b),(b, c),(c, a)\), \(a, b, c\) are three pairwise different numbers; for if \(a=b\), then \((b, c)\) and \((c, a)\) would be two identical stones; similarly, \(a=c\) and \(b=c\) are refuted.

Conversely, for any three pairwise different numbers \(a, b, c\), there is exactly one triplet chain that contains these numbers. Furthermore, it holds that:

I. If \(M=\left\{K_{1}, \ldots, K_{7}\right\}\) is a set with the properties described in the problem, then: Since no stone appears more than once in the triplet chains \(K_{1}, \ldots, K_{7}\), they contain 21 stones. Since the domino set contains only 21 stones \((a, b)\) with \(a \neq b\), each of these stones appears in exactly one of the chains \(K_{1}, \ldots, K_{7}\).

Thus, one of these chains, without loss of generality, the chain \(K_{1}\), contains the stone (0,1). One can therefore perform a renaming of the numbers 2,3,4,5,6 such that the one of these five numbers receives the new name

2 (1), with which

\[
K_{1}=(0,1),(1,2),(2,0)
\]

is. Further, one of the chains \(K_{2}, \ldots, K_{7}\), without loss of generality, the chain \(K_{2}\) contains the stone (0,3). Since \(K_{2}\) also does not contain any of the stones mentioned in (2), it follows that: In \(K_{2}\), apart from 0 and 3, the third number is neither 1 nor 2. One can therefore perform a renaming of the numbers 4,5,6 such that the one of these three numbers receives the new name 4 (3), with which

\[
K_{2}=(0,3)(3,4),(4,0)
\]

is. Then it follows:

Without loss of generality, \(K_{3}\) contains the stone (0,5) and, in addition, none of the stones in (2), (4), so apart from 0 and 5, it contains none of the numbers \(1,2,3,4\). Thus,

\[
K_{3}=(0,5)(5,6),(6,0)
\]

Without loss of generality, \(K_{4}\) contains the stone (1,3) and, in addition, none of the stones in (2), (4). One can therefore perform a renaming of the numbers 5,6 such that the one of these two numbers receives the new name 5 (6), with which

\[
K_{4}=(1,3)(3,5),(5,1)
\]

Without loss of generality, \(K_{5}\) contains the stone (1,4) and, in addition, none of the stones in (2), (4), (7). Thus,

\[
K_{5}=(1,4)(4,6),(6,1)
\]

Without loss of generality, \(K_{6}\) contains the stone (2,3) and, in addition, none of the stones in (4), (7). Thus,

\[
K_{6}=(2,3)(3,6),(6,2)
\]

For \(K_{7}\), only

\[
K_{7}=(2,4)(4,5),(5,2)
\]

remains. 

Therefore, only those sets \(M=\left\{K_{1}, \ldots, K_{7}\right\}\) can have the properties mentioned in the problem, which, after performing renamings according to (1), (3), (6), contain the chains mentioned in (2), (4), (5), (7), (8), (9), (10).

II. Every such set has these properties, since a renaming according to (3) does not change the chain (2) and similarly a renaming according to (6) does not change any of the chains (2), (4), (5), so that the requirements placed on \(M\) in the problem can be confirmed from the information in (2), (4), (5), (7), (8), (9), (10) after these renamings.

III. With I. and II., it is proven that exactly those sets \(M=\left\{K_{1}, \ldots, K_{7}\right\}\), which can be obtained according to (1) - (10), have the properties required in the problem.

Furthermore, it follows: Any two such sets \(M, M^{\prime}\), for which two different choices were made in (1) during their derivation, are different from each other, since the chain that, according to the choice leading to \(M\), is the chain \(K_{1}\) mentioned in (2), does not appear in \(M^{\prime}\).

Similarly, it follows: Any two sets \(M, M^{\prime}\), for which the same choice was made in (1) but different choices in (3) during their derivation, are different from each other, since the chain \(K_{2}\) mentioned in (4) that is contained in \(M\) does not appear in \(M^{\prime}\). Correspondingly, any two sets are also different from each other if the same choices were made in (1) and (3) but different choices in (6) during their derivation.

Thus, it follows in total: By making all the \(5 \cdot 3 \cdot 2\) possible choices in (1), (3), (6), sets with the properties required in the problem are obtained, each exactly once. Therefore, the number of such sets is \(5 \cdot 3 \cdot 2=30\).

Adapted from [5]