Number Theory: Reordering $c_1,\dotsc,c_{10}$ so that $(2k-1)\mid(a_k-b_k)$

Question

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.

Answer 1

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.

Answer 2

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.