Browse · MathNet
PrintIreland_2017
Ireland 2017 counting and probability
Problem
An equilateral triangle of integer side length is subdivided into small triangles of unit side length, as illustrated in the figure below for the case . In this diagram, a sub-triangle is a triangle of any size which is formed by connecting vertices of the small triangles along the grid-lines. It is desired to colour each vertex of the small triangles either red or blue in such a way that there is no sub-triangle with all three of its vertices having the same colour. Let denote the number of distinct colourings satisfying this condition. 
Determine, with proof, for every .
Solution
The answer is , , and for .
First consider the case . All possible colourings are valid, except for the two monochromatic colourings. So .
Next consider the case as shown in the Figure below. The 'inner' triangle cannot be monochromatic, so there are possible colourings for this inner triangle. Without loss of generality, consider one of these as shown in the Figure below. Point 1 must be Red, and therefore Points 2 and 3 must be either , or (3 possibilities). This yields a total of , so .
Before considering the next case, we make a simple observation which we formulate as a lemma.
Lemma. There cannot be 3 equally spaced vertices on the base of any sub-triangle all of which have the same colour.
Proof. Assume that there are 3 equally spaced vertices and , on the base of a sub-triangle all of which have the same colour (say Red). Consider the points formed by the intersections of the lines starting at these vertices and forming with the side of the sub-triangle. If any of the so-formed and forming with the side of the sub-triangle is formed. However, three points is Red, a triangle with Red vertices is formed. This proves the lemma. If all are Blue, then is a Blue triangle. This proves the lemma.
Next consider the case as shown in the Figure below.
Case 1. First assume that the two points 1 and 2 have the same colour, say Blue. Then Point 3 must be Red, and the lemma also implies that Points 4 and 5 are also Red. This in turn implies that Point 6 is Blue. Looking now at Points 7 and 8, we see that they cannot both have the same colour; they cannot both be Blue as this would form a monochromatic triangle 678, and they cannot both be Red as this would violate the lemma (their midpoint, 3, is Red). So, without loss of generality, Point 7 is Blue and Point 8 is Red. This in turn implies that Points 9 and 10 must be Red and Blue respectively. It can be easily checked that this colouring is valid. Accounting for symmetries leads to 12 possibilities (2 choices for the colour of Points 1 and 2, 2 further choices for the colouring of Points 7 and 8, and 3 possible rotations of the large triangle).
Case 2. The only other possibility is that Points 1 and 2 have different colours, and the same holds for the pairs of Points (7, 9) and (8, 10). Then, we must have that Points 1, 8, 9 are the same colour (say Blue) and that Points 2, 7, 10 are the other colour (Red) – if not, a vertex of the large triangle will not be colourable without completing a monochromatic triangle. The outer triangle 645 can then be coloured in different ways and the centre vertex of the large triangle can be coloured in 2 ways (Red or Blue). Accounting for all symmetries, this yields 24 possibilities (2 choices for colouring of Points 1, 8, 9, a further 6 possibilities to colour the outer triangle, and 2 possibilities for the colour of the centre of the large triangle). Adding together all of these distinct colourings from Cases 1 and 2 yields .
Next consider the case as shown in the Figure below. The ‘inner’ triangle cannot be monochromatic, so without loss of generality, two vertices are coloured Blue and one vertex is coloured Red as shown in the diagram. The two Blue vertices then imply that Point 1 is Red, and we also conclude from the lemma that Points 2 and 3 are Red. This in turn implies that Point 4 is Blue.
Looking now at Points 5 and 6, we see that they cannot both have the same colour; they cannot both be Blue as this would form a monochromatic triangle 456, and they cannot both be Red as this would violate the lemma (their midpoint is Red). So, without loss of generality, Point 5 is Blue and Point 6 is Red. Since Point 3 is also Red, the lemma implies that Points 7 and 8 must both be Blue, which in turn implies that Point 9 is Red. But now we are stuck, since we cannot colour the point labelled X without forming a monochromatic triangle (either a Blue triangle X48 or a Red triangle X29). So .
It is easy to see that the diagram for contains the diagram for , and so implies for . This completes the proof.
First consider the case . All possible colourings are valid, except for the two monochromatic colourings. So .
Next consider the case as shown in the Figure below. The 'inner' triangle cannot be monochromatic, so there are possible colourings for this inner triangle. Without loss of generality, consider one of these as shown in the Figure below. Point 1 must be Red, and therefore Points 2 and 3 must be either , or (3 possibilities). This yields a total of , so .
Before considering the next case, we make a simple observation which we formulate as a lemma.
Lemma. There cannot be 3 equally spaced vertices on the base of any sub-triangle all of which have the same colour.
Proof. Assume that there are 3 equally spaced vertices and , on the base of a sub-triangle all of which have the same colour (say Red). Consider the points formed by the intersections of the lines starting at these vertices and forming with the side of the sub-triangle. If any of the so-formed and forming with the side of the sub-triangle is formed. However, three points is Red, a triangle with Red vertices is formed. This proves the lemma. If all are Blue, then is a Blue triangle. This proves the lemma.
Next consider the case as shown in the Figure below.
Case 1. First assume that the two points 1 and 2 have the same colour, say Blue. Then Point 3 must be Red, and the lemma also implies that Points 4 and 5 are also Red. This in turn implies that Point 6 is Blue. Looking now at Points 7 and 8, we see that they cannot both have the same colour; they cannot both be Blue as this would form a monochromatic triangle 678, and they cannot both be Red as this would violate the lemma (their midpoint, 3, is Red). So, without loss of generality, Point 7 is Blue and Point 8 is Red. This in turn implies that Points 9 and 10 must be Red and Blue respectively. It can be easily checked that this colouring is valid. Accounting for symmetries leads to 12 possibilities (2 choices for the colour of Points 1 and 2, 2 further choices for the colouring of Points 7 and 8, and 3 possible rotations of the large triangle).
Case 2. The only other possibility is that Points 1 and 2 have different colours, and the same holds for the pairs of Points (7, 9) and (8, 10). Then, we must have that Points 1, 8, 9 are the same colour (say Blue) and that Points 2, 7, 10 are the other colour (Red) – if not, a vertex of the large triangle will not be colourable without completing a monochromatic triangle. The outer triangle 645 can then be coloured in different ways and the centre vertex of the large triangle can be coloured in 2 ways (Red or Blue). Accounting for all symmetries, this yields 24 possibilities (2 choices for colouring of Points 1, 8, 9, a further 6 possibilities to colour the outer triangle, and 2 possibilities for the colour of the centre of the large triangle). Adding together all of these distinct colourings from Cases 1 and 2 yields .
Next consider the case as shown in the Figure below. The ‘inner’ triangle cannot be monochromatic, so without loss of generality, two vertices are coloured Blue and one vertex is coloured Red as shown in the diagram. The two Blue vertices then imply that Point 1 is Red, and we also conclude from the lemma that Points 2 and 3 are Red. This in turn implies that Point 4 is Blue.
Looking now at Points 5 and 6, we see that they cannot both have the same colour; they cannot both be Blue as this would form a monochromatic triangle 456, and they cannot both be Red as this would violate the lemma (their midpoint is Red). So, without loss of generality, Point 5 is Blue and Point 6 is Red. Since Point 3 is also Red, the lemma implies that Points 7 and 8 must both be Blue, which in turn implies that Point 9 is Red. But now we are stuck, since we cannot colour the point labelled X without forming a monochromatic triangle (either a Blue triangle X48 or a Red triangle X29). So .
It is easy to see that the diagram for contains the diagram for , and so implies for . This completes the proof.
Final answer
f(1) = 6, f(2) = 18, f(3) = 36, and f(n) = 0 for all n ≥ 4
Techniques
Coloring schemes, extremal argumentsEnumeration with symmetry