Let $a_1,a_2,...,a_{11}$ be integers. Prove that there are numbers $b_1,b_2,...,b_{11}$, each $b_i$ equal $-1,0$ or $1$, but not all being $0$, such that the number $$N=a_1b_1+a_2b_2+...+a_{11}b_{11}$$ is divisible by $2015$.
Problem
Source: 2015 Pan-African Mathematics Olympiad Problem 3
Tags: Combinatorial Number Theory, number theory
26.08.2015 17:33
consider all $2^{11}=2048$ subsets of $\{a_1,a_2,\dots ,a_{11}\}$ then by pigeonhole principle sum of two of them for example $A_i,A_j$ are the same modulo $2015$ so difference of sum of elements of $A_i,A_j$ is divisible by $2015$ but this sum is in a form $$N=a_1b_1+a_2b_2+...+a_{11}b_{11}$$ where $b_i\in\{0,1,-1\}$ as desired.
26.08.2015 17:36
Define $S_{b_1,b_2,...,b_{11}}=a_1b_1+a_2b_2+...+a_{11}b_{11}$.For $b_i\in\{0,1\},\forall i\in\{1,2,...,11\}$.We have $2^{11}-1=2047>2015$(we don't have $2^{11}$,because it is not possible that $(b_1,b_2,...,b_{11})=(0,0,...,0)$) such sums.So there are two possibilities\cases: Case 1:From those $2047$ sums there is one sum that is divisible by $2015$.There is nothing else to say,this practically ends our proof. Case 2:From those $2047$ sums there is no sum that is divisible by $2015$.Then,by Pigeon Hole principle,it follows that there are two sequences $(b_1,b_2,...,b_{11})$ and $(c_1,c_2,...,c_{11})$ such that $b_i,c_i\in\{0,1\},\forall i\in\{1,2,...,11\}$ and $S_{b_1,b_2,...,b_{11}}\equiv S_{c_1,c_2,...,c_{11}}\pmod{2015}$.Then $0\equiv S_{b_1,b_2,...,b_{11}}-S_{c_1,c_2,...,c_{11}}=a_1(b_1-c_1)+a_2(b_2-c_2)+...+a_{11}(b_{11}-c_{11})$.Now just note that $b_i - c_i\in\{-1,0,1\},$ $\forall i\in \{1,2,...,11\}$.This ends our proof.