0

I'm struggling solving this problem : I need to prove that given any set of 1011 positive integers, there are 2 numbers such that $x_1 + x_2$ or $x_1 - x_2$ is a multiple of 2020.

basically I understand that I need to show that there are 2 numbers such that $ x_1 + x_2 = 0 \pmod{ 2020} $ or $ x_1 - x_2 = 0\pmod {2020}$ but can't find a way to solve that.

Hope to get a help.

edit - also able to make $x_1+x_1=0 (mod 2020)$ if necessary

MJD
  • 65,394
  • 39
  • 298
  • 580
BOB123
  • 105
  • This is not quite correct as stated: the set ${1010,1011,\dots,2019,2020}$ is a counterexample. But change $1011$ to $1012$ and it's correct. Starting hint: if there exist $x_1,x_2$ whose difference is a multiple of $2020$ then we're done; so you can assume that the set consists of integers from distinct congruence classes modulo $2020$, and try to argue that two of them must add to the zero congruence class. – Greg Martin Jan 10 '21 at 18:59
  • See Given any $n+2$ integers, show that there exist two of them whose sum, or else whose difference, is divisible by $2n$. - $n=1010$ here. – Parcly Taxel Jan 10 '21 at 19:00
  • @GregMartin I have edited the question, you can also consider 2 times a number from the set to show it – BOB123 Jan 10 '21 at 19:02
  • All integers $\bmod 2020$ are $0,\pm 1,\pm 2,\ldots,\pm 1010$; if there are two elements $x_1,x_2$ that are in the same residue class, $x_1-x_2\equiv_{2020} 0$; so consider them to be in different residue classes; again if there are two elements that are $\pm k$ mod 2020, then their sum $\equiv_{2020} 0$; so consider the elements to be either $+k$ or $-m$ mod $2020$ st $k\neq m$; then note that by PHP, one of them must be $1010$ mod $2020$, so take its sum with itself. You can also consider the sum of the element with residue $0$ mod $2020$ with itself (which is in the list, again by PHP). – Prasun Biswas Jan 10 '21 at 19:08

2 Answers2

1

As stated, the problem is flawed; $1011$ numbers is not enough.

For example, if $x,y$ are two distinct elements of the $1011$-element set $ S=\{0,...,1010\}$, then $$ \left\lbrace \begin{align*} &x+y\in\{1,...,2019\}\\[4pt] &|x-y|\in\{1,...,1010\}\\[4pt] \end{align*} \right. $$ hence neither of $x+y,x-y$ is divisible by $2020$.

But $1012$ numbers is enough.

Claim:

If $S$ is a set of integers with $|S|\ge1012$, then there exist two distinct elements of $S$ whose sum or difference is divisible by $2020$.

Proof:

If two distinct elements of $S$ are congruent to each other mod $2020$, then their difference is a multiple of $2020$, and we're done.

Thus assume no two distinct elements of $S$ are congruent to each other mod $2020$.

Then without loss of generality, we can reduce the elements of $S$ mod $2020$, hence we can assume $S\subseteq\{0,...,2019\}$.

Our goal now is to show that there are two distinct elements of $S$ whose sum is $2020$.

Let $A=S{\setminus}\{0,1010\}$ and let $B=\{2020-a{\,\mid\,}a\in A\}$.

Then $A,B$ are subsets of the $2018$-element set $$ \{1,...,1009\}\cup\{1011,...,2019\} $$ hence, since $|A|\ge 1010$ and $|B|=|A|$, it follows by the pigeonhole principle that $A\cap B\ne {\large{\varnothing}}$.

Let $x\in A\cap B$.

Since $x\in B$ we have $x=2020-y\;$for some $y\in A$.

Then $x,y\in A$ and $x+y=2020$.

If $x=y$ then $x+y=2020$ would imply $x=1010$ and $y=1010$, contradiction, since $1010\not\in A$.

Thus $x,y$ are two distinct elements of $S$ whose sum is $2020$.

This completes the proof,

quasi
  • 58,772
0

Hint: There are 2020 possible mod-2020 residues. What if two if the numbers have the same residue? What if no two have the same residue?

MJD
  • 65,394
  • 39
  • 298
  • 580