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.