2
$\begingroup$

My question goes like this.

Write the numbers $1,\ 2,\ 3,\dots,\ 2n$ on a paper, where $n$ is an odd number. Name this list as $l_{2n}$ where $2n$ represents the number of terms in the list. Now choose any two numbers $j$ and $k$ at random from this list. Calculate $\vert j - k\vert$, then remove the numbers $j$ and $k$ from the list and add the number $\vert j-k\vert$ in the list. So we get a new list $l_{2n-1}$ with $2n-1$ terms.

For example, if $n=7$, we write the numbers $$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,\ 10,\ 11,\ 12,\ 13,\ 14$$ Now, we choose two numbers at random, say $6$ and $11$. Now, $\vert6-11\vert=5$. So we remove $6$ and $11$ from the list and add $5$ in it (despite the fact that there is already a $5$). So the new list (with one less number of terms than the previous list) is $$1,\ 2,\ 3,\ 4,\ 5,\ 7,\ 8,\ 9,\ 10,\ 12,\ 13,\ 14,\ 5$$

Now the problem is to prove that given an odd number $n$ and the starting list $1,\ 2,\ 3,\dots,\ 2n$, if we go on doing the above procedure iteratively on each new list, we always reach an odd number i.e. $l_1$ contains just one term which is always an odd number.

Now by studying proof theory, I have concluded that this theorem can be proved by contradiction. I can suppose that the value of $l_1$ is an even number and then backtrack to reach a contradiction to the hypothesis. But I don't know how to do it. Should I keep track of the parities of each number removed or added to the list (which is a difficult thing) or should I just stick to the parity of the end result (which I know is odd but can't prove it). Please help me to do the proof.

$\endgroup$
  • $\begingroup$ Here is a hint for a different approach: note that you are only interested in the parity of the final answer. $\endgroup$ – Mark Bennet Aug 28 '17 at 13:52
  • $\begingroup$ Think about the $3$ possible combinations of odds and evens that you can choose for $j$ and $k$. $\endgroup$ – Donald Splutterwit Aug 28 '17 at 13:56
  • $\begingroup$ @DonaldSplutterwit Sorry but I can't get your point. Which 3 combinations are you talking about? $\endgroup$ – Faiq Irfan Aug 28 '17 at 14:26
  • 2
    $\begingroup$ $j$ and $k$ are both odd, one is odd and one is even, both are even. Now consider the effect each case will have on the list. $\endgroup$ – Donald Splutterwit Aug 28 '17 at 14:33
  • $\begingroup$ By considering cases like @DonaldSplutterwit suggested, can you say something about the "number of odd numbers" in your list? Is there something special about the number of odds remaining? $\endgroup$ – mm8511 Sep 6 '17 at 14:53

Your Answer

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

Browse other questions tagged or ask your own question.