Friday, August 25, 2006

Thursday, August 24, 2006

Add Some Numbahs. Topic: Number Theory. Level: AIME/Olympiad.

Problem: (2003 Putnam - A1) Let $ n $ be a fixed positive integer. How many ways are there to write $ n $ as a sum of positive integers $ n = a_1+a_2+\cdots+a_k $ with $ k $ an arbitrary positive integer and $ a_1 \le a_2 \le \cdots \le a_k \le a_1+1 $?

Solution: So that strange inequality condition basically says that all the numbers are within one of each other. Easy enough. Let's take this approach; for any $ n $, run through each $ k $ from $ 1 $ to $ n $ (if $ k > n $ there are clearly no solutions).

Let $ \displaystyle d = \left\lfloor \frac{n}{k} \right\rfloor $. Then $ kd \le n < k(d+1) $. Essentially, this says that all of the $ a_i $'s are close to $ d $. We claim that in fact $ a_i = d $ or $ a_i = d+1 $ for all $ i $ and a fixed $ k $.

Suppose $ a_i < d $ for some $ i $. Then $ \sum a_i < kd < n $ since the maximum $ a_i $ is within $ 1 $ of the minimum, impossible. Similarly, suppose $ a_i > d+1 $ for some $ i $. Then $ \sum a_i > k(d+1) > n $ since the minimum is within $ 1 $ of the maximum, again impossible. This proves the claim.

Now we claim that there is exactly one solution for any fixed $ k $. Suppose $ a_1, a_2, \ldots, a_j $ are all $ d $ and $ a_{j+1}, a_{j+2}, \ldots, a_k $ are all $ d+1 $. Then the sum is

$ jd+(k-j)(d+1) $.

At $ j = k $, all the $ a_i $'s are $ d $ and the sum is $ kd \le n $. But notice that decreasing $ j $ by $ 1 $ increases the LHS by $ 1 $. So if we keep incrementing $ j $, we will eventually get to $ n $ (if we go all the way to $ j = 0 $ we reach $ k(d+1) > n $, so we must've passed $ n $ somewhere in there). It's easy to see that we can't get $ n $ twice because the LHS only increases. Hence for each $ k $ there is exactly one solution for $ a_1, a_2, \ldots, a_k $.

Since $ k = 1, 2, \ldots, n $ are all possible values for $ k $, there are exactly $ n $ ways to write $ n $ as a sum of the desired form. QED.

--------------------

Comment: Another Putnam problem; they aren't too bad, right? Considering a large percentage of students who take it get zero points out of $ 120 $, anyway. The solution above would probably have to be rigorized immensely before actually being called a proof, but that would be no fun to read and stuff.

--------------------

Practice Problem: (2003 Putnam - B1) Do there exists polynomials $ a(x), b(x), c(y), d(y) $ such that

$ 1+xy+x^2y^2 = a(x)c(y)+b(x)d(y) $

holds identically?

Tuesday, August 22, 2006

Function + Equation = ?? Topic: Algebra. Level: AIME/Olympiad.

Problem: Find all functions $ f(x) $ that satisfy $ f(x)f(y)-f(xy) = x+y $ for all reals $ x,y $.

Solution: Let's start by plugging in something easy, like $ x = y = 1 $. We get

$ [f(1)]^2-f(1) = 2 $

$ [f(1)-2][f(1)+1] = 0 $

so $ f(1) = 2, -1 $. Hmm, make it a little more complicated then and try just $ y = 1 $. Then

$ f(x)f(1)-f(x) = x+1 $

$ f(x)[f(1)-1] = x+1 \Rightarrow f(x) = \frac{x+1}{f(1)-1} $.

But wait, we already know $ f(1) = 2, -1 $ so we can just plug this in. Thus we have

$ f(x) = x+1 $ or $ f(x) = -\frac{x+1}{2} $.

We check by plugging each in:

$ f(x)f(y)-f(xy) = (x+1)(y+1)-(xy+1) = x+y $ (this works)

$ f(x)f(y)-f(xy) = \left(-\frac{x+1}{2}\right) \left(-\frac{y+1}{2}\right) - \left(-\frac{xy+1}{2} \right) \neq x+y $ (this doesn't).

That means only $ f(x) = x+1 $ works. QED.

--------------------

Comment: Functional equations are pretty strange as far as problems go. Basically you go around plugging random things in until you find something useful. Then you work it all out and you usually get an interesting result.

--------------------

Practice Problem: (360 Mathematical Contests - 1.1.49) Find all polynomials $ P(x) $ with integral coefficients such that

$ P(P^{\prime}(x)) = P^{\prime}(P(x)) $

for all real numbers $ x $.

Sunday, August 20, 2006

Ex-ex-exponents! Topic: Inequalities. Level: AIME.

Problem: Let $ a, b, c, p, q $ be positive reals. Prove that

$ \left(a^ab^bc^c\right)^{p+q} \ge a^{pb+qc}b^{pc+qa}c^{pa+qb} $.

Solution: How do you get rid of exponents? Well, take the log of course! Logging both sides and using log rules (multiplication to addition and bringing the power down), the inequality becomes

$ (p+q)(a\log{a}+b\log{b}+c\log{c}) \ge (pb+qc)\log{a}+(pc+qa)\log{b}+(pa+qb)\log{c} $.

We will prove that

$ p(a\log{a}+b\log{b}+c\log{c}) \ge p(b\log{a}+c\log{b}+a\log{c}) $

and

$ q(a\log{a}+b\log{b}+c\log{c}) \ge q(c\log{a}+a\log{b}+b\log{c}) $.

If we add those together, we get the inequality above. But we note that $ (a, b, c) $ and $ (\log{a}, \log{b}, \log{c}) $ are similarly sorted, we can apply the Rearrangement Inequality (see here), which tells us that

$ a\log{a}+b\log{b}+c\log{c} \ge b\log{a}+c\log{b}+a\log{c} $

and

$ a\log{a}+b\log{b}+c\log{c} \ge c\log{a}+a\log{b}+b\log{c} $,

exactly what we needed. Thus the inequality is proven. QED.

--------------------

Comment: Classic way of proving inequalities with exponents; many times, after you take the log, you can apply Jensen's (log is concave) to get some interesting results as well.

--------------------

Practice Problem: Prove AM-GM. For positive reals $ a_1, a_2, \ldots, a_n $,

$ \frac{a_1+a_2+\cdots+a_n}{n} \ge \sqrt[n]{a_1a_2\cdots a_n} $.

Friday, August 18, 2006

Effuvay. Topic: Algebra/NT/Polynomials. Level: AIME.

Problem: Let $ f(x) $ be a polynomial with integer coefficients. Show that $ f(a) $ divides $ f(a+f(a)) $.

Solution: Note that $ a|b $ means $ a $ divides $ b $. Let's prove a more general result, that $ (x-y)|(f(x)-f(y)) $. Write $ \displaystyle f(x) = \sum c_nx^n $. We want to show that

$ \displaystyle (x-y)|\left(\sum c_n(x^n-y^n) \right) $.

But since $ x^n-y^n = (x-y)(x^{n-1}+x^{n-2}y+\cdots+xy^{n-2}+y^{n-1}) $, it's clear that $ x-y $ divides each $ c_n(x^n-y^n) $ and thus their sum. Applying this result to $ x = a+f(a) $ and $ y = a $, we get

$ \displaystyle f(a)|(f(a+f(a))-f(a)) $,

which implies that

$ \displaystyle f(a)|f(a+f(a)) $,

as desired. QED.

--------------------

Comment: The general result is a very useful fact about polynomials with integer coefficients that shows up often; problems can be written based on many variations of it. Writing out the terms of the polynomial is also a good strategy whenever you're stuck.

--------------------

Practice Problem: Let $ f(x) $ be a polynomial with integer coefficients. If $ a, b, c, d $ are distinct integers such that $ f(a) = f(b) = f(c) = f(d) =5 $, show that there cannot exist an integer $ e $ such that $ f(e) = 8 $.

Wednesday, August 16, 2006

Byakugan! Topic: Geometry/Inequalities. Level: AIME/Olympiad.

Problem: (1998 India National Olympiad - #4) Suppose $ABCD$ is a cyclic quadrilateral inscribed in a circle of radius one unit. If $AB \cdot BC \cdot CD \cdot DA \geq 4$, prove that $ABCD$ is a square.

Solution: This reeks of Ptolemy... anything involving cyclic quadrilaterals, products of sides, inequalities and you definitely want to try Ptolemy. If you don't know this, just use your Byakugan and everything should be ok.

In any case, let's try using Ptolemy, which states that

$ AB \cdot CD + AD \cdot BC = AC \cdot BD $

if $ ABCD $ is cyclic. Well, we know $ AC \cdot BD \le 2 \cdot 2 = 4 $ since they can only be as long as the diameter. So

$ AB \cdot CD + AD \cdot BC \le 4 $.

How can we relate this to $ AB \cdot BC \cdot CD \cdot DA $, though? How about... AM-GM! This gives us

$ AB \cdot BC \cdot CD \cdot DA \le \left(\frac{AB \cdot CD + AD \cdot BC}{2}\right)^2 \le 2^2 = 4 $,

which is good. But wait, we have the product is $ \ge 4 $ and is $ \le 4 $, so it in fact must equal $ 4 $. This means equality holds at all the steps, or $ AC $ and $ BD $ are both diameters and $ AB \cdot CD = AD \cdot BC $.

Well, if you think about this, if $ AC $ and $ BD $ are both diameters, then $ ABCD $ is a rectangle so $ AB = CD $ and $ AD = BC $. Combining this with $ AB \cdot CD = AD \cdot BC $, we see that $ AB = BC = CD = DA $ or $ ABCD $ is a square. QED.

--------------------

Comment: After realizing that Ptolemy would probably help (through experience or Byakugan), it wasn't a huge leap to find AM-GM and develop the complete solution. It's good practice to be on the lookout for Ptolemy (in its equality and inequality forms) because it is a very useful result in problems such as this one.

--------------------

Practice Problem: (1991 AIME - #14) A hexagon is inscribed in a circle. Five of the sides have length $81$ and the sixth, denoted by $\overline{AB}$, has length $31$. Find the sum of the lengths of the three diagonals that can be drawn from $A$.

Tuesday, August 15, 2006

Why Do You Exist? Topic: Number Theory. Level: AIME.

Problem: (1997 India National Olympiad - #2) Show that there do not exist positive integers $ m $ and $ n $ such that

$ \frac{m}{n}+\frac{n+1}{m} = 4 $.

Solution: Well, multiply through by $ mn $ and rearrange as a quadratic in $ m $. This is a good idea when you're looking at squares in diophantine equations. We get

$ m^2-4nm+n(n+1) = 0 $.

But for an integer solution to exist, the discriminant must be a square. So

$ 16n^2-4n(n+1) = 12n^2-4n = 4n(3n-1) $

must be square. However, since $ (n, 3n-1) = 1 $ (prove this!), they must both be squares themselves. But $ 3n-1 \equiv 2 \pmod{3} $, which is not a quadratic residue modulo $ 3 $ so there are no solutions, as desired. QED.

--------------------

Comment: Diophantine equations are a favorite of olympiad test writers. Knowing how to handle them can be very beneficial for your next olympiad test...

--------------------

Practice Problem: Determine all integers $ k $ such that the equation $ x^2+y^2 = kxy $ has a solution in the positive integers.

Sunday, August 13, 2006

Fraction, Fraction. Topic: Algebra. Level: AMC/AIME.

Problem: (1969 Canada - #1) If $ \frac{a_1}{b_1} = \frac{a_2}{b_2} = \frac{a_3}{b_3} $ and $ p_1, p_2, p_3 $ are not all zero, show that for all $ n \in \mathbb{N} $,

$ \left(\frac{a_1}{b_1}\right)^n = \frac{p_1a_1^n+p_2a_2^n+p_3a_3^n}{p_1b_1^n+p_2b_2^n+p_3b_3^n} $.

Solution: Well, a good first step seems to be expanding it out. We want to show

$ p_1(a_1b_1)^n+p_2(a_1b_2)^n+p_3(a_1b_3)^n = p_1(a_1b_1)^n+p_2(a_2b_1)^n+p_3(a_3b_1)^n $,

which reduces to

$ p_2(a_1b_2)^n+p_3(a_1b_3)^n = p_2(a_2b_1)^n+p_3(a_3b_1)^n $.

However, noting that $ \frac{a_1}{b_1} = \frac{a_2}{b_2} = \frac{a_3}{b_3} \Rightarrow a_1b_2 = a_2b_1 $ and $ a_1b_3 = a_3b_1 $, we simply substitute and the problem is solved. QED.

--------------------

Comment: Wow. Back in the old days, this qualified for an olympiad problem. It looks slightly complicated at first, but after expanding you're done before you know it.

--------------------

Practice Problem: Show that if $ \frac{a_1}{b_1} = \frac{a_2}{b_2} = \cdots = \frac{a_n}{b_n} $, then

$ \frac{a_i}{b_i} = \frac{a_1+a_2+\cdots+a_n}{b_1+b_2+\cdots+b_n} $

for $ i = 1, 2, \ldots, n $.

Saturday, August 12, 2006

Radek SMASH! Topic: Number Theory. Level: AMC.

Problem: Find a three-digit number such that the sum of the digits is $ 9 $, the product of the digits is $ 24 $, and the number read in reverse is $ \frac{27}{38} $ of the original.

Solution: Now, we could go about mathizing all this nonsense, but instead we're just going to guess-and-check because in this case it is probably much simpler. $ 24 $ only has a few factorizations into three numbers; furthermore, it's not hard to find one that sums to $ 9 $. We see this to be $ 2 \cdot 3 \cdot 4 = 24 $.

Now, to complete the problem, we use the last piece of information. One useful thing this tells us is that the number read in reverse is divisible by $ 27 $. Knowing your powers of $ 3 $, we remember that $ 243 $ is divisible by $ 27 $. Luckily, $ 342 $ is also divisible by $ 38 $ and $ \frac{243}{342} = \frac{27}{38} $. So our number is $ 342 $. QED.

--------------------

Comment: This is the type of problem that will show up on an AMC or easier tests at smaller competitions. Speed is the main thing you're probably worried about for a problem like this; being able to take in the problem statement and analyze it quickly often is the most important skill for winning local competitions.

--------------------

Practice Problem: Use your number theory skills to devise another problem similar to this one - make sure the numerator and denominator of the fraction are both less than $ 50 $ or so (or it just gets pointless; the lower the better).

Friday, August 11, 2006

Solutions? I Think Not. Topic: Number Theory. Level: AIME.

Problem: Prove that there are no positive integer solutions to $ x^2+y^2 = 3z^2 $.

Solution: Let's use our favorite tool - mods. Suppose there exists a solution $ (x,y,z) $; if they share a common factor, we can divide it out, so we can assume WLOG that they do not.

Taking modulo $ 3 $, we get

$ x^2+y^2 \equiv 0 \pmod{3} $.

We can easily see that this requires both $ x $ and $ y $ to be divisible by $ 3 $. Let $ x = 3x_0 $ and $ y = 3y_0 $. Using our original equation,

$ 9x_0^2+9y_0^2 = 3z^2 $

$ 3(x_0^2+y_0^2) = z^2 $.

Modulo $ 3 $ again,

$ z^2 \equiv 0 \pmod{3} \Rightarrow z \equiv 0 \pmod{3} $.

But then $ 3 $ divides each of $ x,y,z $, contradicting our assumption that they do not have a common factor. Hence no solution exists. QED.

--------------------

Comment: More elementary number theory and work with mods; this uses the idea of infinite descent implicitly as well (i.e. we can show that $ x, y, z $ are infinitely divisible by $ 3 $). Diophantine equations are often simplified greatly through mods.

--------------------

Practice Problem: What positive integers can we replace $ 3 $ with such that the problem statement still holds?

Thursday, August 10, 2006

Keep Looking. Topic: Number Theory. Level: AIME.

Problem: Find a positive integer $ n $ such that if you put a $ 2 $ on the left and a $ 1 $ on the right the new number is $ 33n $.

Solution: First, we mathize the problem statement. Adding a $ 2 $ on the left is equivalent to adding $ 2 \cdot 10^k $ for some $ k $. Adding a $ 1 $ to the right is equivalent to multiplying $ n $ by $ 10 $ and adding $ 1 $. So the new number should be

$ 2 \cdot 10^k+10n+1 = 33n $

$ 2 \cdot 10^k+1 = 23n $.

Taking this modulo $ 23 $, we have

$ 2 \cdot 10^k+1 \equiv 0 \pmod{23} $.

We easily check to find $ k = 3 $ works. So, plugging in, we solve

$ 2 \cdot 1000 + 1 = 23n \Rightarrow n = 87 $.

To make sure we didn't do anything stupid, we can see that

$ 33 \cdot 87 = 2871 $,

as desired. QED.

--------------------

Comment: A pretty elementary number theory problem; the hardest part was probably converting the problem statement into its mathematical counterpart. Straightforward calculations with mods gave us the answer quickly.

--------------------

Practice Problem: Characterize all positive integers with the property in the above problem.

Tuesday, August 8, 2006

Back On Track. Topic: Algebra/Geometry. Level: AMC/AIME.

Problem: Two isosceles triangles with side lengths $ x $, $ x $, $ a $ and $ x $, $ x $, $ b $ (with $ a \neq b $) have equal areas. Find $ x $ in terms of $ a $ and $ b $.

Solution: Drop the altitude to the base in each of the triangles and use the Pythagorean Theorem to find the heights to be

$ \sqrt{x^2-\frac{a^2}{4}} $ and $ \sqrt{x^2-\frac{b^2}{4}} $,

respectively. From here, we find the areas and equate them to get

$ \frac{a}{2}\sqrt{x^2-\frac{a^2}{4}} = \frac{b}{2} \sqrt{x^2-\frac{b^2}{4}} $.

Squaring and multiplying through by $ 4 $, we have

$ a^2\left(x^2-\frac{a^2}{4}\right) = b^2\left(x^2-\frac{b^2}{4}\right) $,

which we can solve for $ x $ to obtain

$ x = \frac{\sqrt{a^2+b^2}}{2} $.

QED.

--------------------

Comment: Not a tough problem; just getting back on my feet after taking a long break from problem solving.

--------------------

Practice Problem: Given two figures in a plane, show that there exists a line that bisects both of them.