Raiigorodskii A.M.

Consider a graph where the vertices correspond to all possible three-element subsets of the set $\left\{1,2,3, \ldots, 2^{k}\right\}$, and edges are drawn between vertices that correspond to subsets intersecting at exactly one element. Find the minimum number of colors needed to color the vertices of the graph so that any two vertices connected by an edge are of different colors.
Let $N=C_{n}^{3}$ be the number of vertices of our graph $G$, that is, the number of triples of elements from the set $\{1, \ldots, n\}$. The minimum number of colors $\chi(G)$, in which the vertices can be properly colored, is called the chromatic number of the graph.

We will show that $\chi(G) \geq 1 / 6(n-1)(n-2)$. Let $S$ be the maximum number of vertices of the graph, pairwise not connected by edges. Since the number of vertices of each color does not exceed $S$, then $S \cdot \chi(G) \geq N=1 / 6 n(n-1)(n-2)$.

It remains to check that $S \leq N$. But this is proven in the solution of problem $\underline{97876}$ (where students are elements of our set, and clubs are three-element subsets).

Thus, the lower bound is obtained. We will prove that for $n=2^{k}$, it is exact.

We will show how to color the vertices of the graph in $X=1 / 6(n-1)(n-2)$ colors. Encode the elements of the set $\{1,2, \ldots, n\}$ with all possible sequences of the form $x=\left(x_{1}, \ldots, x_{k}\right)$ of length $k$, consisting of zeros and ones.

Then a vertex of the graph is a triple of such sequences $\left\{\boldsymbol{a}_{1}, \boldsymbol{a}_{2}, \boldsymbol{a}_{3}\right\}$. Associate with the vertex $v$ of the graph a triple $b(v)=\left\{\boldsymbol{b}_{1}, \boldsymbol{b}_{2}, \boldsymbol{b}_{3}\right\}$, where $\boldsymbol{b}_{1}=\boldsymbol{a}_{2}+\boldsymbol{a}_{3}, \boldsymbol{b}_{2}=\boldsymbol{a}_{3}+\boldsymbol{a}_{1}, \boldsymbol{b}_{3}=\boldsymbol{a}_{1}+\boldsymbol{a}_{2}$ - sums modulo two. Clearly, among the sequences $\boldsymbol{b}_{1}, \boldsymbol{b}_{2}, \boldsymbol{b}_{3}$ there are no identical ones. Therefore, $b(v)$ is a set of three distinct elements. Assign a unique color to each set of the form $b(v)$, thus obtaining a coloring of the vertices of the original graph. Note that if two vertices $u, v$ of the graph intersect at exactly one element, then the corresponding triples $b(u), b(v)$ are different. Consequently, the obtained coloring is valid. It remains to count the number of colors used. It is not difficult to see that

1) none of the sequences $\boldsymbol{b}_{1}, \boldsymbol{b}_{2}, \boldsymbol{b}_{3}$ coincides with the sequence $\mathbf{0}$, consisting of all zeros;
2) $\boldsymbol{b}_{1}+\boldsymbol{b}_{2}+\boldsymbol{b}_{3}=2 \boldsymbol{a}_{1}+2 \boldsymbol{a}_{2}+2 \boldsymbol{a}_{3}=\mathbf{0}(\bmod 2)$
3) any set consisting of three distinct sequences $\boldsymbol{b}_{1}, \boldsymbol{b}_{2}, \boldsymbol{b}_{3}$, which satisfies the previous two points, can be obtained from some vertex of the graph in the described way: for this, it is sufficient to consider the vertex $\left\{\boldsymbol{0}, \boldsymbol{b}_{3}, \boldsymbol{b}_{2}\right\}$.

Thus, $\boldsymbol{b}_{1}$ can be chosen in $n-1$ ways, $\boldsymbol{b}_{2}$ in $n-2$ ways, and $\boldsymbol{b}_{3}$ is uniquely determined by them. Since the triples are unordered, the result $(n-1)(n-2)$ should be divided by 6. Thus, the number of different triples $\left\{\boldsymbol{b}_{1}, \boldsymbol{b}_{2}, \boldsymbol{b}_{3}\right\}$ associated with the vertices of the graph is $\chi$, that is, we have colored the vertices in $\chi$ colors.

## Answer

$1 / 6\left(2^{k}-1\right)\left(2^{k}-2\right)$ colors.