Mmm more sequences

Prove that any bounded sequence of real numbers has a convergent sub sequence. (A sub sequence is acquired from a sequence by deleting any number of entries without changing the order of the entries.

I’m not sure if this solution works or not, but it’s what I came up with!

Call our sequence . We have, for some real a and b, that for all n. Let’s call the range of this sequence

Now, define the midpoint of our current range as . It divides our sequence into two parts. We can consider those less than m, and those greater than or equal to m.

Each half will contain either a finite or infinite amount of terms. At least one will contain an infinite amount of terms since our sequence is infinite, so pick a half that has an infinite amount of terms.

Now, we can continue this process. After k times, we will have an infinite subsequence such that, for any positive integers n, m, . This means that we can always squeeze a subsequence o the sequence into a smaller and smaller range. In other words, it converges!

Sequences

The following is a common problem for those getting started working with sequences:

Find a formula for the general term of the sequence:
1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, …..
where the number n occurs n times in the sequence as shown.

The first step is to determine when the first occurrence of k will be. It’s not hard to show that this will be

Call the first occurrence of k . Also, define our sequence as . Then:

For all

or:

So we want our function for to be some sort of floor or something, such that it maps all of those numbers in the range to n. Now, we see that we can, in a way, invert this function. By this I mean, by inverting our function for . Since for all , , by inverting , it will map all of the first occurrence of each integer to the correct value, and then something weird for the other ones. By taking the floor of this, it will put it to the correct value:

Thus, we have:

PUTNAM!!!

…was an epic fail for me the other day. I only got A1 and B1. So the most I can get is a 20. T___T

On the bright side, it means I’m going to be posting on here more often, because now I’m motivated to work harder!! However finals are coming up, so not until Christmas time.

Putnam – Algebra

Prove that there are only a finite number of possibilities for the ordered triple , where are complex numbers satisfying the simultaneous equations:

and list all such triples
(Putnam 1986 B2)

We should start by trying to simplify this triple equality. The presence of the 2xy terms and such suggest factoring. Another obvious hint of factoring is that we want to show that there are finite values for the triple (x-y, y-z, z-x). This implies that for all solutions, this triple is basically the same. One obvious value for this triple is (0,0,0), when x=y=z. This implies that we’re going to factor an (x-y), (y-z), (z-x) some SOMEWHERE in some way, because eventually we’re going to want to show that (x-y) = 0, (y-z) = 0, (z-x) = 0.

This works out quite nicely. If we expand the product in each and subtract the squared term of each, we can factor as such (I’m not going to show it all):

This looks nicer, but it’s still hard to work with. So we need a new way of approaching it. What’s the most unnatural thing about this expression? The fact that we have a triple equality! This is going to be annoying to get a 0 on one side, in order to show that (x-y) and such equals 0. So what’s the best approach? Turn it into three regular equalities! If you see something that looks unnatural or difficult to work with, try turning it into something that you know how to work with.

The first of these equalities is:

Using difference of squares:

This looks like exactly what we want! The others factor in the exact same way, such that our three equalities are:

(by the way, I’m really tired as I’m typing this. So if there are any typos, please let me know. o_e)

We can now rewrite this as:

or
or
or

Now we have a finite amount of cases to examine! Hurrah hurrah!

Suppose we have x=y, y=z. This automatically implies that z=x, and thus T = (0,0,0).

Suppose we have x=y, y+z = 2x + 1. Substituting in the second yields:
.
Meaning T = (0, -1, 1). To confirm that the third equation is satisfied, we note that clearly z does not equal x, and that making the z = y+1 substitution satisfies the other equation.

Suppose we have x+y = 2z + 1, y=z. Substituting yields x = z + 1, and thus T = (1, 0, -1). Again, this satisfies the second part of the 3rd line of equalities.

Suppose we have x+y = 2z + 1, y+z = 2x + 1. Adding them yields:

Since this means the second part of the 3rd line of equalities cannot be true, we must have z = x. Substituting this into the first two equalities yields:

Thus T = (-1, 1, 0).

We have gone through all cases. Thus, our finite set of values for T are (0,0,0), (0, -1, 1), (1, 0, -1), and (-1, 1, 0). HURRAY OH GOD I’M SO TIRED RIGHT NOW.

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.