In the grasshopper problem, we discussed yesterday, we can now observe that the number of points = 2008 in the given set M happens to be the maximum possible value that a grasshopper can choose not to land on. For points 1 to 2009, the grasshopper necessarily lands on a point from M.
This follows from the two facts we deduced- First the number of points from M that appear in a permutation of the m+1 th interval is greater than or equal to two times 1005 - m because there are two landing points by which a length d can be realized. And Second there are 2008 points in M must be greater than sum of all the points up to and including the m+1 th interval which by our greedy strategy, is m+1 times the value we computed in first. Consequently 2008 is the maximum possible value for M.
Let us now look at an alternate way to solve the problem - one based on induction.
To do this we recognize that the problem implies a strengthening of itself. Instead of saying the cardinality of M = 2008, we can assume that the intersection set of M and (0,s - a(min)) is less than or equal to n where a(min) is the minimum of the number of points a1, a2, .. .an+1,s.
Now we can prove that the grasshopper never lands on a point from M in the following way:
For n = 0, we don't have to prove anything
For n > 1, by our strategy, an+1 < an < an-1 < .. < a2 < a1
Let us call this set of all the points so far as T(n+1) instead of the all inclusive M. Also T(n+1) = s
Now we make a claim that for some m belonging to 1 to n+1, the grasshopper is able to do at least m jumps without landing on a point of M and in addition, after these m jumps, he has jumped over at least m points of M.
m cannot be n + 1 because the max number of points in M is n.
Therefore we call n' = n - m the remaining number of forbidden points which can be carried out in n' + 1 jumps. we shift the origin each time to execute this. This proves the claim.
This set of points k from 1 to n+1 such that the grasshopper can skip all the points except for the last by arranging his jumps can be called 'smooth'.
We know that k = 1 is smooth and evident. If we can prove that k works for largest k* = n + 1, the proof is complete.
We claim that Tk* belongs to M and the number of points in the intersection of M with (0,Tk*) is greater than or equal to k*
If there were Tk* not belonging to M, any sequence of jumps that verifies the smoothness of k* can be extended by appending ak* + 1, which is a contradiction to the fact that k* is maximum. The second part of the claim above follows from the fact that if the number of such points were less than k* then there exists k* - 1 instead of n, the grasshopper is able to reach Tk*1 - a1 with k* jumps of lengths without al. Therefore k*+1 is also smooth which is a contradiction.
The third claim made now is that it is sufficient to consider the case M intersection (0, Tkmin-1) which should have less than or equal to kmin - 1 points.
This follows from the above claim because we are using the minimum kmin. Although we don't go into the formal proof for claim 3, we can intuitively follow it from the claim 2.
Now with claim 3 and the strengthening mentioned above, we have kmin - 1 instead of n, the grasshopper is able to reach Tkmin + ar - ax by kmin jumps without landing on any point of M. From there he is able to jump to Tkmin + ar and therefore we reach a situation as in claim 1 with m = kmin + 1 which completes the proof.
This follows from the two facts we deduced- First the number of points from M that appear in a permutation of the m+1 th interval is greater than or equal to two times 1005 - m because there are two landing points by which a length d can be realized. And Second there are 2008 points in M must be greater than sum of all the points up to and including the m+1 th interval which by our greedy strategy, is m+1 times the value we computed in first. Consequently 2008 is the maximum possible value for M.
Let us now look at an alternate way to solve the problem - one based on induction.
To do this we recognize that the problem implies a strengthening of itself. Instead of saying the cardinality of M = 2008, we can assume that the intersection set of M and (0,s - a(min)) is less than or equal to n where a(min) is the minimum of the number of points a1, a2, .. .an+1,s.
Now we can prove that the grasshopper never lands on a point from M in the following way:
For n = 0, we don't have to prove anything
For n > 1, by our strategy, an+1 < an < an-1 < .. < a2 < a1
Let us call this set of all the points so far as T(n+1) instead of the all inclusive M. Also T(n+1) = s
Now we make a claim that for some m belonging to 1 to n+1, the grasshopper is able to do at least m jumps without landing on a point of M and in addition, after these m jumps, he has jumped over at least m points of M.
m cannot be n + 1 because the max number of points in M is n.
Therefore we call n' = n - m the remaining number of forbidden points which can be carried out in n' + 1 jumps. we shift the origin each time to execute this. This proves the claim.
This set of points k from 1 to n+1 such that the grasshopper can skip all the points except for the last by arranging his jumps can be called 'smooth'.
We know that k = 1 is smooth and evident. If we can prove that k works for largest k* = n + 1, the proof is complete.
We claim that Tk* belongs to M and the number of points in the intersection of M with (0,Tk*) is greater than or equal to k*
If there were Tk* not belonging to M, any sequence of jumps that verifies the smoothness of k* can be extended by appending ak* + 1, which is a contradiction to the fact that k* is maximum. The second part of the claim above follows from the fact that if the number of such points were less than k* then there exists k* - 1 instead of n, the grasshopper is able to reach Tk*1 - a1 with k* jumps of lengths without al. Therefore k*+1 is also smooth which is a contradiction.
The third claim made now is that it is sufficient to consider the case M intersection (0, Tkmin-1) which should have less than or equal to kmin - 1 points.
This follows from the above claim because we are using the minimum kmin. Although we don't go into the formal proof for claim 3, we can intuitively follow it from the claim 2.
Now with claim 3 and the strengthening mentioned above, we have kmin - 1 instead of n, the grasshopper is able to reach Tkmin + ar - ax by kmin jumps without landing on any point of M. From there he is able to jump to Tkmin + ar and therefore we reach a situation as in claim 1 with m = kmin + 1 which completes the proof.
No comments:
Post a Comment