# Prove that there are 2 numbers whose difference is divisible by 2n. [closed]

I have been trying to solve this problem using pigeon hole principle but I think it has some subtleties I might not be paying attention to : We have the natural numbers $$1,2,...,2n$$ and we have written them arbitrarily in $$2n$$ numbered places. If we add each number to the number of its place, prove that among these $$2n$$ numbers there are $$2$$ numbers whose difference is divisible by $$2n$$.

Let me see if I understand your formulation correctly.

You consider the natural numbers $$1,2, \dots , 2n$$ for some $$n\in \mathbb{N}$$ but you order them randomly. So basically, to each natural number in this list, you assign a different natural number from the same list. That is, you have a bijection $$f\colon \left\{1,2,\dots ,2n\right\}\to \left\{1,2,\dots ,2n\right\}$$. Here $$f(k)$$ is the spot number $$k$$ belongs to.

Now you consider the numbers $$a_1=1+f(1), a_2=2+f(2), \dots , a_{2n}=2n+f(2n)$$ and you want so show that $$2n\mid (a_i-a_j)$$ for some $$i$$ and $$j$$.

Consider the function $$g\colon \left\{1,2,\dots ,2n\right\}\to \mathbb{Z}_n: i \mapsto a_i \mod 2n$$. It suffices to show that $$g$$ is not injective. Indeed, if $$g$$ is not injective, there exists an $$i$$ and $$j$$ such that $$g(i)=g(j)$$ and thus $$a_i-a_j=0\mod 2n$$ as required.

Assume by contradiction that $$g$$ is injective, then all $$a_i$$'s have different values modulo $$2n$$. Then $$\sum_{i=1}^{2n}a_i\mod 2n=\frac{2n(2n+1)}{2}\mod 2n=n\mod 2n.$$ On the other hand, it is clear that $$\sum_{i=1}^{2n}a_i=\sum_{i=1}^{2n}i+f(i)=2n(2n+1)$$ and thus $$\sum_{i=1}^n a_i\mod 2n=0\mod 2n$$. This concludes the proof.

• Should we instead use the pigeon hole principle on the ai s themselves?
– Pegi
Oct 9, 2019 at 8:41
• @Pegi: That doesn't solve the problem, there are exactly $2n$ numbers $a_i$, hence they could all have different outcomes modulo $2n$. Honestly, I posted this method to quickly as an answer, I think we can get there using the generalized pigeonhole principle on the differences and thinking a bit more but it's not entirely straightforward! Oct 9, 2019 at 8:46
• @Pegi: If you can find a reason why the $a_i$'s can only have $2n-1$ outcomes modulo $2n$ you solved the problem. I wrote down a couple of examples, and this seems to be the case. Oct 9, 2019 at 8:52
• But if 2 of the differences have the same quantity modulo 2 they might be 4 different numbers with the same remainder and that does not give the proof.
– Pegi
Oct 9, 2019 at 8:58
• @Pegi : You are absolutely right I thought perhaps the generalized pigeonhole principle could help here, but it's not. I think the $a_i$'s can only have $2n-1$ outcomes modulo $2n$ and that would solve the problem using the pigeonhole principle on the $a_i$'s as you suggested. It's clear we need to exploit that $f$ is a bijection to do this, but I don't know how yet. Again, I apologize for answering a bit to quickly, it's less trivial than I thought (unless I'm missing something easy here). Oct 9, 2019 at 9:08

Let’s assume each number we randomly put in each cell is $$a_i$$ if the difference of none of them is divisible by $$2n$$ then they all have different values modulo $$2n$$.In that case , the sum of them is $$0 + 1 + ... + 2n-1 = n*(2n-1)$$ on the other hand we know that $$\sigma(a_i )= 2*\sigma(i) = 2n * (2n + 1)$$ and this is a contradiction so there are at least 2 numbers with the same value modulo 2n and that means their difference is divisible by 2n.

• Indeed, that was the easy thing we were missing, I've included it in my answer as well, albeit formulated differently. I don't think your question deserves the amount of downvotes it did. Having said that, I do think the formulation and style can be improved. Oct 17, 2019 at 8:26

We are considering

$$N_k=\sum_1^k k=\frac{k(k+1)}2, \quad k=1,\dots,2n$$

and we need to prove that $$k_2\ge k_1$$ exist such that

$$\frac{k_2(k_2+1)}2-\frac{k_1(k_1+1)}2=2n \iff k_2(k_2+1)-k_1(k_1+1)=4n$$

$$k_2^2+k_2-k_1^2-k_1=4n$$

$$(k_2-k_1)(k_2+k_1+1)=4n$$

then it suffices to take

• $$k_2=2n$$
• $$k_1=2n-a$$

$$a(4n-a+1)=4n \implies4na-a^2+a=4n$$

which has solution for $$a=1$$.

• I don't understand this answer. Why are you considering the numbers $N_k$? Oct 9, 2019 at 9:49