Newsletter #46 - Solution

Problem

The integers <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo separator="true">,</mo><mn>2</mn><mo separator="true">,</mo><mo>…</mo><mo separator="true">,</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">1, 2, \ldots, n</annotation></semantics></math>1,2,…,n are arranged in any order. In one step you may switch any two neighboring integers. Prove that you can never reach the initial order after an odd number of steps.

Solution - by Subhadeep Pal (India)

Proof:

We will proceed by induction on the number of integers.

Base case:

<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>=</mo><mn>2</mn></mrow><annotation encoding="application/x-tex">n = 2</annotation></semantics></math>n=2. Each step we have to flip the two integers. So to get the initial position we have to flip an even number of times. So one can never reach the initial order after an odd number of steps.

Hypothesis:

For <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>=</mo><mi>m</mi></mrow><annotation encoding="application/x-tex">n = m</annotation></semantics></math>n=m, assume one can never reach the initial order after an odd number of steps.

Induction step:

Let we have <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(m+1)</annotation></semantics></math>(m+1) integers, <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo separator="true">,</mo><mn>2</mn><mo separator="true">,</mo><mo>…</mo><mo separator="true">,</mo><mi>m</mi><mo separator="true">,</mo><mi>m</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">1, 2, \ldots, m, m+1</annotation></semantics></math>1,2,…,m,m+1. Observe <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(m+1)</annotation></semantics></math>(m+1). Say it is at the <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i-th position in an order. If it is not flipped in any step, we are down to the hypothesis step and we are done.

If it is flipped, then to get back the original order, <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(m+1)</annotation></semantics></math>(m+1) has to return to the <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i-th position. So one has to flip it in the reverse direction as many times as it already flipped. So <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(m+1)</annotation></semantics></math>(m+1) doesn't change the parity of steps (because one has to go through an even number of steps to fix <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(m+1)</annotation></semantics></math>(m+1) at the <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i-th position).

Also observe that flipping two integers other than <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(m+1)</annotation></semantics></math>(m+1) then flipping <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(m+1)</annotation></semantics></math>(m+1) is the same as first flipping the others and then flipping <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(m+1)</annotation></semantics></math>(m+1), as in:

<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><msub><mi>j</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>j</mi><mn>2</mn></msub><mo separator="true">,</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo separator="true">,</mo><msub><mi>j</mi><mn>3</mn></msub><mo stretchy="false">)</mo><mo>→</mo><mo stretchy="false">(</mo><msub><mi>j</mi><mn>2</mn></msub><mo separator="true">,</mo><msub><mi>j</mi><mn>1</mn></msub><mo separator="true">,</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo separator="true">,</mo><msub><mi>j</mi><mn>3</mn></msub><mo stretchy="false">)</mo><mo>→</mo><mo stretchy="false">(</mo><msub><mi>j</mi><mn>2</mn></msub><mo separator="true">,</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo separator="true">,</mo><msub><mi>j</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>j</mi><mn>3</mn></msub><mo stretchy="false">)</mo><mo>→</mo><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo separator="true">,</mo><msub><mi>j</mi><mn>2</mn></msub><mo separator="true">,</mo><msub><mi>j</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>j</mi><mn>3</mn></msub><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(j_1, j_2, m+1, j_3) \rightarrow (j_2, j_1, m+1, j_3) \rightarrow (j_2, m+1, j_1, j_3) \rightarrow (m+1, j_2, j_1, j_3)</annotation></semantics></math>(j1,j2,m+1,j3)→(j2,j1,m+1,j3)→(j2,m+1,j1,j3)→(m+1,j2,j1,j3)

is the same as

<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><msub><mi>j</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>j</mi><mn>2</mn></msub><mo separator="true">,</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo separator="true">,</mo><msub><mi>j</mi><mn>3</mn></msub><mo stretchy="false">)</mo><mo>→</mo><mo stretchy="false">(</mo><msub><mi>j</mi><mn>1</mn></msub><mo separator="true">,</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo separator="true">,</mo><msub><mi>j</mi><mn>2</mn></msub><mo separator="true">,</mo><msub><mi>j</mi><mn>3</mn></msub><mo stretchy="false">)</mo><mo>→</mo><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo separator="true">,</mo><msub><mi>j</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>j</mi><mn>2</mn></msub><mo separator="true">,</mo><msub><mi>j</mi><mn>3</mn></msub><mo stretchy="false">)</mo><mo>→</mo><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo separator="true">,</mo><msub><mi>j</mi><mn>2</mn></msub><mo separator="true">,</mo><msub><mi>j</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>j</mi><mn>3</mn></msub><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(j_1, j_2, m+1, j_3) \rightarrow (j_1, m+1, j_2, j_3) \rightarrow (m+1, j_1, j_2, j_3) \rightarrow (m+1, j_2, j_1, j_3)</annotation></semantics></math>(j1,j2,m+1,j3)→(j1,m+1,j2,j3)→(m+1,j1,j2,j3)→(m+1,j2,j1,j3)

Therefore, as for <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math>m integers, one can never reach the initial order after an odd number of steps, the same is true for <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(m+1)</annotation></semantics></math>(m+1) integers and so is for any number of integers.

Thank you!

Thanks to AG (NYC), Felix (Würzburg), Sampad Mohanty (Los Angeles), Subhadeep (India), David J. Webb (Hawaii), Fujun Du (China), and DFJ (China) for submitting solutions to this week's challenge problem.