Problem 6

Based on dynamic's comments, the proof was changed a little bit.

Proof:

By mathematical induction, needless to say about n = 2.
Let's consider case n.

Given a set B = {b_1, ..., b_{n-1}}, whose member is between 0 and A_1 + ... + A_n.

A point in B is called "blocker" if it is a sum of some of A_1, ..., A_n.
This kind of points will block the grasshopper.

"step" of a blocker is the maximum count of numbers whose sum equals to the blocker.

Assume grasshopper can jump to point A_1 + A_2 + ... + A_k (k >= 1) with maximum k
(for convenience, we use A_1, ..., A_k. If not the case, we can alwasy rename them).
if k = n, then done.

So, we can assume k < n.

Without loss of generlity, we assume A_{k+1} < A_{k+2} < ... < A_n

Let's consider a group of points:

A_2, A_3, ..., A_k, A_{k+1}; Let p_1 = A_2 + A_3 + ... + A_k + A_{k+1};
A_1, A_3, ..., A_{k-1}, A_{k+1}; Let p_2 = A_1 + A_3 + .... + A_{k-1} + A_{k+1};
...
A_1, A_2, ..., A_{k_1}, A_{k+1}; Let p_k = A_1 + A_2 + .... + A_{k-1} + A_{k+1};
A_1, A_2, ..., A_{k-1}, A_k; Let p_{k+1} = A_1 + A_2 + ... + A_{k-1} + A_k;

Actually, they are k combination of {A_1, ...., A_k, A_{k+1}}, for example, when k = 3,
the group will be:
A_2, A_3, A_4;
A_1, A_3, A_4;
A_1, A_2, A_4;
A_1, A_2, A_3;

Notice that k is the maximum the grasshopper can go, so the following points are
all blockers off the point p_(k+1):

p_{k+1} + A_{k+1}, ...., p_{k+1} + A_n

which are n-k different blockers.

Obviously, p_1, p_2, ..., p_k, p_{k+1} + A_{k+1}, ...., p_{k+1} + A_n are mutually
distinct and p_1, p_2, ..., p_k all smaller than p_{k+1} + A_i, where i >= k + 1.
The total number of the above points is n. If p_i ( 1 <= i <=k) is not blocker,
then there are at most k - 1 blockers smaller than p_i. By our induction, p_i can
be reachable by the grasshopper.

We define another set C = {p_{k+1} + A_{k+1}, ...., p_{k+1} + A_n}.
This set will be expanded in the following way:

If p_i is not a blocker (where 1 <= i <= k), then we add p_i + A_{k+2}, ..., p_i + A_n to set C.

If there are m such p_i (non-blockers) from p_1, ..., p_k. Then we can easily know
set C will have at least n - k + m different values.
Can all these different values be blockers?
(A) If Yes, we know there are k - m blockers from p_1, ..., p_k. In this case, we will have
n -k + m + k -m = n blcokers, which contracdicts the condition.
(B) If No, so we can go further from one of m non-blockers, which contradicts k is the maximum
assumption.