8
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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) $\endgroup$
    – Asinomás
    Jul 13, 2015 at 12:50
  • $\begingroup$ 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? $\endgroup$
    – Soham Chowdhury
    Jul 13, 2015 at 12:51
  • 1
    $\begingroup$ 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/… $\endgroup$
    – Asinomás
    Jul 13, 2015 at 12:52
  • $\begingroup$ 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)? $\endgroup$
    – Soham Chowdhury
    Jul 13, 2015 at 12:54

1 Answer 1

Reset to default
5
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Asinomás
    Jul 13, 2015 at 12:44
  • $\begingroup$ Thank you, I didn't know this. $\endgroup$
    – Soham Chowdhury
    Jul 13, 2015 at 12:46
  • 1
    $\begingroup$ nice @SohamChowdhury pretty intuitive $\endgroup$
    – user210387
    Jul 13, 2015 at 12:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .