2
$\begingroup$

Let

$$S_X = \sum_{x\in X}x$$

and

$$Z = \{1,2,3,...,106\}$$

Prove that, for all subsets $A$ of $Z$ of cardinality $10$, there exist distinct subsets $B,C$ of $A$ such that $S_B=S_C$. Then prove that there exist disjoint subsets $B$ and $C$ of $A$ with that property.

(I have no idea why the problem decided to choose that set instead of, say, $\mathbf N\backslash\{0\}$, but it makes me think it might start failing for larger numbers.)

$\endgroup$
4
  • $\begingroup$ This is essentially an old IMO problem. And, yes it fails with larger numbers. Consider $A=\{1,2,4,8,16,32,64,128,256,512\}$ to make it obvious. $\endgroup$ – Jyrki Lahtonen Oct 8 '16 at 16:52
  • $\begingroup$ OP, is there anything about my answer that is wrong? Please let me know, and I'll try to correct it. Is there anything about it that is unclear? Please let me know, and I'll gladly explain in greater detail. $\endgroup$ – Evan Aad Oct 8 '16 at 19:11
  • $\begingroup$ What does the title have to do with the question? $\endgroup$ – bof Oct 9 '16 at 6:27
  • $\begingroup$ Title has been corrected! And I will read the answer now. $\endgroup$ – Pedro Carvalho Oct 10 '16 at 13:17
4
$\begingroup$

Suppose we have some set $A$ which contains $10$ different numbers between $1$ and $106$. (The fact that they are different is already implicit in the word set, but perhaps it is worth to point out this fact again.)

We have $2^{10}=1024$ possible subsets of $A$. The maximal possible sum is $106+105+\dots+97=1015$, so we have $1016$ possible sums. So by pigeonhole principle there are two sets $B_1\ne C_1$ which give the same sum. (We may also notice that neither of these two sets can be empty, since that is the only way to get zero sum.)

The above argument does not guarantee that these two sets are disjoint. But this can be easily corrected: We simply remove the common elements, i.e. $B:=B_1\setminus(B_1\cap C_1)$ and $C:=C_1\setminus(B_1\cap C_1)$. This will not change the fact that the sums are equal, since we removed the same elements. (And again, neither of those two sets will be empty.)


It is perhaps also worth mentioning that if we use $107$ instead of $106$ then the maximal possible sum is $1025$. So the same argument does not work. (So if we want to prove the same claim also for this case, we need come up with a bit more complicated argument.)


I will add this link confirming that this is very similar a problem from IMO 1972. (As suggested in a comment by Jyrki Lahtonen. Good memory.) The difference is that only the numbers from $10$ to $99$ (i.e., the two digit numbers) are taken there. A bit of searching shows that both these problems, the one with two-digit numbers (Google, Google Books) and the one with the first 106 numbers (Google, but no relevant hits in Google Books) seem to be rather popular illustrations of pigeonhole principle.

$\endgroup$
2
$\begingroup$

Fix an arbitrary $A \subseteq \{1, 2, \dots, 106\}$ of cardinality $10$.

  1. By the pigeonhole principle, there is at least one $n \in \{0,1,\dots,9\}$ such that the number of subsets $D \subseteq A$ that satisfy $$ \sum_{d \in D} d \equiv n\mod 10 $$ (i.e. the last digit of $\sum_{d \in D} d$ is $n$) is at least $\lceil 2^{10}/10\rceil = 103$. Denote this collection of subsets by $C_n$.

    Observing that $\sum_{a \in A} a \leq 97 + 98 + \cdots + 106 = 1015$, another application of the pigeonhole principle yields some $k \in \{0, 1, \dots, 101\}$ such that at least $|C_n|/102 \geq 103/102$ members $D$ of $C_n$, i.e. at least $2$ such members, are such that $$ \sum_{d \in D} d \in \{10k + 1, 10k + 2, \dots, 10k + 10\}. $$

    Choose two such $D$'s, and call them $B$ and $C$, respectively.

  2. Define $B':=B\setminus C$ and $C' := C\setminus B$.

Q.E.D.


If we try to adjust this proof to accommodate the universe $\{1,2,\dots,\mathbf{107}\}$ (or any larger set) rather than $\{1,2,\dots,106\}$, the logic breaks, since then $$ \sum_{a \in A} a \leq \mathbf{98} + 99 + \cdots + \mathbf{107} = \mathbf{1025}, $$ and the pigeonhole principle yields some $k \in \{0, 1, \dots, \mathbf{102}\}$ such that at least $|C_n|/\mathbf{103}$ members $D$ of $C_n$ are such that $$ \sum_{d\in D} d \in \{10k + 1, 10k + 2, \dots, 10k + 10\}. $$ But as long as our best lower estimate for $|C_n|$ is $103$, our best lower estimate for $|C_n|/103$ has to be $\mathbf{1}$ rather than $2$, which doesn't allow us to draw the desired conclusion in the manner done in the proof.

$\endgroup$
1
  • 1
    $\begingroup$ This answer is as far as I can tell correct but is harder to follow than the other one so I marked the other one correct. $\endgroup$ – Pedro Carvalho Oct 10 '16 at 13:24

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.