Planting flowers of unknown colours

Question

A gardener has a sack of indistinguishable bulbs and a flat allotment. In the spring, each bulb will produce either a red, green or blue flower. She wishes to plant some of the bulbs so that when spring comes, some two flowers of the same colour will be exactly one metre apart.

How many bulbs must she plant to achieve her goal?

Answer 1

The problem in graph theoretic terminology is to find the minimal number of vertices required for a unit distance graph with chromatic number of $4$.

Brokes' theorem states that:

Any connected, undirected graph of degree $d$ has chromatic number $k<=d$ unless the graph is either complete or an odd cycle when $k=d+1$.

Unit distance graphs are already undirected. Furthermore any minimal solution will be connected since:

• unconnected vertices may be any colour and thus do not increase the chromatic number; and
• the chromatic number of the disjoint union of two connected graphs is equal to the maximum chromatic number of those two graphs.

All odd cycle graphs are unit distance graphs (odd-sided, regular polygons of side $1$). However odd cycles always have degree $2$ and hence, by Brokes' theorem, a chromatic number of $3$ so no odd cycle is a solution.

All even cycle graphs are unit distance graphs (even-sided, regular polygons of side $1$). However all even cycles have degree $2$ and hence a chromatic number less than or equal to $3$. In fact they have chromatic number $2$ which is easy to see: colour any vertex $colour 1$ and follow an edge to the next vetex and colour it $colour 2$, and continue following edges around the polygon alternating colours as you go until all vertices are coloured; the last vertex will be coloured $colour 2$ and hence will not conflict via the ultimate edge leading back to the first coloured vertex.

We can construct the complete graph containing $3$ vertices, $K_3$, as a unit distance graph - it is an equilateral triangle of side $1$, this also has degree $2$ and a chromatic number of $3$.

To construct a complete unit distance graph with more than $3$ vertices we would need to first find a point on the Euclidean plane that lies at a distance of $1$ from all three of the vertices of an equilateral triangle of side $1$, but there is no such point - so there are no complete unit distance graphs with more than $3$ vertices.

Therefore any solution must have degree $>= 4$ (at least one vertex must have at least four neighbours).

Any neighbours of a vertex $P$ lie on a unit circle centred at $P$.

We now not only know that the solution must be at least $5$, but that any valid instance will contain a vertex $P$ at the centre of a unit circle upon which a further four vertices $Q, R, S, T$ exist.

The only way $5$ could be the solution is if such an instance, with no additional vertices, exists with a chromatic number of $4$. We can check the few cases as follows.

If no pair of $Q, R, S, T$ are $1$ apart the chromatic number would be $2$
- $P$ being $colour 1$ and $Q, R, S, T$ being $colour 2$.

If only one pair of $Q, R, S, T$ are $1$ apart, say $Q$ and $R$, then the graph would be an equilateral triangle of side $1$ $PQR$ and two spokes $PS$ and $PT$, which has a chromatic number of $3$
- $P$ being $colour 1$, $Q$ being $colour 2$, $R$ being $colour 3$, and $S$ and $T$ being free to be either $colour 2$ or $colour 3$.

If exactly two pairs of $Q, R, S, T$ are $1$ apart then there are two cases (ignoring label order isomorphisms):

1. $Q$ and $R$ are one pair and $S$ and $T$ are the other; or
2. $Q$ and $R$ are one pair and $R$ and $S$ are the other.

Case 1 is two vertex-adjoined equilateral triangles $PQR$ and $PST$, which has a chromatic number of $3$
- $P$ being $colour 1$, $Q$ and $S$ (or $Q$ and $T$) being $colour 2$, and $R$ and $T$ (or $R$ and $S$) being $colour 3$.

Case 2 is a unit diamond $PQRS$ and a spoke $PT$ from one of the corners on the diagonal of length $1$, which has a chromatic number of $3$
- $P$ being $colour 1$, $Q$ and $S$ being $colour 2$, $R$ being $colour 3$, and $T$ being free to be either $colour 2$ or $colour 3$.

If exactly three pairs of $Q, R, S, T$ are $1$ apart the only formation is the unit triamond $QRST$ with $P$ at the only vertex of the central equilateral triangle that is not a corner of the triamond, which has a chromatic number of $3$
- $P$ being $colour 1$, $Q$ and $S$ being $colour 2$, and $R$ and $T$ being $colour 3$.

In order for $6$ to be the solution we would need to extend any of these instances by one vertex $U$ to yield a graph of chromatic number $4$ by forcing $Q, R, S, T$ to require three colours. This can only be done by placing $U$ at an unoccupied point $1$ away from two vertices already forced to be of equal colour.

If no pair or one pair of $Q, R, S, T$ are $1$ apart no two are already forced to be of the same colour so it will not work.

If two pairs of $Q, R, S, T$ are $1$ apart in case 1 we may swap the colour groups as indicated by the parenthesised options, hence no two are already actually forced to be of the same colour so it also wont work; in case 2 $Q$ and $S$ are forced to be the same colour but the only points one unit away from both are already occupied ($P$ and $R$).

If exactly three pairs of $Q, R, S, T$ are $1$ apart there are two pairs which are already forced to be of the same colour:

1. $Q$ and $S$, but the only points one unit away from both are already occupied ($P$ and $R$); and
2. $R$ and $T$, but the only points one unit away from both are already occupied ($P$ and $S$).

Thus the solution is $> 6$.

Since an example of a solution with $7$ vertices is provided in ralphmerridew's answer and is illustrated below we can now say that:

The solution is $7$.

• in this example $P$ would be $A$ and $Q, R, S, T$ would be $B, E, D, G$ (in any order) this unit distance graph is known as the Moser spindle.

---

ralphmerridew's solution in visual form - the three colours may be rotated, and additionally either or both of (BD) & (EG) may permute to give the same "conflict" on (CF):

If we label $A$ as the origin, with the unit vectors pointing right and down for convenience, and use $\theta$ to name the angle of rotation to transform the unit diamond* $ABCD$ to $AEFG$ then:

$C = (\sqrt{3}\cos(30), \sqrt{3}\sin(30)) = (\frac32, \sqrt{\frac34})$

$F = (\sqrt{3}\cos(30+\theta), \sqrt{3}\sin(30 + \theta))$

So for $C$ and $F$ to be one unit apart:

$\sqrt{(\frac32-\sqrt{3}\cos(30+\theta))^2+(\sqrt{3}\sin(30+\theta)-\sqrt{\frac34})^2}=1$

$\Rightarrow(\frac32-\sqrt{3}\cos(30+\theta))^2+(\sqrt{3}\sin(30+\theta)-\sqrt{\frac34})^2=1$

$\Rightarrow\frac94-\sqrt{27}\cos(30+\theta)+3\cos^2(30+\theta)+3\sin^2(30+\theta)-3\sin(30+\theta)+\frac34 = 1$

$\Rightarrow\frac94-\sqrt{27}\cos(30+\theta)+3-3\sin(30+\theta)+\frac34 = 1$

$\Rightarrow\sqrt{27}\cos(30+\theta)+3\sin(30+\theta) = 5$

$\Rightarrow\sqrt{27}(\cos(30)\cos(\theta)-\sin(30)\sin(\theta))+3(\sin(30)\cos(\theta)+\cos(30)\sin(\theta)) = 5$

$\Rightarrow\sqrt{27}(\sqrt{\frac34}\cos(\theta)-\frac12\sin(\theta))+3(\frac12\cos(\theta)+\sqrt{\frac34}\sin(\theta)) = 5$

$\Rightarrow\frac92\cos(\theta)-\sqrt{\frac{27}4}\sin(\theta)+\frac32\cos(\theta)+\sqrt{\frac{27}4}\sin(\theta) = 5$

$\Rightarrow\cos(\theta) = \frac56$

• $AEFG$ is a rotation about $A$ of $ABCD$ by $\theta=33.557$ degrees $= 0.58569$ radians (5sf)

• Thus angle $BAG = 93.557$ degrees (5sf)

*two unit equilateral triangles adjoined by one side forming a rhombus with 60 and 120 degree angles

Answer 2

Seven bulbs suffice. Plant them so that ABCD and AEFG are rhombuses with a 1-meter side and a sixty-degree angle at A, and such that CF is 1 meter.

Answer 3

Suppose you were to plant just six bulbs. Could we fail to have two flowers the same color a meter apart? I'll show the answer is yes. (This might be overly complicated, but I couldn't do it in less than four cases)

Call two bulbs adjacent if they are planted a meter apart.

1. First note that if you plant a bulb $X$ adjacent to only two others, then we've already failed. $X$ may come up the third color, and hence in the worst case scenario it is useless to our quest for two flowers the same color.
2. Suppose we choose four points $ABCD$ on a unit rhombus with a unit diagonal. Then these four points correspond to points on a triangular lattice. The other two bulbs $E$ and $F$ must be adjacent to at least two of the points $ABCD$, but this is only possible if $E$ and $F$ are both on the triangular lattice as well. But then $E$ and $F$ are forced into one of the following four locations marked x:

...

  .   .   .   .
.   .   x   .   .
  .   A   B   x  
.   x   C   D   .
  .   .   x   .
.   .   .   .

...

Both $E$ and $F$ are then adjacent to only two other flowers, putting us back in case 1.

3. Suppose you have an equailateral triangle $ABC$ . Any bulb adjacent to two of these puts us back in case 2, so that forces the other bulbs to be adjacent to at most one of the set $ABC$. To avoid case 1, we need $D,E,F$ to be adjacent to $A,B,C$ respectively, and we also need $DEF$ to form an equilateral triangle. However, if $ABC$ comes up red, green, blue and $DEF$ comes up green, blue, red, we're in trouble.
4. Finally, consider bulb $A$. To avoid case 1 we must have at least three bulbs adjacent to $A$. Suppose $AB$, $AC$, and $AD$ are all adjacent. To avoid a triangle (case 3), we know $BC$ are not adjacent, nor are $CD$, nor $BD$. That means $B, C, D$ are all adjacent to the last two bulbs $E$ and $F$ (to avoid case 1), and $E$ and $F$ are not adjacent to each other or $A$ (to avoid case 3). But if $A,E,F$ all come up blue and $B, C, D$ all come up green we're in trouble.

Answer 4

Perhaps I am not understanding the question correctly but what about this, which appears to do it with 4 bulbs: plant one bulb at the centre of a circle of 1 metre radius and then three other bulbs on the circumference of the circle. There are only three colours so one of those on the circumference will be the same colour as the one in the centre.