Given n integers, show that there is a subset whose sum is divisible by n.

Question

I’ve tried this.

Let the integers be $a_1, a_2,...,a_n$.

On dividing any number by $n$, we have $n$ possible remainders which are $0,1,2,...n-1$. Let these $n$ remainders be $n$ pigeonholes.

From the $n$ integers available, we can form $2^n - 1$ possible subsets, assuming each subset must contain at least one element. Each subset is assumed to be a pigeon.

$2^n - 1$ is always greater than or equal to $n$, for all values of $n$ greater than or equal to 1. So, the pigeonhole of the remainder 0, must contain at least one element.

That element is divisible by $n$. Now, when it contains more than one element, the sum of such elements will also be divisible by n, since the individual numbers are divisible by n.

I don’t think this is the right approach though. Any corrections and other methods will be appreciated.

Edit: This approach is completely wrong, as is my previous understanding of the pigeonhole principle. Answers and a link to a similar question are in the comments.

Answer 1

This part is incorrect:

$2^n-1$ is always greater than or equal to $n$, for all values of $n$ greater than or equal to $1$. So, the pigeonhole of the remainder $0$, must contain at least one element.

That's not what the pigeonhole principle states:

In mathematics, the pigeonhole principle states that if $n$ items are put into $m$ containers, with $n > m$, then at least one container must contain more than one item.

Solution:

Lets examine the following subsets: $\{a_1\}, \{a_1, a_2\}, \{a_1, a_2, a_3\}, ..., \{a_1, a_2, a_3\, ... , a_N\}$ and their sums' remainders. If any remainder is $0$ then we've solved the problem. Otherwise we have $N-1$ different remainders $(1, 2, 3, ..., N-1)$ and $N$ different subsets. By the pigeonhole principle we know that at least $2$ of those have the same remainder. Let those $2$ be $\{a_1, a_2, a_3\, ... , a_i\}$ and $\{a_1, a_2, a_3\, ... , a_j\}$ where $i < j$ and their remainder is $r$. We know that the sum of the subset $\{a_1, a_2, a_3\, ... , a_j\}$ is $\{a_{i+1}, , ... , a_j\}$ = $\{a_1, a_2, a_3\, ... , a_j\} - \{a_1, a_2, a_3\, ... , a_i\}$. Therefore the remainder is $r-r=0$ and it is divisible by $N$.