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 by and for . Prove that has 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 points of a grid are marked. Show that for some one can select distinct marked points, say , such that and are in the same row, and are in the same column, , indices taken mod .
We have point and rows and columns, so on average there is 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 grid and at least 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 grid with marked points, so this suggests that we should try to prove something stronger:
Stronger statement: Let points of a grid be marked. Now for some you can select distinct marked points, , such that and are in the same row, and are in the same column, , indices taken mod .
Proof: By induction on n and m. This is true if or if because you can’t choose points in a 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 be a set of real numbers, where is a positive integer. Prove that there exists a monotone sequence such that