Consider the set $\{ 1,2,3,... , 100 \}$. Is it possible to split this set into three disjoint subsets (with union this set) such that the sum of the elements in the first set is divisible by $100$, second by $201$, third by $302$?
I really do not understand how do i attack this problem, i tried to first pick numbers which sum to 100, then for other cases, if one element "a" gets added with a mod 100 = k then i have to add another bunch of number m,n,...,z with m+n+...+z mod 100 = -k but i am pretty sure this is a lame idea, please help me
Note that the sum of all the numbers in your set is $5050$ (see the anecdote about the young Gauss in school). If the sum of the first set is $100a$, the sum of the second is $201b$, and the sum of the third is $302c$ we need to find $a,b,c$ so that $$100a+201b+302c=5050$$ This does not guarantee success because we might not be able to make the partition we want, but it is required. Since we have so many numbers in the set we are likely to be able to get there. We note that $a \le 50, b \le 25, c\le 16$. A good way to set limits on $a,b,c$ is to take the equation modulo various things. $\bmod 2$ tells us that $b$ is even, $\bmod 3$ tells us that $a +2c \equiv 1 \pmod 3$. $\bmod 100$ tells us that $b+2c=50$. Now we find out that $b \equiv 2 \pmod 4$. At this point I would just try all the possible $b$'s. I find that all the $a$s are negative, so there is no solution.
We can make this explicit. We found $b+2c=50$. The minimum the sum of $201b+302c$ can be is $25\cdot 302 =7550 \gt 5050$