Mental math!!!

Throughout my entire, erm, “math career,” one of my largest weaknesses has been my inability to do mental math. Many strong competitors in the olympiad scene have very strong mental math abilities. This is probably a result of speed training and such, as MathCounts is almost all speed, and even AMC and AIME probably requires fast and accurate computations. I’ve always thought that I would be fine without training myself in this aspect, but seeing as I seem to have hit a wall in improving myself, I began wondering whether or not I should focus more on it.

As an experiment, I took a problem from Putnam and Beyond from one of the beginning sections, and decided to work on it only in my head. No calculator, no pencil or paper. Just mental math. And this includes coming up with a finalized proof:

Find the least positive integer n such that any set of n pairwise relatively prime integers greater than 1 and less than 2005 contains at least one prime number.

I began by reformulating the problem into finding the greatest positive integer n such that there exists a set of n pairwise relatively prime integers in the range, none of which is a prime number.

I then start thinking about how we could come up with such a set of integers. None of them are prime, so each one has at least two prime factors. However, they are relatively prime, so if one of these primes shows up in one integer, it can’t show up in any of the others. Also, we can assume that each integer has at most two prime factors. If it has three or more, we can simply remove them and still have a working set, as the number will still not be prime.

A good way to come up with the actual number is to come up with an “intuitive” set, and work from there. I decided to start with . This is where some of the mental math kicks in! Mentally multiplying numbers is a very useful skill. Here, I had to find the largest prime that, when squared, is still less than 2005. So a good estimate is 41. To square it mentally, I used the following trick:

Now we just keep using this method to square some more! We find that , and although we can kind of guess that 47 will go over, we can still confirm that

So now we have a set of 14 integers which works, using the 14 smallest primes. At this point, we should start thinking about whether or not we can get more.

Thinking about it, since , primes that are 47 or greater must be paired with smaller primes in order to create integers within our range. However, this means that each integer in the set MUST have one of these first 14 primes! Since each prime can show up in at most one number, 14 is our achieved upper bound!

Going back to our original problem, any set of 15 or more relatively prime integers between 1 and 2005 must have at least one prime number!

This problem actually took me a day just doing it in my head. Working on it forced me to address my mental math and concentration, both of which are terrible. I’m going to continue doing this to improve my skills! Q.E.D !!

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.