Problem 1734

Let us fix a notation: Number the points $1, 2, \dots, n$; The colour of the string between points $i$ and $j$ is denoted by $c(i, j)$, so that $c(i, j) \in \{\text{B}, \text{G}, \text{R}, \text{Y}\}$ for all $1 \le i, j \le n$, $i \ne j$, and where $\text{B} = \text{Blue}$, $\text{G} = \text{Green}$, $\text{R} = \text{Red}$, and $\text{Y} = \text{Yellow}$.

For $n = 3$, there is a trivial solution, by putting, say, $c(1,2) = \text{B}$, $c(2,3) = \text{G}$, $c(3,1) = \text{R}$. Also, for $n = 4$ it is fairly straightforward to see a solution, say $c(1,2) = c(3,4) = \text{B}$, $c(1,3) = c(2,4) = \text{G}$, and $c(1,4) = c(2,3) = \text{R}$.

Henceforth, assume that $n > 4$.

We first observe that no point can have three strings of the same colour attached to it. For suppose (without loss of generality) that $c(1,2) = c(1,3) = c(1,4) = \text{B}$. Then $c(2,3) = c(2,4) = c(3,4) = \text{B}$. This implies that there must be a fifth point, $5$, say, such that $c(1,5) \neq \text{B}$ (otherwise all strings will have the same colour $\text{B}$). Assume $c(1,5) = \text{G}$. Then $c(2,5), c(3,5), c(4,5) \notin \{\text{B}, \text{G}\}$. Assume that $c(2,5) = \text{R}$, say. Then $c(3,5) \neq \text{R}$, forcing $c(3,5) = \text{Y}$. But then $c(4,5) \notin \{\text{R}, \text{Y}\}$, by condition (ii) applied to the two sets $\{2,4,5\}$ and $\{3,4,5\}$ of three points each. The contradiction $c(4,5) \notin \{\text{B}, \text{G}, \text{R}, \text{Y}\}$ proves that our claim is valid. Consequently, there can be at most two strings of each colour attached to each point, implying that there can be no more than nine points in total.

We now show that it is indeed possible that nine points can be mutually connected by strings such that all conditions (i) to (iii) are satisfied.

Partition the points $1, 2, \dots, 9$ into three subsets of three points each: $X = \{1, 2, 3\}$, $Y = \{4, 5, 6\}$, $Z = \{7, 8, 9\}$. First, consider the three 'internal' monochromatic triangles (all sides Blue) where the points in each of these subsets are connected with Blue strings. Then we construct nine further monochromatic triangles $KLM$, where $K \in X$, $L \in Y$, and $M \in Z$ (three of each of the colours Green, Red and Yellow). This can be done in several ways (six ways, to be precise). We show here a nice symmetrical one: Three Green triangles $\{1, 4, 7\}$, $\{2, 5, 8\}$, $\{3, 6, 9\}$; Three Red triangles $\{1, 5, 9\}$, $\{2, 6, 7\}$, $\{3, 4, 8\}$; Three Yellow triangles $\{1, 6, 8\}$, $\{2, 4, 9\}$, $\{3, 5, 7\}$. See Figure 4.

The motivation behind the method used here was to write a $3 \times 3$ table:
$$T = \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 4 & 5 & 6 \\ \hline 7 & 8 & 9 \\ \hline \end{array}$$
The rows of $T$ ($\{1, 2, 3\}$, $\{4, 5, 6\}$, $\{7, 8, 9\}$) are used to determine the three Blue triangles. The columns ($\{1, 4, 7\}$, $\{2, 5, 8\}$, $\{3, 6, 9\}$) are used to determine the three Green triangles. For the final two colours we use one element from each row and one element from each column, in two possible ways: For the Red triangles: $\{1, 5, 9\}$, $\{2, 6, 7\}$, $\{3, 4, 8\}$; and for the Yellow triangles: $\{3, 5, 7\}$, $\{2, 4, 9\}$, $\{1, 6, 8\}$.

Now we have a string between each two points, and if a triangle contains two sides/strings of the same colour, the third side must also be of that colour.

We conclude that the maximum possible value of $n$ is $n = 9$.