I am interested in applications of somewhat "advanced machinery" (with respect to the usual machinery involved in these cases, which is usually elementary) to olympiad or (high school-level) contest problems in mathematics which yield simple, insight-provoking solutions.

This may be something as simple as basic group theory or linear algebra, for instance. I shall post an example of what I'm looking for as an answer.

Please don't post joke-ish things like the "Fermat's Last Theorem is too weak to prove that $\sqrt 2$ is irrational" thing, please.

Perhaps we could make this CW and have separate answers, each on applications of a specific area of mathematics?

• This isn't really what you want. But sometimes Dirichlet's theorem on arithmetic progressions or Bertrand helps in a lot of problems. (although it is not very common) – Jorge Fernández Hidalgo Jul 13 '15 at 12:50
• I have found Bertrand useful in a few cases, indeed, although I can't remember any particular one. Perhaps you could post an answer with a specific example? – Soham Chowdhury Jul 13 '15 at 12:51
• The probabilistic method is an advanced technique that can give good results in various combinatorics problems. Here is a pdf that uses it to solve olympiad problems which might seem harder without it mit.edu/~evanchen/handouts/ProbabilisticMethod/… – Jorge Fernández Hidalgo Jul 13 '15 at 12:52
• Try posting an answer using something from there. The "pauper's coat" inequality from Engel, perhaps (if this is the same probabilistic method handout I recall reading)? – Soham Chowdhury Jul 13 '15 at 12:54

An example would be Tim Gowers' beautiful proof of the following problem:

Let $n$ be an even integer. How many subsets of the set $\{1,2,\dots,n\}$ can you pick if they all have to have odd size but the intersection of any two of them has to have even size?

using basic linear algebra over finite fields.

Concisely, he considers the characteristic vectors of these subsets and shows that they must be linearly independent over $\Bbb F_2$ for the condition to hold, so the maximum number of such subsets is just $n$.

Takeaway idea: the dot product of the characteristic vectors (over $\Bbb Z$, of course) is equal to the size of the intersection.

• I think this also goes by the name of oddtown theorem. Here is a pdf containing other examples like this,math.mit.edu/~fox/MAT307-lecture15.pdf. – Jorge Fernández Hidalgo Jul 13 '15 at 12:44
• Thank you, I didn't know this. – Soham Chowdhury Jul 13 '15 at 12:46
• nice @SohamChowdhury pretty intuitive – user210387 Jul 13 '15 at 12:51