Let S be a set of n integers. Prove that S has a nonempty subset whose sum is divisble by n. Show that this is best possible by exhibiting a set of n-1 integers that has no nonempty subset whose sum is divisible by n.

Printable View

- April 25th 2007, 07:45 PMherocounting principles
Let S be a set of n integers. Prove that S has a nonempty subset whose sum is divisble by n. Show that this is best possible by exhibiting a set of n-1 integers that has no nonempty subset whose sum is divisible by n.

- April 26th 2007, 07:06 AMPlato
Here is a proof.