-3
$\begingroup$

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$.

$\endgroup$
0

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Should we instead use the pigeon hole principle on the ai s themselves? $\endgroup$
    – Pegi
    Oct 9, 2019 at 8:41
  • $\begingroup$ @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! $\endgroup$ Oct 9, 2019 at 8:46
  • $\begingroup$ @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. $\endgroup$ Oct 9, 2019 at 8:52
  • $\begingroup$ 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. $\endgroup$
    – Pegi
    Oct 9, 2019 at 8:58
  • $\begingroup$ @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). $\endgroup$ Oct 9, 2019 at 9:08
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 17, 2019 at 8:26
0
$\begingroup$

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$.

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

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