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!)

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.

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 #20

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.)

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$ .

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.

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.

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 these ads

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

Tiff says:

December 31, 2011 at 2:02 pm

Could you do the other questions as well?
Thanks!

- girlsangle says:
  
  December 31, 2011 at 5:46 pm
  
  I’ll try! If there are specific ones you’d like me to do, please let me know by emailing girlsangle@gmail.com and I’ll prioritize those.
  
Pingback: 2011 Math Prize for Girls: #11-15 | Girls' Angle
Pingback: 2011 Math Prize for Girls: #6-10 | Girls' Angle
Pingback: 2011 Math Prize for Girls: #1-5 | Girls' Angle

2011 Math Prize for Girls: #16-20

Like this:

About girlsangle

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

Leave a Reply Cancel reply

Search Me

Recent Posts

Categories

Archives

Everything Math

Follow “Girls' Angle”