HMMT 二月 2018 · 冲刺赛 · 第 23 题
HMMT February 2018 — Guts Round — Problem 23
题目详情
- [ 12 ] Kevin starts with the vectors (1 , 0) and (0 , 1) and at each time step, he replaces one of the vectors with their sum. Find the cotangent of the minimum possible angle between the vectors after 8 time steps.
解析
- [ 12 ] Kevin starts with the vectors (1 , 0) and (0 , 1) and at each time step, he replaces one of the vectors with their sum. Find the cotangent of the minimum possible angle between the vectors after 8 time steps. Proposed by: Allen Liu Answer: 987 Say that the vectors Kevin has at some step are ( a, b ) and ( c, d ). Notice that regardless of which vector he replaces with ( a + c, b + d ), the area of the triangle with vertices (0 , 0), ( a, b ), and ( c, d ) is preserved with the new coordinates. We can see this geometrically: the parallelogram with vertices (0 , 0), ( a, b ), ( c, d ), and ( a + c, b + d ) can be cut in half by looking at the triangle formed by any 3 of the vertices, which include the original triangle, and both possible triangles that might arise in the next step. Because the area is preserved, the minimum possible angle then arises when the two vectors, our sides, are as long as possible. This occurs when we alternate which vector is getting replaced for the sum. √ √ 2 2 2 2 Given two vectors ( a, b ) and ( c, d ), with a + b > c + d , we would rather replace ( c, d ) than ( a, b ), and ( a + c, b + d ) has a larger norm than ( a, b ). Then at the n th step, Kevin has the vectors ( F , F ) and ( F , F ), where F = 0 and F = 1. The tangent of the angle between them is the n n − 1 n +1 n 0 1 tangent of the difference of the angles they make with the x-axis, which is just their slope. We can then compute the cotangent as ∣ ∣ ∣ ∣ F n − 1 F n ∣ ∣ 1 + · ∣ ∣ F ( F + F ) ∣ F F ∣ n n +1 n − 1 n n +1 ∣ ∣ = . ∣ ∣ F ∣ ∣ 2 F n − 1 n ∣ ∣ F − F F − n − 1 n +1 n F F n +1 n 2 n +1 We can show (by induction) that F ( F + F ) = F and F − F F = ( − 1) . Thus at n n +1 n − 1 2 n n − 1 n +1 n the 8th step, the cotangent of the angle is F = 987. 16