6
$\begingroup$

I have this homework problem that I'm confused on how to do:

Given any distinct $z_1,\dotsc,z_{10}\in\mathbb{Z}$, show that one can reorder these as $s_5,s_4,\dots,s_1,t_5,\dotsc,t_1$ so that $(2k-1)\mid(s_k-t_k)$; thus $9\mid(s_5-t_5),7\mid(s_4-t_4),$ etc.

I've tried writing $z_i=q_i(2i-1)+r_i$ and comparing the remainders of $s_i$ and $t_i$ modulo $2i-1$, but I haven't been able to solve the problem this way.

$\endgroup$
0
3
$\begingroup$

Let $A=\{z_1,z_2,\ldots,z_{10}\}.$ Since you have ten integers in this set and there are exactly nine remainders modulo $9,$ the pigeonhole principle implies that there are $i_0\neq j_0$ such that $z_{i_0}\equiv z_{j_0}\pmod9.$ Put $s_5=z_{i_0}$ and $t_5=z_{j_0}.$ Now consider the set $A\setminus\{s_5,t_5\}.$ This set contains exactly eight integers. Then as there are exactly seven remainders modulo $7,$ again by the pigeonhole principle there exist $i_1\neq j_1$ such that $z_{i_1}\equiv z_{j_1}\pmod7$ and of course $i_1,j_1\neq i_0,j_0.$ Now put $s_4=z_{i_1}$ and $t_4=z_{j_1}.$ Continue in this way and you'll get the desired result.

$\endgroup$
1
  • 2
    $\begingroup$ Thank you very much, that makes sense. I was trying to solve a general case modulo $2i-1$ and I hadn't thought of just starting with 9, 7, etc. $\endgroup$ Dec 8 '15 at 2:19
2
$\begingroup$

You can use pigeonhole principle.

Start form the last pair: $9 \mid s_5 - t_5$. Consider the remainder of the numbers modulo 9. Since there are 10 numbers, at least two of them (say the $i$-th and the $j$-th) will have the same remainder modulo 9. Pair those up (i.e. set $s_5 = z_i$ and $t_5 = z_j$).

... now we have 8 numbers (all numbers except the $i$-th and the $j$-th), using the pigeonhole principle, two of them must have the same remainder modulo 7. You can do the same, for 5, 3, 1.

$\endgroup$
0

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.