Problem 6

Mathematical induction

When n=2, obvious.

Assume the statement is true for n.

For n+1, write M as {b1,b2,…b(n)}, where b1
Choose a1, a2, …, a(n) such that a1+a2+…a(n) is not equal to b(n-1). By induction, a solution exists for instance with n steps.

If b(n-1)> a1+a2+…a(n), adding b(n) and a(n+1) won’t cause any conflict.

If b(n-1)< a1+a2+…a(n), if b(n) coincides with a1+a2+…a(k), k<=n, by adjusting a(k), a(k+1), …, a(n+1), the conflict can be avoided.

所有跟帖： 

• 回複：Problem 6 -dynamic- ♂ (217 bytes) () 07/27/2009 postreply 18:18:33

• 回複：回複：Problem 6 -屋漏痕- ♂ (224 bytes) () 07/28/2009 postreply 05:53:51

• 回複：回複：回複：Problem 6 -dynamic- ♂ (195 bytes) () 07/28/2009 postreply 09:14:51

• 回複：回複：回複：回複：Problem 6 -屋漏痕- ♂ (79 bytes) () 07/28/2009 postreply 10:07:10

• still off a littlt bit. -屋漏痕- ♂ (0 bytes) () 07/28/2009 postreply 10:58:07

• This one might be right, but I might be wrong. -屋漏痕- ♂ (1042 bytes) () 07/28/2009 postreply 12:39:19