Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi,

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

share|improve this question
2  
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
1  
Right, changed it now! Thank you. –  Dedalus Jul 7 '11 at 19:09
8  
Since this asks for various problems, I think it is a classical case for Community Wiki mode. –  quid Jul 7 '11 at 19:38
1  
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
2  
@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

11 Answers 11

[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 $\mathbb{Z} / p \mathbb{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 (1986), 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

share|improve this answer
7  
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? –  J.A Dec 22 '11 at 3:23

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.

share|improve this answer
    
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

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

share|improve this answer
1  
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.

share|improve this answer

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.

share|improve this answer
    
As always, fantastic examples. Thank you so much! –  Dedalus Dec 21 '11 at 17:22
1  
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

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.

share|improve this answer

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.

share|improve this answer

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.

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

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

share|improve this answer
    
fixed some malformatted tex –  Yoav Kallus May 9 '13 at 22:42

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.