The solution to problem 6 and thanks to dynamic

Thank dynamic for pointing out the shortfall of my previous thoughts to the problem 6. I have a complete proof
to the problem 6. Should you have any questions, let me know

------------------

Proof:

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

Without loss of generality, we assume A_1 < A_2 < ... < A_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.

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+1}, ..., 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?

(1) 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.
(2) If No, so we can go further from one of m non-blockers, which contradicts k is the maximum
assumption.

所有跟帖： 

• excellent proof, needs correction in some places. -dynamic- ♂ (673 bytes) () 07/28/2009 postreply 23:44:13

• Thanks -botong- ♂ (58 bytes) () 07/29/2009 postreply 08:15:04

• Here is a new version -botong- ♂ (2693 bytes) () 07/29/2009 postreply 08:34:38

• Great! -乱弹- ♂ (0 bytes) () 07/30/2009 postreply 17:49:50