0
$\begingroup$

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.

  • 0
    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$2011-12-29

1 Answers 1

2

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.