# Invariance Textbook Problem: Clarification Needed

I am currently reading Michael Soltys' Analysis of Algorithms (2nd Edition), and Problem 1.13 of the subsection titled Invariance reads:

Let $$n$$ be an odd number, and suppose that we have the set $$\{1,2,\dots,2n\}$$. We pick any two numbers $$a$$, $$b$$ in the set, delete them from the set, and replace them with $$|{a-b}|$$. Continue repeating this until just one number remains in the set; show that this remaining number must be odd.

However, I picked $$n=3$$ and performed the following.

• I start with $$\{1,2,3,4,5,6\}$$.
• I pick $$1$$ and $$2$$; I end up with $$(\{1,2,3,4,5,6\}-\{1,2\})\cup\{|{1-2}|\}=\{1,3,4,5,6\}$$.
• I pick $$1$$ and $$6$$; I end up with $$\{3,4,5\}$$.
• I pick $$3$$ and $$5$$; I end up with $$\{2,4\}$$.
• And finally, I pick $$2$$ and $$4$$; I end up with $$\{2\}$$.

Clearly, $$2$$ is not an odd number.

Is there something I misunderstood in my attempt?

I think they don't mean to consider a "set" of numbers (where $$\{3, 4, 5, 5\} = \{3, 4, 5\}$$) but rather a list or multiset of numbers.
In that case the result is true: initially the sum of the entries of the list is $$n(2n+1)$$ which is odd, and at each step the parity of the sum of the entries is preserved. When you choose $$a, b$$, the sum changes from its old value $$s$$ to $$s-a-b+ |b-a|$$. If $$a, b$$ are even then $$-a-b+|b-a|$$ is clearly even, if they are both odd then $$-a-b$$ is even as is $$|b-a|$$, and if one is even and one odd then $$-a-b$$ is odd and $$|b-a|$$ is odd so $$-a-b+|b-a|$$ is odd+odd=even.
• Thank you for your clarification. That makes sense. I personally used a different invariant, reading: "After $n>0$ operations, the number of odd numbers in the set/list is odd." Indeed, the invariant holds when $n=0$. After one operation, there are three cases: (1) Both $a,b$ are even. In that case, the list would 'lose' one even number and no odd number. (2) Both $a, b$ are odd. In that case, the list would 'lose' two odd numbers and gain an even one. However, subtracting $2$ from an even natural number keeps it odd. (3) $a,b$ are of different parity. Then, we only 'lose' an even number. Mar 13 at 18:23
• Two corrections to my comment above. (1) I meant, $n\geq 0$, not $n>0$. (2) In the second case, I meant, "subtracting $2$ from an odd natural number keeps it odd." Mar 13 at 20:51