2011 Math Prize for Girls: #16-20

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

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.

Click here for comments and solutions for problems 6-10.
Click here for comments and solutions for problems 11-15.

Problem #16

Maybe I need bifocals, but I find it challenging to count zeros in strings of zeros. So for now, let’s just say that the ellipse is given by 4x^2 + 9y^2 \le 10^d. (Hey contest designers: Please use exponential notation in situations like this!)

lattice squares

Some of the desired area isn't covered by a square and some squares fall outside of the desired area.

If you imagine each lattice point as the center of a unit square, then you can see that the area of the ellipse is approximated by N, so first, let’s compute this area. The points where the ellipse intersects the axes are located at (\pm \sqrt{\frac{10^d}{4}}, 0) and (0, \pm \sqrt{\frac{10^d}{9}}). The area of this ellipse is \frac{\pi}{6}10^d. Fortunately, I know that \pi = 3.14159\dots, so I can compute that \frac{\pi}{6}10^d = 10^d 0.5235\dots.

That means that as long as the error in this area approximation to N is within a few percent, the answer is going to be 52. The error results from the inaccuracy in approximating the elliptical boundary with the rectilinear boundary of the square tiling. We bound this error by considering similar ellipses of slightly larger and smaller area.

Let E_s denote the given ellipse dilated by a factor of s using the origin as the center of dilation. The E_s form a family of “concentric” ellipses. Pick a > 1 so that E_a fully contains the unit squares centered at every lattice point in E_1. Pick b < 1 so that E_b is covered by the union of all the unit squares centered at the lattice points contained in E_1. By design, the area of E_a is greater than or equal to N, which is in turn greater than or equal to the area of E_b.

The area of E_s is \frac{\pi}{6}10^ds^2, so if we pick a = 1.001 and b = 0.999, the areas of E_a, E_1, and E_b will all begin with the same first two digits. Looking carefully at the problem statement, I believe that d = 9, so the positive y-intercept of the ellipse is about 10^4, which is good because with our choices of a and b, there will then be a thick enough layer of lattice points near the boundary of E_1 whose surrounding unit squares are fully contained in E_a and completely outside of E_b. So the answer is 52.

The key to this problem is realizing that the number of lattice points contained in a large, plump region approximates its area. Although not applicable to this problem, check out the highly related Pick’s theorem if you don’t yet know about it.

Problem #17

You can solve this problem by carrying out the (polynomial) long division. Fortunately, a pattern with period 3 emerges. This pattern gets mildly disrupted by the x^{256} term, but settles back into a nice pattern again.

polynomial long division

This long division just shows the coefficients of the polynomials. The 256 in parentheses indicates a place value. The colored rectangles represents repeated blocks of coefficients.

Counting carefully, we find the answer is 341.

After doing this division, one can produce a shorter, paper friendly, derivation of the answer by taking note of the identity produced:

x^{512}+x^{256}+1 =

(x^2+x+1)( (x-1)(x^{509} + x^{506} + \dots + x^{257}) + x^{255} - (x - 1)(x^{252}+x^{249} + \dots + 1))

which is straightforward to verify.

It helps to be adept at polynomial long division, and the way to get good at it is the same way you get good at doing regular long division: practice.

If you don’t like long division, you can also solve this problem using multiplication if you recognize that \frac{1}{1 + x+ x^2} = (1-x)(1 + x^3 + x^6+x^9 + \dots).

Problem #18

Suppose that F(x) is a polynomial with integer coefficients such that n and F(n) are relatively prime for all positive integers n. Notice that any common divisor of n and the constant term of F(x) must also be a common divisor of n and F(n). Therefore, the constant term of F(x) must be 1 or -1.

Let P(x) = ax^2 + bx + c.

The fact that n and P(n) are relatively prime for all positive integers n tells us that c is 1 or -1.

But we’re also given that P(3) = 89 which is 2 modulo 3. Therefore, c = -1 and 9a + 3b - 1 = 89, which simplifies to 3a + b = 30.

Similarly, the constant term of P(P(x)), which, by direct computation, is a - b - 1, must also be 1 or -1. That is, a - b is either 2 or 0.

If a - b = 0, then a = b, but this is impossible because 3a + b = 30 and 30 is not divisible by 4.

Therefore, a - b = 2. Combining this with 3a + b = 30, we find that a = 8 and b = 6. Thus P(x) = 8x^2 + 6x - 1.

Finally, P(10)=859.

This problem requires a good understanding of divisibility properties and the concept of relatively prime numbers. The critical fact used is that if d divides two numbers, then d divides both their sum and their difference.

Problem #19

On a contest, you’re not going to be expected to do a super long and tedious computation. So the operation in this problem must observe some pattern that will enable you to simplify the desired computation considerably. Patterns are easier to see when you use variables. In any case, for a variety of reasons, it’s a good idea to use variables when embarking on a long computation like this one.

Since v has the form \frac{w-1}{w+1}, let’s see what happens if we compute \frac{w-1}{w+1} \oplus \frac{x -1}{x+1}:

\frac{w-1}{w+1} \oplus \frac{x -1}{x+1} = \frac{\frac{w-1}{w+1} + \frac{x -1}{x+1}}{1 + \frac{(w-1)(x-1)}{(w+1)(x+1)}} = \frac{(x+1)(w-1)+(w+1)(x-1)}{(w+1)(x+1) + (w-1)(x-1)} = \frac{wx - 1}{wx+1} .

That is, if we set f(w) = \frac{w-1}{w+1}, then f(w) \oplus f(x) = f(wx).

That’s the pattern!

Thus, the desired computation reduces to f(w^{14}), where w = \sqrt[7]{17} and the answer is \frac{17^2 - 1}{17^2 + 1} = \frac{288}{290} = \frac{144}{145}.

Problem #20MPFG 20_01

This problem is a geometric probability problem. Let x = AX and y = AY. Then x and y are random variables uniformly distributed on the interval \lbrack 0, 1 \rbrack.

When a random variable is distributed uniformly on the unit interval \lbrack 0, 1 \rbrack, it means that the probability that its value is within some interval I \subset \lbrack 0, 1 \rbrack is equal to the length of I. And, the fact that x and y are independent tells us that the probability that (x, y) lies in some nice subset R of the unit square is equal to the area of R. (Normally, you have to divide by the area of the region of all possible outcomes, but in this case, that area happens to be 1.)

MPFG 20_02

Which points in this unit square are in the desired region?

So let’s find the points (x, y) in the unit square that correspond to x and y values for which XY \le \frac{1}{\sqrt[4]{3}}. Using the law of cosines, we can find the algebraic relations that define this region:

XY^2 = x^2 + y^2 - 2xy \cos(\frac{\pi}{3}) = x^2 + y^2 - xy \le \frac{1}{\sqrt{3}}.

The region is defined by this inequality together with 0 \le x \le 1 and 0 \le y \le 1.

which ellipse?The curved part of the boundary occurs where x^2 + y^2 - xy = \frac{1}{\sqrt{3}}. This is a quadratic equation with discriminant -3, and is therefore an ellipse. Notice the symmetries in the equation: If (x,y) is on the boundary, then so is (y,x), (-x, -y), and (-y, -x). This tells us that the ellipse is centered at the origin and has major and minor axes lying on the lines y=x and y= -x. To single out the exact ellipse, we can compute where the ellipse intersects these axes.

the region

We must compute the area of the shaded region.

For the intersection with y=x, substitute x for y into the equation of the ellipse and solve to find that (\frac{1}{\sqrt[4]{3}}, \frac{1}{\sqrt[4]{3}}) and (-\frac{1}{\sqrt[4]{3}}, -\frac{1}{\sqrt[4]{3}}) are the endpoints of the major axis. For the intersection with y=-x, substitute -x for y into the equation of the ellipse and solve to find that (-\frac{1}{\sqrt[4]{27}}, \frac{1}{\sqrt[4]{27}}) and (\frac{1}{\sqrt[4]{27}}, -\frac{1}{\sqrt[4]{27}}) are the endpoints of the minor axis.

The problem is now to compute the area of the region that is the intersection of the unit square with the ellipse. From the picture, we can see that the ellipse does not go above or to the right of the boundary of the square. But, during the contest, you might not be so confident in your sketch and may wonder if the ellipse intersects the square on its top or right border. To eliminate this possibility, observe that the top and right boundaries of the square correspond to the cases where Y = C or X = C, and in both cases, the shortest possible distance between X and Y is given by the altitude of the equilateral triangle, which is \frac{\sqrt{3}}{2} > \frac{1}{\sqrt[4]{3}}.

To compute the area of the shaded region, we can stretch the whole image in the NW-SE direction to make the ellipse a circle. In order to do this, we have to stretch by a factor equal to the ratio of the length of the major axis to that of the minor axis of the ellipse, i.e. by a factor of \sqrt{3}. Below, we show this process after rotating the whole image by 45 degrees.

the stretch

Stretch the figure in the vertical direction to turn the ellipse into a circle.

The square becomes a rhombus and the shaded region becomes a sector of a circle. The upper left edge of the square makes a 45 degree angle with the ellipse’s major axis on the left. This angle gets stretched to form a 60 degree angle on the right. To see this, note that the tangent of the angle changes from \frac{1}{1} to \frac{\sqrt{3}}{1} and the tangent of 60 degrees is \frac{\sqrt{3}}{1}.

Therefore, the shaded region on the right represents one-third of the area of the circle: \frac{1}{3} \pi (\frac{\sqrt{2}}{\sqrt[4]{3}})^2 = \frac{2}{3\sqrt{3}}\pi. To recover the shaded area in the ellipse, we have to divide by the stretching factor. Notice that because we only stretched in one direction, we should not divide by the square of the stretching factor. The upshot is that the desired probability turns out to be \frac{2}{9}\pi. For some reason, the question asks for the nearest integer to 900 times this probability, so the final answer is 628. (It’s possible that the contest designers did this as a way to provide a touch of reassurance to the contest taker.)

If you had trouble with this problem, there are 3 main components. One is understanding geometric probability. This is frequently covered for simpler situations in high school geometry. When dealing with uniform probabilities, geometric probability questions very often translate into an area computation. A second component is determining the region whose area yields the probability, and this involves knowing tools to compute length, such as the law of cosines, although in this case, you could find the equation for the ellipse by using only the Pythagorean theorem since the triangle is equilateral. The third component is the actual computation of the elliptical sector. To compute the area, understanding that ellipses are circles stretched in two directions can be very helpful, but you can always resort to the powerful tools of Calculus.

Here’s a question to further test your understanding of the situation. What are the coordinates of the point on the ellipse whose x-coordinate is maximal? (You do not need to use Calculus to answer this.)


About girlsangle

We're a math club for girls.
This entry was posted in Contest Math and tagged , . Bookmark the permalink.

5 Responses to 2011 Math Prize for Girls: #16-20

  1. Tiff says:

    Could you do the other questions as well?

  2. Pingback: 2011 Math Prize for Girls: #11-15 | Girls' Angle

  3. Pingback: 2011 Math Prize for Girls: #6-10 | Girls' Angle

  4. Pingback: 2011 Math Prize for Girls: #1-5 | Girls' Angle

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s