Putnam – Series and Calculus

Let be a real number. For each integer , define a
sequence , by the condition

,

,

Evaluate .
(Putnam 1985 A3)

The RHS of the sequence recursive definition looks a lot like , so we should write it in this form:

This works very nicely, as when we goto the next term, we cancel out the 1, square, then subtract the 1 again. For the first few values of j:

(We’re going to leave it in that form for now)

And it’s easy to show that

Thus, we have:

And we want to find:

We’ll focus on the part that doesn’t include the -1, as it clearly isn’t affected by the limit.

To simplify this, we’ll let , and find the limit as

Call this expression . Then we have:

To evaluate this limit, use L’Hopital’s Rule:

Thus, our original limit is . Hip hip hurrah!

Putnam – Pigeonhole

Prove that there exist integers a, b, c, none of which with absolute value greater than 1 million, such that:

The words “there exist” almost immediately points toward the pigeonhole principle. The key is to realize that if we remove the absolute value, then the difference between two numbers of the form will also be in this form. Thus, if we can find two numbers of this form within of each other, or show that they exist, then we’ll be done. To keep the absolute value of 1 million condition, we will restrict our numbers to the positive integers, so that the difference of each number in our difference is bounded between -1 million and 1 million.

Our lower bound for such numbers is clearly 0. To develop a crude upper bound, we have that:
for positive a, b, and c.

Thus, if we maximize a, b, and c, then our upper bound is

Since there are choices for each integer, the total number of numbers is . Now, if we divide the range of possible values into intervals, each one is less than the following size (if we use our upper bound):

Thus, there will be two in the same interval! Yayayay, QED.

Cylindrical coordinates – Round 2!!

This is just an update to an older post I made, which you can see here. In it, we reduce a Putnam problem into finding the volume of the set of all points satisfying:

where .

This is the equation for a torus. At the time of that post, I said that I didn’t have an intuitive reasoning for why that is. Now I do! Consider when z = 0, which is the xy cross section of the solid. We have:

This is the set of all points farther than 2 from the origin, but less than 4 from the origin. This is the main cross section of our torus.

Now, rewrite our main equation in the form:

Consider as we decrease or increase z. There is symmetry in this, so for now we’ll just refer to the increasing. The decreasing is exactly the same. As we increase z, the RHS gets smaller and smaller, and thus, the range of possible values of r gets smaller and smaller. Suppose that for some value of Z, the RHS was equal to .001. Then r must be greater than 2.999 and less than 3.001. This leads to the reasoning that the distance from the center of the tube to the origin is 3. Also, since the LHS is strictly positive, z must be less than or equal to 1. This leads to the reasoning that the radius of the tube is 1. This leads to the definition of our torus.

Now, suppose you still didn’t quite know this definition. Or perhaps you figured it out during the test, but wasn’t sure if it was a well known fact or not. The intuitive reasoning offers some insights, but it’s not a proof. How else could you do the problem?

One way is simply by integration. Consider as we vary z, from -1, to 1. Each one defines a set of points in R^2. Thus, we can integrate the area of this set in terms of z from -1 to 1.

Simplifying (or should I say expanding?) the expression yields:

The outer radius squared is , and the inner radius squared is . Thus, the area of the set of points, given z, is:

Where that last step comes from difference of squares.

Thus, integrating from -1 to 1 yields , as the integral of from -1 to 1 is , since it is the area of a semi circle of radius 1.

Olympiad – Sequences

Let k be a positive integer. The sequence is defined by , and for , is the nth positive integer greater than that is congruent to n modulo k. Find in closed form.
(AMO 1997)

Do this by playing around with various values of k and generating the first few terms of the sequence for each:

k=1
1, 3, 6, 10, 15

k=3
1, 5, 12, 22, 35

These sequences are easy to analyze, and both seem to follow the rule:

If you can’t see how to get this, define , try to come up with what is by conjecturing the pattern will continue, etc.

So all that’s left is to prove this formula.

No matter what k is, .

So suppose our formula holds for . We want to show its also true for .

Since we have from our inductive step that (note that this holds for our base case since also follows the modulo rule of the sequence), we also have that . So this is the first number greater than congruent to i+1 modulo k. We want the (i + 1)th number. So we must add k to this expression i more times. Thus:

Using our inductive step, we can substitute for :

Interpretting that fraction as a sum:

QED

Putnam – Calculus

Easy Putnam calculus problem from the 1980’s:

Define polynomials for by ,
for , and

for . Find, with proof, the explicit factorization of
into powers of distinct primes.
(Putnam 1985 – B2)

Using their definition, you can start churning out the polynomials for values of n = 0, 1, 2, 3. It’s given that . So we can plug this into the expression for the derivative of , and integrate. We are given that for all n, implying that when we integrate, the constant term is 0. Doing this out a few times, we get:

At this point, it’s worth conjecturing that for all n. Part of finding this is realizing that you have to factor the expressions. The biggest hints for this should be that they want the value of factored, and the coefficients in highly suggest factoring out an x and then factoring the resulting quadratic.

Best way to prove this would be induction. Assume that

From our given, we have:

The RHS isn’t particularly easy to integrate, but since we know what we want to be, we can take the derivative of it and show that its equal to the LHS. Since we know that the constant term of each is 0, this will show that the integral of the RHS is equal to what we want:

So by induction, , and

Btw, I highly recommend that you read Uzumaki, it’s my new favorite manga. It’s short, only 19 chapters. I read it in about a day. I highly recommend it. It’s quite creepy, and made my night.

Edit: Kay is a picky little fellow and called me out for copying that Uzumaki part from something I posted on his blog, so I might type up a more indepth Uzumaki review later to satisfy his craving for spirals.

USAMO – Invariants

Here’s a nifty invariant problem that we did in WOOT. I had trouble with it for a while but after reviewing stuff last night it magically made sense suddenly.

The sides of a 99-gon are initially colored so that consecutive sides are red, blue, red, blue, red, blue, yellow. We make a sequence of modifications in the coloring, changing the color of one side at a time to one of the three given colors (red, blue, yellow), under the constraint that no two adjacent sides may be the same color. By making a sequence of such modifications, is it possible to arrive at the coloring in which consecutive sides
are red, blue, red, blue, red, blue, red, yellow, blue?
(USAMO 1994, #2)

This was when the USAMO was only 5 problems in one session, instead of 6 problems split into two sessions, so this should be viewed as around a 1/4 difficulty level, as opposed to a 2/5.

Since we’re dealing with a problem where we are changing things, the first thing to do is to look for an invariant. That is, something that remains consistent, no matter what we change. A first natural step is to replace the colors with numbers. Lets say Red = 1, Blue = 2, Yellow = 3. Then we have the sequence:

1, 2, 1, 2, 1, 2 ….., 1, 2, 3

Which we want to transform to

1, 2, 1, 2 ,1, 2, …., 1, 3, 2

An easy way to look for an invariant is to make a move on our original sequence, and compare the resulting sequence to the original. For example, we can make the following change:

1, 2, 1, 2, 1, 2 ….., 1, 2, 3
->
1, 2, 3, 2, 1, 2 ….., 1, 2, 3

Now we begin searching for an invariant. It’s natural to only look at the area we changed:

2, 1, 2
->
2, 3, 2

It’s fairly obvious that the sum and product isn’t constant. Considering that the desired end state doesn’t vary in sum or product, it’s probably not worth investigating. Keeping in mind that it’s a rearrangement, and conjecturing that the end state won’t be reachable, we should look at an invariant which relates consecutive terms.

Looking at the original sequence and the altered sequence, one possible variant is the number of increases and decreases. For example, as we go from 2 ,to 1, to 2, we have one decrease and one increase in the value of the terms. As we go from 2 to 3 to 2, we also have one decrease and one increase. This is a possible invariant, and thus it should be checked if it applies to all such alterations. We will list all such ways of altering a triple by changing the second term of it. We may assume that the first and third terms are the same. If they weren’t, then it would not be possible to alter it, as it would result in two consecutive sides being the same color. All possible triple moves are:

(1, 2 ,1) (1, 3, 1)
(2, 1, 2) (2, 3, 2)
(3, 1, 3) (3, 2, 3)

Now we can see that our invariant holds for all possible moves. So we need a way of relating this to the entire sequence. I did this as follows:

Define a function f(a,b) = 1 if b > a , and -1 if b < a

Define the oscillating sum of a 99-gon labeled with numbers to be:

where is the number corresponding with the ith side. Because of the invariant we discovered, making a legal move does not affect this oscillating sum.

It's easy to see that the oscillating sum for the beginning state is 1, while the oscillating sum for the desired stage is -1. Thus, it cannot be achieved through through the legal moves described.

AIME – Number Theory

I’m going to outline my thought process for going through a problem, perhaps somebody will find it helpful. At times it’s at the point of rambling and such, but reviewing my thought process helps me refine it.

Consider the sequence of integers , where .

Let . Find the maximum value of .

I began by expression the two consecutive terms algebraically, which are:

and .

The key to cracking this problem is the fairly obvious observation that the GCD must divide both of these expressions. It’s safe to assume that the second term will never be a multiple of the first, as this would imply that divides . Lets call the GCD of this expression G.

We have that G must divide and . However, this implies that G also divides . This leads us to wishful thinking: What if G were actually ? Would this maximize it? It’s hard with the information we have to justify it now, but it’s worth looking into.

Assume that . Then:

must be an integer. Doing the division, we get:

Clearly the largest possible value of n is n = 200. This gives us G = 401.

We now have a very very good guess for our answer, but it is still only a guess. How can we be sure whether or not this is the largest? In our logic, it’s clear that given a specific n, a theoretical maximum G is 2n + 1. However, this isn’t actually the G for all numbers. Hypothetically, the numbers could get quite large, and our G will fall below our theoretical maximum of 2n + 1, but since n is so large anyway, it could still be greater than 401. At this point, it might be worth trying to show that 401 is actually the largest we can get.

But where to start? Maybe with some of our original ideas. Going back, we still have that G must divide 2n + 1, as well as . Can we turn this into algebra? I think so. Put:

$\frac{2n + 1}{a} = \frac{n^2 + 100}{b} = G$

Both of these must be integers. we can assume that a and b are relatively prime, or G wouldn’t be the largest divisor of both, but it’s not apparent how this will be helpful.

At this point, I decided that this was a dead end and took another step back. We want to show that the largest possible value is 401. This is still closely related to the idea of assuming that was the GCD. Perhaps we need to again work by narrowing down the GCD.

From other number theory problems, we know that if GCD(a,b) = G, then G must divide ax + by for any integers x and y. So if we got a linear combination of a_n and a_{n+1} that is 401, we’d be done.

So we need a linear combination of and . equal to 401. Playing around with them, we see that we need a way to get rid of the n terms.

At this point, I played around, keeping a list of combinations I had come across, until I found two which added together to get rid of all the n terms. Indeed, if we let :

Thus, the GCD of any two consecutive terms MUST divide 401.

Number Theory – Digits

I’m pretty lazy and don’t feel like writing the solution >.> but here is an easy yet interesting problem I did:

Prove that among any 18 consecutive three-digit numbers, at least one is divisible by the sum of its digits.

Simple GCD problem

Let be a sequence of natural numbers such that
where ..
Prove that for all n.
(Russia 1995)

Here, it helps a bunch that we know that . It gives us something clear and simple to aim for. The equation they gave us is also easy to work with, as we can plug in variables as well.

Since we know that for any integers a and b, each is a multiple of gcd(a, b), it is easy to come up with some interesting values to plug in for i and j. For example, we have:

Now we have shown that is a multiple of n for all n. So we can write:

, for some integer b.

We’d be done if we can show that this value of b is always 1, which leads us to generalize. We have:

for some integer n and i.

Is there a nice value of i which works? Yes! Let i = bn!

And we’re done, as we’ve shown that a sequence satisfies the conditions only if it is the natural numbers. Clearly the “if” requirement holds. QED.

SUMMER

I haven’t posted on here for a while for many reasons. Probably the biggest was that after studying for AP’s, seeing as it’s senior year, I was basically done, and couldn’t force myself to do any math, despite how much I love it. So I spent the last month or so having my gaming binge, and now, I’m ready to start it up again.

I got two new math books, Princeton’s Companion to Mathematics, and Putnam and Beyond. I’m still waiting for my USAMTS books to get in the mail. Hopefully those are good too. I’m planning on going through Putnam and Beyond over the summer. Princeton’s Companion will be more of a reference book, as of now I don’t plan on actually going through it. Maybe if I get really bored. Anyway, I’ll be posting more Putnam problems on here, and perhaps some other funky stuff too. Just letting you know, I’m still alive.