A grasshopper jumps along the real axis. He starts at point 0 and makes 2009
jumps to the right with lengths 1; 2; : : : ; 2009 in an arbitrary order. Let M be a set of 2008
positive integers less than 1005 * 2009. Prove that the grasshopper can arrange his jumps in
such a way that he never lands on a point from M.

Let us make a set of landing points for the grasshopper.
We look into the case when M does not contain numbers divisible by 2009.
We fix the numbers 2009k as landing points k = 1, 2, .... 1005
Consider the open interval I-k = (2009(k-1), 2009k)
We show that we can choose exactly one point outside of M as a landing point in 1004 of these intervals such that all lengths from 1 to 2009 are realized.
By excluding one interval from the 1005, we say that 2009 will indeed appear.
And each interval is length 2009 so a number d picked form 1 to 1004 is sufficient to guarantee that 2009-d  will also be picked. therefore 1004 is enough.
We pick these points in a greedy way.
Let n-k be the number of elements that belong to the interval Ik. We order these numbers in a decreasing way, so let p1, p2 ...p1005 be a permutation of 1,2, ...1005 such that the first is greater than the second which in turn is greater than the third and so on.
We leave the first interval out saying that it doesn't have a landing point now assuming that the other intervals have a landing point with d2, ... , dm where m = 1, .. 1004.
We show that there is a point in d2 .. dm that can be implemented with a new landing point in the m+1 th interval.
We do this by assuming the contrary.There are 1004-(m-1) other lengths obstructed by the np-m+1 points of M in the m+1th interval.

Each length d can be realized by two landing points namely the previous hop and the current hop.
This means that the number of elements of M that belong to the m+1 interval are greater than twice the number of points remaining to be chosen from the 1005 and written as twice * (1005-m)

Adding up the number of elements for each of the 1005 intervals equals the sum of 2008
so we know that 2008 is greater the number of points belonging to the interval from all of the m+1 intervals. and since each of these is greater than those chosen for the m+1th interval
we say that 2008 has to be greater than m+1 times the points chosen for the m+1th interval

Together the above two facts show that 2008 is greater than m+1 times twice * (1005-m)
This is minimum only when m = 1004 but the resulting value with m = 1004 is greater than 2008 - a contradiction.
Consequently there is a point in d2 .. dm that can be iplementd with a new landing point in the m+1th interval.

We now look at the other case when M does contain a number divisible by 2009. In this case we can say there is a number for which we can take multiples but it leaves a remainder less than 2009
Also we know from above that we have a landing point between 1005 and 2008.
So there are only two ranges we need to satisfy that they have a landing point
while everything else already has been shown to have it. One of this range is r shy of the multiple of 2009 and the other is 2009-r excess of the next multiple of2009. Note that both of them form a multiple of 2009. Hence we can use a similar logic as above for these ranges as well.
Thus we cover all the cases to show the grasshopper can arrange his jumps such that he can skip all point  from M