Here is a question.I am quoting it:

Question by user Nahum Litvin Let A be a set of 100 natural numbers. prove that there is a set B B⊆A such that the sum of B's elements can be divided by 100 I am stuck for a few days now. Please help!

Making an attempt to provide proof, this was my reply:

Total number of possible subsets of $A$ excluding the null set is $2^{100}-1$ which is clearly greater than $100$. Now, if we consider any $101$ subsets of $A$, the sum of the elements of any such subset $S$ is congruent to $0,1,2,3,...,$or $99$ modulo $100$. If there is one such set whose sum of elements is indeed divisible by $100$, we are done. Else, by the Pigeon Hole Principle, $\sigma(S_1) \equiv \sigma(S_2)\equiv j$ mod $100$ for some two sets $S_1$, $S_2$, where $\sigma(X)$ is the sum of the elements of a set $X$ and $1\leq j \leq 99$. So, we have $\sigma (S_1)-\sigma(S_2)\equiv 0$ mod 100. If the cardinality of $S_1$ is greater than that of $S_2$,we simple have the set $S_1-S_2$ satisfying the given condition.

As Henry rightly pointed out, in its current form it is incorrect as it does not consider the case when $S_2$ is not a subset of $S_1$.

My question is : Proceeding on my track, can I construct a set $P$ from $S_1$ and $S_2$ with the conditions I have mentioned so that the sum of elements is divisible by 100?If not, why do you think such a construction fails?

Edit: To be clear,I was asking if we can construct a set P from S_1 and S_2 so that S_2 is not a subset of S_1 with the condition $\sigma(S_1) \equiv \sigma(S_2)\equiv j$ mod 100 Thank you very much.

  • $\begingroup$ As you say, this doesn't work unless $S_1$ is a subset of $S_2$ or vice versa. Here's a hint: restrict your choice of possible subsets so that no matter which $S_1$ and $S_2$ you pick from them, one is always a subset of the other. $\endgroup$ – Lopsy Dec 29 '11 at 18:15
  • $\begingroup$ I was asking if we can construct a set P from S_1 and S_2 so that S_2 is not a subset of S_1 with the condition $\sigma(S_1) \equiv \sigma(S_2)\equiv j$ $\endgroup$ – Eisen Dec 29 '11 at 18:18

Consider $A=\{1,2,3,4,5,6,7\}$. It has $2^7=128$ subsets, so there must be two with the same sum $\pmod {100}$, which there are. One pair would be $\{1,4\}$ and $\{2,3\}$. But there is no subset which sums to $0 \pmod {100}$. The critical difference in the other answer was that each subset was a subset of all that came after, so you could take the set difference to get a subset that summed to $0 \pmod {100}$. Your route gets us that from any set of $7$ elements you can find two subsets with the same sum $\pmod {100}$, or that you can find an expression of the sort $a_1 \pm a_2 \pm \ldots a_n=0 \pmod {100}$ from any set of $7$ elements and in this example it would be $1-2-3+4=0$ The original question only allowed plus signs.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.