Contest problems with connections to deeper mathematics

Question

I already posted this on math.stackexchange, but I'm also posting it here because I think that it might get more and better answers here! Hope this is okay.

We all know that problems from, for example, the IMO and the Putnam competition can sometimes have lovely connections to "deeper parts of mathematics". I would want to see such problems here which you like, and, that you would all add the connection it has.

Some examples:

1. Stanislav Smirnov mentions the following from the 27th IMO: "To each vertex of a regular pentagon an integer is assigned in such a way that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers $x,y,z$ respectively, and $y <0$, then the following operation is allowed: the numbers $x,y,z$ are replaced by $x+y$, $-y$, $z+y$, respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps".

   He mentions that a version of this problem is used to prove the Kottwitz-Rapoport conjecture in algebra(!). Further, a version of this has appeared in at least a dozen research papers.

2. (Taken from Gerry Myerson in this thread https://math.stackexchange.com/questions/33109/contest-problems-with-connections-to-deeper-mathematics)

   On the 1971 Putnam, there was a question, show that if $n^c$ is an integer for $n=2,3,4$,… then $c$ is an integer.

   If you try to improve on this by proving that if $2^c$, $3^c$, and $5^c$ are integers then $c$ is an integer, you find that the proof depends on a very deep result called The Six Exponentials Theorem.

   And if you try to improve further by showing that if $2^c$ and $3^c$ are integers then $c$ is an integer, well, that's generally believed to be true, but it hadn't been proved in 1971, and I think it's still unproved.

The most interesting part would be to see solutions to these problems using both elementary methods, and also with the more abstract "deeper methods".

Answer 1

[Found another of these Putnam problems; it seems that the protocol here is to post separate big-list examples separately rather than add them to one big-answer.]

2002 Problem B-6. Let $p$ be a prime number. Prove that the determinant of the matrix $$ \left(\begin{array}{lll}x&y&z\cr x^p &y^p&z^p\cr x^{p^2}&y^{p^2}&z^{p^2}\end{array}\right) $$ is congruent modulo $p$ to a product of polynomials of the form $ax+by+cz$ where $a,b,c$ are integers.

This actually works for the analogous $n\times n$ determinant for each $n$, and also over any finite field $k$ rather than just the prime field $\mathbf{Z} / p \mathbf{Z}$. The case $n=2$ is basically Fermat's little theorem; the general case is Moore's $q$-analogue of the Vandermonde determinant, used by Dickson to find the subring of $k[x_1,\ldots,x_n]$ invariant under all $k$-linear transformations of the $x_i$: they're the polynomials in $n$ fundamental invariants of degrees $q^n - q^i$ ($i=0,1,2,\ldots,n-1$), with the invariant of degree $q^n-1$ being the $q-1$ power of the Moore determinant. Moreover, replacing that power with the Moore determinant itself yields the invariants for $SL_n(k)$ instead of $GL_n(k)$. This century-old theorem has found applications ranging from algebraic topology to Diophantine and algebraic geometry.

References:

E.H.Moore: A two-fold generalization of Fermat's theorem, Bull. AMS 2 #7 (1896), 189-199.

L.E.Dickson: A fundamental system of invariants of the general modular linear group with a solution of the form problem. Trans. AMS 12 (1911), 75-98

Answer 2

The following problem led me to some interesting parts of mathematics.

Putnam 2005 B6: Given a permutation $\pi \in S_n$, let $\text{fix}(\pi)$ be the number of fixed points of $\pi$ and $\text{sgn}(\pi)$ its sign. Show that

$$\sum_{\pi \in S_n} \frac{\text{sgn}(\pi)}{\text{fix}(\pi) + 1} = (-1)^{n+1} \frac{n}{n+1}.$$

First write $F_n(x) = \sum_{\pi \in S_n} \text{sgn}(\pi) x^{\text{fix}(\pi)}$; then the above is precisely $\int_0^1 F_n(x) dx$. On the other hand, one can write down a recurrence for $F_n(x)$ which leads, after a little effort, to the beautiful identity

$$\sum_{n \ge 0} \frac{F_n(x)}{n!} y^n = (1 + y) e^{xy - y}.$$

But the RHS is easy to integrate. (There is an alternate solution which realizes $F_n(x)$ as a certain determinant that you can guess now that I have said the word "determinant.")

Some time after solving this problem I realized that the above identity is a special case of a beautiful result called the exponential formula which I describe in detail in this blog post. The exponential formula, in turn, besides being an important tool in combinatorics in its own right, is related to combinatorial species and symmetric functions, both of which I was better able to appreciate because of my experience with the above problem.

The exponential formula is also an interesting way to think about the relationship between two definitions of the zeta function of a variety over a finite field. I briefly discuss this in these two blog posts.

Answer 3

This year's recent Putnam exam offered at least one more example:

Putnam Exam 2011, Problem B6 Suppose $p$ is an odd prime. Prove that for $n\in \{0,1,2...p-1\}$, at least $\frac{p+1}{2}$ of the numbers $\sum^{p-1}_{k=0} \phantom. k! \phantom. n^{k}$ are not divisble by $p$.

Eric Naslund posted his solution at the end of his Mathoverflow question, asking

Can we improve the bound for the number of zeros? Also is there a deeper connection here with other parts of mathematics motivating this problem?

Indeed there are further connections. In his accepted answer, Felipe Voloch recognized Eric's technique from a 1992 paper of Mit'kin [M] that improves the bound further, and noted a relation with Stepanov's method to bound the number of solutions of equations over finite fields (i.e. his proof [S] of the Weil bounds for hyperelliptic curves); Gerry Myerson's comment added the bibliographic information for the Mit'kin paper (see References below), and reported that the improved bound was $2p^{2/3} + 2$. My first answer to the same MO question gave an alternative solution using properties of the Laguerre orthogonal polynomials, which Kiran Kedlaya simplified to use only the determinants of two Hankel matrices $\det((i+j+n)!)_{i,j=0}^m$ (see the solution posted at the Putnam Directory). Later I found a more direct way to connect such matrices with the problem, related with the theory of Padé approximants; see my second answer, posted earlier today. Both versions of this Hankel-determinant approach generalize to give the same kind of $(p+O(1))/2$ bound for various other polynomials of degree $p-1$, and the bounds are sharp at least for some Čebyšev polynomials.

References:

[M] Mit'kin, D.A.: An estimate for the number of roots of some comparisons by the Stepanov method, Mat. Zametki 51 #6 (1992), 52–58, 157; translation in Math. Notes 51 #5–6 (1992), 565–570

[S] Stepanov, A.: An elementary proof of the Hasse-Weil theorem for hyperelliptic curves, J. Number Theory 4 (1972), 118–143.

Answer 4

Basically all problems in the Miklós Schweitzer Competition (Hungary) are of research level. The contest lasts 10 days with 10 problems, and any literature can be used. All high school and university students can enter and there is no distinction based on age. See here.

Answer 5

A few Putnam problems come to mind. Here's one that I could locate most easily.

1992 problem B-6. Let $\cal M$ be a set of real $n \times n$ matrices such that
i) $I \in \cal M$ (identity matrix);
ii) If $A\in \cal M$ and $B \in \cal M$ then exactly one of $AB$ and $-AB$ is in $\cal M$;
iii) If $A\in \cal M$ and $B\in \cal M$ then either $AB=BA$ or $AB=-BA$;
iv) If $A \in \cal M$ and $A \neq I$ then there is at least one $B \in \cal M$ such that $AB = -BA$.
Prove that $\cal M$ contains at most $n^2$ matrices.

It turns out that equality holds precisely when $\cal M$ is constructed as follows: let $n=2^m$ for some integer $m>0$, let $G$ be the extraspecial group $2_+^{1+2m}$ (generalized dihedral group), and let $\rho$ be the unique irreducible representation of $G$ that is nontrivial on the center. Then $\rho$ has dimension $n$. Let $\cal M$ be the image under $\rho$ of any set of representatives of $G$ modulo its 2-element center that contains the identity.

The solution leads naturally to this construction because it uses ideas from representation theory (if $\cal M$ were larger than $n^2$, there would be a linear relation, etc.).

Answer 6

Here is one I liked:

Putnam 1963 A2: Let $f:\ \mathbb{N}\rightarrow\mathbb{N}$ be a strictly increasing multiplicative function. (that is it satisfies $f(mn)=f(m)f(n)$ for any relatively prime integers $m,n$.) If $f(2)=2$, prove that $f(n)=n$ for $n\in \mathbb{N}$.

The problem is fairly standard, and follows by induction. However, it was motivated by the following generalization due to Erdos:

If $f:\mathbb{N}\rightarrow \mathbb{R}$ is multiplicative and monotonically increasing, then $f(n)=n^\alpha$ for some $\alpha$.

Two nice proofs of this generalization can be found in the American Mathematical Monthly. See this article by Everett Howe or this article by Joel Cohen.

Answer 7

Another Putnam problem, from the same exam that produced Q.Yuan's nice example:

Putnam 2005, Problem B5 Let $P(x_1,\ldots,x_n)$ denote a polynomial with real coefficients in the variables $x_1,\ldots,x_n$, and suppose that [paraphrased] the Laplacian of $P$ vanishes identically and $x_1^2 + \cdots + x_n^2$ divides $P(x_1,\ldots,x_n)$. Show that $P=0$ identically.

That is: Prove that no nonzero harmonic polynomial is divisible by $x_1^2 + \cdots + x_n^2$. Each of the three solutions reported at http://amc.maa.org/a-activities/a7-problems/putnam/-pdf/2005s.pdf (one by Yours Truly) grows naturally out of one approach to the development of the theory of spherical harmonics. See also Signed factors of harmonic polynomials for a generalization that appeared on this forum a few weeks ago.

Answer 8

Sometimes, interesting clusters of questions may arise in this way.

1. The last problem given at the 1991 Mathematical Olympiad asked to construct an infinite bounded sequence of real numbers having $|x_i-x_j|\cdot |i-j|^{1+\epsilon} \geq 1$ for all $i \neq j$. Every professional mathematician will recognize this as a problem about badly approximable numbers; its solution is to take $x_n$ to be a big enough constant times the fractional part of $n\sqrt{2}$ (and this works with $\epsilon = 0$).

2. A similar looking but rather more difficult problem was given at a 239 St. Petersburg Olympiad: disprove the existence, for all $n \gg 0$ sufficiently large, of a set of $n$ points $P_1,\ldots,P_n$ contained by the disk of radius $10\sqrt{n}$ in $\mathbb{R}^2$ and having pairwise distances $d(P_i,P_j) > \sqrt{|i-j|}$. While it surely must have been motivated by the previous problem's appearance at a previous contest, this is a question about the relationship of transfinite diameter to the capacity of potential theory. Just multiplying the inequalities leads to a sharp estimate with both sides having for logarithms $\frac{1}{2}n^2\log{n} + O(n^2)$, and there is no immediate contradiction. If the estimate held with an error term of only $o(n^2)$ then, scaling the picture by $\sqrt{n}$ and letting $n \to \infty$, the points would attain the transfinite diameter of the disk, which would only be possible if they charged the equilibrium measure - the unform measure supported on the boundary circle, - forcing them to determine distances smaller than $o(1/\sqrt{n})$. We only have an estimate with $O(n^2)$, but we may still retain and justify the intuition that the limit measure $\nu$ in the scaled picture, obtained from the Dirac mass of the points after extraction of weak limit in $n \to \infty$, is very far from the two-dimensional Lebesgue measure $\mu$. Since the original disk has positive $\nu$-measure, we may expect to find a nested chain of disks $D$ with an increasing concentration of points $\nu(D)/\mu(D)$. Making this precise will eventually produce a disk $D$ having $\nu(D)/\mu(D)$ arbitrarily large, and again, this would force $D$ to contain points of distance only $o(1/\sqrt{n})$. This means arbitrarily small distances in the unscaled picture, a contradiction.

3. But now, returning to diophantine approximations, one may bring elements from both questions and ask, with the optimal exponent $1/2$, to produce a bounded set of points $P_n$ in the plane having $d(P_i,P_j) \cdot |i-j|^{\frac{1}{2}+\epsilon} \geq 1$. Indeed the sequence $\big( \{n\sqrt{2} \}, \{n\sqrt{3}\} \big)$ has the desired property (where $\sqrt{2}$ and $\sqrt{3}$ can be replaced by generic real numbers, which will be the more direct route to proving the statement). But the proof is considerably harder (the diophantine variant would require some form of Schmidt's theorem), and I do not know if the statement continues to hold with $\epsilon = 0$.

Answer 9

I sympathize with the question, but I fear it is too broad, because if you make a search for "matrix" or "integral" on Art of Problem Solving (the olympiad section) you will get lots and lots of replies. Whole fields of olympiad mathematics are basically taken from advanced mathematics. Zero-sum combinatorics, coding theory, inequalities, more inequalities (with both an analysis and a linear algebra proof), even some functional equations are prone to advanced approaches (not advanced as in requiring 5 years of reading EGA, but advanced as in not taught in school - which is a rather unnatural divide to take anyway). A good way to find such problems is to look out for Russian mathematical contest problems (particularly the olympiad of the St. Petersburg Lyceum 239, if you can get your hands on their problems), since these are very often authored by academics rather than by teachers, educators or full-time olympiad trainers.

Answer 10

I really think Problem 5 from IMO 2006 is a basic beatiful fact about algebraic dynamics: take $p$ any polynomial of degree $n > 1$ with integer coefficients. Iterate it as many times you want to get a polynomial $q$. Then $q$ has at most $n$ integral fixed points. (one can actually classify all the integral cycles...)

Answer 11

Consider a triangulated convex area on a plane with distinct integers in each node of triangulation. Call a triangle positive if the integers in its vertices increase clockwise and negative if they increase counterclockwise. Let the number of nodes in the area's boundary be $N$. Prove that the difference between the number of positive and negative triangles does not exceed $N-2$.

The above is not the exact wording, the XIX Soviet Union Math Olympiad had a specific triangulated hexagonal area, but IMO that made no difference.

One can trace Green's theorem and calculus of residues from this problem.

Answer 12

A problem on Tournament of the towns 2002 Fall/A-level:

A sequence with first two terms equal to $1$ and $24$ respectively, is defined by the following rule: each subsequent term is equal to the smallest positive integer which has not yet occurred in the sequence and is not coprime with the previous term. Prove that all positive integers occur in this sequence.

Let $a_k$ be the k-th element in the sequence. Proving that for all $n$, there exists a $k = k(n)$, such that $a_k = n$ is a fun exercise. Being able to upper bound $k$ is already non-trivial. And proving that $n \sim k(n)$ -which I tried for quite some time, but failed- unless $n$ is a prime or three times a prime is research level. Just a few minutes ago I found out that Hofman and Pilipczuk proved it three years ago; http://www.mimuw.edu.pl/~malcin/ekg.pdf

Answer 13

Nearly all the problems of the International Tournament of Young Mathematicians (team competition for high school students, where problems are published several months in advance) contain open questions related to research problems.

Here is an example:

ITYM 2012, Problem 5. Let $n \geq 3$ be a positive integer, and let $P_n$ be the set of vertices of a regular $n$-gon. A subset $A \subset P_n$ is called stable if the center of gravity of the points in $A$ coincides with the center of the regular $n$-gon.

1. When $n$ is prime, find the number of stable subsets $A \subset P_n$ and describe them.

2. The same problem when $n$ is the product of two distinct prime numbers.

3. The same problem when $n$ is a power of a prime number.

4. Investigate the problem for an arbitrary $n$.

5. Suggest and study additional directions of research.

This problem is related to finding sums of roots of unity that vanish, see e.g. here.

Answer 14

$\textbf{Problem IMO 1986}$. Let $n$ be a natural number. If $k^{2}+k+n$ is a prime number for $0\leq k \leq \lfloor\sqrt{n/3}\rfloor$, then show that $k^{2}+k+n$ is a prime for $0\leq k \leq n-2$.

Theorem: The class number of forms with discriminant $-p$ is $1$ if and only if for each $x$, $0\leq x \leq \lfloor\sqrt{n/3}\rfloor$, $x^{2}+x+n$ is a prime number.

Reference: http://www.ias.ac.in/article/fulltext/reso/004/06/0091-0092

Answer 15

IMO 2007 P6. Let $n$ be a positive integer. Consider the set $S$ of points $(x, y, z)$ with $x, y, z \in \{0, 1, \dots, n\}$ and $x + y + z > 0$, so $S$ is a set of $(n+1)^3 - 1$ points in three-dimensional space. Determine the smallest possible number of planes, the union of which contains $S$ but does not include $(0, 0, 0)$.

It seems to me that this problem is inspired from a paper by Alon and Füredi [ 1 ] which proves a more general result using the polynomial method. That result, in a certain way (hint: duality), generalises the bound on the size of affine blocking sets which was independently proved by Jamison 2, and Brouwer-Schrijver 3. The result has many similarities with the classical Chevalley-Warning theorem, and in fact we can use a common bound on the degree of polynomials vanishing over all points of a grid except one (see [4]) to prove both the Chevalley-Warning theorem and this result.

This work can also been seen as an important step towards the celebrated result of Alon, Combinatorial Nullstellensatz, which has found several applications in combinatorics and number theory. You can see this mathoverflow question which discusses CN and the so-called polynomial method: How to recognise that the polynomial method might work.

Moreover, in Section 6 of this paper, Alon and Füredi note that

Another proof for Theorem 1 can be obtained (in a way that resembles the one in 3), by using Hilbert's Nullstellensatz.

Some recent work on generalisations of this can be found in [4] and [5].

There is a quantitative refinement of this result which talks about the number of points missed by a given number of hyperplanes that do not cover all these points. In [6] and [7] it is shown that this refinement, the so-called Alon-Füredi theorem, and its generalizations imply the following:

• Chevalley-Warning theorems and their restricted variable generalisations.
• Olson's theorem, Erdos-Ginzburg-Ziv theorem, and related results on Davenport's constant.
• Schwartz-Zippel lemma(s) and their generalisations.
• Computation of the minimum Hamming distance of Reed-Muller type affine cartesian codes.
• Old and new results on blocking sets and partial covers in finite geometry.

References

1. Noga Alon and Zoltán Füredi. Covering the cube by affine hyperplanes. European J. Combin., 14(2):79–83, 1993.

2. Robert E. Jamison. Covering finite fields with cosets of subspaces. J. Comb. Theory Ser. A, 22(3):253–266, 1977.

3. A. E. Brouwer and A. Schrijver. The blocking number of an affine space. J. Comb. Theory Ser. A, 24(2):251–253, 1978.

4. Simeon Ball and Oriol Serra. Punctured combinatorial Nullstellensätze. Combinatorica, 29(5):511–522, 2009.

5. Géza Kós and Lajos Rónyai. Alon's nullstellensatz for multisets. Combinatorica 32(5):589–605, 2012.

6. Pete L. Clark, Aden Forrow, John R. Schmitt. Warning's Second Theorem with Resricted Variables. To appear in Combinatorica. arXiv:1404.7793

7. Anurag Bishnoi, Pete L. Clark, Aditya Potukuchi and John R. Schmitt. On zeroes of a polynomial in a finite grid. arXiv:1508.06020

Answer 16

In a Swedish math competition for high-school teachers, where I was on the problem committee, I contributed with this problem (swedish).

For those that are not familiar with Swedish, the problem is essentially about proving a bijection between two sets of combinatorial objects, where the first set essentially is a special case of the combinatorial objects in Knop and Sahis famous formula for the Jack polynomials.

This problem is then about showing that Kostka numbers for rectangular Young diagrams can be computed in two different ways.

The advantage of the second way will be apparent in an upcoming paper, and is related to study of normalized Jack characters.

We use this bijection in a published paper.

Answer 17

IMO 2003-6:

Show that for each prime $p$, there exists a prime $q$ such that $n^p − p$ is not divisible by $q$ for any positive integer $n$.

This obviously looks like something you want to apply the Chebotarev Density Theorem to. The condition that is to be satisfied translates to $f(X) = X^p-p$ not having a linear factor over $\mathbb{F}_q$. Now by Chebotarev, there are infinitely many primes $q$ for which $f$ is actually irreducible modulo $q$, since $\operatorname{Gal}(f)\cong\operatorname{Aff}(\mathbb{F}_p)$ contains permutations without fixed points, hence certainly $f$ does not have a linear factor.

[In fact, the condition is not only implied by the irreducibility of $f$, it is equivalent to it. This is a little exercise in field theory: suppose we have $g \mid f$ with $\deg g < \deg f$. Then we have a finite field extension $k/\mathbb{F}_q$ of degree $d<p$ and an element $x \in k$ satisfying $x^p=p$. If $y$ is the image of $x$ under the field norm $\operatorname{N}_{k/\mathbb{F}_q}$, we obtain the equation $y^p=p^d$ by taking norms. Hence $p^d$ is $p$-divisible in $\mathbb{F}_q^\times$, hence $p$ itself is $p$-divisible in $\mathbb{F}_q^\times$. This shows that $f$ must have a linear factor over $\mathbb{F}_q$.]

Answer 18

Colorado Mathematical Olympiad (1986): Santa Claus and his elves paint the plane with two colors, red and green. Prove that the plane contains two points of the same color, exactly one inch apart.

So what's the minimum number of colors Santa needs to paint the plane so that no two points one inch apart get the same color? That's the chromatic number of the plane $\chi$ and we still don't know its exact value, although we know that $5 \leq \chi \leq 7$.