Contest problems with connections to deeper mathematics. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T18:00:17Z http://mathoverflow.net/feeds/question/69737 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics Contest problems with connections to deeper mathematics. Dedalus 2011-07-07T18:09:47Z 2013-05-10T09:29:26Z <p>Hi,</p> <p>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.</p> <p>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.</p> <p>Some examples:</p> <ol> <li><p>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 &lt;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". </p> <p>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.</p></li> <li><p>(Taken from Gerry Myerson in this thread <a href="http://math.stackexchange.com/questions/33109/contest-problems-with-connections-to-deeper-mathematics" rel="nofollow">http://math.stackexchange.com/questions/33109/contest-problems-with-connections-to-deeper-mathematics</a>)</p> <p>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.</p> <p>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 <a href="http://planetmath.org/encyclopedia/SixExponentialsTheorem.html" rel="nofollow">The Six Exponentials Theorem</a>.</p> <p>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.</p></li> </ol> <p>The most interesting part would be to see solutions to these problems using both elementary methods, and also with the more abstract "deeper methods".</p> http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics/69742#69742 Answer by Noam D. Elkies for Contest problems with connections to deeper mathematics. Noam D. Elkies 2011-07-07T19:26:25Z 2011-07-07T20:59:59Z <p>A few Putnam problems come to mind. Here's one that I could locate most easily.</p> <p>1992 problem B-6. Let $\cal M$ be a set of real $n \times n$ matrices such that<br> i) $I \in \cal M$ (identity matrix);<br> ii) If $A\in \cal M$ and $B \in \cal M$ then exactly one of $AB$ and $-AB$ is in $\cal M$;<br> iii) If $A\in \cal M$ and $B\in \cal M$ then either $AB=BA$ or $AB=-BA$;<br> iv) If $A \in \cal M$ and $A \neq I$ then there is at least one $B \in \cal M$ such that $AB = -BA$.<br> Prove that $\cal M$ contains at most $n^2$ matrices.</p> <p>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.</p> <p>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.). </p> http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics/69744#69744 Answer by GH for Contest problems with connections to deeper mathematics. GH 2011-07-07T19:50:44Z 2011-07-07T19:50:44Z <p>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 <a href="http://www.amazon.com/Contests-Higher-Mathematics-Schweitzer-Competitions/dp/0387945881" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics/69745#69745 Answer by Noam D. Elkies for Contest problems with connections to deeper mathematics. Noam D. Elkies 2011-07-07T19:56:17Z 2013-05-09T15:54:17Z <p>[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.]</p> <p>2002 Problem B-6. Let $p$ be a prime number. Prove that the determinant of the matrix $$\left(\begin{array}{lll}x&amp;y&amp;z\cr x^p &amp;y^p&amp;z^p\cr x^{p^2}&amp;y^{p^2}&amp;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.</p> <p>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.</p> <p>References:</p> <p>E.H.Moore: A two-fold generalization of Fermat's theorem, <em>Bull. AMS</em> <strong>2</strong> #7 (1986), 189-199.</p> <p>L.E.Dickson: A fundamental system of invariants of the general modular linear group with a solution of the form problem. <em>Trans. AMS</em> <strong>12</strong> (1911), 75-98</p> http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics/69759#69759 Answer by Qiaochu Yuan for Contest problems with connections to deeper mathematics. Qiaochu Yuan 2011-07-08T00:43:09Z 2011-07-08T02:42:37Z <p>The following problem led me to some interesting parts of mathematics.</p> <p><strong>Putnam 2005 B6:</strong> 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</p> <p>$$\sum_{\pi \in S_n} \frac{\text{sgn}(\pi)}{\text{fix}(\pi) + 1} = (-1)^{n+1} \frac{n}{n+1}.$$</p> <p>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</p> <p>$$\sum_{n \ge 0} \frac{F_n(x)}{n!} y^n = (1 + y) e^{xy - y}.$$</p> <p>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.")</p> <p>Some time after solving this problem I realized that the above identity is a special case of a beautiful result called the <strong>exponential formula</strong> which I describe in detail in <a href="http://qchu.wordpress.com/2009/06/24/gila-vi-the-cycle-index-polynomials-of-the-symmetric-groups/" rel="nofollow">this blog post</a>. The exponential formula, in turn, besides being an important tool in combinatorics in its own right, is related to <a href="http://en.wikipedia.org/wiki/Combinatorial_species" rel="nofollow">combinatorial species</a> and <a href="http://en.wikipedia.org/wiki/Symmetric_function" rel="nofollow">symmetric functions</a>, both of which I was better able to appreciate because of my experience with the above problem. </p> <p>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 <a href="http://qchu.wordpress.com/2009/08/23/newtons-sums-necklace-congruences-and-zeta-functions/" rel="nofollow">these</a> <a href="http://qchu.wordpress.com/2009/11/04/newtons-sums-necklace-congruences-and-zeta-functions-ii/" rel="nofollow">two</a> blog posts. </p> http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics/69764#69764 Answer by Noam D. Elkies for Contest problems with connections to deeper mathematics. Noam D. Elkies 2011-07-08T02:46:59Z 2011-07-08T02:46:59Z <p>Another Putnam problem, from the same exam that produced Q.Yuan's nice example:</p> <p><strong>Putnam 2005, Problem B5</strong> 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.</p> <p>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 <a href="http://amc.maa.org/a-activities/a7-problems/putnam/-pdf/2005s.pdf" rel="nofollow">http://amc.maa.org/a-activities/a7-problems/putnam/-pdf/2005s.pdf</a> (one by Yours Truly) grows naturally out of one approach to the development of the theory of spherical harmonics. See also <a href="http://mathoverflow.net/questions/67411/signed-factors-of-harmonic-polynomials" rel="nofollow">http://mathoverflow.net/questions/67411/signed-factors-of-harmonic-polynomials</a> for a generalization that appeared on this forum a few weeks ago.</p> http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics/69953#69953 Answer by Eric Naslund for Contest problems with connections to deeper mathematics. Eric Naslund 2011-07-10T19:53:50Z 2011-07-10T19:58:57Z <p>Here is one I liked:</p> <blockquote> <p>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}$.</p> </blockquote> <p>The problem is fairly standard, and follows by induction. However, it was motivated by the following generalization due to Erdos:</p> <blockquote> <p>If $f:\mathbb{N}\rightarrow \mathbb{R}$ is multiplicative and monotonically increasing, then $f(n)=n^\alpha$ for some $\alpha$. </p> </blockquote> <p>Two nice proofs of this generalization can be found in the American Mathematical Monthly. See <a href="http://www.ams.org/mathscinet/search/publdoc.html?arg3=&amp;co4=AND&amp;co5=AND&amp;co6=AND&amp;co7=AND&amp;dr=all&amp;pg4=AUCN&amp;pg5=TI&amp;pg6=PC&amp;pg7=ALLF&amp;pg8=ET&amp;review_format=html&amp;s4=&amp;s5=monotone%2520multiplicative%2520function&amp;s6=&amp;s7=&amp;s8=All&amp;vfpref=html&amp;yearRangeFirst=&amp;yearRangeSecond=&amp;yrop=eq&amp;r=2&amp;mx-pid=868104" rel="nofollow">this</a> article by Everett Howe or <a href="http://www.ams.org/mathscinet/search/publdoc.html?arg3=&amp;co4=AND&amp;co5=AND&amp;co6=AND&amp;co7=AND&amp;dr=all&amp;pg4=AUCN&amp;pg5=TI&amp;pg6=PC&amp;pg7=ALLF&amp;pg8=ET&amp;review_format=html&amp;s4=&amp;s5=monotone%2520multiplicative%2520function&amp;s6=&amp;s7=&amp;s8=All&amp;vfpref=html&amp;yearRangeFirst=&amp;yearRangeSecond=&amp;yrop=eq&amp;r=1&amp;mx-pid=999417" rel="nofollow">this</a> article by Joel Cohen.</p> http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics/83990#83990 Answer by Noam D. Elkies for Contest problems with connections to deeper mathematics. Noam D. Elkies 2011-12-21T04:55:17Z 2011-12-21T04:55:17Z <p>This year's recent Putnam exam offered at least one more example:</p> <blockquote> <p><strong>Putnam Exam 2011, Problem B6</strong> 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$.</p> </blockquote> <p>Eric Naslund posted his solution at the end of <a href="http://mathoverflow.net/questions/82648" rel="nofollow">his Mathoverflow question</a>, asking</p> <blockquote> <p>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?</p> </blockquote> <p>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 <a href="http://amc.maa.org/a-activities/a7-problems/putnam/-pdf/2011s.pdf" rel="nofollow">Putnam Directory</a>). Later I found a more direct way to connect such matrices with the problem, related with the theory of <a href="http://en.wikipedia.org/wiki/Pade_approximant" rel="nofollow">Padé approximants</a>; 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.</p> <p>References:</p> <p>[M] Mit'kin, D.A.: An estimate for the number of roots of some comparisons by the Stepanov method, <em>Mat. Zametki</em> <strong>51</strong> #6 (1992), 52–58, 157; translation in <em>Math. Notes</em> <strong>51</strong> #5–6 (1992), 565–570</p> <p>[S] Stepanov, A.: An elementary proof of the Hasse-Weil theorem for hyperelliptic curves, <em>J. Number Theory</em> <strong>4</strong> (1972), 118–143. </p> http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics/84018#84018 Answer by darij grinberg for Contest problems with connections to deeper mathematics. darij grinberg 2011-12-21T18:13:14Z 2011-12-21T18:13:14Z <p>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. <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&amp;t=188350" rel="nofollow">Zero-sum combinatorics</a>, <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&amp;t=355915" rel="nofollow">coding theory</a>, <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?t=22364" rel="nofollow">inequalities</a>, <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?f=585&amp;t=290874" rel="nofollow">more inequalities</a> (with both an analysis and a linear algebra proof), even <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?f=38&amp;t=326814" rel="nofollow">some functional equations</a> 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.</p> http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics/84068#84068 Answer by Woett for Contest problems with connections to deeper mathematics. Woett 2011-12-22T02:34:08Z 2013-05-09T22:39:56Z <p>A problem on Tournament of the towns 2002 Fall/A-level:</p> <p>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.</p> <p>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; <a href="http://www.mimuw.edu.pl/~malcin/ekg.pdf" rel="nofollow">http://www.mimuw.edu.pl/~malcin/ekg.pdf</a></p> http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics/130209#130209 Answer by Dan Sălăjan for Contest problems with connections to deeper mathematics. Dan Sălăjan 2013-05-09T22:29:26Z 2013-05-09T22:29:26Z <p>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...)</p> http://mathoverflow.net/questions/69737/contest-problems-with-connections-to-deeper-mathematics/130240#130240 Answer by Igor Kortchemski for Contest problems with connections to deeper mathematics. Igor Kortchemski 2013-05-10T09:29:26Z 2013-05-10T09:29:26Z <p>Nearly all the problems of the <a href="http://www.itym.org/" rel="nofollow">International Tournament of Young Mathematicians</a> (team competition for high school students, where problems are published several months in advance) contain open questions related to research problems. </p> <p>Here is an example:</p> <blockquote> <p>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.</p> <ol> <li><p>When $n$ is prime, ﬁnd the number of stable subsets $A \subset P_n$ and describe them.</p></li> <li><p>The same problem when $n$ is the product of two distinct prime numbers.</p></li> <li><p>The same problem when $n$ is a power of a prime number.</p></li> <li><p>Investigate the problem for an arbitrary $n$.</p></li> <li><p>Suggest and study additional directions of research.</p></li> </ol> </blockquote> <p>This problem is related to finding sums of roots of unity that vanish, see e.g. <a href="http://arxiv.org/abs/math/9511209" rel="nofollow">here</a>.</p>