Prove that there is at least one subset of 11 numbers whose sum is divisible by 11.

Question

I was trying to think in terms of pigeonhole but not much luck.

Edit: Any 11 natural numbers.

Answer 1

This is a famous problem, let $a_1,a_2,\dots , a_{11}$ be your numbers.

Consider the subsets:

$\{a_1\}$

$\{a_1,a_2\}$

$\{a_1,a_2,a_3\}$

$\{a_1,a_2,a_3,a_4\}$

$\dots$

$\{a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10},a_{11}\}$

If one of these subsets has sum that is $0\bmod 11$ we are done, otherwise two of these subsets must have the same sum $\bmod 11$. If this is the case, can you use these two sets to find a third set that has a sum of elements divisible by $11$?

Answer 2

Presumably you have a set of eleven distinct integers and wish to show that this set contains a subset whose sum is divisible by eleven regardless what numbers the set actually contained (you really should specify what type of numbers since otherwise it is ambiguous. The set $\{1,\frac{1}{2},\frac{1}{3},\frac{1}{5},\frac{1}{7},\dots\}$ would not have any sum divisible by eleven)

Major Hint:

Let our set of integers be $\{a_1,a_2,a_3,\dots,a_{11}\}$

Define the sequence of numbers $b_n=\sum\limits_{i=1}^n a_i$ and consider the set of numbers formed (that is, we are looking at the set of numbers $\{0,a_1, (a_1+a_2), (a_1+a_2+a_3), (a_1+a_2+a_3+a_4),\dots\}$)

How can you then describe $b_i-b_j$ for $i>j\geq 0$?

If $b_i\equiv b_j\pmod{11}$ with $i>j\geq 0$, what can you say about $b_i-b_j$?

Can you guarantee that there is some pair $i,j$ such that $b_i\equiv b_j\pmod{11}$?