0
$\begingroup$

I came across the following problem when looking at a Putnam practice paper. I saw similar problems on here, but I didn't see the exact one. I would like to know if my proof is valid.

Given any $n+2$ integers, show that there exist two of them whose sum, or else whose difference, is divisible by $2n$.

My Attempt:

Call the set of $n+2$ integers $S$. Consider the criteria for which the sum or difference of $2$ elements of $S$ are divisible by $2n$.

Let $a,b \in S$, so that $a = nq_1 +r_1, b = nq_2 + r_2$.

It follows, $a+b = nq_1 +r_1 + nq_2 + r_2$

$= n(q_1 + q_2) + (r_1 + r_2)$

Case $1$: $r_1 + r_2 = n$

$a+b = n(q_1+q_2) + n$ $= n(q_1 + q_2 + 1)$

$2n$ will divide this if and only if $q_1 + q_2 + 1 = 2k$ for some $k\in \mathbb{Z}$. In other words, it will divide it if and only if $q_1 + q_2 = 2k - 1 $, so if $q_1 + q_2$ is odd.

Case 2: $r_1 + r_2 = 0$

So, $a+b = nq_1 + nq_2$ $= n(q_1 + q_2)$ This will be divisible by $2n$ if and only if $q_1 + q_2 = 2k$ for some $k\in \mathbb{Z}$.

Consider the situation when the first $n$ members of $S$ have a unique remainder when divided by $n$. By the pigeonhole principle, the $n+1$ member of $S$ is congruent to one of these first $n$ members $\mod n$ . Since $|S| = n+2$, the $n+2$ element of $S$ must be congruent $\mod n$ to one of the other elements of $S$. If this were $n+1$ then Case 2 above would necessarily be satisfied. This is because we could subtract the terms to get the result, and out of the three terms that are congruent, the sum or difference of one such pair of their quotients must be even.

Assuming that the proposition is false, it follows that no three terms can be congruent $\mod n$ or else by Case 2 the proposition would be satisfied. It also must be the case that there exists a subset of $S$ with $2$ or more members, which is congruent to $z \mod n$ , and there exists another subset of $S$ with at least one member which is congruent to $n-z \mod n$. The reason for this is that there are $\frac{n}{2}$ possible congruences $\mod n$ which do not satisfy this property. At most $2$ elements of $S$ can be allocated for each of these possible congruences. Thus there are $2$ elements remaining, and so the property is satisfied.

Call $U$ the subset which contains the two members which are congruent to $z \mod n$ . The parity of their quotients must be different or else Case 2 would be satisfied. But then Case 1 must be satisfied, because of the element which is congruent to $n-z \mod n$. This element has some parity, and thus the sum of its quotient with the quotient of one of the terms of $U$ must be odd. All possibilities have been exhausted, and thus the theory is proved.

$\endgroup$
3
$\begingroup$

I find your proof difficult to follow. I would write a proof using the pigeonhole principle as follows:

Consider the $2n$ congruence classes modulo $2n$ which we will denote by $\{0,1,\dots,2n-1\}$. Put two congruence classes $p$ and $q$ in the same pigeonhole if $p=2n-q \mod 2n$. Note that there are $n+1$ such pigeionholes because $0$ and $n$ are on their own and the remaining $2n-2$ congruence classes are paired in $n-1$ pairs $(1,2n-1)$, $(2,2n-2), \dots, (n-1,n+1)$ .

There are $n+2$ integers in $S$ and $n+1$ pigeonholes so there must be (at least) two integers $a,b \in S$ in the same pigeonhole. Then either:

$a=b \mod 2n \Rightarrow a-b = 0 \mod 2n$

or

$a=2n-b \mod 2n \Rightarrow a+b=0 \mod 2n$

$\endgroup$
  • $\begingroup$ Looks good to me, thanks! $\endgroup$ – Jack Pfaffinger Jan 25 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.