Mathematical Food for Thought

  
 
google
yahoo
bing
 

  • About

    Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
  
Eww… Topic: Algebra/Inequalties. Level: AIME/Olympiad. September 30th, 2006

Problem: Find the minimum value of

\frac{\left(x+\frac{1}{x}\right)^6-\left(x^6+\frac{1}{x^6}\right)-2}{ \left(x+\frac{1}{x}\right)^3-\left(x^3+\frac{1}{x^3}\right)}

for x > 0 .

Solution: Make a handy substitution a = x , b = \frac{1}{x} and 1 = a^3b^3 . Then we want to minimize

\frac{(a+b)^6-(a^6+b^6)-2a^3b^3}{(a+b)^3-(a^3+b^3)} = \frac{2a^4+5a^3b+6a^2b^2+5ab^3+2b^4}{a+b}

after cancelling 3ab . But we see that this evenly divides and becomes

2a^3+3a^2b+3ab^2+2b^2 = (a+b)^3+(a^3+b^3) .

But a+b \ge 2 and a^3+b^3 \ge 2 by AM-GM and the same equality case, so

(a+b)^3+a^3+b^3 \ge 10

with equality at a = b = 1 . QED.

——————–

Comment: It was very useful to make the substitution and then homogenize the numerator so you could cancel things out evenly. Then classical inequalities (AM-GM) helped us finish it.

——————–

Practice Problem: Prove that (a^3+b^3+c^3-3abc)(a+b+c) \ge 0 .

Posted in AIME, Algebra, Inequalities, Olympiad || 2 Comments »
This Is Mental Math?!? Topic: Number Theory. Level: AIME. September 27th, 2006

Problem: (2006-2007 Warm-Up 2) Let f(x) be the sum of the digits of x . Find f(f(f(8765^{4321}))) .

Solution: Let’s try bounding our quantity. We know

f(x) < 9 \cdot \lceil \log{x} \rceil

because \lceil \log{x} \rceil is the number of digits of x (except when x is a power of ten, but those are trivial) and the biggest digit is 9 . So we can say that

f(8765^{4321}) < 9 \cdot \lceil \log{8765^{4321}} \rceil < 9 \cdot \log{10000^{10000}} = 360000

so

f(f(8765^{4321})) < 9 \cdot \lceil \log{360000} \rceil < 9 \cdot \log{1000000} = 54

and

f(f(f(8765^{4321}))) < 13

because the largest sum of digits of any number less than 54 is 4+9 = 13 . So we know our value is less than 13 . But remember that the sum of the digits of a number is equal to itself \pmod{9} (prove this!) and 8765^{4321} \equiv (-1)^{4321} \equiv 8 \pmod{9} so our answer is also 8 \pmod{9} . But the only number less than 13 that works is then 8 . QED.

——————–

Comment: Admittedly, this is not likely to show up on a mental math test, but it’s feasible to do in your head. The bounding is not horrific and taking the mod is also not bad. Of course, 45 seconds is pretty quick, but if you knew how to approach the problem already, it was definitely possible (and done).

——————–

Practice Problem: Show that the sum of the digits of a number is congruent to itself modulo nine.

Posted in AIME, Number Theory || 3 Comments »
Parity Check. Topic: Logic/NT. Level: AIME/Olympiad. September 25th, 2006

Problem: (2000 Putnam – B1) Let a_j, b_j, c_j be integers for 1 \le j \le N . Assume for each j , at least one of a, b, c is odd. Show that exist integers r, s, t such that ra_j+sb_j+tc_j is odd for at least \frac{4N}{7} values of j , 1 \le j \le N .

Solution: A pretty notation-heavy, strange, contrived problem. Let’s get started. Where do we get 7 in the denominator? How about from the number of binary triples that contain at least one 1 ? In fact we may simplify the problem so that a_j, b_j, c_j, r, s, t are all in the set \{0, 1\} because we only care about even and odd. Cool.

Now let’s see… for which binary triples (a_j, b_j, c_j) and (r, s, t) is ra_j+sb_j+tc_j odd? Try it out. We will list the binary triples and give them variable names to simplify our lives.

A = (0, 0, 1)
B = (0, 1, 0)
C = (0, 1, 1)
D = (1, 0, 0)
E = (1, 0, 1)
F = (1, 1, 0)
G = (1, 1, 1) .

Now we will write ra_j+sb_j+tc_j as U \cdot V where U = (r, s, t) and V = (a_j, b_j, c_j) . We make the following table:


. A B C D E F G
A X . X . X . X
B . X X . . X X
C X X . . X X .
D . . . X X X X
E X . X X . X .
F . X X X X . .
G X X . X . . X

where an X in the entry in row U and column V signifies that U \cdot V is odd. Notice that each choice of (r, s, t) makes four odd and each choice of (a_j, b_j, c_j) has four possible (r, s, t) to make it odd. Let k_U denote the number of times U \cdot (a_j, b_j, c_j) is odd for 1 \le j \le N . We want to show that there exists a U such that k_U \ge \frac{4N}{7} . We know

\displaystyle \sum_{U=A}^G k_U

is the number of times we have an odd sum if we apply every possible (r, s, t) . But if we apply every (r, s, t) we know from our table that each of the N binary triples (a_j, b_j, c_j) produces an odd for four of the seven (r, s, t) . So in fact

\displaystyle \sum_{U=A}^G k_U = 4N .

But since the average of the k_U ’s is then \frac{4N}{7} , there must exist at least one k_U such that k_U \ge \frac{4N}{7} , as desired. QED.

——————–

Comment: IMO, a very cool problem. Something that at first glance you sort of stare blankly at how they got such a ridiculous problem but then you realize it is a Putnam B1 so it couldn’t possibly that bad, which is soon followed by your realization of the simplification to binary and finally the recognition of the seven as the number of binary triples with at least one 1 . Yay!

——————–

Practice Problem: I have seven light bulbs which are off and seven switches labeled with the binary triples above. A switch turns on a light bulb if the dot product (as above) of the number of the switch and the number of the light bulb is odd. Show that if I flip each switch once the light bulbs will still all be off.

Posted in Logic, Number Theory || No Comments »
Pell. Topic: NT. Level: AIME/Olympiad. September 23rd, 2006

Problem: (2000 Putnam – A2) Prove that there exist infinitely many integers n such that n, n + 1, n + 2 are each the sum of the squares of two integers. [Example: 0 = 0^2 + 0^2, 1 = 0^2 + 1^2, 2 = 1^2 + 1^2.]

Solution: Consider the Pell Equation

x^2-2y^2 = 1 .

It is well-known that this equation has an infinite number of positive integer solutions (x,y) . This can be derived using truncated continued fractions representation of \sqrt{2} (see here). So if we let n = 2y^2 = y^2+y^2 , we have

n+1 = x^2+0^2

n+2 = x^2+1^2 ,

completing the problem. QED.

——————–

Comment: This was one of the official solutions to the problem, even though all you had to know was that Pell Equations have an infinite number of solutions. There is a constructive solution to the problem as well, based on choosing certain n .

——————–

Practice Problem: Find the constructive solution (i.e. all numbers of the form n = f(k) work for some function f ).

Posted in AIME, Number Theory, Olympiad || 2 Comments »
Infinite… POWER! Topic: Algebra/Inequalities/S&S. Level: AIME/Olympiad. September 22nd, 2006

Problem: (2000 Putnam – A1) Let A be a positive real number. What are the possible values of \displaystyle \sum_{j=0}^{\infty} x_j^2 , given that x_0, x_1, \ldots are positive numbers such that \displaystyle \sum_{j=0}^{\infty} x_j = A ?

Solution: First, we will try to guess what the range is using inequalities. We obviously have

\displaystyle \sum x_j^2 > 0

because all the x_j are positive. Also,

\displaystyle \sum x_j^2 < \left(\sum x_j\right)^2 = A^2

by “expansion” (infinitely, but that’s ok). So for now, our guess is the interval (0, A^2) . We want to show that given any \alpha \in (0, A^2) we can make a sequence such that \displaystyle \sum x_j = A and \displaystyle \sum x_j^2 = \alpha . Well, we like easy sequences so consider if x_j is a geometric sequence with common ratio r . Then

\displaystyle \sum x_j = \frac{x_0}{1-r} = A .

We want to show that given any \alpha , we can find a positive real r satisfying r < 1 , the above equation, and

\displaystyle \sum x_j^2 = \frac{x_0^2}{1-r^2} = \alpha .

Rewriting the two equations (and squaring the first), we have

x_0^2 = A^2(1-r)^2 = \alpha(1-r^2)

so

(A^2+\alpha)r^2-(2A^2)r+(A^2-\alpha)

(r-1)[(A^2+\alpha)r-(A^2-\alpha)] .

Since we want |r| < 1 , we must use the second factor, which gives us

r = \frac{A^2-\alpha}{A^2+\alpha} .

But if \alpha \in (0, A^2) , clearly A^2 &#8211; \alpha < A^2 + \alpha \Rightarrow \frac{A^2-\alpha}{A^2+\alpha} < 1 , so there exists some positive ratio such that \displaystyle \sum x_j = A and \displaystyle \sum x_j^2 = \alpha . Hence the possible values are (0, A^2) . QED.

——————–

Comment: A surprisingly difficult A1 problem on a Putnam; it had less perfect scores than A2, B1, and B2 (which will probably be posted over the next week or so). It required some experience with inequalities to guess the range and then a clever assumption of a geometric series to complete the proof.

——————–

Practice Problem: What if the terms could be any nonzero real? What are the possible values of \displaystyle \sum x_j^2 then?

Posted in AIME, Algebra, Inequalities, Olympiad, Sequences & Series || 1 Comment »
« Previous Entries
Next Page »
Google

 

  
 
free web counters
Etronics