Archive for the ‘Putnam / competitions’ Category

A student I’m tutoring was working unsuccessfully on the following problem from the 2011 Mandelbrot Competition:

Let a, b be positive integers such that \log_a b = (\log 23)(\log_6 7) + \log_2 3 + \log_6 7. Find the minimum value of ab.

After some tinkering, I concluded that the problem as stated has no solution. I am now almost certain it was printed incorrectly: \log 23 should be replaced by \log_2 3, and then we can solve the problem as follows:

\log_a b + 1 = (\log_2 3 + 1)(\log_6 7 + 1) = \log_2 6 \log_6 42 = \log_2 42.

It follows that \log_a b = \log_2 21. Since a, b are positive integers we must have a \ge 2, and then it follows that the smallest solution occurs when a = 2, b = 21. But what I’d like to discuss, briefly, is the argument showing that the misprinted problem has no solution.


Read Full Post »

Putnam 2009

Kent Merryfield continues his tradition of posting the Putnam results every year. Before I came to MIT I didn’t understand why this was necessary, but after taking it I learned that the results are only sent to the relevant officials at each school, who distribute the results in a manner of their choosing. This seems to me to be a pretty inefficient system, and I’ve never really understood why it’s done this way, so kudos to Dr. Merryfield for making this information more widely available.

Read Full Post »

The problems from IMO 2009 are now available. I haven’t had much time to work on them, though.

There are two classical geometry problems, which I already know I won’t attempt. While I am well aware that classical geometry often requires a great deal of ingenuity, I am also aware of the existence of the field of automatic geometric theorem proving. On this subject I largely agree with Doron Zeilberger: it is more interesting to find an algorithm to prove classes of theorems than to prove individual theorems. The sooner we see areas like classical geometry as “low-level,” the sooner we can work on the really interesting “high-level” stuff. (Plus, I’m not very good at classical geometry.)

Zeilberger’s typical example of a type of theorem with a proof system is the addition or multiplication of very large numbers: it is more interesting to prove (a + 1)(a - 1) = a^2 - 1 symbolically than it is to prove individual “theorems” such as 999 \cdot 1001 = 999999. Zeilberger himself played a significant role in the creation of another proof system, but for the far less trivial case of hypergeometric identities (which includes binomial identities as a special case).

But so I can make my point concretely, I’d like to discuss some examples based on the types of problems most of us had to deal with in middle or high school.


Read Full Post »

In the previous post we used the Polya enumeration theorem to give a sneaky, underhanded proof that

\displaystyle \sum_{m \ge 0} Z(S_m) t^m = \exp \left( z_1 t + \frac{z_2 t^2}{2} + \frac{z_3 t^3}{3} + ... \right).

If you’ve never seen the exponential function used like this, you might be wondering how it can be “explained.”

To explore this question, I’d like to give three other proofs of this result, the last of which will be “direct.” Along the way I’ll be attempting to describe some basic principles of species theory in an informal way. I’ll also give some applications, including to a Putnam problem.


Read Full Post »


Get every new post delivered to your Inbox.

Join 324 other followers