Let $A = \{a_1, a_2, . . . , a_n\}$ where $a_1 < a_2 < \cdots < a_n.$ Let $\phi : A \to A$ be one-to-one correspondence, and $a_1 + \phi(a_1) < a_2 + \phi(a_2) < \cdots< a_n + \phi(a_n).$
Show that $\phi(a_i) = a_i$ for $i = 1, 2,\ldots , n.$
We prove this by contradiction and induction. When $n=1$, obviously, $a_1 = \phi(a_1)$. Assume $a_i = \phi(a_i)$ for $1 \leq i \leq n$, we want to prove that $a_{n+1} = \phi(a_{n+1})$, and the inequality is false otherwise. We make $a_{n+1} = \phi(a_k)$ for some $1 \leq k \leq n$.
From here, I had a few ideas such as engaging in a series of "swaps" between different unsatisfactory $ϕ(a_k)$ until a contradiction occurs, or using strong induction, but I don't know how to continue the proof.
Answer
For anything but the simplest problems, induction isn't the kind of thing you go into the proof knowing that you'll use it. You might strongly suspect that induction will happen, but it's hard to know in advance exactly how it will happen. Instead, here is how I thought of a proof, and stumbled onto the fact that it wanted to use induction. The bits in block quotes are a self-contained proof; the surrounding text is explanation.
If we can show that any $a_i = \phi(a_i)$, then we're immediately done by induction.
More generally,
We are done by induction - "strong induction" if you must - if we can find a strict nonempty subset of the $a_i$ such that $\phi$ is bijective on that subset.
Suppose $\phi(a_2) = a_1$, the smallest possible way this theorem could fail. Then $a_1 + a_2 = a_2 + \phi(a_2) > a_1 + \phi(a_1)$, so $a_2 > \phi(a_1)$ and hence $\phi(a_1) = a_1$. So we've found our fixed point of $\phi$ and we're done. (Actually we've also found a contradiction, but that's not important.)
Suppose $\phi(a_3) = a_1$. Then we have $\phi(a_2) + a_2 < \phi(a_3) + a_3 = a_1 + a_3 < a_2 + a_3$, so $\phi(a_2) < a_3$ and hence either $\phi(a_2) = a_2$ (a fixed point!) or $\phi(a_2) = a_1$ (in which case we're done, either by noting the contradiction that $\phi(a_2) = \phi(a_3)$, or by invoking the previous case.)
Looks like induction might work.
Suppose $\phi(a_k) = a_1$. Then we have $\phi(a_{k-1}) + a_{k-1} < \phi(a_k) + a_k = a_1 + a_k < a_{k-1} + a_k$, so $\phi(a_{k-1}) < a_k$.
Similarly:
Suppose $\phi(a_k) = a_1$, with $k \not = n$. Then for all $i$ with $1 \leq i < k$, we have $\phi(a_{k-i}) + a_{k-i} < \phi(a_k) + a_k = a_1 + a_k < a_{k-i} + a_k$, so $\phi(a_{k-i}) < a_k$.
So $\phi$ sends $\{a_1, \dots, a_k\}$ to $\{a_1, \dots, a_k\}$, so we're done by strong induction.
This argument fails only if $k=n$; then the inductive step isn't actually reducing anything. So the only bad case is if $\phi(a_n) = a_1$.
But now we can do the entire argument with reversed inequalities:
Suppose $\phi(a_k) = a_n$, with $k \not = 1$. Then for all $i$ with $k < k+i < n$, we have $\phi(a_{k+i}) + a_{k+i} > \phi(a_k) + a_k = a_n + a_k > a_{k+i} + a_k$, so $\phi(a_{k+i}) > a_k$.
So $\phi$ sends $\{a_k, \dots, a_n \}$ to itself, so we're done by strong induction.
This argument fails only if $k=1$; then the inductive step isn't reducing anything.
So the bad case is that $\phi(a_n) = a_1$ and $\phi(a_1) = a_n$; in that case we're done by strong induction because we've found a subset $\{a_1, a_n\}$ on which $\phi$ is bijective.
This argument fails only if $n=2$; then the inductive step isn't reducing anything. A separate argument is required. [We can use the argument from above:] Suppose $n=2$, and that $\phi(a_2) = a_1$. Then $a_1 + a_2 = a_2 + \phi(a_2) > a_1 + \phi(a_1)$, so $a_2 > \phi(a_1)$ and hence $\phi(a_1) = a_1$. So we've found our fixed point of $\phi$ and we're done. (Actually we've also found a contradiction, but that's not important.)
Summary: it turned out at the end that two base cases were required: $n=1$ and $n=2$. It wasn't obvious where the induction would come in until I did some small examples; then it became clear that strong induction was the way to go. Even then, it wasn't clear exactly which subset was required until noting how the most obvious method failed.
No comments:
Post a Comment