Maths Olympiad Prep

Library / /4 of 6

Combinatorics Difficulty 5.7 AIME, harder Prove it Brazil

Determine all values of nn such that it is possible to divide a triangle in nn smaller triangles such that there are not three collinear vertices and such that each vertex belongs to the same number of segments.

Solution

Consider the planar graph which vertices are the vertices of the triangles and edges are the sides of the triangles. Let VV, EE and FF be the number of vertices, edges and faces of such graph and dd be the degree of each vertex. Note that n=F1n = F - 1. Then E=3F2=dV2    V=2EdE = \frac{3F}{2} = \frac{dV}{2} \iff V = \frac{2E}{d} and F=2E3F = \frac{2E}{3}. By Euler's theorem, VE+F=2    1d+13=12E+12>12    1d>16    d<6V - E + F = 2 \iff \frac{1}{d} + \frac{1}{3} = \frac{1}{2E} + \frac{1}{2} > \frac{1}{2} \implies \frac{1}{d} > \frac{1}{6} \iff d < 6. It's not hard to see that d3d \ge 3 and that each value for dd determines VV, EE and FF. Indeed d=3    F=4d = 3 \implies F = 4; d=4    F=8d = 4 \implies F = 8; d=5    F=20d = 5 \implies F = 20. The following examples show that the possible values for nn are indeed 33, 77 and 1919.
Figure 1
Figure 2
Figure 3

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 and solution reproduced as published; topic and difficulty added by this site.