Originally Posted by

**oleholeh** Well, I figured it out even before I checked for responses here (it happens a lot ;p). Anyway, assume that T does not have a subset whose sum is 0 mod m. Then take a T of size one (which does not equal 0 mod m of course) For every additional element you add to this T, the sum now becomes a mod m that has not appeared before. Why? Otherwise for T_1 and T_2 with same sum mod m, you take the subset of elements that are on T_2 but not T_1, and that new subset = 0 mod m. Now, when T has reached the size m, the collection of T's must contain m unique possible values of mod m, meaning all including 0. Contradiction.