50th Mathematical Olympiad in Ukraine, Fourth Round (March 23, 2010)

In order to get at least $502$ points Andriy can place his cards as follows, starting from the left: $2009,2007,2005,\dots ,3,1$. We prove by induction, that he gets $502$ points in this case. Lesya has $1005$ options to place her cards and we present all of them in the following table:

2	4	6	2008	2010
4	6	8	2010	2
6	8	10	2	4
2008	2010	2	2004	2006
2010	2	4	2006	2008

If we compare Andriy's variant with the first row, we obtain: $2,4,\dots ,2010$ and $2009,2007,2005,\dots ,3,1$. Hence, Andriy gets exactly $502$ in the first columns. This is our base. Let us suppose, that in $k$-th row Andriy gets $502$ points.

Let us prove that in $(k+1)$-th row he gets the same number of points. We have that the number of points decreases by $1$ at the beginning of the row and increases by $1$ at the end, comparable to $k$-th row.

We now show that Andriy can not get better result. Lesya knows the position of Andriy's cards, hence, she can choose the row which gives maximum points to her. So we now compute how many points can Andriy get over all $1005$ Lesya's options. Let us place all Andriy's cards under our $1005\times 1005$ table.

We compute total number of points: when we have the number $2009$, Andriy will get $1004$ points, Andriy's number $2007$ will get $1003$ points, and so on, number $1$ will get $0$ points. So our total number is $1004+1003+\dots +1+0=\frac{1005\cdot 1004}{2}=502\cdot 1005$ points.

Hence, Andriy's average number of points over all $1005$ Lesya's options is $502$, which proves our result.