Prove a more general theorem

Often when you try to prove something, it is easier prove a stronger statement. Many of the examples of this, are statements that are proven by induction. E.g. define the sequence of functions $f_n:\mathbb{R}\to\mathbb{R}$ by $f_1(x)=x^2-1$ and $f_n(x)=f_{n-1}(f_1(x))$ for $n\geq 2$ . Prove that $f_n$ has $n+1$ real roots (inspired by problem 2 day 1 IMC 2004).

When solving this problem, it helps to find a stronger statement, that is true for all n, because that gives you a stronger induction hypothesis, so that you can make the induction step. But sometimes, this is not enough, and you have to “invent” (or should I say discover?) other cases. Let me give an example of this:

Problem 5 day 1 IMC 1999: Suppose that $2n$ points of a $n\times n$ grid are marked. Show that for some $k > 1$ one can select $2k$ distinct marked points, say $a_1,...,a_{2k}$ , such that $a_{2i-1}$ and $a_{2i}$ are in the same row, $a_{2i}$ and $a_{2i+1}$ are in the same column, $\forall i$ , indices taken mod $2k$ .

We have $2n$ point and $n$ rows and $n$ columns, so on average there is $2$ points in each row and in each column. If we knew that there was at least two points in each row and column, the problem would be easy: We could just start at one point, go to a point in the same row, then to a point in the same column, and so on. Continue to do this (you can do that, because there is a least two points in each row and column), until you hit a point you have visited before, and you have a loop (if you both began and ended with a “row-move” or with “column-moves”, you can just “jump over” the first point). But unfortunately, there could be rows or columns with only one point or none points at all. If there is both a row and a column with at most 1 point in each, we can delete this row and column, and we have a problem with a $(n-1)\times (n-1)$ grid and at least $2(n-1)$ marked points. This gives us a hope, that we can prove the statement by induction. But what if all rows contains 2 marked points, but some columns only contain 1? If we delete a column, we would get a $n\times (n-1)$ grid with $2n-1$ marked points, so this suggests that we should try to prove something stronger:

Stronger statement: Let $n+m$ points of a $n\times m$ grid be marked. Now for some $k > 1$ you can select $2k$ distinct marked points, $a_1,...,a_{2k}$ , such that $a_{2i-1}$ and $a_{2i}$ are in the same row, $a_{2i}$ and $a_{2i+1}$ are in the same column, $\forall i$ , indices taken mod $2k$ .

Proof: By induction on n and m. This is true if $n=1$ or if $m=1$ because you can’t choose $m+1$ points in a $1\times m$ grid. If we have two point in every row and column, we can just use the above proof, if not, we delete a row or column with at most one point, and thereby reduces the problem to a smaller one.

Here is another IMC problem, you can try to solve:

Problem 5 day 1 IMC 2004: Let $S$ be a set of $\displaystyle { 2n \choose n } + 1$ real numbers, where $n$ is a positive integer. Prove that there exists a monotone sequence $\{a_i\}_{1\leq i \leq n+2} \subset S$ such that
$|x_{i+1} - x_1 | \geq 2 | x_i - x_1 | ,\text{for all } i=2,3,\ldots, n+1$