excellent proof, needs correction in some places.

When adding p_i + A_{k+1} to C, there is a problem because A_{k+1} is already used in p_i. Therefore you need to start with A_{k+2}, but A_{k+2} need not exist (k = n-1 for example). Fortunately k can not be n - 1 (not hard to see). The argument that C has at least n - k + m elements needs more justification. it is not very hard, but can be tricky to get it correct.

Another side comment: We can not assume A_1 < A_2 < ... < A_n. Since A_1 through A_k is chosen by a specific rule we can not assume the order of them. It is always safe to assume A_{k+1} < A_{k+2} < ... < A_n though, and it is enough for your proof.

I really like your proof. Great job.

所有跟帖： 

• 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