A game involves jumping to the right on the real number line. If $a$ and $b$ are real numbers and $b > a$, the cost of jumping from $a$ to $b$ is $b^3-ab^2$. For what real numbers $c$ can one travel from $0$ to $1$ in a finite number of jumps with total cost exactly $c$?
The most interesting part of this problem is getting the answer--proving that it works is one of those things that probably has an elegant solution, but the one you come up with while you're taking the exam is most likely going to be ugly.
The point is that the cost, $b^2(b-a)$, is the area of a rectangle with vertices on the $x$-axis at $a$ and $b$, and height $b^2$. So the total cost in jumping from $0$ to $1$ is the sum of the areas of a bunch of rectangles whose bases are all next to each other on the $x$-axis and whose upper right vertex is on the curve $y=x^2$. (Sorry I'm not industrious enough to figure out how to embed the right picture!) And that should stir a memory from calculus class...So the sums of these rectangles are always bigger than \[ \int_0^1 x^2 \, dx = 1/3. \] And of course they're always less than $1$. But in the limit, they should approach $1/3$, so we expect the answer to the question to be $c \in (1/3,1]$. At least we've already shown that the only representable $c$ are in $(1/3,1]$, so the idea will be to show that any such value of $c$ can be attained by judiciously choosing the steps along the way.
There's probably some elegant way to do this, but let's try the following: jump at $0, a, 2a, \cdots, na, 1$, where $n$ is some integer and $a$ is some real number such that $na \le 1$. Let's figure out the total cost.
Remembering that $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}6$, we can pretty quickly get the total cost to be \[ 1 - na + \frac{n(n+1)(2n+1)}6 a^3, \] and the only question is which values this can take. Well, this is a cubic polynomial in $a$. It's $1$ when $a=0$ and its derivative is $\frac{n(n+1)(2n+1)}2 a^2 - n$, which is negative for $a$ between $0$ and \[ \sqrt{\frac2{(n+1)(2n+1)}} = \sqrt{\frac1{(n+1)(n+1/2)}}, \] where it reaches its minimum over all positive values of $a$. (Notice that that value is less than $1/n$ as well.)
So the cubic polynomial, since it's continuous, can take on all values between its minimum and $1$. If we plug in the $a$ where it reaches its minimum value and simplify, we get that its minimum value is \[ 1- \frac23 n \sqrt{\frac2{(n+1)(2n+1)}} = 1 - \frac23 \sqrt{\frac1{(1+1/n)(1+1/2n)}}. \] Let's call that $y_n$. Then $y_n > 1/3$ for any $n$, but for $n$ sufficiently large, the expression inside the square root can get as close to $1$ as we want, so $y_n$ can get as close to $1/3$ as we want. Thus, to get any $c \in (1/3,1]$, first take $n$ large enough so that $y_n < c$, and then there will be some value of $a$ such that jumping at $0,a,2a,\cdots,na,1$ will give us $c$ (by e.g. the Intermediate Value Theorem, if you like).
See, I told you that the details of the proof wouldn't be all that nice. Actually, after checking the official solution I still like mine a little better (it's essentially the same, of course).
Top 200 scores:
(62,3,0),(63,13,59).
Saturday, March 31, 2012
Wednesday, March 28, 2012
Putnam 1998 B5
Let $N$ be the positive integer with $1998$ decimal digits, all of them $1$; that is, \[ N = 1111 \cdots 11. \] Find the thousandth digit after the decimal point of $\sqrt{N}$.
Our first B-side is much easier than it looks. There are lots of ways to approach this problem, but let's think approximately first. What's the idea here? The decimal expansion for $1/9$ has a bunch of $1$'s in it, and $\sqrt{1/9} = 1/3$. Hmm. If we just move the decimal point to the left...So $N$ is about $1/9 \cdot 10^{1998}$, so $\sqrt{N}$ is about $1/3 \cdot 10^{999}$. Well, we obviously need a better approximation.
So $N$ actually equals $1/9 (10^{1998}-1)$, so let's call its square root $1/3 (10^{999} - x)$, where we expect $x$ to be something really small. The idea will be to get a handle on the size of $x$. Here's the equation: \[ \begin{align*} \left( \frac13 ( 10^{999} - x) \right)^2 &= \frac19 (10^{1998}-1) \\ \frac19 (10^{1998} - 2x10^{999} + x^2) &= \frac19 (10^{1998}-1) \\ 2x 10^{999} -x^2 &= 1 \end{align*} \] That suggests that $x$ is about $10^{-999}/2$ (the $x^2$ is negligible). So if we had to guess at gunpoint right now, we'd say that the square root is about $\frac13 ( 10^{999} - 10^{-999}/2 )$, which in decimal expansion turns out to be $999$ 3's in front of the decimal point, then $999$ 3's to the right of it, then a 1, then a bunch of 6's. (Maybe it's easier to see the pattern if you replace $1998$ and $999$ by $2$ and $1$, $4$ and $2$, etc, so e.g. $\sqrt{11}$ is about $3.316$, $\sqrt{1111}$ is about $33.33166$, etc.) So our guess would be that the answer is $1$, and the rest of the problem is just about proving that our guess is right.
Let's try this: let $a = 1/3 (10^{999} - 10^{-999}/2)$, and see what $a-\sqrt{N}$ is. Well, $a^2-N = 10^{-1998}/36$, which is tiny, so $(a-\sqrt{N})(a+\sqrt{N}) = 10^{-1998}/36$, so $a-\sqrt{N} = 10^{-1998}/(36(a+\sqrt{N})) < 10^{-1998}$, so our approximation of $\sqrt{N}$ by $a$ should be good to at least $1998$ places to the right of the decimal point. That's plenty.
Top 199 scores:
(55,2,29),(8,0,105)
Our first B-side is much easier than it looks. There are lots of ways to approach this problem, but let's think approximately first. What's the idea here? The decimal expansion for $1/9$ has a bunch of $1$'s in it, and $\sqrt{1/9} = 1/3$. Hmm. If we just move the decimal point to the left...So $N$ is about $1/9 \cdot 10^{1998}$, so $\sqrt{N}$ is about $1/3 \cdot 10^{999}$. Well, we obviously need a better approximation.
So $N$ actually equals $1/9 (10^{1998}-1)$, so let's call its square root $1/3 (10^{999} - x)$, where we expect $x$ to be something really small. The idea will be to get a handle on the size of $x$. Here's the equation: \[ \begin{align*} \left( \frac13 ( 10^{999} - x) \right)^2 &= \frac19 (10^{1998}-1) \\ \frac19 (10^{1998} - 2x10^{999} + x^2) &= \frac19 (10^{1998}-1) \\ 2x 10^{999} -x^2 &= 1 \end{align*} \] That suggests that $x$ is about $10^{-999}/2$ (the $x^2$ is negligible). So if we had to guess at gunpoint right now, we'd say that the square root is about $\frac13 ( 10^{999} - 10^{-999}/2 )$, which in decimal expansion turns out to be $999$ 3's in front of the decimal point, then $999$ 3's to the right of it, then a 1, then a bunch of 6's. (Maybe it's easier to see the pattern if you replace $1998$ and $999$ by $2$ and $1$, $4$ and $2$, etc, so e.g. $\sqrt{11}$ is about $3.316$, $\sqrt{1111}$ is about $33.33166$, etc.) So our guess would be that the answer is $1$, and the rest of the problem is just about proving that our guess is right.
Let's try this: let $a = 1/3 (10^{999} - 10^{-999}/2)$, and see what $a-\sqrt{N}$ is. Well, $a^2-N = 10^{-1998}/36$, which is tiny, so $(a-\sqrt{N})(a+\sqrt{N}) = 10^{-1998}/36$, so $a-\sqrt{N} = 10^{-1998}/(36(a+\sqrt{N})) < 10^{-1998}$, so our approximation of $\sqrt{N}$ by $a$ should be good to at least $1998$ places to the right of the decimal point. That's plenty.
Top 199 scores:
(55,2,29),(8,0,105)
Tuesday, March 20, 2012
Putnam 1999 A6
The sequence $(a_n)_{n \ge 1}$ is defined by $a_1 = 1$, $a_2 = 2$, $a_3 = 24$, and, for $n \ge 4$, \[ a_n = \frac{6a_{n-1}^2 a_{n-3} - 8 a_{n-1} a_{n-2}^2}{a_{n-2}a_{n-3}} . \] Show that, for all $n$, $a_n$ is an integer multiple of $n$.
Two parts to this problem: find a closed-form formula for $a_n$, and then show that $n$ divides $a_n$. It's not immediately clear that we'll be able to find a closed-form formula, and there might be a way to do the problem without it, but trying to find one will give us some insight even if we fail.
If we simplify the equality above, we get $a_n = \frac{6a_{n-1}^2}{a_{n-2}} - \frac{8a_{n-1} a_{n-2}}{a_{n-3}}$. Hm, what if we divide everything by $a_{n-1}$? That gives \[ \frac{a_n}{a_{n-1}} = 6 \frac{a_{n-1}}{a_{n-2}} - 8 \frac{a_{n-2}}{a_{n-3}}. \] Ah, that looks less complicated. In fact this is a recurrence relation on a related sequence, $b_n = \frac{a_n}{a_{n-1}}$. We've got $b_2 = 2$, $b_3 = 12$, and $b_n = 6 b_{n-1} - 8 b_{n-2}$ for $n \ge 4$.
Now here's where you have to know a little bit of elementary stuff about recurrence relations. I think this is useful enough that it should get its own post. I'll write one after this problem using this particular recurrence as an example. Let's skip to the solution for now: $b_n = 4^{n-1} - 2^{n-1} = 2^{n-1}(2^{n-1}-1)$. And since $a_n$ is the product of all the $b_k$ from $2$ up to $n$, we get \[ a_n = 2^{n(n-1)/2} (2^{n-1}-1)(2^{n-2}-1)(\cdots)(2^2-1). \] On to part two: we just need to show that $n$ divides this gigantic integer. Not so hard here, although we need a nice fact from number theory. First let's write $n = 2^k m$, where $m$ is odd (that is, separate out the $2$'s from the prime factorization of $n$). We can also assume that $n \ge 3$ because it's clear that $1$ divides $a_1$ and $2$ divides $a_2$. Now clearly $k < n(n-1)/2$ for $n \ge 3$ (since for instance $k < n$), so $2^k$ divides the giant product. So we just need to show that $m$ divides it as well. This boils down to showing that $m$ divides $2^k-1$ for some $k < n$; and now a nice elementary number theory fact comes to the rescue, namely Euler's theorem (or Fermat's generalized little theorem, or whatever you like to call it): \[ m| (a^{\varphi(m)} -1) \, \text{for all $a$ relatively prime to $m$,} \] where $\varphi(m)$ is Euler's $\varphi$ function, equal to the number of positive integers less than $m$ relatively prime to $m$. (When $m$ is prime, $\varphi(m) = m-1$, and we get what is generally called Fermat's little theorem.)
Anyway, $\varphi(m)$ is certainly less than $m$, which is $\le n$, and we can take $a=2$ which is relatively prime to $m$, so $m$ divides one of the factors in the giant product and we're done.
Usually A6 is the hardest problem on the first side, but this one was a paper tiger (A5 turned out to be the killer in 1999). We won't be doing many A6's or B6's, so we can savor the moment.
Top 205 scores:
(31,11,9),(1,5,148)
Two parts to this problem: find a closed-form formula for $a_n$, and then show that $n$ divides $a_n$. It's not immediately clear that we'll be able to find a closed-form formula, and there might be a way to do the problem without it, but trying to find one will give us some insight even if we fail.
If we simplify the equality above, we get $a_n = \frac{6a_{n-1}^2}{a_{n-2}} - \frac{8a_{n-1} a_{n-2}}{a_{n-3}}$. Hm, what if we divide everything by $a_{n-1}$? That gives \[ \frac{a_n}{a_{n-1}} = 6 \frac{a_{n-1}}{a_{n-2}} - 8 \frac{a_{n-2}}{a_{n-3}}. \] Ah, that looks less complicated. In fact this is a recurrence relation on a related sequence, $b_n = \frac{a_n}{a_{n-1}}$. We've got $b_2 = 2$, $b_3 = 12$, and $b_n = 6 b_{n-1} - 8 b_{n-2}$ for $n \ge 4$.
Now here's where you have to know a little bit of elementary stuff about recurrence relations. I think this is useful enough that it should get its own post. I'll write one after this problem using this particular recurrence as an example. Let's skip to the solution for now: $b_n = 4^{n-1} - 2^{n-1} = 2^{n-1}(2^{n-1}-1)$. And since $a_n$ is the product of all the $b_k$ from $2$ up to $n$, we get \[ a_n = 2^{n(n-1)/2} (2^{n-1}-1)(2^{n-2}-1)(\cdots)(2^2-1). \] On to part two: we just need to show that $n$ divides this gigantic integer. Not so hard here, although we need a nice fact from number theory. First let's write $n = 2^k m$, where $m$ is odd (that is, separate out the $2$'s from the prime factorization of $n$). We can also assume that $n \ge 3$ because it's clear that $1$ divides $a_1$ and $2$ divides $a_2$. Now clearly $k < n(n-1)/2$ for $n \ge 3$ (since for instance $k < n$), so $2^k$ divides the giant product. So we just need to show that $m$ divides it as well. This boils down to showing that $m$ divides $2^k-1$ for some $k < n$; and now a nice elementary number theory fact comes to the rescue, namely Euler's theorem (or Fermat's generalized little theorem, or whatever you like to call it): \[ m| (a^{\varphi(m)} -1) \, \text{for all $a$ relatively prime to $m$,} \] where $\varphi(m)$ is Euler's $\varphi$ function, equal to the number of positive integers less than $m$ relatively prime to $m$. (When $m$ is prime, $\varphi(m) = m-1$, and we get what is generally called Fermat's little theorem.)
Anyway, $\varphi(m)$ is certainly less than $m$, which is $\le n$, and we can take $a=2$ which is relatively prime to $m$, so $m$ divides one of the factors in the giant product and we're done.
Usually A6 is the hardest problem on the first side, but this one was a paper tiger (A5 turned out to be the killer in 1999). We won't be doing many A6's or B6's, so we can savor the moment.
Top 205 scores:
(31,11,9),(1,5,148)
Sunday, March 11, 2012
Putnam 1999 A4
Sum the series \[ \sum_{m=1}^{\infty} \sum_{n=1}^{\infty} \frac{m^2n}{3^m(n3^m + m3^n)}. \]
That denominator looks pretty ugly and it doesn't seem like there's much of a way to simplify it right away. One thing to notice, though, is that it's nearly symmetric--if we interchange $m$ and $n$, we get something that looks pretty similar.
So what happens if, for any $x$ and $y$, we add up the terms where $(m,n) = (x,y)$ and $(m,n) = (y,x)$? (We should probably assume that $x\ne y$ for now; we'll have to handle those terms separately.) Let's see: that's \[ \frac{x^2y}{3^x(y3^x + x3^y)} + \frac{y^2x}{3^y(x3^y+y3^x)} = \frac{xy}{x3^y+y3^x} \left( \frac{x}{3^x} + \frac{y}{3^y} \right). \] That looks nice and symmetric.
Actually, it looks like we can get more things that look like $\frac{x}{3^x}$ if we divide the top and bottom of the left fraction by $3^x3^y$. That gets us \[ \frac{(x/3^x)(y/3^y)}{(x/3^x) + (y/3^y)} \left( \frac{x}{3^x} + \frac{y}{3^y} \right) = \frac{x}{3^x} \frac{y}{3^y}. \] Well, that's really simple.
Now we have to be careful. What do we actually get in the sum? If $x=y$ then we get $\frac{x^3}{2x3^{2x}} = \frac{x^2}{2 \cdot 3^{2x}}$, and for each pair of unequal $x$ and $y$ we get $\frac{x}{3^x} \frac{y}{3^y}$. So let's call the sum $S$; then we're saying \[ S = \sum_{x=1}^{\infty} \frac{x}{2 \cdot 3^x} + \sum_{x < y} \frac{x}{3^x} \frac{y}{3^y},\] and now we can play a slightly fancy trick that might not be obvious: if we want to change that second sum to sum over all pairs $(x,y)$ where $x \ne y$, we can notice that since the summand is symmetric, we'd just double our contribution. In other words, \[ \sum_{x \ne y} \frac{x}{3^x} \frac{y}{3^y} = 2 \sum_{x < y} \frac{x}{3^x} \frac{y}{3^y}. \] We're ready to put it all together now: \[ S = \sum_{x=1}^{\infty} \frac{x^2}{2 \cdot 3^x} + \sum_{x \ne y} \frac12 \frac{x}{3^x} \frac{y}{3^y} \], and we can bring the $x=y$ terms back into the fold, since $\frac12 \frac{x}{3^x} \frac{y}{3^y} =\frac{x^2}{2 \cdot 3^{2x}}$ when $x=y$. Finally: \[ S = \frac12 \sum_{x=1}^{\infty} \sum_{y=1}^{\infty} \frac{x}{3^x} \frac{y}{3^y} = \frac12 \left( \sum_{x=1}^{\infty} \frac{x}{3^x} \right) \left( \sum_{y=1}^{\infty} \frac{y}{3^y} \right),\] so the answer is just $T^2/2$, where $T = \sum_{n=1}^{\infty} \frac{n}{3^n}$.
If you're still with me, you probably know how to compute this sum. It's a calculus thing, really. In fact $\sum_{n=1}^{\infty} n x^n = \frac{x}{(1-x)^2}$ for $|x|<1$; start with the geometric series, take the derivative, and multiply by $x$. So plugging in $x=1/3$ gives $T = 3/4$ and hence $S = 9/32$.
It's not a bad idea to check a few terms to see if this looks like the right order of magnitude for $S$; it's easy to lose a factor of $2$ here or there. This problem is not too easy, and it requires some attention to detail to make sure you're counting everything right. If you want to see what a very clean version of this same solution looks like, check the Putnam solutions page. It's usually a lot easier to write a very pretty and terse version of a solution once you've understood the original long-winded one you came up with, but we don't have time for refinements--there are five other problems to do and that one might have taken us an hour!
Top 205 scores:
(33,27,3),(3,2,137)
That denominator looks pretty ugly and it doesn't seem like there's much of a way to simplify it right away. One thing to notice, though, is that it's nearly symmetric--if we interchange $m$ and $n$, we get something that looks pretty similar.
So what happens if, for any $x$ and $y$, we add up the terms where $(m,n) = (x,y)$ and $(m,n) = (y,x)$? (We should probably assume that $x\ne y$ for now; we'll have to handle those terms separately.) Let's see: that's \[ \frac{x^2y}{3^x(y3^x + x3^y)} + \frac{y^2x}{3^y(x3^y+y3^x)} = \frac{xy}{x3^y+y3^x} \left( \frac{x}{3^x} + \frac{y}{3^y} \right). \] That looks nice and symmetric.
Actually, it looks like we can get more things that look like $\frac{x}{3^x}$ if we divide the top and bottom of the left fraction by $3^x3^y$. That gets us \[ \frac{(x/3^x)(y/3^y)}{(x/3^x) + (y/3^y)} \left( \frac{x}{3^x} + \frac{y}{3^y} \right) = \frac{x}{3^x} \frac{y}{3^y}. \] Well, that's really simple.
Now we have to be careful. What do we actually get in the sum? If $x=y$ then we get $\frac{x^3}{2x3^{2x}} = \frac{x^2}{2 \cdot 3^{2x}}$, and for each pair of unequal $x$ and $y$ we get $\frac{x}{3^x} \frac{y}{3^y}$. So let's call the sum $S$; then we're saying \[ S = \sum_{x=1}^{\infty} \frac{x}{2 \cdot 3^x} + \sum_{x < y} \frac{x}{3^x} \frac{y}{3^y},\] and now we can play a slightly fancy trick that might not be obvious: if we want to change that second sum to sum over all pairs $(x,y)$ where $x \ne y$, we can notice that since the summand is symmetric, we'd just double our contribution. In other words, \[ \sum_{x \ne y} \frac{x}{3^x} \frac{y}{3^y} = 2 \sum_{x < y} \frac{x}{3^x} \frac{y}{3^y}. \] We're ready to put it all together now: \[ S = \sum_{x=1}^{\infty} \frac{x^2}{2 \cdot 3^x} + \sum_{x \ne y} \frac12 \frac{x}{3^x} \frac{y}{3^y} \], and we can bring the $x=y$ terms back into the fold, since $\frac12 \frac{x}{3^x} \frac{y}{3^y} =\frac{x^2}{2 \cdot 3^{2x}}$ when $x=y$. Finally: \[ S = \frac12 \sum_{x=1}^{\infty} \sum_{y=1}^{\infty} \frac{x}{3^x} \frac{y}{3^y} = \frac12 \left( \sum_{x=1}^{\infty} \frac{x}{3^x} \right) \left( \sum_{y=1}^{\infty} \frac{y}{3^y} \right),\] so the answer is just $T^2/2$, where $T = \sum_{n=1}^{\infty} \frac{n}{3^n}$.
If you're still with me, you probably know how to compute this sum. It's a calculus thing, really. In fact $\sum_{n=1}^{\infty} n x^n = \frac{x}{(1-x)^2}$ for $|x|<1$; start with the geometric series, take the derivative, and multiply by $x$. So plugging in $x=1/3$ gives $T = 3/4$ and hence $S = 9/32$.
It's not a bad idea to check a few terms to see if this looks like the right order of magnitude for $S$; it's easy to lose a factor of $2$ here or there. This problem is not too easy, and it requires some attention to detail to make sure you're counting everything right. If you want to see what a very clean version of this same solution looks like, check the Putnam solutions page. It's usually a lot easier to write a very pretty and terse version of a solution once you've understood the original long-winded one you came up with, but we don't have time for refinements--there are five other problems to do and that one might have taken us an hour!
Top 205 scores:
(33,27,3),(3,2,137)
Sunday, March 4, 2012
Putnam 2001 A5, part 2
When we left off, we had seen that $(a,n) = (13,2)$ solved the equation $a^{n+1} - (a+1)^n = 2001$, and any other positive integer solution pair had to be of the form $(7,2k+1)$ or $(13,2k)$ for some positive integer $k$. It remains to rule out all of the rest of these.
But wait! Let's look mod $3$; since both of our $a$'s reduce to $1$ mod $3$, we get $1-2^n \equiv 0$ mod $3$, which happens if and only if $n$ is even. So $(7,2k+1)$ doesn't work for any $k$.
It seems like we won't be able to do the last part, ruling out all the other $(13,2k)$, using congruence conditions only, because using congruence conditions usually either rules out all solutions or doesn't rule out infinitely many, and we already know there's at least one solution. (SPOILER ALERT: it's easy if you know the right congruence! To avoid the following discussion, try looking mod 8. The official Putnam solutions page doesn't miss any tricks.)
Well, how about bounding the possible values of $n$ when $a=13$? Does $13^{n+1} - 14^n$ grow without bound? Let's see: if we tried to compare $13^{n+1} > 14^n$, this would reduce to $13 > (1 + 1/13)^n$. Huh, it looks like for large enough $n$, the $14^n$ term actually gets bigger than the $13^{n+1}$ term, so the left side is negative.
How large is large enough? Well, the expansion of $(1+1/13)^n$ starts off $1 + n/13 + \cdots$, and all the other terms are positive, so if $n \ge 156$ then the left side of the original equation is negative. So we just need to rule out all $n < 156$.
This can be done using congruence conditions. Let's just mash together as many congruences as we can. So:
Mod $5$: $3^{n+1} - 4^n \equiv 1$, write out powers of $3$ $\Rightarrow$ $n \equiv 2$ mod $4$
Mod $23$: $13^{n+1} \equiv 14^n$; write out powers of $13$ $\Rightarrow$ $n \equiv 2$ mod $22$
Mod $29$: $13^{n+1} \equiv 14^n$; write out powers of $13$ $\Rightarrow$ $n \equiv 2$ mod $28$
Putting these together gives $n \equiv 2$ mod $308$, which means that if $n$ is not $2$, then it can't be less than $156$, and we're done.
As you might expect, this one was a little tougher for the contestants. I'm a little surprised at just how tough it was, though--only 31 of the top 200 got (nearly) full credit.
Top 200 scores:
(12,9,10),(9,41,119)
But wait! Let's look mod $3$; since both of our $a$'s reduce to $1$ mod $3$, we get $1-2^n \equiv 0$ mod $3$, which happens if and only if $n$ is even. So $(7,2k+1)$ doesn't work for any $k$.
It seems like we won't be able to do the last part, ruling out all the other $(13,2k)$, using congruence conditions only, because using congruence conditions usually either rules out all solutions or doesn't rule out infinitely many, and we already know there's at least one solution. (SPOILER ALERT: it's easy if you know the right congruence! To avoid the following discussion, try looking mod 8. The official Putnam solutions page doesn't miss any tricks.)
Well, how about bounding the possible values of $n$ when $a=13$? Does $13^{n+1} - 14^n$ grow without bound? Let's see: if we tried to compare $13^{n+1} > 14^n$, this would reduce to $13 > (1 + 1/13)^n$. Huh, it looks like for large enough $n$, the $14^n$ term actually gets bigger than the $13^{n+1}$ term, so the left side is negative.
How large is large enough? Well, the expansion of $(1+1/13)^n$ starts off $1 + n/13 + \cdots$, and all the other terms are positive, so if $n \ge 156$ then the left side of the original equation is negative. So we just need to rule out all $n < 156$.
This can be done using congruence conditions. Let's just mash together as many congruences as we can. So:
Mod $5$: $3^{n+1} - 4^n \equiv 1$, write out powers of $3$ $\Rightarrow$ $n \equiv 2$ mod $4$
Mod $23$: $13^{n+1} \equiv 14^n$; write out powers of $13$ $\Rightarrow$ $n \equiv 2$ mod $22$
Mod $29$: $13^{n+1} \equiv 14^n$; write out powers of $13$ $\Rightarrow$ $n \equiv 2$ mod $28$
Putting these together gives $n \equiv 2$ mod $308$, which means that if $n$ is not $2$, then it can't be less than $156$, and we're done.
As you might expect, this one was a little tougher for the contestants. I'm a little surprised at just how tough it was, though--only 31 of the top 200 got (nearly) full credit.
Top 200 scores:
(12,9,10),(9,41,119)
Putnam 2001 A5, part 1
Prove that there are unique positive integers $a, n$ such that $a^{n+1}-(a+1)^n = 2001$.
Now this is a truly enjoyable problem. Short, easy statement, interesting proof, lovely result (of course I have a fondness for Diophantine equations, so I may be a little biased here).
As with many Putnam problems, it's not obvious where to start. With many of these Diophantine equation problems, it usually helps to consider the equation mod $m$, for some carefully chosen number(s) $m$. (This is a technique that you must familiarize yourself with in order to solve many of these problems, and it's completely elementary--see e.g. http://www.math.rutgers.edu/~erowland/modulararithmetic.html for a brief introduction.)
Prime values of $m$ are usually easiest. Which primes would simplify the equation nicely? Well, one obvious start is primes dividing $2001$. So let's see which ones those would be...$2001$ is divisible by $3$, and then it may take awhile to find more factors after that (we may even start to suspect that $667$ is prime), but eventually we can get $2001 = 3 \cdot 23\cdot 29$. (After you get this by trial division, you can check by noticing that $26^2 = 676$, and $23 \cdot 29 = (26-3)(26+3) = 26^2 - 9 = 676 - 9$.) Hopefully this doesn't take too long--three hours can go by awfully quickly if we spend too much of it factoring three-digit integers!
So if we look mod 3, mod 23, or mod 29, we get $a^{n+1}-(a+1)^n \equiv 0$, and it's not immediately clear how that is going to help us. Although it's frustrating to have done all that work for what seems to be no reward, let's shelve that for the time being.
While doing that reduction, we might realize that it would be better if we could kill one of the terms on the left side. Aha--so let's try taking the equation mod $a$ instead. Notice that $a \equiv 0$ and $a+1 \equiv 1$, so the left side becomes $-1$. So we just get $-1 \equiv 2001$ mod $a$, so $a$ divides $2002$. (To see this without using modular arithmetic, just think of expanding the left side in powers of $a$; then the constant term will be $-1$ and everything else will be divisible by $a$, so if you add $1$ to both sides the left side will be divisible by $a$ and the right side will be $2002$.)
Well, that certainly narrows it down, but $2002$ has a lot of divisors. In fact, $2002 = 2 \cdot 7 \cdot 11 \cdot 13$, so it has $16$ different positive divisors. (How did I get this number without writing them all down? Exercise for the reader!)
If we wanted to kill off the other term, we could take the equation mod $a+1$. Then we get $(-1)^{n+1} \equiv 2001$ mod $a+1$, so there are two cases: $n$ is odd and $a+1$ divides $2000$, or $n$ is even and $a+1$ divides $2002$.
Hmm, so that narrows down the candidates for $a$ even more. We need a divisor $a$ of $2002$ such that $a+1$ divides $2000$ or $2002$. Looks like we're going to have to write down all the divisors of $2002$. If you did the parenthetical exercise above, you should have some idea of how to write them all down systematically, so let's cut to the chase here: \[a = 1, 2, 7, 11, 13, 14, 22, 26, 77, 91, 143, 154, 182, 286, 1001, 2002. \] Phew!
So which of these have the property that $a+1$ is a divisor of $2000$ or $2002$? It turns out that only $a=1, 7, 13$ have this property (you do have to go through and check each of these separately, but each check is very quick). And we can throw out $a=1$ right away: $1^{n+1}-2^n = 1-2^n$ can't equal $2001$ for any positive integer $n$, since it's definitely negative. All right, that's real progress! We've shown that if $a, n$ satisfy the conditions of the problem, then $a=7$ (and $n$ is odd) or $a=13$ (and $n$ is even).
We might start to wonder now what the solution is. It can't hurt to try small values of $n$ for each of our $a$'s; this will also give us a bit of a sense of how big the left side gets. Well, notice that $13^3$ is about $2000$. In fact, if we try $n=2$, we can see that $13^3-14^2 = 2197-196 = 2001$. Voila--there is our solution, and now all we have to do is show that it's unique.
Continued in the next post.
Now this is a truly enjoyable problem. Short, easy statement, interesting proof, lovely result (of course I have a fondness for Diophantine equations, so I may be a little biased here).
As with many Putnam problems, it's not obvious where to start. With many of these Diophantine equation problems, it usually helps to consider the equation mod $m$, for some carefully chosen number(s) $m$. (This is a technique that you must familiarize yourself with in order to solve many of these problems, and it's completely elementary--see e.g. http://www.math.rutgers.edu/~erowland/modulararithmetic.html for a brief introduction.)
Prime values of $m$ are usually easiest. Which primes would simplify the equation nicely? Well, one obvious start is primes dividing $2001$. So let's see which ones those would be...$2001$ is divisible by $3$, and then it may take awhile to find more factors after that (we may even start to suspect that $667$ is prime), but eventually we can get $2001 = 3 \cdot 23\cdot 29$. (After you get this by trial division, you can check by noticing that $26^2 = 676$, and $23 \cdot 29 = (26-3)(26+3) = 26^2 - 9 = 676 - 9$.) Hopefully this doesn't take too long--three hours can go by awfully quickly if we spend too much of it factoring three-digit integers!
So if we look mod 3, mod 23, or mod 29, we get $a^{n+1}-(a+1)^n \equiv 0$, and it's not immediately clear how that is going to help us. Although it's frustrating to have done all that work for what seems to be no reward, let's shelve that for the time being.
While doing that reduction, we might realize that it would be better if we could kill one of the terms on the left side. Aha--so let's try taking the equation mod $a$ instead. Notice that $a \equiv 0$ and $a+1 \equiv 1$, so the left side becomes $-1$. So we just get $-1 \equiv 2001$ mod $a$, so $a$ divides $2002$. (To see this without using modular arithmetic, just think of expanding the left side in powers of $a$; then the constant term will be $-1$ and everything else will be divisible by $a$, so if you add $1$ to both sides the left side will be divisible by $a$ and the right side will be $2002$.)
Well, that certainly narrows it down, but $2002$ has a lot of divisors. In fact, $2002 = 2 \cdot 7 \cdot 11 \cdot 13$, so it has $16$ different positive divisors. (How did I get this number without writing them all down? Exercise for the reader!)
If we wanted to kill off the other term, we could take the equation mod $a+1$. Then we get $(-1)^{n+1} \equiv 2001$ mod $a+1$, so there are two cases: $n$ is odd and $a+1$ divides $2000$, or $n$ is even and $a+1$ divides $2002$.
Hmm, so that narrows down the candidates for $a$ even more. We need a divisor $a$ of $2002$ such that $a+1$ divides $2000$ or $2002$. Looks like we're going to have to write down all the divisors of $2002$. If you did the parenthetical exercise above, you should have some idea of how to write them all down systematically, so let's cut to the chase here: \[a = 1, 2, 7, 11, 13, 14, 22, 26, 77, 91, 143, 154, 182, 286, 1001, 2002. \] Phew!
So which of these have the property that $a+1$ is a divisor of $2000$ or $2002$? It turns out that only $a=1, 7, 13$ have this property (you do have to go through and check each of these separately, but each check is very quick). And we can throw out $a=1$ right away: $1^{n+1}-2^n = 1-2^n$ can't equal $2001$ for any positive integer $n$, since it's definitely negative. All right, that's real progress! We've shown that if $a, n$ satisfy the conditions of the problem, then $a=7$ (and $n$ is odd) or $a=13$ (and $n$ is even).
We might start to wonder now what the solution is. It can't hurt to try small values of $n$ for each of our $a$'s; this will also give us a bit of a sense of how big the left side gets. Well, notice that $13^3$ is about $2000$. In fact, if we try $n=2$, we can see that $13^3-14^2 = 2197-196 = 2001$. Voila--there is our solution, and now all we have to do is show that it's unique.
Continued in the next post.
Putnam 1995 A1
Let $S$ be a set of real numbers which is closed under multiplication (that is, if $a$ and $b$ are in $S$, then so is $ab$). Let $T$ and $U$ be disjoint subsets of $S$ whose union is $S$. Given that the product of any three (not necessarily distinct) elements of $T$ is in $T$ and that the product of any three elements of $U$ is in $U$, show that at least one of the two subsets $T$, $U$ is closed under multiplication.
Closure under multiplication is a property that most math majors are pretty familiar with, as it comes up in abstract algebra courses as a property of groups. The only real pitfall to avoid here is assuming something implicitly/unconsciously. So let's see: we'd like to show that one of the two subsets is closed under multiplication. Here, proof by contradiction seems like a good idea, because it lets us get our hands on actual elements.
That is, if we assume that $T$ and $U$ are not closed under multiplication, we get elements $t_1, t_2 \in T$ such that $t_1t_2$ is not in $T$. Since $T$ and $U$ are disjoint and their union is $S$, that means $t_1t_2 \in U$. Similarly we can get elements $u_1, u_2 \in U$ such that $u_1u_2$ is not in $U$, which means that it must be in $T$.
It's a good sign that we've used some of the properties of $T$ and $U$ already. So now we have these four elements--what should we do with them? Well, we haven't used the "triple product" property yet, so we need to multiply some combination of these elements so we can use it.
The obvious choice is the product (call it $p$) of all four:
\[ p = (t_1 t_2)(u_1 u_2). \] So notice that since $(u_1 u_2) \in T$, $p$ is the product of three elements of $T$, so it has to be in $T$. But since $(t_1 t_2) \in U$, $p$ is also the product of three elements of $U$, so it has to be in $U$. But $T$ and $U$ are disjoint. Contradiction!
This was the first Putnam problem I ever solved, so it's reasonable for it to be the first problem on the blog.
I'll finish each Putnam problem discussion with a measure of how others did on the problem, which comes from the official Putnam website. The numbers below represent the number of the top 200 participants (plus ties) who got the scores 10, 9, 8, and 2, 1, 0, respectively. It is a quirk of the Putnam exam that scores of 3, 4, 5, 6, or 7 are not given at all! So for instance 64 of the top 204 participants got a score of 9 out of 10 for this problem.
Top 204 by score:
(115,64,20), (1,0,4)
Closure under multiplication is a property that most math majors are pretty familiar with, as it comes up in abstract algebra courses as a property of groups. The only real pitfall to avoid here is assuming something implicitly/unconsciously. So let's see: we'd like to show that one of the two subsets is closed under multiplication. Here, proof by contradiction seems like a good idea, because it lets us get our hands on actual elements.
That is, if we assume that $T$ and $U$ are not closed under multiplication, we get elements $t_1, t_2 \in T$ such that $t_1t_2$ is not in $T$. Since $T$ and $U$ are disjoint and their union is $S$, that means $t_1t_2 \in U$. Similarly we can get elements $u_1, u_2 \in U$ such that $u_1u_2$ is not in $U$, which means that it must be in $T$.
It's a good sign that we've used some of the properties of $T$ and $U$ already. So now we have these four elements--what should we do with them? Well, we haven't used the "triple product" property yet, so we need to multiply some combination of these elements so we can use it.
The obvious choice is the product (call it $p$) of all four:
\[ p = (t_1 t_2)(u_1 u_2). \] So notice that since $(u_1 u_2) \in T$, $p$ is the product of three elements of $T$, so it has to be in $T$. But since $(t_1 t_2) \in U$, $p$ is also the product of three elements of $U$, so it has to be in $U$. But $T$ and $U$ are disjoint. Contradiction!
This was the first Putnam problem I ever solved, so it's reasonable for it to be the first problem on the blog.
I'll finish each Putnam problem discussion with a measure of how others did on the problem, which comes from the official Putnam website. The numbers below represent the number of the top 200 participants (plus ties) who got the scores 10, 9, 8, and 2, 1, 0, respectively. It is a quirk of the Putnam exam that scores of 3, 4, 5, 6, or 7 are not given at all! So for instance 64 of the top 204 participants got a score of 9 out of 10 for this problem.
Top 204 by score:
(115,64,20), (1,0,4)
Saturday, March 3, 2012
Subscribe to:
Posts (Atom)