HMMT 二月 2009 · 冲刺赛 · 第 28 题

英文解析

28. [ 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 polynomialfunction 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 6
    one red and at least one blue edge?
    Answer: 14 Solution: The existence of the Chebyshev polynomials, which express cos( nθ ) asa polynomial in cos( θ ), imply that Bob draws a blue line between cos( θ ) and each other vertex, andalso 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 eachother pair of vertices.
    2 π
    Let m and n be positive integers. Notice that cos( nθ ) is a periodic function with period , andn
    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 formk
    2 π 2 πsome k . Therefore, if cos( nθ ) can be expressed as a polynomial in cos( mθ ) then = for some k ,
    n mkso m | n . This shows that there is a blue line between two vertices cos( aθ ) and cos( bθ ) if and only ifone 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
    ( )
    all red edges, and = 20 triangles total. Thus there are 20 − 3 − 3 = 14 triangles having at least one 6
    red and at least one blue edge.3