2011 Math Prize for Girls: #11-15

Here are comments and solutions to problems 11-15 on the 2011 Math Prize for Girls contest that took place at MIT on September 17, 2011.

Click here for comments and solutions for problems 1-5.
Click here for comments and solutions for problems 6-10.
Click here for comments and solutions for problems 16-20.

Problem #11

This problem is about a linear recurrence relation. The theory of linear recurrence relations is well understood. The better your facility with this topic, the easier you’ll find this problem. I’ll start by giving a solution that takes advantage of a sound understanding of the theory.

Using that theory, I know that the given sequence can be written

a_n = Ar_1^n+Br_2^n+Cr_3^n,

where A, B, and C are constants and r_1, r_2, and r_3 are roots of the cubic equation associated with the recurrence relation: x^3 = 2x^2 - 2x + 1. Because 1 is a root of this cubic, we can factor completely and find that the three roots are:

1, \frac{1 + \sqrt{3}i}{2}, and \frac{1 - \sqrt{3}i}{2}.

These three roots are sixth roots of unity. This tells us that the sequence a_n is periodic with a period of 6 (or possibly something that divides evenly into 6).

We’re given the values of a_{20}, a_{25}, and a_{30}, which, knowing about the periodicity, is the same as knowing that a_0 = a_{30} = 100, a_1 = a_{25} = 10, and a_2 = a_{20} = 1. We’re asked to compute a_{1331} which is equal to a_{-1} since 1331 is congruent to -1 modulo 6.

Thus, the answer is a_{-1} = a_2 - 2a_1 + 2a_0 = 1 - 20 + 200 = 181.

Now, let’s pretend we know nothing about the theory of linear recurrence relations and we find ourselves confronted with this problem. What one might try to do is suppose that the sequence begins ab, c, and then compute the next few values looking for some pattern (and since this is a contest math problem, there is very likely some simplifying pattern). So we just compute:

abc, 2c – 2ba, 2c – 3b + 2ac – 2b + 2a, a (!), b (!), c (!)…

and we see we come right back to the starting 3 values. So then we can work modulo 6 and find a = 100, b = 10, and c = 1 and that we need to find a_5, which is c – 2b + 2a = 181.  (I put the exclamation marks in the last three computed values of the sequence above because if I knew nothing about the theory of recurrence relations, I’d be thrilled during the contest to discover that ab, and c return so wonderfully because that means that the entire sequence is just 6 numbers that repeat over and over.)

If you had trouble, study linear recurrence relations. They sprout up all over the place: Fibonacci numbers, continued fractions, combinatorics…  They’re also a good way to learn more about matrices, characteristic equations, and determinants.

Problem #12

In this problem, we seek values of n where S(S(n))=n. The function rule that defines S(n) looks complicated with greatest integer functions and logarithms all over the place so it would be very unpleasant if we had to use that function rule and directly compute S(S(n)). Fortunately, this is a math contest, so you can bet that there is a less obscure description of the function. Just keep your wits about you and start unraveling the function rule.

Since all logarithms are base 10, we know that 10^{\lfloor \log n \rfloor} is the largest power of 10 less than or equal to n. Therefore, \lfloor \frac{n}{10^{\lfloor \log n \rfloor}} \rfloor is the leftmost digit of n. That means that the expression in parentheses in the function rule yields the number you get if you erase the first (leftmost) digit of n. Combining these observations, we can see that the net effect of the function rule is to move the leftmost digit of n over so that it becomes its rightmost digit. For example, S(7438) = 4387.

Applying S twice to a number moves its leftmost two digits over to the right…unless the digit second in from the left is zero, because in that case, after applying S once, all zeros that come directly after the (original) leftmost digit of n are erased.

Now that we have a clearer description of S, we can set about finding those n for which S(S(n))=n. If the second or third digit (from the left) of n is zero, then S(S(n)) won’t even have the same number of digits as n, so we can ignore all numbers whose second or third digit (from the left) is zero. Suppose \underline{d_hd_{h-1}d_{h-2}\dots d_0} is such a decimal number whose digits are the d_k. (The underscore reminds us that this expression does not stand for the product of the d_k.) Then

S(S(\underline{d_hd_{h-1}d_{h-2}\dots d_0})) = \underline{d_{h-2}d_{h-3}\dots d_0d_{h}d_{h-1}}.

For this to equal \underline{d_hd_{h-1}d_{h-2}\dots d_0}, we need d_h = d_{h-2}, d_{h-1} = d_{h-3}, . . ., d_2 = d_0, d_1 = d_h, and d_0 = d_{h-1}. We get two types of solutions depending on whether h is even or odd. If h is even, then all these equations tell us that all digits are equal. If h is odd, then all the odd digits are equal and all the even digits area equal. So let’s divide the solutions into sets according to how many digits the numbers have and start counting:

For 1 digit numbers, all work, so that gives 9 solutions.

For 2 digit numbers, all work provided that the units digit isn’t zero, so that gives 81 solutions.

For 3 digit numbers (i.e. h = 2), we have 9 solutions (namely, 111, 222, 333, etc.)

For 4 digit numbers, we can specify the first two digits freely subject to the condition that we don’t use zero, and then the rest of the number is determined. But also, we need numbers less than or equal to 2011, so that gives us the following solutions: 1111, 1212, 1313, 1414, 1515, 1616, 1717, 1818, and 1919, for a total of 9 more solutions.

Hence the answer is 9 + 81 + 9 + 9 = 108.

By the way, this problem is a good example of the kind of math problem that only lives in the math contest world. That’s because good mathematicians would never bother describing the function S using such a complex looking, obfuscating formula. When good mathematicians aren’t being whimsical, they seek clarity, not obfuscation, so they’d just describe the function S by describing its effect on the digits of n.  Even more, such a function in mathematical research isn’t likely because the function has a special affinity for a specific base, and the choice of 10 as a base is arbitrary. And then there’s that silly, seemingly traditional, math contest invocation of the year of the exam in the problem statement.

If you had trouble, perhaps the complex looking function intimidated you? If you have a basic, sound knowledge of arithmetic, the greatest integer function, and exponents and logarithms, then you have all you need to unravel this problem. Don’t be intimidated. Just think through it step by step. Especially on a math contest, you have good reason to expect that there will be a much simpler description. And after you figure out the nicer description, be careful not to trip up on details such as the effect of zero digits.

Problem #13

This problem is about pattern recognition and Sophie Germain’s identity. We’re told that 104,060,465 has a 5 digit prime factor and are asked to find it. Unfortunately, I’m not sure I can say something that would be very helpful if you had trouble with this one. Here’s what happened when I tried to solve it.

First, I noticed that the number is close to 10^8 and so I thought to try to factor it by finding x and y such that

104060465 = (10000+x)(10000 + y) = 10^8 + (x+y)10^4 + xy.

I fiddled with this approach for a little while and didn’t get anywhere, so I thought, “hey, this is a contest math problem…if this approach seems laborious, then it’s probably the wrong approach…there has to be some ‘nice’ way of finding the factor…I must be missing some neat observation.” So I looked at the 9 digit number again and noticed that it amusingly looks a little like the 1, 4, 6, 4, 1 row of Pascal’s triangle…and then I realized how to do the problem because I know that the rows of Pascal’s triangle are the digits of powers of 11 (if you take a sufficiently high base, but here, 14641 is exactly 11^4). That is, 104060401 = 101^4. Therefore, 104060465 = 101^4 + 64 = 101^4 + 4(2^4), which is exactly in the form of one side of Sophie Germain‘s identity:

a^4 + 4b^4 = (a^2 + 2b^2 + 2ab)(a^2 + 2b^2 - 2ab).

Substituting a = 101 and b= 2, we find that

104060465 = (101^2 + 2(2^2) + 2(101)(2))(101^2 + 2(2^2) - 2(101)(2)) = (10613)(9805).

Since we are told that there is a 5 digit prime factor, it must be 10613.

Because this approach works so snugly and factoring directly would be tedious and time-consuming, I’m confident that the contest designers had this solution in mind when they set the problem. If you aren’t able to recognize the given number as 101^4 + 4(2^4), I’m not sure what you could do to solve this problem in a reasonable amount of time. While you’re taking a math competition, be careful not to allot too much time to a tedious approach even if you know it should work in principle. Instead, try to look for something you hadn’t noticed before. In this case, I’m not sure how one would become prepped to notice an application of Sophie Germain’s identity other than to say that if you enjoy math and keep on studying it, you’ll put yourself in an ever better position to recognize such things.

Problem #14

This is an optimization problem. When you fix p, the function F(p,q) is linear in q, so the value of G(p) will be equal to F(p,1) or F(p, 0) depending on whether the coefficient of q (i.e. the slope) is positive or negative, respectively. The coefficient of q is -12p + 7. This is positive or negative according to whether p < 7/12 or p > 7/12. (If the slope is zero, it doesn’t matter whether we take F(p,0) or F(p,1) because they’ll be equal!) Thus, G(p) = F(p,1) = 3-5p if p \le 7/12 and G(p) = F(p,0) = 7p-4 if p > 7/12. Because the slope of G(p) is negative when p \le 7/12 and positive when p > 7/12, the minimal value of G(p) occurs right where p = 7/12.

Problem #15

Because all outcomes are equally likely, we have to count how many ways the desired condition holds and divide by 6^4 to get the probability of that condition happening. The desired condition is:

\frac{a+b}{c+d} = \frac{1}{2}(\frac{a}{c} + \frac{b}{d}) = \frac{ad + bc}{2cd}.

This can be rearranged to acd + bcd = ad^2 + bc^2.

Now let’s exploit the fact that the variables are all powers of 2: let a=2^A, b=2^B, c = 2^C, and d = 2^D. The condition becomes:

2^{A+C+D} + 2^{B+C+D} = 2^{A+2D} + 2^{B+2C}.

(And note that 1 \le A, B, C, D \le 6.) The only ways that this equation can hold are if (if it helps, think of this equation as an identity involving binary numbers):

  • A + C +D = B + C + D = A + 2D = B + 2C
  • A+C+D = A+2D and B+C+D = B + 2C
  • A+C+D = B + 2C and B + C+ D = A +2D

So we just have to count these possibilities being careful not to double count any cases. The first case is equivalent to A = B and C = D. The second is equivalent to C = D. Since the first case is more restrictive than the second, we can simply ignore the first case and worry about the second and third cases only.

The third case is equivalent to A+D = B+C. That is, how many ways can two pairs of normal dice produce the same sums? If there are n ways to get the sum s, then there are n^2 ways for two pairs to get the sum s. So the total number of ways to get this third case is 1^2+2^2+3^2+4^2 + 5^2 + 6^2 + 5^2+4^2+3^2+2^2+1^2. Of these cases, there are 6^2 where C = D; these are the cases that overlap with the second condition above. And the number of cases that fall within the second condition is 6^3.

Thus, the total number of possibilities is 2(1^2+2^2+3^2+4^2 + 5^2) + 6^3 = 326 and the answer is 326/6^4 = 163/648.


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: #11-15

  1. I don’t happen to know Sophie Germain’s identity, though I did recognize the 101^4 in there from Pascal’s triangle. But, when I’m faced with something like a sum of squares (or fourth powers, or constants times those, or whatever) I try some wishful thinking.

    In other words, when I see (101^2)^2 + 8^2, I wish I had a 2 * 101^2 * 8 in the middle so I could factor it as a perfect square. Then I have (101^2)^2 + 2 * 101^2 * 8 + 8^2 – 2 * 101^2 * 8, and this becomes (101^2 + 8)^2 – 2 * 101^2 * 8, and luckily 2 * 8 happens to be a perfect square, so I have (101^2 + 8)^2 – (4 * 101)^2, which is at last equivalent to your method.

    • girlsangle says:

      Yes, that’s nice!

      I’m curious to know what percentage of contestants recognized the given number as 101^4 + 64 and what percentage of those also succeeded in solving the problem. And I’m curious to know if any contestants solved the problem during the contest without recognizing the number as 101^4 + 64.

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

  3. Pingback: 2011 Math Prize for Girls: #16-20 | 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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s