HMMT 二月 2009 · 冲刺赛 · 第 28 题
HMMT February 2009 — Guts Round — Problem 28
题目详情
- [ 15 ] The vertices of a regular hexagon are labeled cos( θ ) , cos(2 θ ) , . . . , cos(6 θ ). For every pair of ver- tices, Benjamin 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 θ ), 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?
解析
- [ 15 ] The vertices of a regular hexagon are labeled cos( θ ) , cos(2 θ ) , . . . , cos(6 θ ). 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 θ ), and otherwise Roberta draws a red line through the 6 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? Answer: 14 Solution: The existence of the Chebyshev polynomials, which express cos( nθ ) as a polynomial in cos( θ ), imply that Bob draws a blue line between cos( θ ) and each other vertex, and also between cos(2 θ ) and cos(4 θ ), between cos(2 θ ) and cos(6 θ ), and between cos(3 θ ) and cos(6 θ ) (by ′ substituting θ = 2 θ or 3 θ as necessary). We now show that Roberta draws a red line through each other pair of vertices. 2 π Let m and n be positive integers. Notice that cos( nθ ) is a periodic function with period , and n 2 π 2 π cos( mθ ) is periodic with period . Thus, any polynomial in cos( mθ ) is also periodic of period . m m 2 π This may not be the minimum period of the polynomial, however, so the minimum period is for mk 2 π 2 π some k . Therefore, if cos( nθ ) can be expressed as a polynomial in cos( mθ ) then = for some k , n mk so m | n . This shows that there is a blue line between two vertices cos( aθ ) and cos( bθ ) if and only if one of a or b divides the other. Drawing the graph, one can easily count that there are 3 triangles with all blue edges, 3 triangles with ( ) 6 all red edges, and = 20 triangles total. Thus there are 20 − 3 − 3 = 14 triangles having at least one 3 red and at least one blue edge.