Alright if there's nothing better than this then the problem is completely disgusting...it's not too hard to see that we want solutions to 5n^2-m^2=+/- (small), which we can solve in the usual way. the positive solutions correspond to the minimal values of a_n while the negative correspond to maximal. for (small)=1, the smallest positive solution is (305,682) but then after some horrible bounding with the aid of a calculator i can get that we have to check (small)=2, 3, 4, 5, 6 for better solutions. the smallest negative solution is (1292, 2889) which is a little better, but still the computation is just terrible.

Is there actually an easy (by easy i mean non-brute force lol) way to solve this without using a machine? I heard that the team leaders of the participating countries attempted to solve this by hand, then resorted to excel and still got different answers.

CatalystOfNostalgia wrote: Alright if there's nothing better than this then the problem is completely disgusting...it's not too hard to see that we want solutions to 5n^2-m^2=+/- (small), which we can solve in the usual way. the positive solutions correspond to the minimal values of a_n while the negative correspond to maximal. for (small)=1, the smallest positive solution is (305,682) but then after some horrible bounding with the aid of a calculator i can get that we have to check (small)=2, 3, 4, 5, 6 for better solutions. the smallest negative solution is (1292, 2889) which is a little better, but still the computation is just terrible. why did I get maximum at $ 1292$ and minimum at $ 1597$? and yes, I took csl824's "advice" and used MS Excel

Well, is it just me or does it seem that Fibonacci numbers have to do with this problem as well. 1597 is the largest fibonacci number less than 2009 so it might have to do with the problem I don't see 1292 though.

1292 is half a Fibonacci number. Here's a few things I noticed (via computer simulations, not proofs). The values of $ n$ that have solutions to $ m^2 - 5n^2 = 4$ are $ F_0$, $ F_2$, $ F_4$, $ F_6$, and so on. Hence the values of $ n$ that have solutions to $ m^2 - 5n^2 = 1$ are half of $ F_0$, $ F_6$, $ F_{12}$, $ F_{18}$, and so on. The values of $ n$ that have solutions to $ m^2 - 5n^2 = -4$ are $ F_1$, $ F_3$, $ F_5$, and so on. Hence the values of $ n$ that have solutions to $ m^2 - 5n^2 = -1$ are half of $ F_3$, $ F_9$, $ F_{15}$, and so on. By modular arguments, $ m^2 - 5n^2$ can never be $ \pm 2$ or $ \pm 3$. If we could prove some of the patterns above, we could probably solve the given problem.

Well, we're looking at $ n\sqrt{5}$ modulo 1. This is the same as $ 2n\left(\frac{1+\sqrt{5}}{2}\right)$ modulo 1, so we're looking at the sequence $ 2\phi,\, 4\phi,\, 6\phi,\ldots, 4018\phi$ modulo 1, where $ \phi = \frac{1+\sqrt{5}}{2}$. We can prove by induction that $ \phi^{k+1} = F_k\phi + F_{k-1}$, where $ F_k$ are the Fibonacci numbers with $ F_0 = F_1 = 1$. So in modulo 1, $ F_k\phi = \phi^{k+1}$. This is nice for us because $ \phi^{k}$ gets closer and closer to an integer as $ k$ increases. We can see this by noting that $ \left( \frac{1+\sqrt{5}}{2} \right)^k + \left( \frac{1-\sqrt{5}}{2} \right)^k$ is an integer for all positive integer $ k$, and $ \left( \frac{1-\sqrt{5}}{2} \right)^k$ tends to 0 as $ k \to \infty$. In particular, when looking at fractional parts, $ \phi^2,\, \phi^4,\, \phi^6,\ldots$ tends to 1 and $ \phi^3,\, \phi^5,\, \phi^7,\ldots$ tends to 0. Finally, every positive integer can be written as the sum of distinct, nonconsecutive Fibonacci numbers. So letting $ 2n = F_{k_1} + F_{k_2} + \cdots + F_{k_r}$, with $ k_1 < k_2 < \cdots < k_r$ and no two consecutive, then $ 2n\phi = \phi^{k_1+1} + \phi^{k_2+1} + \cdots + \phi^{k_r+1} \pmod 1$. I'll outline the rest of this: basically, if we want to maximize the fractional part if $ 2n\phi$, we first want $ k_1$ to be the largest odd number possible (so $ \phi^{k_1+1}$ is close to 1), then $ k_2,\, k_3,\ldots$ to be even numbers (which have to be at least $ k_1+3$ by the non-consecutive stipulation) so that $ \phi^{k_2+1},\, \phi^{k_3+1}, \ldots$ "push" the number even closer to 1. Given the properties of $ \phi$, it's not hard to prove that this "greedy" algorithm always works, and that we would always prefer a larger $ k_1$ over a smaller one. To minimize $ 2n\phi$, just switch "even" and "odd" in the above. For the maximum, the best we can do is $ 2n = F_{17} = 2584$, so $ n=1292$. For the minimum, we can't use $ 2n = F_{16} = 1597$ since 1597 is odd, so we have to use $ 2n = F_{14} + F_{17} = 610+2584 = 3194$, so $ n = 1597$.

I will post two solutions. The first is based on continued fraction approximation The second is based on the theorem of Pell equation Very sorry for written in Chinese,I will explain if not clear

The second solution

our chinese solve our problem

how to use the pell equation to solve it?

Happy new year,I will give some more explanations on the first solution based on some simple facts of continued fraction approximation As $ \sqrt{5}$ can be written as $ <2,4,4,4,...>$ Then we get the approximation-fraction of $ \sqrt{5}$:$ 2,\frac{9}{4},\frac{38}{17},\frac{161}{72},\frac{682}{305},\frac{2889}{1292},\frac{12238} {5473}$,they are known as $ \frac{h_n}{k_n}$ for $ n=1,2,...$ An important property of continued fraction approximation :$ |\sqrt{5}-\frac{h_n}{k_n}|<\frac{1}{k_nk_{n+1}}$ Suppose $ \sqrt{5}=\frac{2889}{1292}-c$where $ 0<c<\frac{1}{1292*5473}$ Thus $ \{1292\sqrt{5}\}>1-1292c>\frac{5472}{5473}$ But for any $ k$,$ k\neq 1292$ and $ 0<k\le 2009$,then $ 2889k\neq0,mod1292$ Hence,$ \{k\sqrt{5}\}=\{\frac{2889}{1292}k-kc\}<\frac{1291}{1292}-kc<\frac{5472}{5473}$ which implies $ a_{1292}$ is the maximal Let's search for the minimal: $ 305+1292=1597$ $ \{1597\sqrt{5}\}=\frac{1}{1292}-1597c$ $ \{305\sqrt{5}\}=\frac{1}{1292}-305c>\{1597\sqrt{5}\}$ For any $ n$ which is not equal to $ 305$ or $ 1597$ we have $ 1292n\neq1,mod 1292$ Hence $ \{n\sqrt{5}\}>\frac{2}{1292}-2009c>a_{1597}$ which implies $ a_{1597}$ is the minimal QED

hxy09 wrote: $ <2,4,4,4,...>$ Could you please explain this notation? I don't quite understand it.

1=2 wrote: hxy09 wrote: $ <2,4,4,4,...>$ Could you please explain this notation? I don't quite understand it. There should be a semicolon $[2;4,4,...]$ and it means \[ \sqrt{5}=2+\frac{1}{4+\frac1{4+\frac 1{4+...}}} \]

Georg-A. wrote: 1=2 wrote: hxy09 wrote: $ <2,4,4,4,...>$ Could you please explain this notation? I don't quite understand it. There should be a semicolon $[2;4,4,...]$ and it means \[ \sqrt{5}=2+\frac{1}{4+\frac1{4+\frac 1{4+...}}} \] Both notations are correct.