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

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 »
Leftovers. Topic: Algebra/Polynomials. Level: AIME.	December 22nd, 2006
Problem: (Stanford Putnam Practice) Find the remainder when you divide $x^{81}+x^{49}+x^{25}+x^9+x$ by . Solution: Since they’re both divisible by , we first divide that out, and just remember to multiply the remainder by at the end. Let be the first polynomial and be the second. we have for some polynomials with $\deg(r) < deg(Q) = 2$ . We want to find . Consider the two roots of . Plugging them into the equation, we obtain and . Evaluating at those two values, we find that and . But since has degree less than , the only possible is the constant polynomial . Then the remainder is . QED. ——————– Comment: This is a super important technique when it comes to polynomial division. Using the $\deg(Q)$ roots of and the fact that , we can hypothetically always determine this way, without dividing. This usually comes up when has nice roots, so if it doesn’t, look for a better way. ——————– Practice Problem: (Stanford Putnam Practice) How can the quadratic equation $\frac{(x-a)(x-b)}{(c-a)(c-b)}+\frac{(x-b)(x-c)}{(a-b)(a-c)}+\frac{(x-c)(x-a)}{(b-c)(b-a)} = 1$ have three roots ? [Reworded] Posted in AIME, Algebra, Polynomials \|\| 1 Comment »
Strikethrough. Topic: Geometry/NT. Level: AIME.	December 20th, 2006
Problem: (Stanford Putnam Practice) Let $P_1, P_2, \ldots , P_{2007}$ be distinct points in the plane. Connect the points with the line segments $P_1P_2, P_2P_3, \ldots, P_{2006}P_{2007}, P_{2007}P_1$ . Can one draw a line that passes through the interior of every one of these segments? Solution: Playing around with pictures for a while, our intuition says that since is odd, this is impossible. Now let’s try to prove it. Suppose there exists such a line . Then we know that the endpoints of each line segment lie on opposite sides of the line. So and lie on opposite sides of ; and lie on opposite sides of ; $\cdots$ $P_{2007}$ and lie on opposite sides of . But wait, by a simple induction we know that $P_1, P_3, P_5, \ldots, P_{2007}$ lie on the same side. That gives us the contradiction we seek. Thus does not exist, as desired. QED. ——————– Comment: Not a bad problem, though pretty simple after you realized that you could fix the line before the points. It’s easy to see that this generalizes to any set of an odd number of points (try the sides of a triangle, for example), so we have proven in fact a decently strong result. ——————– Practice Problem: (Stanford Putnam Practice) Show that if every room in a house has an even number of doors, then the number of outside entrance doors must be even as well. Posted in AIME, Geometry, Number Theory \|\| 3 Comments »
I Am The Greatest (Common Divisor)! Topic: Number Theory. Level: Olympiad.	December 19th, 2006
Problem: (Stanford Putnam Practice) Suppose $(a_i)_{i \ge 1}$ is a sequence of positive integers satisfying $\gcd(a_i, a_j) = \gcd(i, j)$ for $i \neq j$ . Show that for each . Solution: Let be an arbitrary positive integer. If we can show that we will be done. We have $\gcd(a_n, a_{2n}) = \gcd(n, 2n) = n$ so . Then for some positive integer . Similarly, we know $kn\|a_{kn}$ so $a_{kn} = ckn$ for some positive integer . Then, however, $\gcd(a_n, a_{kn}) = (kn, ckn) = kn$ and $\gcd(n, kn) = n$ so we must have $kn = n \Rightarrow k = 1$ . Thus . QED. ——————– Comment: At first, induction seemed the way to go, but after a while you realize that the induction step is, well, not very likely since $a_1 = 1, a_2 = 2, \ldots, a_k = k$ puts very few restrictions on $a_{k+1}$ . So then you look to a better option, trying to find the strongest use of $\gcd(i, j)$ . It turns out that this happens when is a multiple of , which is exactly how the above proof starts. ——————– Practice Problem: (Stanford Putnam Practice) Let be a prime number. Show that divides infinitely many of the numbers $1, 11, 111, 1111, \ldots$ . [Reworded] Posted in Number Theory, Olympiad \|\| No Comments »

free web counters