Mathematical Food for Thought


			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.

Meta
- Register
- Log in
- Valid XHTML
- XFN
- WordPress

Credits
- Design by Stacee Leung
- Coded by Daynah Nguyen
- Powered by Wordpress

Polynomial On The Floor? Topic: Algebra/Polynomials. Level: AIME.	May 30th, 2006
Problem: (2005 Putnam – B1) Find a nonzero polynomial such that $P(\lfloor a \rfloor, \lfloor 2a \rfloor) = 0$ for all reals numbers . Solution: What’s the relation between $\lfloor a \rfloor$ and $\lfloor 2a \rfloor$ ? We can see that either $\lfloor 2a \rfloor = 2 \lfloor a \rfloor$ or $\lfloor 2a \rfloor = 2 \lfloor a \rfloor + 1$ for all reals (yes, even negative ones). So it suffices to have a polynomial with zeros at and , such as . QED. ——————– Comment: This is about the easiest question you’ll see on a Putnam test. Each question is worth 10 points (120 total) and about half of the people who take it get 0 points. ——————– Practice Problem: (2005 Putnam – A1) Show that every positive integer is a sum of one or more numbers of the form , where and are nonnegative integers and no summand divides another. (For example, .) Posted in AIME, Algebra, Polynomials \|\| 3 Comments »
Don’t Mess With The Juggernaut. Topic: Inequalities. Level: Olympiad.	May 28th, 2006
Problem: Given nonnegative reals satisfying , find the minimum of the expression for $k \ge \frac{15}{4}$ . Solution: At first glance, we’re like it’s just a boring classical homogeneous symmetric inequality. The minimum must occur at ! But looking into it a little more, we find that if $a = b = \frac{3}{2}, c = 0$ we get something smaller. In fact, we will show that this is the minimum. We claim that $a^3+b^3+c^3+kabc \ge \frac{(a+b+c)^3}{4}$ . Expanding and rearranging, this is equivalent to $3(a^3+b^3+c^3)+(4k-6)abc \ge 3(a^2b+a^2c+b^2c+b^2a+c^2a+c^2b)$ . But wait, this form reminds us a lot of Schur! Schur says that (multiplied by a factor of ) $3(a^3+b^3+c^3)+9abc \ge 3(a^2b+a^2c+b^2c+b^2a+c^2a+c^2b)$ . So it remains to show that $(4k-15)abc \ge 0$ . But since $4k-15 \ge 0$ (from $k \ge \frac{15}{4}$ ) and are nonnegative, the inequality is clearly true. Hence we have $a^3+b^3+c^3+kabc \ge \frac{(a+b+c)^3}{4} = \frac{27}{4}$ for $k \ge \frac{15}{4}$ . Note that the equality conditions are met in both inequalities when $a = b = \frac{3}{2}$ and . QED. ——————– Comment: Original problem was motivated by the case , but easily generalized by seeing the proof. This is an interesting inequality because it doesn’t have the usual equality case except when $k = \frac{15}{4}$ . ——————– Practice Problem: Solve for $x \in \mathbb{R}$ $2x^2-3x\lfloor x-1 \rfloor+\lfloor x-1 \rfloor^2 \le 0$ . Posted in Inequalities, Olympiad \|\| 3 Comments »
It’s A One-To-One Tie! Topic: Linear Algebra.	May 26th, 2006
Note: Added my linear algebra book to the Math Books page. ——————– Definition: A function $f: A \to B$ is linear if and for $x,y \in A$ and $c \in \mathbb{R}$ (or, rather, any field $\mathbb{F}$ ). Furthermore, it is one-to-one if and only if $f(x) = f(y) \Rightarrow x = y$ . ——————– Problem: Let and be vector spaces, and let $T: V \to W$ be linear. Then is one-to-one if and only if carries linearly independent subsets of onto linearly independent subsets of . Solution: First we will show that if is one-to-one, then it carries linearly independent subsets of onto linearly independent subsets of . Let be a linearly independent subset of . Suppose $S = \{x_1, x_2, \ldots, x_k\}$ . We want to show that $R = \{T(x_1), T(x_2), \ldots, T(x_k)\}$ is also linearly independent. Suppose that is not. Then there exist $a_1, a_2, \ldots, a_k$ not all zero such that $a_1T(x_1)+a_2T(x_2)+\cdots+a_kT(x_k) = 0$ . Since is linear, we can rewrite this as $T(a_1x_1)+T(a_2x_2)+\cdots+T(a_kx_k) = T(a_1x_1+a_2x_2+\cdots+a_kx_k) = 0$ . Since and is one-to-one, we must have $a_1x_1+a_2x_2+\cdots+a_kx_k = 0$ . But is linearly independent, so this is only possible if $a_1 = a_2 = \cdots = a_k = 0$ , a contradiction. So is linearly independent. Now, we will prove the converse – if takes linearly independent subsets of to linearly independent subsets of then is one-to-one. Let $x, y \in V$ be nonzero such that . It suffices to show that . If $\{x, y\}$ is linearly dependent, then for some $c \in \mathbb{R}$ , so . If $T(x) = T(y) \neq 0$ , we have $c = 1 \Rightarrow x = y$ . In the case that , the set $\{x\}$ is linearly independent but takes it onto $\{0\}$ , which is linearly dependent, a contradiction. If $\{x, y\}$ is linearly independent, then $\{T(x), T(y)\}$ is also linearly independent. But since , the set is clearly linearly dependent, a contradiction. Lastly, we have . So must be a one-to-one function, as desired. QED. ——————– Comment: Basically, we made extensive use of the properties of a linear transformation to prove both directions. A nice corollary to this proof is that if is one-to-one, then is linearly independent if and only if is linearly independent. ——————– Practice Problem: Let and be vector spaces, and let $T: V \to W$ be linear. Then is one-to-one if and only if $N(T) = \{0\}$ (here, is the kernal of , defined by $N(T) = \{x \| T(x) = 0\}$ ). Posted in Linear Algebra \|\| No Comments »
The Algebra Of Lines? Topic: Linear Algebra.	May 24th, 2006
Note: See MathWorld for any necessary definitions. ——————– Problem: Let $\{v_1, v_2, \ldots, v_m\}$ be a linearly independent set of vectors in a nonzero subspace of $\mathbb{R}^n$ such that $span(v_1, v_2, \ldots, v_m) \subset S$ . Then it can be extended by adding some more vectors to form a basis of . Solution: Take any vector $v_{m+1} \in S$ such that $v_{m+1}$ is not a linear combination of $\{v_1, v_2, \ldots, v_m\}$ (i.e. $v_{m+1}$ is not in the span of the original set of vectors). The existence of such a vector is guaranteed by the fact that the span is strictly contained within Since it is not a linear combination, the new set $\{v_1, v_2, \ldots, v_{m+1}\}$ is still linearly independent. Furthermore, it has a greater span than the original set. If the new span is still strictly contained within , we may add another vector $v_{m+2} \in S$ . Repeating this process allows us to keep increasing the span. But we also note that this process must terminate because a set of vectors that is linearly independent must span all of $\mathbb{R}^n$ ; therefore, after adding some vector with $m < k \le n$ we will have formed a basis $\{v_1, v_2, \ldots, v_k\}$ of . QED. ——————– Comment: This is actually a lemma that leads to one of the most basic nontrivial results in Linear Algebra, that every subspace of $\mathbb{R}^n$ in fact has a basis. The idea is trivial in $\mathbb{R}^3$ , for example, because a single vector is the basis for any line through the origin and two vectors are the basis for any plane through the origin. It is known that lines and planes through the origin (as well as and $\mathbb{R}^3$ itself) are the only subspaces in $\mathbb{R}^3$ . ——————– Practice Problem: Any two bases of a subspace of $\mathbb{R}^n$ have the same number of elements (this number is called the dimension of ). Posted in Linear Algebra \|\| 3 Comments »
Productive! Topic: Algebra/NT. Level: AIME.	May 23rd, 2006
Problem: (2006 Bellevue BATH Team) Evaluate $\displaystyle \sum_{a=1}^{10} \sum_{b=1}^{10} \sum_{c=1}^{10} \sum_{d=1}^{10} dcab$ . Solution: Note that we can write the sum as $\displaystyle \sum_{b=1}^{10} \sum_{c=1}^{10} \sum_{d=1}^{10} (1 \cdot bcd+ 2 \cdot bcd + \cdots + 10 \cdot bcd) = \sum_{b=1}^{10} \sum_{c=1}^{10} \sum_{d=1}^{10} (1+2+\cdots+10)bcd$ . Using the same idea, we can write it as $(1+2+\cdots+10)(1+2+\cdots+10)(1+2+\cdots+10)(1+2+\cdots+10) = 55^4$ . QED. ——————– Comment: Evaluating multiple summations this way is very effective. Other examples include factoring the harmonic series $\displaystyle 1+\frac{1}{2}+\frac{1}{3}+\cdots = \left(1+\frac{1}{2}+\frac{1}{2^2}+\cdots\right) \left(1+\frac{1}{3}+\frac{1}{3^2}+\cdots\right) \left(1+\frac{1}{5}+\frac{1}{5^2}+\cdots\right) = \prod \sum_{i=0}^\infty \frac{1}{p^i}$ or, more generally, any integer value of the Riemann Zeta Function $\displaystyle \zeta(s) = 1^s+\frac{1}{2^s}+\frac{1}{3^s}+\cdots = \prod \sum_{i=0}^\infty \frac{1}{p^is}$ . Furthermore, since $\displaystyle \sum_{i=0}^\infty \frac{1}{p^is}$ is an infinite geometric series of common ratio $\frac{1}{p^s}$ , we can say that $\zeta(s) = \prod \frac{1}{p^s-1}$ , where the product is taken over all primes . Posted in AIME, Algebra, Number Theory \|\| No Comments »

free web counters