## Coloured Strings

#### Problem

In a cuboid shaped room a hook is placed in the centre of each wall, the floor, and the ceiling. Every pair of hooks has either a piece of red or blue string tied between them. As this task is being performed triangles will be formed between sets of three hooks with edges being red or blue.

Prove that it is impossible to complete this task without forming at least one triangle of the same colour.

#### Solution

From each hook there are five pieces of string connected to it, which means that the problem is equivalent to colouring all the edges of a fully connected hexagon, $ABCDEF$, so that no triangle formed between any three vertices has all of its edges the same colour.

If we consider the number of red and blue edges connected to a particular vertex, $(R,B)$, the edges can be coloured in the following way: $(0,5)$, $(1,4)$, $(2,3)$, $(3,2)$, $(4,1)$, $(5,0)$. It is significant to note that at least three edges at each vertex must be the same colour.

Without loss of generality let us suppose that we colour $AB$, $AC$, and $AD$ red:

Clearly $BC$ and $CD$ must be both blue, otherwise triangle $ABC$ or triangle $ACD$ would be red. However, it is now impossible to colour $BD$ red or blue without making either triangle $ABD$ red or triangle $BCD$ blue.

Hence it is impossible to colour the hexagon using two colours so as to not form a triangle with three edges the same colour, which means that the original task involving the pieces of string is also impossible.

What if three colours were allowed?
Investigate using $k$ colours to colour a fully connected $n$-gon.

Problem ID: 259 (09 Jan 2006)     Difficulty: 3 Star

Only Show Problem