# Contest problems with connections to deeper mathematics

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 http://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".

-
I think you have some confusing typos- I suppose you mean that if $2^c$ and $3^c$ and $5^c$ are integers, etc, where you write $2c$,$3c$ and $5c$. –  Geoff Robinson Jul 7 '11 at 18:38
Right, changed it now! Thank you. –  Dedalus Jul 7 '11 at 19:09
Since this asks for various problems, I think it is a classical case for Community Wiki mode. –  quid Jul 7 '11 at 19:38
I could solve the $n^c$ problem quickly (for $k<c<k+1$ the $k$-th difference sequence takes values in $(0,1)$ for large $n$). Can you provide some references for the $2^c$, $3^c$, $5^c$ problem and its variants? Thanks in advance. –  GH from MO Jul 7 '11 at 21:17
@GH, I think if you search for "Six Exponentials Theorem" and/or "Four Exponentials Conjecture", either webwide or at Math Reviews, you'll probably come across the statements, and then I think it's not hard to see the application to $2^c,3^c,(5^c)$. A proof of Six Exponentials was given by Lang, late 1960s if memory serves. –  Gerry Myerson Jul 7 '11 at 23:38

[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

-
It's also an example of the "field of one element" heuristic: the $q=1$ case should recover Vandermonde, with the symmetric group $S_n$ and the alternating group $A_n$ playing the roles of $GL_n(q)$ and $SL_n(q)$ respectively; and the elementary symmetric functions, which generate the invariants of $S_n$, can be constructed as quotients of generalized Vandermonde determinants (that is, as Schur functions), as Dickson's invariants are $q$-Schur functions. [The analogy $A_n$ invariants doesn't work quite so nicely because taking the $q-1$ power of a Vandermonde det. isn't helpful when $q=1$...] –  Noam D. Elkies Jul 7 '11 at 20:35
That's really amazing. Thanks a lot for posting it! –  Dedalus Jul 8 '11 at 18:32
It also works with complex conjugation. In general any operator $O$ on a field satisfying $O(ab)=f(a)O(b)+g(a)b$, for instance all derivations and all field automorphisms, has a determinant of this form. –  Will Sawin Dec 21 '11 at 22:43
@Noam D. Elkies: What is the complexity of computing permanent of Moore matrix? Vandermonde needs $O(nlog{n})$. Is there a similar complexity algorithm for Moore as well? –  Turbo Dec 22 '11 at 3:23
Another interpretation of this matrix: Consider $x,y,z$ as elements in $\mathbb{F}_{p^3}$, conjugate over $\mathbb{F}_{p}$. This matrix is invertible iff $\{ x,y,z \}$ constitute a normal basis of $\mathbb{F}_{p^3}$ over $\mathbb{F}_{p}$. Why? Because we want all of them to be linearly independent, and all the (distinct) linear combinations of $x,y,z$ appear in the factorization of the determinant. (One can prove this more generally, as in the infinite case of the normal basis theorem). –  Ofir Gorodetsky Feb 4 at 18:40

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.

-
That's a good one too. I actually solved it by (re)deriving the exponential formula and setting $z_i = (-1)^{i-1}$ for $i \geq 2$ [in the notation of your blog post, which is different from the $x$ and $y$ that you use here] to get the generating function $(1+y) \exp(xy-y)$, which I then integrated as you did. This is Stanley's "Third solution" at <amc.maa.org/a-activities/a7-problems/putnam/-pdf/2005s.pdf>. –  Noam D. Elkies Jul 8 '11 at 2:28
@Noam: yes, that's what I ended up realizing, but at the time I argued more indirectly. There is a combinatorial recurrence for $F_n(x)$ that is equivalent to the differential equation $\frac{\partial G}{\partial y} = \left( x - 1 + \frac{1}{1+y} \right) G$ where $G$ is the two-variable generating function above. Of course this is just a special case of one proof of the exponential formula. –  Qiaochu Yuan Jul 8 '11 at 2:41
In case you can't guess the "determinant" solution: it's the first one in the sane place <amc.maa.org/a-activities/a7-problems/putnam/-pdf/2005s.pdf>. –  Noam D. Elkies Jul 8 '11 at 5:05

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.

-
As always, fantastic examples. Thank you so much! –  Dedalus Dec 21 '11 at 17:22
It is also interesting to note if you look up the Putnam stats for this year's exam that literally not a single student was able to answer question B6 on the exam. –  Samuel Reid Jun 8 '12 at 22:48

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.).

-
Seriously, though, there is "group representation" written all over this problem. –  darij grinberg Dec 21 '11 at 18:21

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.

-

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.

-

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.

-

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 Lebesque 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$.

-

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...)

-

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

-
fixed some malformatted tex –  Yoav Kallus May 9 '13 at 22:42

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.

-

-
I can understand the downvote, but I'm not going to put THIS in a comment. –  darij grinberg Dec 21 '11 at 18:33

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, ﬁnd 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.

-

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].

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.

-
Interesting. Does the result continue to hold if $S$ is replaced by its subset $T$, each point of which has its nonzero coordinates equal? (That is, does $T$ require the same minimal number of affine planes to cover as does $S$ ?) Gerhard "Still Figuring This One Out" Paseman, 2015.05.11 –  Gerhard Paseman May 12 at 4:26
At least for the two dimensional version of this problem, the minimum is not the same. Take a 3x3 grid in the plane. The minimum number of lines for S is 4, while T can be covered with 3 lines, x + y = 1, x + y = 2 and x + y = 4. I guess it can be generalised to higher dimensions as well, but for that I will need a pen and paper. –  Anurag May 12 at 4:47

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.

-