Friday, June 23, 2006
RSI 2006.
I'll be leaving tomorrow morning for Boston, Massachusetts! Probably no blog posts for 6 weeks! Take a break from math! Or not!
Tuesday, June 20, 2006
All Paired Up. Topic: Algebra/NT. Level: AIME.
Problem: Find a closed form for the sum
$ \displaystyle \sum_{i=1}^n \sum_{j=i+1}^n i \cdot j = 1 \cdot 2+1 \cdot 3+\cdots+1 \cdot n+2 \cdot 3+2 \cdot 4+\cdots+2 \cdot n+\cdots+(n-1) \cdot n $.
Solution: Consider the expansion of
$ \displaystyle (1+2+\cdots+n)^2 = \sum_{i=1}^n \sum_{j=1}^n i \cdot j $.
It's not hard to see that if we let the desired sum be $ S $, we have
$ (1+2+\cdots+n)^2 = 2S+(1^2+2^2+\cdots+n^2) $
since each pair is counted twice and the squared terms are there. But we can simplify the sums by well-known formulas to get
$ \frac{n^2(n+1)^2}{4} = 2S+\frac{n(n+1)(2n+1)}{6} $,
which becomes
$ S = \frac{n(n-1)(n+1)(3n+2)}{24} $
after massive simplification. QED.
--------------------
Comment: Symmetry was definitely the best way to approach this problem (or as far as I know anyway). You could've found a lot of ugly summations to get to the desired expression as well.
--------------------
Practice Problem: Can you generalize? In any way, shape, or form.
$ \displaystyle \sum_{i=1}^n \sum_{j=i+1}^n i \cdot j = 1 \cdot 2+1 \cdot 3+\cdots+1 \cdot n+2 \cdot 3+2 \cdot 4+\cdots+2 \cdot n+\cdots+(n-1) \cdot n $.
Solution: Consider the expansion of
$ \displaystyle (1+2+\cdots+n)^2 = \sum_{i=1}^n \sum_{j=1}^n i \cdot j $.
It's not hard to see that if we let the desired sum be $ S $, we have
$ (1+2+\cdots+n)^2 = 2S+(1^2+2^2+\cdots+n^2) $
since each pair is counted twice and the squared terms are there. But we can simplify the sums by well-known formulas to get
$ \frac{n^2(n+1)^2}{4} = 2S+\frac{n(n+1)(2n+1)}{6} $,
which becomes
$ S = \frac{n(n-1)(n+1)(3n+2)}{24} $
after massive simplification. QED.
--------------------
Comment: Symmetry was definitely the best way to approach this problem (or as far as I know anyway). You could've found a lot of ugly summations to get to the desired expression as well.
--------------------
Practice Problem: Can you generalize? In any way, shape, or form.
Saturday, June 17, 2006
Egyptian. Topic: Number Theory. Level: AIME.
Problem: (1991 India National Olympiad - #10) For any positive integer $n$, let $s(n)$ denote the number of ordered pairs $(x,y)$ of positive integers for which $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$. Determine the set of positive integers for which $s(n) = 5$.
Solution: Rewrite the equation as
$ n(x+y) = xy $
$ (x-n)(y-n) = n^2 $.
So for each pair $ (a,b) $ with $ ab = n^2 $, there exist a pair $ (x,y) = (a+n, b+n) $ satisfying
$ \frac{1}{x}+\frac{1}{y} = \frac{1}{n} $.
Hence we want to find an $ n^2 $ with $ 5 $ distinct factors. We see that $ n^2 = p^4 $ for $ p $ prime is the only case (since $ 5 $ itself is prime, meaning $ n = p^rq^s $ is not possible), so we thus have $ s(n) = 5 $ for $ n = p^2 $, where $ p $ is any prime. QED.
--------------------
Comment: A standard problem involving Simon's Favorite Factoring Trick and counting the number of divisors. SFFT is always something to look for when you have $ xy, x, y $ terms (sorta like completing the square except not).
--------------------
Practice Problem: (1991 India National Olympiad - #1) Find the number of positive integers $n$ for which
(i) $n \leq 1991$;
(ii) $6$ is a factor of $(n^2 + 3n +2)$.
Solution: Rewrite the equation as
$ n(x+y) = xy $
$ (x-n)(y-n) = n^2 $.
So for each pair $ (a,b) $ with $ ab = n^2 $, there exist a pair $ (x,y) = (a+n, b+n) $ satisfying
$ \frac{1}{x}+\frac{1}{y} = \frac{1}{n} $.
Hence we want to find an $ n^2 $ with $ 5 $ distinct factors. We see that $ n^2 = p^4 $ for $ p $ prime is the only case (since $ 5 $ itself is prime, meaning $ n = p^rq^s $ is not possible), so we thus have $ s(n) = 5 $ for $ n = p^2 $, where $ p $ is any prime. QED.
--------------------
Comment: A standard problem involving Simon's Favorite Factoring Trick and counting the number of divisors. SFFT is always something to look for when you have $ xy, x, y $ terms (sorta like completing the square except not).
--------------------
Practice Problem: (1991 India National Olympiad - #1) Find the number of positive integers $n$ for which
(i) $n \leq 1991$;
(ii) $6$ is a factor of $(n^2 + 3n +2)$.
Friday, June 16, 2006
Mission Accomplished! Topic: Algebra. Level: AIME.
Problem: (1991 India National Olympiad - #7) Solve the following system for real $ x, y, z $
$ x+y-z = 4 $
$ x^2-y^2+z^2 = -4 $
$ xyz = 6 $.
Solution: Well, we simply go about solving this system the regular way - look for something to eliminate. We try using the first and second equations and find
$ (x-z)^2 = (4-y)^2 \Rightarrow x^2-2xz+z^2 = 16-8y+y^2 $,
which we subtract from the second equation to get
$ 2xz = 8y-20 $.
Using the third equation, we have $ 2xz = \frac{12}{y} $ so we substitute, multiply through by $ y $ (it can't be zero), and divide by $ 4 $ to get
$ 0 = 2y^2-5y-3 = (2y+1)(y-3) $.
So $ y = -\frac{1}{2}, 3 $. But from the second equation, we see that $ y = -\frac{1}{2} $ gives $ x^2+z^2 < 0 $ but they are real so this is impossible. Hence $ y = 3 $. It remains to solve for $ x $ and $ z $ using
$ x-z = 1 $
$ xz = 2 $.
Substitute $ z = \frac{2}{x} $ into the first one and again multiply through by $ x $ to find
$ x^2-x-2 = (x-2)(x+1) = 0 $.
We then have $ x = 2, -1 $ with corresponding $ z = 1, -2 $. Checking, we see that both solutions work, so our final solution set is
$ (2, 3, 1) $; $ (-1, 3, -2) $.
QED.
--------------------
Comment: Not bad for an olympiad question - just requires basic algebraic manipulation and solving quadratics. Looking for the right things to square and substitute made this problem considerably easier.
--------------------
Practice Problem: (1994 India National Olympiad - #2) If $ x^5-x^3+x = a $, prove that $ x^6 \ge 2a-1 $.
$ x+y-z = 4 $
$ x^2-y^2+z^2 = -4 $
$ xyz = 6 $.
Solution: Well, we simply go about solving this system the regular way - look for something to eliminate. We try using the first and second equations and find
$ (x-z)^2 = (4-y)^2 \Rightarrow x^2-2xz+z^2 = 16-8y+y^2 $,
which we subtract from the second equation to get
$ 2xz = 8y-20 $.
Using the third equation, we have $ 2xz = \frac{12}{y} $ so we substitute, multiply through by $ y $ (it can't be zero), and divide by $ 4 $ to get
$ 0 = 2y^2-5y-3 = (2y+1)(y-3) $.
So $ y = -\frac{1}{2}, 3 $. But from the second equation, we see that $ y = -\frac{1}{2} $ gives $ x^2+z^2 < 0 $ but they are real so this is impossible. Hence $ y = 3 $. It remains to solve for $ x $ and $ z $ using
$ x-z = 1 $
$ xz = 2 $.
Substitute $ z = \frac{2}{x} $ into the first one and again multiply through by $ x $ to find
$ x^2-x-2 = (x-2)(x+1) = 0 $.
We then have $ x = 2, -1 $ with corresponding $ z = 1, -2 $. Checking, we see that both solutions work, so our final solution set is
$ (2, 3, 1) $; $ (-1, 3, -2) $.
QED.
--------------------
Comment: Not bad for an olympiad question - just requires basic algebraic manipulation and solving quadratics. Looking for the right things to square and substitute made this problem considerably easier.
--------------------
Practice Problem: (1994 India National Olympiad - #2) If $ x^5-x^3+x = a $, prove that $ x^6 \ge 2a-1 $.
Monday, June 12, 2006
Hockey! Topic: Probability & Combinatorics. Level: AMC/AIME.
Theorem: (Hockey Stick) $ rCr+(r+1)Cr+\cdots+nCr = (n+1)C(r+1) $.
Proof: Consider the number of ways to choose $ r+1 $ people out of a group of $ n+1 $ people. This is clearly $ (n+1)C(r+1) $. Now try counting this another way. Suppose we number the people $ 1, 2, \ldots, n+1 $. Consider the cases based on the highest-numbered person.
If the highest-numbered person in the $ r+1 $ person group is $ \le r $, we clearly cannot have $ r+1 $ people.
On the other hand, if the highest-numbered person, numbered $ k+1 $, is greater than $ r $, we automatically include $ k+1 $ and choose the remaining $ r $ people from the lower $ k $ numbers, giving $ kCr $. So we thus have
$ (n+1)C(r+1) = rCr+(r+1)Cr+\cdots+nCr $
as desired. QED.
--------------------
Comment: This always struck me as one of the most interesting theorems, partially because of its name, which is derived from the shape it forms on Pascal's Triangle (try finding each of the terms).
Proof: Consider the number of ways to choose $ r+1 $ people out of a group of $ n+1 $ people. This is clearly $ (n+1)C(r+1) $. Now try counting this another way. Suppose we number the people $ 1, 2, \ldots, n+1 $. Consider the cases based on the highest-numbered person.
If the highest-numbered person in the $ r+1 $ person group is $ \le r $, we clearly cannot have $ r+1 $ people.
On the other hand, if the highest-numbered person, numbered $ k+1 $, is greater than $ r $, we automatically include $ k+1 $ and choose the remaining $ r $ people from the lower $ k $ numbers, giving $ kCr $. So we thus have
$ (n+1)C(r+1) = rCr+(r+1)Cr+\cdots+nCr $
as desired. QED.
--------------------
Comment: This always struck me as one of the most interesting theorems, partially because of its name, which is derived from the shape it forms on Pascal's Triangle (try finding each of the terms).
Saturday, June 10, 2006
Five Whole Numbers. Topic: Algebra/Polynomials. Level: AIME.
Problem: (1999 JBMO - #1) Let $ a, b, c, x, y $ be five real numbers such that $ a^3+ax+y = 0 $, $ b^3+bx+y = 0 $, and $ c^3+cx+y = 0 $. If $ a, b, c $ are all distinct numbers, prove that their sum is zero.
Solution: Consider the polynomial $ f(t) = t^3+tx+y $. Since it is a third degree polynomial, it can have at most three real roots. But we are given that
$ f(a) = 0 $, $ f(b) = 0 $, $ f(c) = 0 $
so we know that it in fact has exactly three distinct real roots and no other ones. But by Vieta's Formulas, we know that the sum of the roots is the coefficient of the $ t^2 $ term, which is zero. Thus
$ a+b+c = 0 $,
as desired. QED.
--------------------
Comment: A pretty simple problem to be on an olympiad, even if it is the Junior Balkan Math Olympiad (JBMO). The solution is almost immediate if you have worked with polynomials a lot.
--------------------
Practice Problem: (2000 JBMO - #1) Let $x$ and $y$ be positive reals such that
$x^3 + y^3 + (x + y)^3 + 30xy = 2000$.
Show that $x + y = 10$.
Solution: Consider the polynomial $ f(t) = t^3+tx+y $. Since it is a third degree polynomial, it can have at most three real roots. But we are given that
$ f(a) = 0 $, $ f(b) = 0 $, $ f(c) = 0 $
so we know that it in fact has exactly three distinct real roots and no other ones. But by Vieta's Formulas, we know that the sum of the roots is the coefficient of the $ t^2 $ term, which is zero. Thus
$ a+b+c = 0 $,
as desired. QED.
--------------------
Comment: A pretty simple problem to be on an olympiad, even if it is the Junior Balkan Math Olympiad (JBMO). The solution is almost immediate if you have worked with polynomials a lot.
--------------------
Practice Problem: (2000 JBMO - #1) Let $x$ and $y$ be positive reals such that
$x^3 + y^3 + (x + y)^3 + 30xy = 2000$.
Show that $x + y = 10$.
Wednesday, June 7, 2006
Kakuro. Topic: Logic.
Taking a break from math, here is an interesting puzzle. It's called Kakuro and it's similar to Sudoku, but not really the same either. Basically, you have a lot of open squares and some dark squares with a diagonal slash through them (and some irrelevent filled dark squares). These dark squares might have a number in the lower left corner and/or a number in the upper right corner.
Lower Left - All the consecutive blank spaces below contain different numbers (1-9) and sum to the number in the lower left corner of the dark square.
Upper Right - All the consecutive blank spaces to the right contain different numbers (1-9) and sum to the number in the upper right corner of the dark square.
These puzzles all have a unique solution that can be determined through logic (no guessing is necessary), but they can be very difficult! Take a stab at it. If it's too easy, check out some of the other puzzles on the site.
Lower Left - All the consecutive blank spaces below contain different numbers (1-9) and sum to the number in the lower left corner of the dark square.
Upper Right - All the consecutive blank spaces to the right contain different numbers (1-9) and sum to the number in the upper right corner of the dark square.
These puzzles all have a unique solution that can be determined through logic (no guessing is necessary), but they can be very difficult! Take a stab at it. If it's too easy, check out some of the other puzzles on the site.
Monday, June 5, 2006
Better Count Them Right. Topic: Probability & Combinatorics/Sets. Level: AIME.
Problem: (2006 ARML Tiebreaker - #1) In how many ways can you choose three distinct numbers from the set $ \{1, 2, \ldots, 34\} $ such that the sum is divisible by three? [Reworded]
Solution: Well let's break it down into cases. Even better, let's just look at the elements $ \pmod{3} $. There are $ 11 $ $ 0 $'s, $ 12 $ $ 1 $'s, and $ 11 $ $ 2 $'s.
CASE 1: $ 0, 0, 0 $.
Well we can just take $ 11 \cdot 10 \cdot 9 $ but since we want combinations of these, it is $ \frac{11 \cdot 10 \cdot 9}{3 \cdot 2 \cdot 1} = 165 $.
CASE 2: $ 1, 1, 1 $.
Same idea, only we have $ 12 $ to choose from. $ \frac{12 \cdot 11 \cdot 10}{3 \cdot 2 \cdot 1} = 220 $.
CASE 3: $ 2, 2, 2 $.
Same as CASE 1. $ 165 $.
CASE 4: $ 0, 1, 2 $.
We have $ 11 \cdot 12 \cdot 11 $ total sets of three. We see that since the elements are distinct modulo three none of them can be permutations of each other. So we have $ 11 \cdot 12 \cdot 11 = 1452 $.
It's not hard to tell that these are all the cases (well, a little harder under time pressure) so we can just sum them up to get $ 165+220+165+1452 = 2002 $. QED.
--------------------
Comment: The fastest correct answer to this problem at the Las Vegas ARML Site was 2 minutes and 2 seconds. Across the country, it was somewhere around 1 minute. Pretty quick.
--------------------
Practice Problem: (2006 ARML Tiebreaker - #2) Let $ f(x) = mx+b $ where $ m $ and $ b $ are integers with $ m > 0 $. If $ 2^{f(x)} = 5 $ when $ x = \log_8{10} $, find the ordered pair $ (m, b) $. [Reworded]
Solution: Well let's break it down into cases. Even better, let's just look at the elements $ \pmod{3} $. There are $ 11 $ $ 0 $'s, $ 12 $ $ 1 $'s, and $ 11 $ $ 2 $'s.
CASE 1: $ 0, 0, 0 $.
Well we can just take $ 11 \cdot 10 \cdot 9 $ but since we want combinations of these, it is $ \frac{11 \cdot 10 \cdot 9}{3 \cdot 2 \cdot 1} = 165 $.
CASE 2: $ 1, 1, 1 $.
Same idea, only we have $ 12 $ to choose from. $ \frac{12 \cdot 11 \cdot 10}{3 \cdot 2 \cdot 1} = 220 $.
CASE 3: $ 2, 2, 2 $.
Same as CASE 1. $ 165 $.
CASE 4: $ 0, 1, 2 $.
We have $ 11 \cdot 12 \cdot 11 $ total sets of three. We see that since the elements are distinct modulo three none of them can be permutations of each other. So we have $ 11 \cdot 12 \cdot 11 = 1452 $.
It's not hard to tell that these are all the cases (well, a little harder under time pressure) so we can just sum them up to get $ 165+220+165+1452 = 2002 $. QED.
--------------------
Comment: The fastest correct answer to this problem at the Las Vegas ARML Site was 2 minutes and 2 seconds. Across the country, it was somewhere around 1 minute. Pretty quick.
--------------------
Practice Problem: (2006 ARML Tiebreaker - #2) Let $ f(x) = mx+b $ where $ m $ and $ b $ are integers with $ m > 0 $. If $ 2^{f(x)} = 5 $ when $ x = \log_8{10} $, find the ordered pair $ (m, b) $. [Reworded]
Sunday, June 4, 2006
Thursday, June 1, 2006
Stop Being So Cheap. Topic: Calculus/Inequalities. Level: Olympiad.
Problem: Minimize the average cost function $ \displaystyle C(l_1, l_2, \ldots, l_m) = \sum_{i=1}^m p_ic_il_i $ where $ p_i $ and $ c_i $ for $ i = 1, 2, \ldots, m $ are constants (representing probability and cost per letter of a codeword) and $ l_i $ for $ i = 1, 2, \ldots, m $ are variables (representing codeword length) subject to the constraint $ \displaystyle \sum_{i=1}^m 2^{-l_i} \le 1 $.
Solution: Assume all summations run from $ 1 $ to $ m $. Now, let's put our favorite technique Langrange multipliers to the use! We see that we must have equality to minimize $ C $ (or we could just decrease and arbitrary $ l_i $) so let
$ \displaystyle g(l_1, l_2, \ldots, l_m) = \left(\sum 2^{-l_i}\right) - 1 = 0 $
Then we have
$ C_{l_i} = p_ic_i = \lambda g_{l_i} = \lambda(\ln{(2)} \cdot 2^{-l_i}) $,
where $ C_{l_i} $ and $ g_{l_i} $ are the partial derivatives of $ C $ and $ g $ with respect to $ l_i $. So
$ 2^{-l_i} = \frac{p_ic_i}{\ln{(2)} \cdot \lambda} $.
Then we substitute back into our constraint $ g $ to get
$ \displaystyle g(l_1, l_2, \ldots, l_m) = \left(\sum 2^{-l_i}\right) - 1 = \left(\sum \frac{p_ic_i}{\ln{(2)} \cdot \lambda} \right) - 1 = 0 $,
which gives us
$ \displaystyle \lambda = \frac{\sum p_ic_i}{\ln{(2)}} $,
so, solving from our equation above,
$ \displaystyle l_i = -\log_2{\left(\frac{p_ic_i}{\sum p_ic_i}\right)} $.
Hence we have our minimum $ C $ as
$ \displaystyle C_{min} = \sum p_ic_il_i = -\sum p_ic_i \log_2{\left(\frac{p_ic_i}{\sum p_ic_i}\right)} = \sum p_ic_i \log_2{\left(\frac{\sum p_ic_i}{p_ic_i}\right)} $.
QED.
--------------------
Comment: Here we have a real-world application of the technique of Lagrange multipliers, a common optimization technique in multivariate calculus. In actuality, the $ l_i $ need to be restricted to integers, but this gives us a lower bound that can be achieved in special cases. It can be further shown that an optimal code has an average cost of at most
$ \displaystyle C_{min} + \sum p_ic_i $.
Solution: Assume all summations run from $ 1 $ to $ m $. Now, let's put our favorite technique Langrange multipliers to the use! We see that we must have equality to minimize $ C $ (or we could just decrease and arbitrary $ l_i $) so let
$ \displaystyle g(l_1, l_2, \ldots, l_m) = \left(\sum 2^{-l_i}\right) - 1 = 0 $
Then we have
$ C_{l_i} = p_ic_i = \lambda g_{l_i} = \lambda(\ln{(2)} \cdot 2^{-l_i}) $,
where $ C_{l_i} $ and $ g_{l_i} $ are the partial derivatives of $ C $ and $ g $ with respect to $ l_i $. So
$ 2^{-l_i} = \frac{p_ic_i}{\ln{(2)} \cdot \lambda} $.
Then we substitute back into our constraint $ g $ to get
$ \displaystyle g(l_1, l_2, \ldots, l_m) = \left(\sum 2^{-l_i}\right) - 1 = \left(\sum \frac{p_ic_i}{\ln{(2)} \cdot \lambda} \right) - 1 = 0 $,
which gives us
$ \displaystyle \lambda = \frac{\sum p_ic_i}{\ln{(2)}} $,
so, solving from our equation above,
$ \displaystyle l_i = -\log_2{\left(\frac{p_ic_i}{\sum p_ic_i}\right)} $.
Hence we have our minimum $ C $ as
$ \displaystyle C_{min} = \sum p_ic_il_i = -\sum p_ic_i \log_2{\left(\frac{p_ic_i}{\sum p_ic_i}\right)} = \sum p_ic_i \log_2{\left(\frac{\sum p_ic_i}{p_ic_i}\right)} $.
QED.
--------------------
Comment: Here we have a real-world application of the technique of Lagrange multipliers, a common optimization technique in multivariate calculus. In actuality, the $ l_i $ need to be restricted to integers, but this gives us a lower bound that can be achieved in special cases. It can be further shown that an optimal code has an average cost of at most
$ \displaystyle C_{min} + \sum p_ic_i $.
Subscribe to:
Posts (Atom)