Integers summing up to multiple of $12$.

Question

We were taught pigeonhole principle in the combinatorics class and then given a problem which I could not solve.The problem is as follows:

For any $12$ integers,$a_1,a_2,...,a_{12}$ not necessarily distinct,prove that some of them will sum up to a multiple of $12$.

Our instructor gave us a hint but I do not understand how to use it.He asked us to consider $A_k=a_1+...+a_k$ for $1\leq k\leq 12$ and apply pigeonhole principle.But my question is that the sum could also be $a_1+a_3+a_8+a_9$,not necessarily consecutive.Then I should have considered the sums $a_{\pi(1)}+...+a_{\pi(k)}$,where $\pi$ is a permutation of $\{1,2,...,12\}$. Can someone tell me why and give proper hint so that I can solve the problem.

Answer 1

Consider $A_k$ (mod 12). Is it possible to have two sums $A_i$ and $A_j$, $i\neq j$ such that $A_i\equiv A_j$ (mod 12) without having some set of elements adding to a multiple of 12? You should then use the pigeonhole principle to determine there exists $A_k\equiv 0$ (mod 12).