1

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

  • Hint: suppose you could. Say the three disjoint groups are ${a_i},{b_i}, {c_i}$. Then we deduce that $\sum a_i=100A, \sum b_i=201B, \sum c_i=302C$ for natural numbers $A,B,C$. This means that $5050=100A +201B+302C$. Show that this is not possible. – lulu Oct 03 '19 at 16:34

1 Answers1

0

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$

Ross Millikan
  • 374,822
  • Hmm i realize such a lame problem it is :( thanks for your answer :) –  Oct 03 '19 at 16:47
  • 1
    @Peterjoshua: I don't think it is lame. I left a lot of my thought process in because I thought it might be helpful in the future. It would me more standard to delete the things about mod 2 and mod 3 because they don't wind up being important. With other constants it can be very difficult, similar to the knapsack problem or subset sum, both of which are NP hard – Ross Millikan Oct 03 '19 at 19:32