## 2012 Math Prize for Girls: #16-20

Here are comments and solutions to (some of) the problems on the 2012 Math Prize for Girls contest that took place at MIT on September 22.

I’m going to try to resolve the problems in a straightforward, lo-tech way. I might indicate some alternative solutions. And I’ll discuss what math you need to study if you had trouble with the problem.

I hope to cover all the problems before next year’s contest.

Problem #16

This problem is a bit peculiar. It almost seems as though the point is obfuscation more than anything else because it simply asks for the area of an ellipse with major axis 20/3 and minor axis 16/3, and the area of such an ellipse is $\pi \cdot \frac{10}{3} \cdot \frac{8}{3} = \frac{80}{9} \pi$.

If you didn’t realize this, it probably means that you were thrown by the way in which this fact was communicated, using the language of complex numbers and introducing a mysterious new term, “three-presentable.” There’s no actual need for the machinery of complex numbers to solve this problem. You just need to be familiar enough with complex numbers to be able to realize that the set T is an ellipse.

Don’t let mysterious terms intimidate you. So let’s just ignore “three-presentable” until we really need to use it (and we’ll see that we never do need it!).

The complex numbers of absolute value 3 are given by $3e^{it}$ for $0 \le t < 2\pi$. So T is the set of complex numbers of the form

$3e^{it} - \frac{1}{3e^{it}} = 3e^{it} - \frac{1}{3}e^{-it} = (3 - 1/3)\cos t + i(3 + 1/3)\sin t$.

If you weren’t able to see the ellipse before, can you see it now? The points $((3 - 1/3)\cos t, (3 + 1/3)\sin t)$ for $0 \le t < 2\pi$ constitute an ellipse. If you’re more used to seeing the Cartesian equation representation of an ellipse, note that if $x = (8/3)\cos t$ and $y = (10/3)\sin t$, then

$\frac{9}{64}x^2 + \frac{9}{100}y^2 = 1$.

I suppose if you really want to use the machinery of complex numbers, you could compute the contour integral $\frac{1}{2i} \oint_T \bar{z} dz$, and then you won’t even have to realize that you’re finding the area of an ellipse. If you don’t know contour integration, doesn’t this fact alone make you want to rush out and learn it?

If you had trouble with this problem, brush up on your facility with complex numbers…and study contour integration! It’s one of the most beautiful subjects.

Problem #17

There’s no way contest designers would expect participants to make $17^3$ substitutions to determine which are solutions and which aren’t. There must be another way. Here we’re asked to find solutions to a polynomial equation. As soon as you progress past solving linear equations, an important and powerful concept appears: factoring. A natural thing to do is to try to factor the polynomial

$P(a, b, c) = a^3 + b^3 + c^3 + 2abc - a^2b - a^2c - b^2c - ab^2 - ac^2 - bc^2$.

Normally, a polynomial that appears out of the blue will not factor. But, this polynomial doesn’t appear out of the blue. This polynomial lives in a math contest! Some key observations help us. First, the polynomial is homogeneous of degree 3. Second, it is symmetric. This suggests factoring as:

$(ma + nb + nc)(na + mb + nc)(na + nb + mc)$

because if it has a linear factor, by symmetry, it would also have permutations of that linear factor as factors as well. Since it is of degree 3, two of the coefficients in the linear factor must be equal (otherwise there would be 6 permutations of the factor which would lead to a sixth degree polynomial). At this point, rather than solving for $m$ and $n$, I just fiddled with some possibilities and found that:

$P(a, b, c) = (a - b - c)(-a + b - c)(-a -b +c)$.

We can count solutions where $c$ is greater than $a$ and $b$ and exploit symmetry to figure out the total number of solutions. For a fixed value of $c$, there are $c-1$ pairs of values $(a, b)$ that make the 3rd factor $c - a - b$ zero. This also implies that $2 \le c \le 17$. So there are 1 + 2 + 3 + … + 16 solutions where $c$ is greater than $a$ or $b$, for a total of 17(8) such solutions. Notice that in all these cases, $c$ is the unique largest value among $a$, $b$, and $c$. By symmetry, this means that any solution $(a, b, c)$ to $P(a, b, c) = 0$ has a unique maximal component, so to find all the solutions, we just have to multiply 17(8) by 3 to allow for the 3 components $a$, $b$, or $c$ to each have a chance to be maximal. The answer is 408.

Problem #18

Let’s solve the more general problem obtained by replacing “10” in the original problem statement with “N,” where N is a positive integer.

Let $E_k$ denote the expected number of steps it will take Sherry to reach N starting at k.

Note that $E_1 = 1 + E_2$, because from 1, Sherry will always take one step to move to 2, so the expected number of steps from 1 will be 1 more than the expected number of steps from 2.

Similar reasoning enables us to see that $E_2 = 1 + 0.5(E_1 + E_3)$ because from 2, there’s a 50-50 chance of going to 1 or 3 after 1 step. And, for all $2 \le k \le N-1$, we have $E_k = 1 + 0.5(E_{k-1} + E_{k+1})$. When $k = N$, Sherry doesn’t have to move to get to N, so $E_N = 0$.

So, we essentially have a system of N linear equations in N unknowns, and we have to find $E_1$. There are many ways to proceed, but here’s a way that is fairly efficient and exploits the symmetry in the equations. We rewrite the equations like so:

$E_1 - E_2 = 1$

$0.5(E_k - E_{k+1}) = 1 + 0.5(E_{k-1} - E_k)$, for $2 \le k \le N-1$

In this way, we can “zip” through the equations one by one in order and find:

$E_k - E_{k+1} = 2k -1$, for $1 \le k \le N-1$.

If we add all these equations up, we get a telescoping sum and find that $E_1 - E_N = 1 + 3 + 5 + \dots + (2N - 3) = (N-1)^2$. Since $E_N = 0$, we find that $E_1 = (N-1)^2$ (and, furthermore, $E_k = (N-1)^2 - (k-1)^2$).

So, the answer to the specific problem is $9^2 = 81$.

As an exercise, you might try to solve the system of linear equations using Cramer’s rule and computing the relevant determinants.

Problem #19

Let’s solve a slightly more general problem and replace the 17 in the problem with $a$ and the function $L(x)$ with $L(x) = x - \frac{x^2}{b}$.

If you know calculus, this problem can be solved by recognizing that the term $na_n$ represents an approximation to $D(1)$, where $D(t)$ satisfies the differential equation $D' = -D^2/b$ and has the boundary condition $D(0) = a$. By integrating, we find the closed form formula $D(t) = \frac{ab}{at + b}$, hence $\lim_{t \to \infty} na_n = D(1) = \frac{ab}{a+b}$.

To see that the iteration does represent an approximation to $D(1)$, we use Euler’s method with a time step $\Delta t = 1/n$: Set $D_0 = a$ and recursively define (according to the method)

$D_{m+1} = D_m + D'(D_m)\Delta t = D_m - \frac{D_m^2}{bn} = nL(D_m/n)$.

So $D_1 = nL(D_0/n)$, $D_2 = nL(D_1/n) = nL(L(D_0/n))$, $D_3 = nL(D_2/n) = nL(L(L(D_0/n)))$, and so forth until we find $D_n = nL^{(n)}(D_0/n) = na_n$. (Here, $L^{(n)} (x)$ denotes the repeated composition $L \circ L \circ L \circ \cdots \circ L (x)$, where there are $n$ occurrences of $L$.)

Therefore, the answer is $\frac{17\cdot 2}{17 + 2} = \frac{34}{19}$.

If you don’t know calculus, here’s one way you can solve this problem.

Let’s define $g(a, b) = \lim_{n \to \infty} na_n$. The figure below illustrates the iteration $L^{(n)}(x)$.

Now, recall that all parabolas are similar to each other.

That is, if this image illustrates the iteration $L^{(n)}(x)$ with $L(x) = x - x^2/b$, then if we scale this picture by a factor of $\lambda$, we will obtain the picture that illustrates the iteration $L^{(n)}(\lambda x)$ with $L(x) = x - x^2/(\lambda b)$. Therefore, $g(\lambda a, \lambda b) = \lambda g(a,b)$.

This means that to determine $g(a,b)$, we can focus on computing $g(a, 1)$. In this case, $L(x) = x - x^2$.

Now observe that $g(a,1)$ will not be affected if we perturb $L(x)$ by anything that approaches 0 on the order of or faster than $x^3$ (as $x$ approaches 0). That’s because when we compute $L^{(n)}(a/n)$, a perturbation that small will affect successive iterates by something on the order of $\frac{1}{n^3}$ (or smaller), and the net effect after $n$ applications of $L$ will have order $\frac{1}{n^2}$ (or smaller). After multiplying $L^{(n)}(a/n)$ by $n$ to get $a_n$, this change will have order $\frac{1}{n}$ (or smaller), and in the limit, the effect is no change at all.

For example, we could replace $L(x) = x - x^2$ with $\bar{L}(x) = x - x^2 + x^3 - \dots -(-x)^k \dots$ without affecting $g(a,1)$. This perturbation was carefully chosen to make the iteration easy to compute. For $\vert x \vert < 1$, the function $\bar{L}$ is a geometric series which evaluates to $\frac{x}{1+x} = \frac{1}{1 + \frac{1}{x}}$. Computing successive iterates in $\bar{L}^{(n)}(a/n)$, we find:

$\bar{L}(a/n) = \frac{1}{1 + \frac{n}{a}}$,

$\bar{L}(\bar{L}(a/n)) = \frac{1}{1 + (1 + \frac{n}{a})} = \frac{1}{2 + \frac{n}{a}}$,

$\bar{L}(\bar{L}(\bar{L}(a/n))) = \frac{1}{3 + \frac{n}{a}}$,

and, in general, $\bar{L}^{(n)} (a/n) = \frac{1}{n + \frac{n}{a}}$.

We then compute $g(a,1) = \lim_{n \to \infty} n\bar{L}^{(n)}(a/n) = \lim_{n \to \infty} \frac{n}{n + \frac{n}{a}} = \frac{1}{1 + \frac{1}{a}} = \frac{a}{a+1}$.

Thus, $g(17, 2) = 2g(17/2, 1) = 2\frac{17/2}{17/2 + 1} = \frac{34}{19}$.

To check your understanding, let $M(x) = \log (1+x)$. What is

$\lim_{n \to \infty} nM^{(n)}(17/n)$?

Problem #20

A straightforward way of resolving this problem is to use Euler’s identity and the binomial theorem to convert the equation into a 6th degree polynomial whose roots are the $\cot^2(r_k)$. The answer can then be read off of the coefficients (using Vieta’s formulas).

The given expression $\tan(15x) = 15\tan(x)$ can be written as

$\sin(15x)\cos(x) = 15\sin(x)\cos(15x)$.

Expressions for $\cos(nx)$ and $\sin(nx)$ in terms of $\cos(x)$ and $\sin(x)$ can be obtained using Euler’s identity and the binomial theorem like this:

$\cos(nx) + i\sin(nx) = e^{inx} = (e^{ix})^n = (\cos(x) + i\sin(x))^n = \sum_{k=0}^n \binom{n}{k}\cos^{n-k}x(i\sin(x))^k$.

We find

$\cos(15x) = \cos^{15}(x) - \binom{15}{2}\cos^{13}(x)\sin^2(x) + \binom{15}{4}\cos^{11}(x)\sin^4(x) - \dots$

and

$\sin(15x) = 15\cos^{14}(x)\sin(x) - \binom{15}{3}\cos^{12}(x)\sin^3(x) + \binom{15}{5}\cos^{10}(x)\sin^5(x) - \dots$.

Substituting these expressions into $\sin(15x)\cos(x) = 15\cos(15x)\sin(x)$, we get:

$\cos(x)(\binom{15}{1}\cos^{14}(x)\sin(x) - \binom{15}{3}\cos^{12}(x)\sin^3(x) + \binom{15}{5}\cos^{10}(x)\sin^5(x) - \dots)$

$= 15 \sin(x)(\cos^{15}(x) - \binom{15}{2}\cos^{13}(x)\sin^2(x) + \binom{15}{4}\cos^{11}(x)\sin^4(x) - \dots)$.

Since $0 < x < \pi/2$, neither $\sin(x)$ nor $\cos(x)$ will be zero, hence we can divide by them to obtain:

$(\binom{15}{1}\cos^{14}(x) - \binom{15}{3}\cos^{12}(x)\sin^2(x) + \binom{15}{5}\cos^{10}(x)\sin^4(x) - \dots)$

$= 15 (\cos^{14}(x) - \binom{15}{2}\cos^{12}(x)\sin^2(x) + \binom{15}{4}\cos^{10}(x)\sin^4(x) - \dots)$.

Eliminating the common term $15\cos^{14}(x)$ from both sides and then dividing by $\sin^{14}(x)$ yields:

$- \binom{15}{3}C^6 + \binom{15}{5}C^5 - \dots = 15 ( - \binom{15}{2}C^6 + \binom{15}{4}C^5 - \dots)$,

where we have set $C = \cot^2(x)$.

So, by Vieta’s formulas, the answer is $\frac{15\binom{15}{4} - \binom{15}{5}}{15\binom{15}{2} - \binom{15}{3}} = \frac{78}{5}$.