27. (BLR) Ten points such that no three of them lie on a line are marked in the plane. Each pair of points is connected with a segment. Each of these segments is painted with one of $k$ colors in such a way that for any $k$ of the ten points, there are $k$ segments each joining two of them with no two being painted the same color. Determine all integers $k, 1 \leq k \leq 10$, for which this is possible.
27. Since this is essentially a graph problem, we call the points and segments vertices and edges of the graph. We first prove that the task is impossible if \( k \leq 4 \). Cases \( k \leq 2 \) are trivial. If \( k=3 \), then among the edges from a vertex \( A \) there are two of the same color, say \( A B \) and \( A C \), so we don't have all the three colors among the edges joining \( A, B, C \). Now let \( k=4 \), and assume that there is a desired coloring. Consider the edges incident with a vertex \( A \). At least three of them have the same color, say blue. Suppose that four of them, \( A B, A C, A D, A E \), are blue. There is a blue edge, say \( B C \), among the ones joining \( B, C, D, E \). Then four of the edges joining \( A, B, C, D \) are blue, and we cannot complete the coloring. So, exactly three edges from \( A \) are blue: \( A B, A C, A D \). Also, of the edges connecting any three of the 6 vertices other than \( A, B, C, D \), one is blue (because the edges joining them with \( A \) are not so). By a classical result, there is a blue triangle \( E F G \) with vertices among these six. Now one of \( E B, E C, E D \) must be blue as well, because none of \( B C, B D, C D \) is. Let it be \( E B \). Then four of the edges joining \( B, E, F, G \) are blue, which is impossible. For \( k=5 \) the task is possible. Label the vertices \( 0,1, \ldots, 9 \). For each color, we divide the vertices into four groups and paint in this color every edge joining two from the same group, as shown below. Then among any 5 vertices, 2 must belong to the same group, and the edge connecting them has the considered color.  | yellow: | 011220 | 366993 | 57 | 48 | | :--- | :--- | :--- | :--- | :--- | | red: | 233442 | 588115 | 79 | 60 | | blue: | 455664 | 700337 | 91 | 82 | | green: | 677886 | 922559 | 13 | 04 | | orange: | 899008 | 144771 | 35 | 26. |  A desired coloring can be made for \( k \geq 6 \) as well. Paint the edge \( i j \) in the \( (i+j) \)th color for \( i<j \leq 8 \), and in the \( 2i \)th color if \( j=9 \) (the addition being modulo 9 ). We can ignore the edges painted with the extra colors. Then the edges of one color appear as five disjoint segments, so that any complete \( k \)-graph for \( k \geq 5 \) contains one of them.