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.
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 (Hey contest designers: Please use exponential notation in situations like this!)
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 so first, let’s compute this area. The points where the ellipse intersects the axes are located at and The area of this ellipse is . Fortunately, I know that , so I can compute that
That means that as long as the error in this area approximation to 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 denote the given ellipse dilated by a factor of using the origin as the center of dilation. The form a family of “concentric” ellipses. Pick so that fully contains the unit squares centered at every lattice point in Pick so that is covered by the union of all the unit squares centered at the lattice points contained in By design, the area of is greater than or equal to which is in turn greater than or equal to the area of
The area of is so if we pick and , the areas of and will all begin with the same first two digits. Looking carefully at the problem statement, I believe that , so the positive -intercept of the ellipse is about , which is good because with our choices of and , there will then be a thick enough layer of lattice points near the boundary of whose surrounding unit squares are fully contained in and completely outside of 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.
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 term, but settles back into a nice pattern again.
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:
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
Suppose that is a polynomial with integer coefficients such that and are relatively prime for all positive integers . Notice that any common divisor of and the constant term of must also be a common divisor of and . Therefore, the constant term of must be or
The fact that and are relatively prime for all positive integers tells us that is or
But we’re also given that which is 2 modulo 3. Therefore, and , which simplifies to
Similarly, the constant term of , which, by direct computation, is must also be or . That is, is either 2 or 0.
If , then but this is impossible because and 30 is not divisible by 4.
Therefore, . Combining this with , we find that and . Thus .
This problem requires a good understanding of divisibility properties and the concept of relatively prime numbers. The critical fact used is that if divides two numbers, then divides both their sum and their difference.
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 has the form , let’s see what happens if we compute :
That is, if we set , then .
That’s the pattern!
Thus, the desired computation reduces to , where and the answer is .
This problem is a geometric probability problem. Let and . Then and are random variables uniformly distributed on the interval .
When a random variable is distributed uniformly on the unit interval , it means that the probability that its value is within some interval is equal to the length of . And, the fact that and are independent tells us that the probability that lies in some nice subset of the unit square is equal to the area of . (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.)
So let’s find the points in the unit square that correspond to and values for which . Using the law of cosines, we can find the algebraic relations that define this region:
The region is defined by this inequality together with and .
The curved part of the boundary occurs where . This is a quadratic equation with discriminant -3, and is therefore an ellipse. Notice the symmetries in the equation: If is on the boundary, then so is , , and . This tells us that the ellipse is centered at the origin and has major and minor axes lying on the lines and . To single out the exact ellipse, we can compute where the ellipse intersects these axes.
For the intersection with , substitute for into the equation of the ellipse and solve to find that and are the endpoints of the major axis. For the intersection with , substitute for into the equation of the ellipse and solve to find that and 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 or and in both cases, the shortest possible distance between and is given by the altitude of the equilateral triangle, which is .
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 . Below, we show this process after rotating the whole image by 45 degrees.
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 to and the tangent of 60 degrees is .
Therefore, the shaded region on the right represents one-third of the area of the circle: . 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 . 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 -coordinate is maximal? (You do not need to use Calculus to answer this.)