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

Bigger Means Better. Topic: Algebra/Inequalities/Sets. Level: Olympiad.	May 12th, 2007
Definition: A set is said to be convex if, for any $X, Y \in S$ and $\lambda \in [0,1]$ , we have $\lambda X+(1-\lambda)Y \in S$ . ——————– Definition: Let $f: D \rightarrow \mathbb{R}$ be a real-valued function defined on a convex set . We say that is convex if, for all $X, Y \in D$ and $\lambda \in [0, 1]$ , we have $\lambda f(X) + (1-\lambda) f(Y) \ge f(\lambda X+(1-\lambda)Y)$ . ——————– Theorem: (Jensen’s Inequality) Let be a real-valued, convex function defined on a convex set . Given $x_1, x_2, \ldots, x_n \in D$ and nonnegative reals $w_1, w_2, \ldots, w_n$ such that $w_1+w_2+\cdots+w_n = 1$ , we have $w_1f(x_1)+w_2f(x_2)+\cdots+w_nf(x_n) \ge f(w_1x_1+w_2x_2+\cdots+w_nx_n)$ or, more concisely, $\displaystyle \sum_{i=1}^n w_if(x_i) \ge f\left(\sum_{i=1}^n w_ix_i\right)$ . Proof: We proceed by induction on . Base Case – , we have $f(x_1) \ge f(x_1)$ which is trivially true. , we have $\lambda_1 f(x_1)+\lambda_2 f(x_2) \ge f(\lambda_1 x_1+\lambda_2 x_2)$ with $\lambda_1+\lambda_2 = 1$ which is true by the definition of convexity. Induction Step – Suppose $\displaystyle \sum_{i=1}^k w_if(x_i) \ge f\left(\sum_{i=1}^k w_ix_i\right)$ . We wish to show $\displaystyle \sum_{i=1}^{k+1} u_if(x_i) \ge f\left(\sum_{i=1}^{k+1} u_ix_i\right)$ for nonnegative reals $u_1, u_2, \ldots, u_{k+1}$ that sum to . Well, $\displaystyle f\left(\sum_{i=1}^{k+1} u_ix_i\right) \le u_{k+1}f(x_{k+1})+(1-u_{k+1})f\left(\frac{1}{1-u_{k+1}} \sum_{i=1}^k u_ix_i\right)$ by the definition of convexity. But since $\displaystyle \frac{1}{1-u_{k+1}} \sum_{i=1}^k u_i = \sum_{i=1}^k \frac{u_i}{1-u_{k+1}} = 1$ , by our inductive hypothesis (the term case) we must have $\displaystyle f\left(\frac{1}{1-u_{k+1}} \sum_{i=1}^k u_ix_i\right) \le \sum_{i=1}^k \frac{u_i}{1-u_{k+1}} f(x_i)$ . Combining this into the above inequality, we obtain $\displaystyle f\left(\sum_{i=1}^{k+1} u_ix_i\right) \le u_{k+1}f(x_{k+1})+(1-u_{k+1})\sum_{i=1}^k \frac{u_i}{1-u_{k+1}} f(x_i) = \sum_{i=1}^{k+1} u_if(x_i)$ as desired, completing the induction. QED. ——————– Definition: The convex hull of a set is defined to be the smallest convex set containing . It is the set of all points that can be written as $\displaystyle \sum_{i=1}^n a_ix_i$ , where is a natural number, $a_1, a_2, \ldots, a_n$ are nonnegative reals that sum to , and $x_1, x_2, \ldots, x_n \in S$ . ——————– Definition: A vertex of a set is a point $v \in D$ such that for all $x \in D$ not equal to and $\lambda > 1$ we have $\lambda v+(1-\lambda)x \not\in D$ . ——————– Theorem: Let $V_D = \{v_1, v_2, \ldots, v_k\}$ be the set of vertices of a compact convex set . The convex hull of is . Example: The set of vertices of a convex polygon is, in fact, its vertices as traditionally defined in geometry. Any point inside the polygon can be written as a convex combination of its vertices. ——————– Theorem: If is a real-valued, convex function defined on a compact convex set , then $\displaystyle \max_{x \in D} f(x) = \max_{x \in V_D} f(x)$ , where is the set of vertices of . Proof: We will show that $\displaystyle f(x) \le \max_{x \in V_D} f(x)$ for all $x \in D$ . Let $\displaystyle x = \sum_{i=1}^k \lambda_i v_i$ where $\lambda_1, \lambda_2, \ldots, \lambda_k$ are nonnegative reals that sum to and $V_D = \{v_1, v_2, \ldots, v_k\}$ . This is possible by the preceding theorem. Then by Jensen’s Inequality we get $\displaystyle \sum_{i=1}^k \lambda_i f(v_i) \ge f\left(\sum_{i=1}^k \lambda_i v_i\right) = f(x)$ . And since $\displaystyle \max_{x \in V_D} f(x) \ge \sum_{i=1}^k \lambda_i f(v_i)$ , we have $\displaystyle \max_{x \in V_D} f(x) \ge f(x)$ for all $x \in D$ . Furthermore, since is a subset of , we know that this maximum is attained, thus $\displaystyle \max_{x \in D} f(x) = \max_{x \in V_D} f(x)$ as desired. QED. ——————– Comment: This is a very useful result, as it allows us to limit our search for the maximum of a function to its set of vertices, which is usually a considerably smaller set, though it may still be infinite (think sphere). In any case, this works well for constrained optimization problems in which the domain is limited to a polygon, the easiest application of this theorem. ——————– Practice Problem: Let and be real numbers satisfying $\|2x-y\| \le 3$ and $\|y-3x\| \le 1$ . Find the maximum value of . Posted in Algebra, Inequalities, Olympiad, Sets \|\| 3 Comments »
Spacy. Topic: S&S/Sets. Level: AMC.	February 7th, 2007
Problem: (2007 AMC 12A – #25) Call a set of integers spacy if it contains no more than one out of any three consecutive integers. How many subsets of $\{1, 2, 3, \ldots, 12\}$ , including the empty set, are spacy? Solution: We will solve this problem with a recursion on , which we will define as the number of spacy subsets of $\{1, 2, 3, \ldots, n\}$ . We can easily calculate , , , and . Now we will think about how to evaluate in terms of previous terms. Obviously, we can keep all the subsets in $S_{n-1}$ . These will account for any space subsets that don’t contain the element . Now we just need to count the ones that do contain the element . If a spacy subset contains , it cannot have or . So take all the spacy subsets of $\{1, 2, \ldots, n-3\}$ and add the element to them to get all the spacy subsets that contain . Since these are both of the cases, we obtain $S_n = S_{n-1}+S_{n-3}$ . Some calculations yield $S_{12} = 129$ . QED. ——————– Comment: In all honesty, a pretty standard recursion problem, which is probably better off on an easy olympiad-style contest because it’s too easy to guess on the AMC. After just calculating a few terms, it wasn’t hard to see the recursion and assume its validity. A more interesting problem would be to find the closed form for that recursion (eww?). Maybe generating functions will save the day. ——————– Practice Problem: Can you find a closed form for ? Posted in AMC, Sequences & Series, Sets \|\| 1 Comment »
Guess What? Topic: Probability/Sets. Level: AIME/Olympiad.	January 11th, 2007
Problem: (2002 Putnam – B4) An integer , unknown to you, has been randomly chosen in the interval with uniform probability. Your objective is to select in an odd number of guesses. After each incorrect guess, you are informed whether is higher or lower, and you must guess an integer on your next turn among the numbers that are still feasibly correct. Show that you have a strategy so that the chance of winning is greater than . Solution: We first prove that, in the interval , we can guess with a strategy that allows us to get the desired number in an even number of guesses with $\frac{2}{3}$ probability. This is easy by induction. Base case: . Pick . If , it’s an odd number, but if $n \neq 2$ , we can get it in the subsequent guess. So there is a $\frac{2}{3}$ chance. Induction step: Suppose it’s true for the interval . We want to show it is true for the interval . Start by choosing . If , it’s an odd number of guesses, but if , it’s even. Then guess (if we find that ) on the second guess. So if , we can get it in an even number of guess. If we find that , it's just choosing from the interval in an even number of guesses, so by the inductive hypothesis this is $\frac{2}{3}$ . Hence the probabability in the interval is $P(n=3k+3)+P(n=3k+1)+P(n<3k+1) \cdot P(\text{even # of guesses}) = \frac{1}{3k+3}+\frac{1}{3k+3}+\frac{3k}{3k+3} \cdot \frac{2}{3} = \frac{2}{3}$ completing the induction. So now we have the interval . Choose . If , we're done in an odd number of guesses. Otherwise, we want to guess which is in $[1,2001] = [1,3 \cdot 667]$ in an even number of guesses. By the lemma above, the probability of this is $\frac{2}{3}$ . Therefore, the total probability is $P(n = 2002)+P(n<2002) \cdot P(\text{even # of guesses}) = \frac{1}{2002}+\frac{2001}{2002} \cdot \frac{2}{3} = \frac{1335}{2002} > \frac{2}{3}$ , as desired. QED. ——————– Comment: This was a pretty neat problem. The way I figured out the solution was by an interesting recursion that find the best strategy for based on optimizing the best strategies for with in trying to get an even and odd number of guesses. The pattern revealed the first lemma, which lead directly to the solution. It seems like some of the later problems on the test were a little easier than the earlier problems. ——————– Practice Problem: (2002 Putnam – A3) Let $n \ge 2$ be an integer and be the number of non-empty subsets of $\{1, 2, \ldots, n\}$ with the property that the average of the elements of is an integer. Prove that is always even. Posted in AIME, Olympiad, Probability & Combinatorics, Sets \|\| 3 Comments »
Pretty Sorta Equal To. Topic: Sets. Level: AIME/Olympiad.	December 27th, 2006
Problem: (Stanford Putnam Practice) Let $S = \{1, 2, \ldots n\}$ and let $S_1, S_2, \ldots, S_n$ be subsets of satisfying $\|S_i \cap S_j\|$ for $i \neq j$ . Show that $\max(\|S_1\|+\|S_2\|+\cdots+\|S_n\|)$ is asymptotically $n \sqrt{n}$ . Solution: We will start by showing that the expression is at most asymptotically $n\sqrt{n}$ . Suppose it is asymptotically . Then $\|S_i\| \sim k$ . And on average, any element will be contained in of the . Consider the sets that contain the element . The remaining elements of each subset must all be different, so there must be at least elements in the original set. So $k(k-1)+1 \sim n \Rightarrow k \sim \sqrt{n}$ is an upper bound. Now let’s show that we can obtain this upper bound. Let be the closest integer to $\sqrt{n}$ . Partition into subsets, approximately the intervals $(1, m); (m+1, 2m); \ldots ; (n-m+1, n)$ . Each part should contain about elements (because the argument is asymptotic, it doesn’t really matter). Label them by $a_{11}, a_{12}, \ldots, a_{1m}, a_{21}, a_{22}, \ldots, a_{mm}$ where $a_{ij}$ is the th element of the th part. We want to choose sets of elements satisfying the conditions of the problem; we claim that we can do this by choosing one element from each interval for each set. First, construct sets: $\{a_{11}, a_{21}, a_{31}, \ldots, a_{m1}\}$ $\{a_{12}, a_{22}, a_{32}, \ldots, a_{m2}\}$ $\cdots$ $\{a_{1m}, a_{2m}, a_{3m}, \ldots, a_{mm}\}$ . Then, to create the next sets, we take the elements which lie along the same diagonal (supposing we had a copy of those sets), for instance, $\{a_{11}, a_{22}, a_{33}, \ldots a_{mm}\}$ $\{a_{21}, a_{32}, a_{43}, \ldots a_{m(m-1)}, a_{1m}\}$ $\{a_{31}, a_{42}, a_{53}, \ldots, a_{1(m-1)}, a_{2m}\}$ $\cdots$ $\{a_{m1}, a_{12}, a_{23}, \ldots, a_{(m-1)m}\}$ . In fact, if we repeat this process, we will get all sets of elements, none of which share more than a single element. Hence we know that the value is asymptotic to $nm \sim n\sqrt{n}$ . QED. ——————– Comment: The above proof is very “fuzzy.” It lacks a lot of the rigor needed to actually prove the result, but it gives the basic idea, which is all I was aiming for. A solid proof of the result would probably be very long and tedious (unless some other elegant method is used, or perhaps some other strong known results). Posted in AIME, Olympiad, Sets \|\| 2 Comments »
Gimme That! Topic: Sets. Level: AIME/Olympiad.	December 24th, 2006
Problem: (1996 Putnam – B1) Define a selfish set to be a set which has its own cardinality (number of elements) as an element. Find, with proof, the number of subsets of $\{1, 2, \ldots, n\}$ which are minimal selfish sets, that is, selfish sets none of whose proper subsets is selfish. Solution: We define to be the desired number. Trying small cases, we get $S_1 = 1: \{1\}$ $S_2 = 1: \{1\}$ $S_3 = 2: \{1\}; \{2, 3\}$ $S_4 = 3: \{1\}; \{2, 3\}; \{2, 4\}$ and . Well now we’re tempted to say that , the th Fibonnaci number (with ). To do so, we want to find a bijection between the minimal selfish subsets of $T_n = \{1, 2, \ldots, n\}$ and the minimal selfish subsets of $T_{n-1} = \{1, 2, \ldots, n-1\}$ and $T_{n-2} = \{1, 2, \ldots, n-2\}$ . Clearly all the minimal selfish subsets of $T_{n-1}$ are in as well. The remaining minimal selfish subsets of are those which contain the element . Consider the following bijection between the minimal selfish subsets of containing and the minimal selfish subsets of $T_{n-2}$ : $P = \{a_1, a_2, \ldots, a_k, n\} \leftrightarrow Q = \{a_1-1, a_2-1, \ldots, a_k-1\}$ . Clearly because otherwise $\{a_i\}$ would be a selfish subset. Also, $a_k \le n-1$ . Hence the mapping works both ways; it remains to show that if one is a minimal selfish subset, so is the other. Since , we know that both are selfish or neither of them is. Furthermore, if contains a selfish subset $\{b_1, b_2, \ldots, b_k\}$ , will contain the selfish subset $\{b_1-1, b_2-1, \ldots, b_{k-1}-1\}$ and if contains the selfish subset $\{c_1, c_2, \ldots, c_k\}$ then will contain the selfish subset $\{c_1+1, c_2+1, \ldots, c_k+1, n\}$ . So the bijection works. That means we have $S_n = S_{n-1}+S_{n-2}$ so , as desired. QED. ——————– Comment: Decently hard for a B1, at the least the part that involved rigorously proving that the mapping is actually a bijection. It was pretty easy to figure out what the answer was, but as usual much more difficult to prove it. ——————– Practice Problem: (1996 Putnam – A1) Find the least number such that for any two squares of combined area , a rectangle of area exists such that the two squares can be packed in the rectangle (without interior overlap). You may assume that the sides of the squares are parallel to the sides of the rectangle. Posted in AIME, Olympiad, Sets \|\| 5 Comments »

free web counters