Maths Olympiad Prep

Library / /804 of 860

Geometry Difficulty 5.6 AIME, harder Find the answer

Let C\mathcal{C} be the hyperbola y2x2=1y^{2}-x^{2}=1. Given a point P0P_{0} on the xx-axis, we construct a sequence of points (Pn)\left(P_{n}\right) on the xx-axis in the following manner: let n\ell_{n} be the line with slope 1 passing through PnP_{n}, then Pn+1P_{n+1} is the orthogonal projection of the point of intersection of n\ell_{n} and C\mathcal{C} onto the xx-axis. (If Pn=0P_{n}=0, then the sequence simply terminates.) Let NN be the number of starting positions P0P_{0} on the xx-axis such that P0=P2008P_{0}=P_{2008}. Determine the remainder of NN when divided by 2008.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let Pn=(xn,0)P_{n}=\left(x_{n}, 0\right). Then the n\ell_{n} meet C\mathcal{C} at (xn+1,xn+1xn)\left(x_{n+1}, x_{n+1}-x_{n}\right). Since this point lies on the hyperbola, we have (xn+1xn)2xn+12=1\left(x_{n+1}-x_{n}\right)^{2}-x_{n+1}^{2}=1. Rearranging this equation gives xn+1=xn212xnx_{n+1}=\frac{x_{n}^{2}-1}{2x_{n}} Choose a θ0(0,π)\theta_{0} \in(0, \pi) with cotθ0=x0\cot \theta_{0}=x_{0}, and define θn=2nθ0\theta_{n}=2^{n} \theta_{0}. Using the double-angle formula, we have cotθn+1=cot(2θn)=cot2θn12cotθn\cot \theta_{n+1}=\cot \left(2 \theta_{n}\right)=\frac{\cot^{2} \theta_{n}-1}{2 \cot \theta_{n}} It follows by induction that xn=cotθnx_{n}=\cot \theta_{n}. Then, P0=P2008P_{0}=P_{2008} corresponds to cotθ0=cot(22008θ0)\cot \theta_{0}=\cot \left(2^{2008} \theta_{0}\right) (assuming that P0P_{0} is never at the origin, or equivalently, 2nθ2^{n} \theta is never an integer multiple of π\pi ). So, we need to find the number of θ0(0,π)\theta_{0} \in(0, \pi) with the property that 22008θ0θ0=kπ2^{2008} \theta_{0}-\theta_{0}=k \pi for some integer kk. We have θ0=kπ220081\theta_{0}=\frac{k \pi}{2^{2008}-1}, so kk can be any integer between 1 and 2200822^{2008}-2 inclusive (and note that since the denominator is odd, the sequence never terminates). It follows that the number of starting positions is N=220082N=2^{2008}-2. Finally, we need to compute the remainder when NN is divided by 2008. We have 2008=23×2512008=2^{3} \times 251. Using Fermat's Little Theorem with 251, we get 22008(2250)4256145=5(mod251)2^{2008} \equiv\left(2^{250}\right)^{4} \cdot 256 \equiv 1^{4} \cdot 5=5(\bmod 251). So we have N3(mod251)N \equiv 3(\bmod 251) and N2(mod8)N \equiv-2(\bmod 8). Using Chinese Remainder Theorem, we get N254N \equiv 254 (mod2008)(\bmod 2008).

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.