Maths Olympiad Prep

Library / /71 of 71

Algebra Difficulty 6.1 National Olympiad Prove it United States

Problem:

The vertices of a regular hexagon are labeled cos(θ)\cos (\theta), cos(2θ)\cos (2 \theta), cos(3θ)\cos (3 \theta), cos(4θ)\cos (4 \theta), cos(5θ)\cos (5 \theta), cos(6θ)\cos (6 \theta). For every pair of vertices, Bob draws a blue line through the vertices if one of these functions can be expressed as a polynomial function of the other (that holds for all real θ\theta), and otherwise Roberta draws a red line through the vertices. In the resulting graph, how many triangles whose vertices lie on the hexagon have at least one red and at least one blue edge?

Solution

Solution:

Answer: 14

The existence of the Chebyshev polynomials, which express cos(nθ)\cos (n \theta) as a polynomial in cos(θ)\cos (\theta), imply that Bob draws a blue line between cos(θ)\cos (\theta) and each other vertex, and also between cos(2θ)\cos (2 \theta) and cos(4θ)\cos (4 \theta), between cos(2θ)\cos (2 \theta) and cos(6θ)\cos (6 \theta), and between cos(3θ)\cos (3 \theta) and cos(6θ)\cos (6 \theta) (by substituting θ=2θ\theta' = 2 \theta or 3θ3 \theta as necessary). We now show that Roberta draws a red line through each other pair of vertices.

Let mm and nn be positive integers. Notice that cos(nθ)\cos (n \theta) is a periodic function with period 2πn\frac{2 \pi}{n}, and cos(mθ)\cos (m \theta) is periodic with period 2πm\frac{2 \pi}{m}. Thus, any polynomial in cos(mθ)\cos (m \theta) is also periodic of period 2πm\frac{2 \pi}{m}. This may not be the minimum period of the polynomial, however, so the minimum period is 2πmk\frac{2 \pi}{m k} for some kk. Therefore, if cos(nθ)\cos (n \theta) can be expressed as a polynomial in cos(mθ)\cos (m \theta) then 2πn=2πmk\frac{2 \pi}{n} = \frac{2 \pi}{m k} for some kk, so mnm \mid n. This shows that there is a blue line between two vertices cos(aθ)\cos (a \theta) and cos(bθ)\cos (b \theta) if and only if one of aa or bb divides the other.

Drawing the graph, one can easily count that there are 3 triangles with all blue edges, 3 triangles with all red edges, and (63)=20\binom{6}{3} = 20 triangles total. Thus there are 2033=1420 - 3 - 3 = 14 triangles having at least one red and at least one blue edge.

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.