Maths Olympiad Prep

Library / /25 of 39

Combinatorics Difficulty 6.7 National Olympiad Prove it Croatia

A magical triangulation is a partition of a triangle on smaller triangles by a finite number of segments whose endpoints are vertices of the triangle or points in its interior, such that in every point (including the vertices of the triangle) meets the same number of segments.
What is the maximal number of smaller triangles on which we can divide the triangle in a magical triangulation?

Solution

Let nn be the number of smaller triangles, tt the number of points in the triangulation (including the vertices of the triangle), dd the number of segments (including the sides of the triangle) and kk the number of segments meeting in each point of the triangulation.

Obviously tk=2dt \cdot k = 2 \cdot d holds. Furthermore, dd segments are sides of n+1n + 1 triangles, so 2d=3(n+1)2d = 3(n + 1) since each segment is a side of exactly two triangles.

Finally, let us consider the sum of inner angles of smaller triangles. That sum is equal to n180n \cdot 180^\circ. On the other hand, in each of t3t - 3 points in the interior of the triangle that sum is equal to 360360^\circ, so when we add the angles of the big triangle we get that the sum of angles of the smaller triangles is equal 180+(t3)360180^\circ + (t - 3) \cdot 360^\circ. Hence n180=180+(t3)360n \cdot 180^\circ = 180^\circ + (t - 3) \cdot 360^\circ, i.e. 2t=n+52t = n + 5. From these equations, it follows that
n=5k66k=246k+5. n = \frac{5k - 6}{6 - k} = \frac{24}{6 - k} + 5.
So, 6k6 - k divides 2424 and the only possibilities for a positive integer nn are obtained if k{2,3,4,5}k \in \{2, 3, 4, 5\}, i.e. n{1,3,7,19}n \in \{1, 3, 7, 19\}. The maximal possible number of smaller triangles is 1919 and the following example shows that this can be achieved.

Figure 1

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.