Let $A$ be a set of $100$ natural numbers. prove that there is a set $B$ $$B\subseteq A$$ such that the sum of $B$'s elements can be divided by $100$

I am stuck for a few days now. Please help!

  • 2
    $\begingroup$ So have you tried anything? $\endgroup$ – smanoos Dec 29 '11 at 17:19
  • $\begingroup$ Interesting problem. I wonder, does the conclusion still hold if you allow repeated elements in $A$? I don't think the two solutions posted so far work in this case. $\endgroup$ – Dimitrije Kostic Dec 29 '11 at 17:41
  • 1
    $\begingroup$ @DimitrijeKostic: it works just the same. In fact, we don't care about the actual numbers, just the value $\pmod {100}$, so $1$ and $101$ are equivalent. yoyo's proof goes through just fine even if there are matches. $\endgroup$ – Ross Millikan Dec 29 '11 at 17:43
  • $\begingroup$ @RossMillikan Yeah, I realized that a few minutes after I left my comment. :-) $\endgroup$ – Dimitrije Kostic Jan 2 '12 at 21:22

take a chain of subsets of $A$, $\emptyset\subset\{a_1\}\subset\{a_1,a_2\}\subset...\subset A$. this chain has 101 elements. now sort them by their sum modulo 100. two of the sets in the chain must be equal modulo 100. hence there is $n>m$ with $ (0+a_1+...+a_n)-(0+a_1+...+a_m) $ divisible by 100, so that $a_{m+1}+...+a_n$ is divisible by 100.

here is a more detailed explanation:

let $A_0=\emptyset, A_i=\{a_1,a_2,...,a_i\}$ where $A=\{a_1,...,a_{100}\}$. let $s_0=0, s_i=\sum_{k=1}^ia_k$. we have 101 numbers $s_0,...,s_{100}$ which we will sort into 100 groups $G_0,...,G_{99}$. we put $s_i$ in group $G_r$ if the remainder after dividing $s_i$ by $100$ is equal to $r$. since there are 101 numbers $s_i$ and only $100$ groups, one of the groups $G_r$ will have at least two numbers $s_n,s_m$ in it (without loss of generality, $n>m$ since one of them will have bigger subscript). if $s_n=100k+r$ and $s_m=100l+r$ then $s_n-s_m=100(k-l)$ is divisible by $100$. by construction, the number $s_n-s_m$ is precisely the sum $a_{m+1}+...+a_n$ corresponding to the subset $A_n\backslash A_m$ of $A$ (note that $A_n$ is not empty because $n>m\geq0$ and that $A_m$ is a proper subset of $A_n$ so that the difference $A_n\backslash A_m$ is nonempty).

  • $\begingroup$ two of the sets in the chain must be equal modulo 100 ? why is that? $\endgroup$ – Nahum Dec 29 '11 at 18:05
  • 3
    $\begingroup$ @NahumLitvin 101 pigeons, 100 holes $\endgroup$ – yoyo Dec 29 '11 at 18:11
  • $\begingroup$ but how do you use it? i know that 101 pigeons, 100 holes. so 1 hole got 2 inside but why is it the modulo 100 hole? $\endgroup$ – Nahum Dec 29 '11 at 18:26
  • $\begingroup$ @NahumLitvin: It is not. The difference of the two pigeons in the same hole is the solution. For a multiplicative variant of very similar thinking see this problem. $\endgroup$ – Jyrki Lahtonen Dec 29 '11 at 19:08

Use induction with the statement being "a subset for each number smaller or equal than n', then look at the numbers mod 100. Add the new number to an appropriate subset mod 100 (this is where the pigeonhole principle comes in). For induction root look at cases of even and odd numbers (to do 1 and 2).


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.