In the following post, all sequences are numbered starting at 1.

The homework page for the Mathematical Problem Solving (that is, the Putnam) seminar here at MIT contains the following warning:

You are expected to solve on your own problems which you hand in. Some collaboration with other students in the seminar is o.k. as long as you don't simply copy someone else's work. You should also not hand in any problems whose solution you are already familiar with.

I've never considered myself a particularly creative problem-solver. My main asset is in having seen a wide variety of problems and being aware of a wide variety of tools. So this puts me in an interesting spot: I cannot hand in solutions to several interesting problems on these problem sets because I am already too familiar with them and I am forced to solve problems whose solution techniques are not immediately obvious to me (which can only be a good thing, but...). Even a problem I haven't seen before that is phrased in a very interesting way reduces readily to a lemma in Engel:

Problem 1: Define a sequence of positive integers as follows. Pick . Once have been chosen, let be the smallest positive integer not already chosen and not of the form . The sequence begins . Find a simple formula for .

Before I discuss the solution, let me discuss my first impression before I recalled the lemma in question. This problem appears at first to be quite mysterious. skips a strange sequence (the sequence ) which we do not understand; it seems as though to understand we need to understand , but then it seems as though to understand we need to understand ! By comparison, consider the following problem (given in the same chapter in Engel):

Problem 2: Find a simple formula for the sequence of natural numbers that skips the squares. The sequence begins

Solution. It appears that we should write where increases by every time we skip a square. But the indices at which increases are not the squares; rather, the first skip occurs at , the second at , and in general (after we have skipped squares) the at . The approximate growth rate of is then the inverse function of , or , but here is the key observation: the exact formula for is given by



Why? and clearly agree whenever , and in between stays the same whereas increases monotonically to its next integer value. We therefore find that



This is what I meant when I said that if we understood (the sequence of integers we skipped), we would understand . The obvious approach from here is to generalize what we did above and to consider a given monotonically increasing sequence of positive integers (such as ) with a straightforward inverse function and find an exact formula for the sequence that skips the values of . By the above discussion, such a sequence can be given as



where (which is the actual function we need an inverse for). Applying this idea to (a sequence that skips the values of ), we conclude that what we need is the inverse function of . But we don't know it, so now we have to solve a horrid functional equation!

At this point, inspiration might strike in the form of a well-chosen guess. We have observed that a sequence like the one that skips the squares is approximately linear (since it skips a sequence that becomes sparse). But if skips the sequence then it stands to reason that both and should be approximately linear, and moreover that the closed forms of both sequences should involve floor functions. (This would also make the inverse function of approximately linear.)

The functions we should be looking at are therefore of the form , and this is as good an inspiration as I can muster for the lemma that trivializes this problem.

Lemma (Engel, Chapter 6, E17): Let be positive irrational real numbers such that . Then the sequences are disjoint and their union is .

Proof. Engel gives a proof by contradiction that, while short, I find unenlightening. Let me give the following slightly more visual proof:

Given any natural number , divide up the interval into four intervals with endpoints at the points and calls those intervals, from left to right, . Now, is an interval of length with irrational endpoints; it therefore contains exactly one natural number . If , then




.

On the other hand, if , then


.

The interval construction we described therefore describes an algorithm that sorts any natural number into exactly one of the two progressions along with its index in that progression.

Now, if it is the case that , then we must have both and . The algebra is easy enough, but I should remark that the original problem was given with the following

Hint: The answer involves .

It is now obvious that and we are done.

---

It would be pointless to submit this solution for scoring. Even if I explained that the answer can be motivated by a more general idea (that of skipping a given integer sequence), what I am sure the professors teaching the Putnam seminar are looking for is a solution generated with as little prior knowledge of problems of this type as possible. Such problem-solving is beyond me as a general rule, and certainly I commend any of my classmates who solved this problem without being aware of Engel's lemma. This problem was rated a three, which means "Extremely difficult. Only a few students should be able to solve it."

And we are talking about a class that includes four of the six US IMO 2008 team members! (Alex Zhai is at Harvard and Evan O'Dorney is, of course, not in college.)

Nevertheless, I hope that I presented the above discussion (up to the "approximately linear and involving floor functions" step) in a way that was motivated enough so that Engel's lemma did not seem to appear out of thin air. It is not entirely unmotivated: if and are given to be disjoint and to have union , then their natural densities (which are and ) must add to . Given this information, we could have concluded that if was approximately linear then and must have asymptotic densities respectively without the lemma, and indeed this idea provides a nice motivation to the lemma itself, though I am still not sure how easy it would have been to discover the lemma independently. That is the sort of discovery best left to better mathematicians than myself.

---

Practice Problem 1: a) Give an alternate proof of Engel's lemma based on the discussion about constructing a sequence that skips another sequence. (This might be unnecessarily messy.)

b) Why does Engel's lemma fail if are rational? Salvage it.

Practice Problem 2: Determine the closed form of the positive integer sequence such that are disjoint and their union is .