3
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 13 at 18:23
  • $\begingroup$ 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." $\endgroup$ Mar 13 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.