Thursday, August 24, 2006

Add Some Numbahs. Topic: Number Theory. Level: AIME/Olympiad.

Problem: (2003 Putnam - A1) Let $ n $ be a fixed positive integer. How many ways are there to write $ n $ as a sum of positive integers $ n = a_1+a_2+\cdots+a_k $ with $ k $ an arbitrary positive integer and $ a_1 \le a_2 \le \cdots \le a_k \le a_1+1 $?

Solution: So that strange inequality condition basically says that all the numbers are within one of each other. Easy enough. Let's take this approach; for any $ n $, run through each $ k $ from $ 1 $ to $ n $ (if $ k > n $ there are clearly no solutions).

Let $ \displaystyle d = \left\lfloor \frac{n}{k} \right\rfloor $. Then $ kd \le n < k(d+1) $. Essentially, this says that all of the $ a_i $'s are close to $ d $. We claim that in fact $ a_i = d $ or $ a_i = d+1 $ for all $ i $ and a fixed $ k $.

Suppose $ a_i < d $ for some $ i $. Then $ \sum a_i < kd < n $ since the maximum $ a_i $ is within $ 1 $ of the minimum, impossible. Similarly, suppose $ a_i > d+1 $ for some $ i $. Then $ \sum a_i > k(d+1) > n $ since the minimum is within $ 1 $ of the maximum, again impossible. This proves the claim.

Now we claim that there is exactly one solution for any fixed $ k $. Suppose $ a_1, a_2, \ldots, a_j $ are all $ d $ and $ a_{j+1}, a_{j+2}, \ldots, a_k $ are all $ d+1 $. Then the sum is

$ jd+(k-j)(d+1) $.

At $ j = k $, all the $ a_i $'s are $ d $ and the sum is $ kd \le n $. But notice that decreasing $ j $ by $ 1 $ increases the LHS by $ 1 $. So if we keep incrementing $ j $, we will eventually get to $ n $ (if we go all the way to $ j = 0 $ we reach $ k(d+1) > n $, so we must've passed $ n $ somewhere in there). It's easy to see that we can't get $ n $ twice because the LHS only increases. Hence for each $ k $ there is exactly one solution for $ a_1, a_2, \ldots, a_k $.

Since $ k = 1, 2, \ldots, n $ are all possible values for $ k $, there are exactly $ n $ ways to write $ n $ as a sum of the desired form. QED.


Comment: Another Putnam problem; they aren't too bad, right? Considering a large percentage of students who take it get zero points out of $ 120 $, anyway. The solution above would probably have to be rigorized immensely before actually being called a proof, but that would be no fun to read and stuff.


Practice Problem: (2003 Putnam - B1) Do there exists polynomials $ a(x), b(x), c(y), d(y) $ such that

$ 1+xy+x^2y^2 = a(x)c(y)+b(x)d(y) $

holds identically?


  1. You can prove the existence of a unique solution for each k inductively, it's really easy. That is, it's obvious that for n = 1, 2, 3, ... k there's only one solution and for all the others we reduce mod k by subtracting one from everything.

  2. Okay, you have to prove that a_i isn't less than d.

    PS: Do we get edit buttons now that we have to log in? =O

  3. That was pretty much what I thought of for the unique solution part, since it's obvious that it can only sum to whatever mod k in one way, but I decided that the way I explained it was simpler (less rigorous, maybe). The first time I solved it I didn't use induction, though.

    I don't know if you get edit buttons; I can edit your posts lol. If you do, it should be right after the date and time of your post.

  4. practice:

    if you put numbers for x,y, you see that the equations you get are linearly independent. so the answe is no.

  5. I don't understand what you mean by linearly independent...

  6. I think he means this:

    Set variables for a, b, c, d as quadratic polynomials (they obviously cannot have a higher degree); then we have twelve variables.

    Plugging in arbitrary numbers for x, y, Amir claims that every equation we get is linearly independent, which means that their intersection is empty (twelve variables, more than twelve equations).

    This does not seem obvious to me at all.

  7. hm....
    i was thinking like 1-x+x^2, and 1+x+x^2 cant both be multiples of same functions.