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

Update: Here are two MathOverflow questions about this subject, where you can find more examples

About these ads
Explore posts in the same categories: Problem solving

Tags: , ,

You can comment below, or link to this permanent URL from your own site.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 37 other followers

%d bloggers like this: