Mathematical Food for Thought


			Mathematical Food for Thought

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

RSI 2006	March 31st, 2006
For anyone interested, I got accepted and will be attending! Posted in Announcements \|\| 2 Comments »
Zero Has No Friends. Topic: Combinatorics/Inequalities/Sets. Level: Olympiad.	March 30th, 2006
Problem: (360 Problems For Mathematical Contests – 6.1.9) Find the maximum number of nonzero terms of the sum $\displaystyle \sum_{i,j=1}^n \|f(i)-f(j)\|$ where $f:\{1,2,\ldots,n\} \rightarrow \{a,b,c\}$ is one of the possible functions. Solution: Let be the number of elements $p \in \{1,2,\ldots,n\}$ such that . Similarly define and to be the corresponding values for and , respectively. Since there are total values in the domain, we know . We will try counting the opposite of what we want and minimizing it; the number of pairs such that . The number of ways we can pick two elements that map to is ( choices for both the first and second). Similarly, the number that map to and are and , respectively. Now it remains to minimize for . By Cauchy or AM-GM, we know $x^2+y^2+z^2 \ge \frac{1}{3}(x+y+z)^2 = \frac{n^2}{3}$ . But remember that have to be positive integers, so we have two separate cases: (1) if is a multiple of , then the minimum is $\frac{n^2}{3}$ , (2) otherwise, it is $\frac{n^2+2}{3}$ . So we then subtract the minimum number of zero terms from the total number of terms to get $\frac{2n^2}{3}$ if is a multiple of and $\frac{2(n^2-1)}{3}$ otherwise. This can also be stated as $\left\lfloor \frac{2n^2}{3} \right\rfloor$ . QED. ——————– Comment: It can be a good idea to look at the complement of what you actually are counting because it may be a lot simpler to count. This is a common technique in probability problems as well. ——————– Practice Problem: (360 Problems For Mathematical Contests – 6.1.6) Let $a_1, a_2, \ldots, a_n$ be positive real numbers and let $k \ge 0$ . Prove that $\displaystyle k+\sqrt[n]{\prod_{i=1}^n a_i} \le \sqrt[n]{\prod_{i=1}^n (k+a_i)} \le k +\frac{1}{n} \sum_{i=1}^n a_i$ . Posted in Inequalities, Olympiad, Probability & Combinatorics, Sets \|\| No Comments »
Set To Set. Topic: Sets. Level: Olympiad.	March 29th, 2006
Problem: (360 Problems For Mathematical Contests – 6.1.4) Let be a set with elements and let be a subset of with $k \ge 1$ elements. Find the number of functions $f: A \rightarrow A$ such that . Problem: First consider the elements of . Since has to return the same set of elements, no two elements $a,b \in X$ can have (or we wouldn’t be able to get the entire set back). So if we pick any element we have choices for . Then when we pick we only have choices for . Continuing this, we find that there are ways to assign each element in . Now for the other elements of , we can arbitrarily assign where they map to. Since each has elements to map to, there is an additional factor of $n^{n-k}$ to the number of functions. This gives us a total of $k! \cdot n^{n-k}$ possible functions . QED. ——————– Comment: Basic sets and functions are a good thing to know in order to build on. They don’t require much mathematical background to work through, and are mostly logical (with some combinatorics). ——————– Practice Problem: (360 Problems For Mathematical Contests – 6.1.1) Let be a set with elements and let be a subset of with $m \ge 1$ elements. Find the number of functions $f: A \rightarrow A$ such that $f(B) \subseteq B$ . Posted in Olympiad, Sets \|\| No Comments »
Ceva’s Here! Topic: Geometry/Inequalities. Level: Olympiad.	March 28th, 2006
Problem: (1996 IMO Shortlist – #13) Let be an equilateral triangle and let be a point in its interior. Let the lines meet the sides at the points , respectively. Prove that $A_1B_1 \cdot B_1C_1 \cdot C_1A_1 \ge A_1B \cdot B_1C \cdot C_1A$ . Solution: First thing to take into account is the fact that the triangle is equilateral. There is probably a good reason for this, so let’s try and find it. Applying the Law of Cosines on triangle , we find $(A_1B_1)^2 = (A_1C)^2+(B_1C)^2-A_1C \cdot B_1C$ . But since $(A_1C-B_1C)^2 \ge 0 \Rightarrow (A_1C)^2+(B_1C)^2-A_1C \cdot B_1C \ge A_1C \cdot B_1C$ , we have $(A_1B_1)^2 \ge A_1C \cdot B_1C$ . Similarly, $(B_1C_1)^2 \ge B_1A \cdot C_1A$ and $(C_1A_1)^2 \ge C_1B \cdot A_1B$ . Multiplying these three inequalities together, we obtain $(A_1B_1 \cdot B_1C_1 \cdot C_1A_1)^2 \ge (A_1B \cdot B_1C \cdot C_1A)(A_1C \cdot B_1A \cdot C_1B)$ . But by Ceva’s, we know $A_1B \cdot B_1C \cdot C_1A = A_1C \cdot B_1A \cdot C_1B$ , so $(A_1B_1 \cdot B_1C_1 \cdot C_1A_1)^2 \ge (A_1B \cdot B_1C \cdot C_1A)^2$ and $A_1B_1 \cdot B_1C_1 \cdot C_1A_1 \ge A_1B \cdot B_1C \cdot C_1A$ as desired. QED. ——————– Comment: After we were able to figure out an effective way to use the equilateral condition, it wasn’t hard to see the inequality there. Then the problem just asks for Ceva, which fits in nicely at the end. ——————– Practice Problem: (1996 USAMO – #5) Let be a triangle, and an interior point such that $\angle MAB=10^\circ$ , $\angle MBA=20^\circ$ , $\angle MAC=40^\circ$ , and $\angle MCA=30^\circ$ . Prove that the triangle is isosceles. Posted in Geometry, Inequalities, Olympiad \|\| No Comments »
Yum! Topic: Inequalities. Level: Olympiad.	March 27th, 2006
Problem: Let be positive reals such that . Prove that $\frac{a}{a^3+a^2+4}+\frac{b}{b^3+b^2+4}+\frac{c}{c^3+c^2+4} \le \frac{1}{2}$ . Solution: We will use a method of solving inequalities called “Isolated Fudging.” Since the variables are separated we will prove an inequality for each individual term. We guess that there exists a real such that $\frac{a}{a^3+a^2+4} \le \frac{1}{6}+ka^2-k$ . Doing the same for each variable and summing up, we see that this will prove the result. To find , we throw in some calculus (the part ensuing is not necessary in a formal solution write-up, so you don’t need to include any calculus in the “official” solution). Let $f(a) = \frac{1}{6}+ka^2-k-\frac{a}{a^3+a^2+4}$ . Differentiating with respect to , we have $f^{\prime}(a) = 2ak-\frac{(a^3+a^2+4)-a(3a^2+2a)}{(a^3+a^2+4)^2}$ . Looking at the equality case in the problem, we see that . So if our guess is correct, then $f^{\prime}(1) = 0$ . So $f^{\prime}(1) = 2k-\frac{1}{36} = 0 \Rightarrow k = \frac{1}{72}$ . Now back to the solution. It remains to show that $\frac{a}{a^3+a^2+4} \le \frac{1}{6}+\frac{1}{72}a^2-\frac{1}{72} = \frac{11}{72}+\frac{1}{72}a^2$ , which is equivalent to $72a \le (a^3+a^2+4)(a^2+11)$ , or $0 \le (a-1)^2(a^3+3a^2+16a+44)$ . Since is a positive real, we have and $(a-1)^2 \ge 0$ , so it is true. Hence $\frac{a}{a^3+a^2+4}+\frac{b}{b^3+b^2+4}+\frac{c}{c^3+c^2+4} \le \left(\frac{11}{72}+\frac{1}{72}a^2\right) + \left(\frac{11}{72}+\frac{1}{72}b^2\right) + \left(\frac{11}{72}+\frac{1}{72}c^2\right) = \frac{1}{2}$ , as desired. QED. ——————– Comment: Isolated Fudging is a pretty neat trick and there are many variations on it, which are nice to learn. It lets you come up with solutions that have extremely strange numbers but magically work out. ——————– Practice Problem: (2005 IMO – #3) Prove that for all positive with product at least , $\frac{a^5-a^2}{a^5+b^2+c^2} + \frac{b^5-b^2}{b^5+c^2+a^2} + \frac{c^5-c^2}{c^5+a^2+b^2} \ge 0$ . Posted in Inequalities, Olympiad \|\| 2 Comments »

free web counters