| |
About
Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
Math Books
Math Stuff
My Tests
Practice Tests
Tutorials
|
|
Problem: Show that there do not exist four lattice points such that the pairwise squares of the distances between the points are all odd integers.
Solution: WLOG, assume that one of the points is the origin. We can do so because it can just be translated to any other point in the plane. Let the other points be  ;  ; and  .
Since the origin is one of our points, we know  ,  , and  are all odd. So each pair  for  must have one odd and one even (so that the sum of the squares will be odd). Then by Pigeonhole, we have two  ’s with the same parity. Then since the  ’s have the opposite parity as the ’s, they are also the same.
Let  and  be the points with the same parity on both coordinates. Then  and  are both even. Hence the square of the distance between these two points is  , which is even because the sum of two even numbers is even. Therefore, not all the pairwise squares of distances can be odd. QED.
——————–
Comment: Originally came from a different problem, which I misread and came up with a solution for this problem instead. Well, anyway, it’s not particularly difficult, but it’s nice to WLOG a point to the origin and make things cleaner, as you can probably tell.
——————–
Practice Problem: (Olympiad Problem Solving MidTerm) Show that there do not exist four points in the Euclidean plane such that the pairwise distances between the points are all odd integers. (Note: They don’t have to be lattice points; that’s where I misread it.)
|
Problem: (Olympiad Problem Solving MidTerm) Suppose we have  rectangles with sides of integer lengths not exceeding  . Prove that there exist three of these rectangles, which we call  ,  , and  , such that fits wholly inside and fits wholly inside . (Note: If two rectangles are identical, then each ‘fits’ inside the other.)
Solution: Well, again the numbers suggest Pigeonhole, so we get right to it. We want to construct sets of rectangles such that any three rectangles in each set would satisfy the condition. It might help to redefine the condition. Let  and  denote the length and width of rectangle  , respectively. We may assume  or we just switch the values for and to obtain the same rectangle. We want to find rectangles  such that  and  .
Consider plotting rectangles on the coordinate plane with the axes equal to and . All the rectangles lie below or on the line  (shown in blue below. We want to create fifty different holes to guarantee that three fall into a single one; all while keeping in mind that any three in a hole must satisfy our condition. Consider the following holes (shown in red):
If we continue these sets of red lines until the entire portion of the graph we want is full, we will have exactly fifty. Algebraically defined, we have
 for  .
Since we have  holes and  pigeons, we know there are at least  pigeons in a single hole, or three rectangles in a single set. From the graph, it’s easy to see that if three rectangles lie on either the vertical or horizontal line of any set, they fit within each other. They all have one equal dimension, so we just arrange the other dimension in nondecreasing order. If two lie on a vertical line and the third on the horizontal, the third is clearly the smallest and then arrange the other two in nondecreasing order by length. Similarly, if two lie on a horizontal line and a third on the vertical, the third is the largest and arrange the other two in nondecreasing order by width. Hence the problem is solved. QED.
——————–
Comment: More good Pigeonhole practice. Transfering the problem onto the graph and then determining the sets were the key steps, and the details pretty much worked themselves out from there. It’s often a good idea to reduce things to algebra instead of geometry – in reality, this problem had nothing to do with geometry.
——————–
Practice Problem: If you wanted four rectangles that fit inside each other, how many total rectangles would you need? Five?  ?
|
Problem: (Olympiad Problem Solving MidTerm) At each of the vertices of a regular –gon one of the numbers  is written. Prove
that there are  vertices  of this polygon such that
(a)  , and
(b) if the numbers written at are  , respectively, then  .
Solution: Well looking at the numbers given, it’s not terribly difficult to guess that it is a Pigeonhole problem (the and the  are pretty good indicators). But what are the pigeons and the holes?
Consider the longest diagonals (connecting two opposite vertices). There are  of these, conveniently enough. Label each of these diagonals with the absolute value of their difference. These differences range from  to  because the maximal difference is  and the minimal is clearly zero from the absolute value.
Now let the possible differences be the holes and the diagonals be the pigeons; since we have holes and pigeons, there are two diagonals with equal differences. Let  be the endpoints of the first and  the endpoints of the second.
We know that  . Also note that  form a rectangle because it has two diagonals of equal length which bisect each other. Thus the opposite sides are parallel. If  , we have  , but those are opposite sides and hence parallel and we are done. If  , we have  , which again are opposite sides so we are done here, too. Hence the problem is solved. QED.
——————–
Comment: Took a bit to realize how to set up the pigeons and the holes, but it worked out nicely. It’s good practice to do a lot of Pigeonhole problems because when you see one you have more experience in determining the pigeons and the holes.
——————–
Practice Problem: Generalize the problem to a  -gon with the numbers  .
|
Problem: (Olympiad Problem Solving MidTerm) Let  be a polynomial that is nonnegative for all real  . Prove that for some  , there are polynomials  such that
 .
Solution: First we will make some restrictions on  , namely that it has an even degree and a positive coefficient on the highest-order term. If it has an odd degree take  and we get  for one of the cases which is a contradiction. Similarly, if it has a negative coefficient on the highest-order term, take  so again . In both these cases, cannot be nonnegative for all real .
Next, we will proceed by strong induction on the degree of .
Base case:  . Then  .
Then suppose the condition is satisfied for  . We will show that it must also hold for  .
Denote  over all reals . Since is nonnegative,  .
Consider the polynomial  , which is still nonnegative and of degree  . For some value of ,  because  at some point. Let that value be  (just take one of them; there might be more). The multiplicity at must be even because if it was odd then  would go negative for some  . Let the multiplicity at be  .
So we have  for some  . We note that is nonnegative as well because  is nonnegative and  would be negative if was negative anywhere, a contradiction. By our original restrictions,  is even. However, that means is a nonnegative polynomial with  so  must be expressible in the form  for some  by our inductive hypothesis.
Then ![\displaystyle p(x) = f(x)+m = (x-x_0)^{2b}g(x)+m = \sum_{j=1}^{k_1} [(x-x_0)^bf_j(x)]^2 + (\sqrt{m})^2](http://www.wangsblog.com/jeffrey//pictures/b8a88ff192533469c837e100f88bf275.gif "\displaystyle p(x) = f(x)+m = (x-x_0)^{2b}g(x)+m = \sum_{j=1}^{k_1} [(x-x_0)^bf_j(x)]^2 + (\sqrt{m})^2") , completing the induction. QED.
——————–
Comment: A pretty fun, semi-difficult problem. I tried a few failed approaches before reaching this cool one, including getting rid of higher order terms first and reducing it to a lower degree polynomial which employs the same general idea but fails in some cases. Another way to do this problem (from the solutions guide) is simply to factor the polynomial into linear and quadratic terms, show that each linear term has even multiplicity and use the sum of squares product formula on the quadratic terms –  . This actually proves a stronger result, that each nonnegative polynomial can be written as the sum of the squares of two other polynomials.
——————–
Practice Problem: (Olympiad Problem Solving MidTerm) Find a polynomial in more than one variable that is always nonnegative that cannot be written as the sum of squares.
|
Problem: (1975 IMO – #2) Let  be an infinite sequence of strictly positive integers, so that  for any . Prove that there exists an infinity of terms  , which can be written like  with strictly positive integers and  .
Solution: Let's take two cases - there exist  that are relatively prime and there don't exist such members of the sequence.
Well if  , we can just use the Chicken McNugget Theorem and we can find  such that  for all  . There are an infinite number of such  because the sequence is strictly increasing.
Now suppose there don’t exist such  . Since  is not relatively to any of the infinite other terms and it only has a finite number of divisors, at least one divisor  of divides an infinite number of other terms in the sequence by the Infinite Pigeonhole Principle. Then consider the sequence  . We can then apply the same two cases on this sequence and keep going until the first condition holds true (this process terminates because only has a finite number of divisors – at some point it will either be relatively prime to another member of the sequence or equal  and be relatively prime anyway).
Therefore there always exist infinitely many satisfying the condition. QED.
——————–
Comment: An interesting problem, more so the second case, though. Sort of like a recursive function with a terminating condition. In any case, in the recursion it’s important to specify that it will eventually terminate, or it won’t be a valid justification.
——————–
Practice Problem: Prove the Chicken McNugget Theorem – given two positive integers  such that  , the largest value of such that there do not exist positive integers  with  is  .
|
|
|
