Putnam

22 11 2009

This has been my first year on the Putnam committee: the committee that selects the problems for the William Lowell Putnam undergraduate competition. The committee consists of 3 members appointed for a 3-year term each (each year, one person’s term ends and another one is appointed in his place) and a fourth person, Loren Larson, who is a “permanent” secretary of the committee. To start with, each committee member proposes some number of problems (normally, at least 10). The problem sets and solutions are then circulated and discussed, and eventually the committee meets in person to decide on the final selection. This is all done in strict confidence and well in advance of the actual competition.

I have never written the Putnam. I wrote the Math Olympiad back in the days and qualified for the International Math Olympiad in my last year of high school, but Putnam is not available in Europe. I’m not sure that I would have been interested anyway. I wanted to study the “serious” mathematics: the big theories, the heady generalizations, the grand visions. Olympiads and competitions faded into the distant background and pretty much stayed there until last year.

I did point out my Putnam virginity when I was approached about joining the committee, and was told that Putnam does try to engage from time to time people who are not normally on the circuit, if only to have a larger pool of potential ideas. Of course, the advantage of having people on the committee who are on the Putnam circuit is that they know what’s expected, what works and what doesn’t, what has already been used and shouldn’t be recycled, and so on. Last year’s other two committee members – Mark Krusemeyer and Bjorn Poonen – are Putnam veterans, and of course Bjorn is a four-time Putnam fellow. Mark’s term ends this year; I don’t know yet who will be joining us this January.

Well, you could call it a steep learning curve. Putnam problems are expected to be hard in a particular way: they should require ingenuity and insight, but not the knowledge of any advanced material beyond the first or occasionally second year of undergraduate studies, and there should be a short solution so that, in principle, an infinitely clever person could solve all 12 problems in the allotted 6 hours. (In reality, that doesn’t happen very often, and I’ve heard that it generates considerable attention when someone comes too close.) The problems are divided into two groups of six – A1-A6 for the morning session and B1-B6 for the afternoon session – and there is a gradation of the level of difficulty within each group. A1 is often the hardest to come up with – it should be the easiest of the bunch, but should still require some clever insight and have a certain kind of appeal. The difficulty (for the competitor, not for us) then increases with each group, with A6 and B6 the hardest problems on the exam. There are also various subtle differences between the A-problems and B-problems; this is something that I would not have been aware of if another committee member hadn’t pointed it out to me. For example, a B1 could involve some basic college-level material (e.g. derivatives or matrices), but this would not be acceptable in an A1, which should be completely elementary.

The competition is taking place in two weeks, so you’ll know soon enough what problems we ended up selecting. Meanwhile, it might entertain you to see a few of my duds: problems I proposed that were rejected for various reasons. They will not be appearing on the actual exam and I’m not likely to propose variants of them in the future. The solutions are under the cut, along with an explanation of why each problem is a dud.

A ball is shot out of a corner $A$ of a square-shaped billiard table $ABCD$ at an angle $\theta$ to the edge $AB$ . The ball travels in a straight line without losing speed; whenever it hits one of the walls of the table, it bounces off it so that the angle of reflection is equal to the angle of incidence. Find all values of $\theta$ such that the ball will hit one of the corners $A,B,C,D$ after bouncing off the walls exactly 2009 times.
Are there integer numbers $a_1<a_2<\dots<a_{2009}$ such that $\sum_{i<j}(a_j-a_i)=31415926535$ ?
Given $n$ , determine the largest integer $m(n)$ with the property that any $n$ points $P_1,P_2,\dots,P_n$ on a circle must determine at least $m(n)$ obtuse angles $P_iP_jP_k$ .

Solution to 1. Introduce a coordinate system so that $A=(0,0)$ , $B=(0,1)$ , $C=(1,1)$ , $D=(1,0)$ . Now “straighten out” the trajectory of the ball using the reflection principle: follow the trajectory of the ball until it first hits a wall. Once that happens, instead of drawing the next segment inside the square $ABCD$ draw the symmetric reflection of it with respect to the wall that was hit, and continue similarly. The straightened trajectory is a half-line in the first quadrant, starting at the origin, at an angle $\theta$ to the $x$-axis. The desired outcome is equivalent to the line meeting its first lattice point $P$ after crossing exactly 2009 “walls” $x=m$ or $y=n$ , for $m,n$ integer. Then $P$ must be one of the points (2010,1), (2009,2),…, (1,2010). This yields the possible values of $\theta$ :

$\theta=\tan^{-1}\frac{2011-n}{n},\ n=1,2,\dots,2010.$

It remains to check whether any of these values must be excluded on the grounds that the line segment from (0,0) to $(2011-n,n)$ contains another integer point, say $(k,m)$ with $k+m<2011$ . If that were so, we would have

$\frac{2011-n}{n}=\frac{k}{m},\ (2011-n)m=kn,\ 2011m=n(k+m).$

In particular, $k+m$ divides $2011 m$ , hence must have a nontrivial common divisor with 2011. But 2011 is prime, so that $k+m=2011$ , a contradiction. Hence all 2010 values of $\theta$ as above yield the desired outcome.

Why it’s a dud: This is an example of a problem whose difficulty depends very strongly on knowing a certain “trick” or technique – in this case, the reflection principle. The committee aims to avoid this type of questions. It doesn’t help that the trick is an old one.

Solution to 2. Rewrite the sum as $\sum_{k=1}^{2008} c_k(a_{k+1}-a_k)$ , where $c_k$ is the number of pairs $(i,j)$ such that $1\leq i\leq k<j\leq 2009$ . We count the number of such pairs: for each $k$ there are $k$ choices of $i$ and $2009-k$ choices of $j$ , so that $c_k=k(2009-k)$ . In particular, all $k$ are even. But then the above sum must also be even, in particular it cannot be 31415926535.

Why it’s a dud: This was supposed to be a candidate for an A1 or B1, but might be too easy even for that (there are several other short solutions in addition to the above). It was also judged only moderately clever and attractive. We ended up finding something more inspired.

Solution to 3. If $n=2,3,4$ , easy examples (2 points, an equilateral triangle and a square) show that $m(n)=0$ . Assume therefore that $n\geq 5$ and let ${\cal P}=\{P_1,\dots,P_n\}$ . We will first find the smallest possible number $m(P,n)$ of the obtuse angles $P_iP_jP_k$ with $P_i$ fixed, then sum over $i$ and divide by 2 (because each angle was counted twice). Let $P_i=P$ for short, and let $P'$ be the point antipodal to $P$ on the circle. We will say that points $P_j,P_k$ lie on the same side of $P$ if they lie on the same arc between $P$ and $P'$ . Note that it is to our advantage to have $P'\in{\cal P}$ whenever possible, because then there are no obtuse angles involving both $P$ and $P'$ .

Case 1: $n$ is even. Let $n=2k+2$ , $k\geq 2$ , and assume that $P'\in{\cal P}$ . There is a one-to-one correspondence between the obtuse angles $PP_jP_k$ and the (unordered) pairs of points $P_j,P_k$ on the same side of $P$ . Let $x$ and $n-x-2=2k-x$ denote the numbers of points on each side of $P$ . Suppose that both $x$ and $2k-x$ are at least 2, then the number of such pairs is

${x\choose 2}+{2k-x\choose 2}=x^2-2kx+k(2k-1).$

This is minimized when $x=k$ , and the minimum value is $k^2-k$ . If on the other hand $x\leq 1$ or $2k-x\leq 1$ , the number of pairs is at least ${2k-1\choose 2}=(k-1)(2k-1),$ which is $\geq k^2-k$ since $k\geq 2$ . Thus $m(P,n)\geq k^2-k$ , and this number is indeed attained for each $P\in{\cal P}$ if $P_j$ form a regular $n$ -gon. It follows that for $n$ even,

$m(n)=\frac{n}{2}(\frac{n}{2}-1)(\frac{n}{2}-2).$

Case 2: $n$ is odd. Let $n=2k+3$ , $k\geq 1$ . Assume that $P'\in{\cal P}$ , and let $x$ and $n-x-2=2k+1-x$ be the numbers of points on each side of $P$ . Suppose that both $x$ and $2k+1-x$ are at least 2, then the number of same-side pairs $P_j,P_k$ is

${x\choose 2}+{2k+1-x\choose 2}=\frac{1}{2}\big(x(x-1)+(2k+1-x)(2k-x)\big)=x^2-(2k+1)x+k(2k+1).$

Given the constraint that $x$ is integer, this is minimized when $x=k$ or $k+1$ , with minimum value $k^2$ . As in case 1, we check that if $x$ or $2k+1-x$ are at most 1, then the number of pairs is at least ${2k\choose 2}=k(2k-1),$ which is $\geq k^2$ since $k\geq 1$ . Thus $m(P,n)\geq k^2$ .

Note, however, that if $n$ is odd then there is at least one point $P\in{\cal P}$ such that $P'\notin{\cal P}$ . For that point, the number of same-side pairs is

${x\choose 2}+{2k+2-x\choose 2}=x^2-(2k+2)x+(k+1)(2k+1),$

which is minimized when $x=k+1$ , with minimum value $k(k+1)$ . (As before, we can check that the cases $x\leq 1$ and $2k+2-x\leq 1$ are not minimal.)

It follows that

$m(n)\geq \frac{1}{2}\big( (2k+2)k^2+k(k+1)\big)=\frac{k(k+1)(2k+1)}{2} =\frac{(n-1)(n-2)(n-3)}{8},$

and this is attained when the first $2k$ points form a regular $2k$ -gon and the last one is placed arbitrarily.

Why it’s a dud: It would have to be an A5 or higher, given the length of the solution. (There is no short one as far as we know; the solutions that we came up with are all lengthy and can be difficult to write up.) However, it does not really require the kind of ingenuity that this group of problems is expected to call for. You shouldn’t be able to solve an A5 by following your nose. Here, though, once you get going, the procedure is fairly straightforward.

About these ads

Actions

Information

Date : November 22, 2009
Categories : mathematics: general

3 responses

3 12 2009: John Armstrong (17:34:02) :

That’s not the reason that problem 1 is a dud. It’s a dud because it was used not very long ago in a Putnam exam. I saw it when I was going through old Putnams (Putni?) with some undergraduates a year ago.
3 12 2009: Carnival of Mathematics #60 « ∑idiot's Blog (21:03:21) :

[...] on the notoriously difficult Putnam exam (and yet more puzzles), head over to Izabella’s post at The Accidental [...]
4 12 2009: Best of luck on the Putnam « ACME Science (12:40:54) :

[...] the Accidental Mathematician is on his first year of writing problems for the Putnam and has the following to say about the problem difficulty on the Putnam: Well, you could call it a [...]

The Accidental Mathematician

Putnam

Like this:

Actions

Information

3 responses

Recent Posts

Older posts

Categories

My Twitter page

Google+

Admin links

Mathematicians and allied scientists

There's life beyond mathematics

Follow “The Accidental Mathematician”