From: Android Subject: P.O.D. 7/27 The base of a triangle is 80 units long and one of the base angles measures 60 degrees. The sum of the lengths of the other two sides is 90. Find the length of the shortest side. Benjie From: bboru@lobby.ti.com (B. Borowicz) Subject: POD spoiled >The base of a triangle is 80 units long and one of the base angles >measures 60 degrees. The sum of the lengths of the other two sides is 90. >Find the length of the shortest side. Look out below! SPOILER HERE /\ x/ \ / \ y /___________\ 80 Call the angle under y 60 degrees. Draw an altitude to the base. The right side of the triangle is now in 30-60-90 ratio, so the altitude is y*sqrt3/2. The section of the base under y is y/2. The left part of the triangle is also a right triangle, of course, so the section of the base under x must be sqrt(x^2-alt^2). The two sections must sum to 80, so you have the equations: sqrt(x^2 - y^2*3/4) + y/2 = 80 x + y = 90 Subtract and square the first equation for: x^2 - y^2 + 80*y = 6400 Subtract and square the second equation for: x^2 - y^2 + 180*y = 8100 Subtract these and you find y = 17. Obviously, this is the shorter part of 90, so the shorter side is length 17. From: pfriel@geom.umn.edu Subject: P.O.D.--Spoiler SPOILER Call the triangle ABC, with segment AB having length 80 and angle BAC having measure 60 degrees. Drop an altitude from C to D(on AB). CAD is then a 30-60-90 triangle. Give BC length x, and AC length 90-x. AD then has length (90 -x)/2, and BD: (70 +x)/2. We now have two right triangles, each with CD as a leg. Apply the Pythagorean theorem to each, and set the values of CD equal. -PWF From: Susan Schwartz Wildstrom Subject: POD (triangle) Spoiler I called the remaining two sides a and 90-a (with (90-a) opposite the 60 degree angle. OOPS--I suppose I should leave some space in case someone doesn't want to read this, but--I do have a question--since the Subject line already says that this spoils (solves) a POD, why leave all the space--anyone who doesn't want to read the message can just skip it. Also, don't you think POD's should be numbered (or dated) so readers can tell which POD a message contains a solution for??? In any event, after naming the triangle as above, I applied the law of cosines (90-a)^2 = a^2 + 6400 - 2(a)(80)cos 60 8100 - 180a + a^2 = a^2 + 6400 - 80a (NB cos 60 = 1/2) 1700 = 100a so 17 = a 90-a = 73 Thus the shortest side is 17 units long. Good problem--I teach precalculus during the school year. I need to remember this one to share with my classes! Thanks! Susan From: "Greg Kuperberg" Subject: Spur-of-the-moment problem (SOMP) Here are two standard definitions of an ellipse: An ellipse is a stretched circle. An ellipse is a maximal set of points such that the sum of the distances to two given points, the foci, is constant. Show that the two definitions are equivalent. Greg From: "Greg Kuperberg" Subject: Another SOMP (Spur-of-the-moment problem) Here are two standard definitions of a rational number: A rational number is a ratio of integers. A rational number is a repeating decimal. Show that they are equivalent. Greg From: Android Subject: Another POD This is from this year's AHSME. I can't get the right answer, and don't know why? My answer was 14 off. A square of perimeter 20 is inscribed in a square of perimeter 28. What is the greatest distance between a vertex of the inner square and a vertex of the outer square? Enjoy, Benjie From: Android Subject: Posts All right, due to the large amount of posts we get, I decide to moderate this list further. I have no way of forcing you not to post, but please follow the guideline. Post only problems, announcements, general knowledge article and informative math articles. When post spoilers to problems, email them to iams-request with SPOILER at the subject line. I will process them, filter them and post them. Keep good discussions, but when they get too detailed, discuss it off the list. I don't want to moderate discussions, but if it gets worse, I will have to. This doesn't mean that you can't post discussions, just don't post the ones that are in 2nd or 3rd rounds...... Feedbacks are welcome. Benjie From: pfriel@geom.umn.edu Subject: Another POD--- SPOILER From: erickw@sfu.ca Subject: Lockers, birthdays, and probability... I recently revisited this problem when someone asked it to me, and this time I found some new insights...So I thought I'd share this write-up with IAMS. A friend asked me recently what the chances are that there are two lockers at SFU (the university) with the exact same combination (if we only consider the locks with 60 numbers on the dial, and 3-number combinations). Well, there are about 60^3 = 216,000 possible combinations. A few of these combinations are not valid, but we'll ignore that and assume that all 216,000 are equally likely. So, the question becomes, what is the probability that among m randomly chosen numbers from 1 to n, some two are equal? Well, in our problem with n=216,000, we'd need 216,001 numbers to be sure that some two are equal. But what do you suppose m would have to be in order to have, say, at least a 50% chance of two identical combinations? And in general what would m have to be in order for the probability to be p? Think about it for a while, or just take a guess...215,999? 200,000? 108,000? Ready for the real answer? SOLUTION (+ more) follows... 548. That's right, five hundred and forty eight! This is a stunning example of the so-called "birthday paradox". It's usually stated in the following form: if there are 23 people at a party, then there is a greater than 50% chance that two people will have the same birthday (not counting Feb. 29). I heard that Johnny Carson once tried to test this out by asking 23 members of the audience for their birthdays, but he did it wrong: he only compared all their birthdays to his own, and *not* to each other. This is very important in order for it to work :-). Now, how is it possible that only a few hundred lockers are necessary? Well, think about it this way: for each pair of lockers, there is a 1/216,000 chance of them having the same combination. But the number of *pairs* of lockers is about 150,000, which means there ought to be a good chance of there being some pair that match (now, those 150,000 or so events are not really independent, which is why the probability is 50% rather than 150/216...Actually this has to do with another probability semi-paradox I noticed recently; I'll mention it at the end). So, let's look at this in a more combinatorial way: if there are m lockers, then how many ways can all the combinations be different? Well, exactly nPm, the number of ways of choosing m distinct objects from n where order matters. And how many configurations of lockers and combinations are possible? Simply n^m, as each of the m lockers has n possible combinations. Since we assumed that all combinations are equally likely, the probability of them being all different is nPm/n^m, so the probability of two being equal is (1-nPm/n^m). We can approximate nPm = n(n-1)(n-2)...(n-m+1) by (n-m/2)^m, which turns out to be a pretty good overestimate. So nPm/n^m is approximately (1-m/2n)^m (actually slightly lower). If we choose m = sqrt(n), this gives (1-1/2m)^m, and for large m is very close to exp(-1/2) = 0.6065...Which is not quite good enough (we want it to be less than 0.5). It turns out the value we're looking for is m = sqrt(n*ln(4)) ~= 1.177 sqrt(n). This is only an approximation, but it's a pretty good one (the value of m/sqrt(n) when n=216,000 is 1.179). How good is that approximation of nPm? Well, I haven't double-checked this, but I believe that if we set m = k sqrt(n) for a fixed k, then nPm/(n-m/2)^m approaches 1 as n goes to infinity. So the approximation is very good for sufficiently large n. This also leads to the following generalization (by solving for k): Let m = sqrt(n*ln(1/p^2)). Then lim nPm/n^m = p. n->oo So, for 0 < p < 1, m is Theta(sqrt(n)), meaning c1 < m/sqrt(n) < c2 for some constants c1 and c2 depending only on p. Note that this also agrees with our previous heuristic of considering the number of pairs. Now, what about that other probability semi-paradox I mentioned? Well, you can see that each of the events (a = b) here are pairwise independent. In other words the fact that Bill has the same birthday as Jill doesn't affect the probability that Alice has the same birthday as Bob, or even Jill. But taken as a whole, they are not independent! Certainly if Bill and Jill share a common birthday, and Jill has the same birthday as George, there's no way George and Bill can have different birthdays... Another smaller example (the one I first came up with, although in a slightly different form, because circles are hard to draw in ASCII :-), is if X is a random variable uniformly distributed over [0,2*Pi], the events: sin X > 0, cos X > 0, tan X < 0 are pairwise independent, but clearly mutually exclusive. This says that the independence of more than 2 events means *more* than simple pairwise independence (my guess would be independence of all combinations of events, e.g. A and (B \intersect C) are independent, etc...). Maybe you've all seen this already, but I never learned it when I took Statistics, and never even noticed it until now. Well, hope you enjoyed this and/or found it interesting (hopefully both!), and didn't find it *too* long either... :-) -- Erick From: "Don A. Hanlen" Subject: Re: Spur-of-the-moment problem (SOMP) On Tue, 27 Jul 1993, Greg Kuperberg wrote: > Here are two standard definitions of an ellipse: An ellipse is a > stretched circle. An ellipse is a maximal set of points such that > the sum of the distances to two given points, the foci, is constant. > > Show that the two definitions are equivalent. > > Greg The two definitions are not equivalent. An oval is a stretched circle. -- Don A. Hanlen From: sstrklnd@oyster.smcm.edu Subject: Re: SOMP (Spoiler) Here are two standard definitions of a rational number: A rational number is a ratio of integers. A rational number is a repeating decimal. Show that they are equivalent. SPOILER Not a proof, but a discussion: In one direction, given a ratio of integers suppose the denominator is m. When dividing by m, the possible remainders are 0,1,2,...m-1. If a remainder of 0 is reached when dividing the fraction, the number can be written as a decimal which terminates (ie, repeats 0). Otherwise, after at most m-1 divisions, a remainder must be repeated and thus the decimal expansion repeats. On the other hand, any repeating decimal can be written as a fraction of integers by multiplying by appropriate powers of 10 and a little arithmetic: For example, to write 1.23456565656... as a fraction, let x = 1.234565656... Then 1,000x = 1234.565656... and 100,000x = 123,456.5656... Subtracting, we get 99,000x = 122,222 so x = 122,222/99,000 --- ******************************************************** Susan R. Strickland * "If at first * St. Mary's College of Maryland * you do succeed - * St. Mary's City, MD 20686 * try to hide * sstrklnd@oyster.smcm.edu * your astonishment." * ******************************************************** From: Android Subject: Problem with Splicing Subject: Re: Two Questions (problem with splicing) Um, thanks to a reply by t-davidw, I just realized that the splicing method suggested by some still doesn't work, even if you somehow make the difficulties with 2.000...=1.999... go away. The problem is with negative reals. Someone (sorry, I've lost track of who) suggested you could take, for example, 1.2 and 3.2, and splice them to make 13.22 (note, that this splicing must depend on the order, for otherwise splice(a,b)=splice(b,a), implying that splice isn't injective). Well, what about -1.2 and 3.2? Easy, I suppose: -13.22. But then the real ringers come in, when we consider -1.2 and -3.2, or 1.2 and -3.2.... Now what? We've already used up +/-13.22, and still have two more cases to go.... Now, splicing will be _surjective_, but the original question (unless I completely misread it) was about a bijective function. From: alanm@efi.com Subject: Re: Problem with Splicing > Um, thanks to a reply by t-davidw, I just realized that the splicing > method suggested by some still doesn't work, even if you somehow make > the difficulties with 2.000...=1.999... go away. > > The problem is with negative reals. You can eliminate this too. First map R onto R+ (x >= 0) then do the splicing technique. The mapping from R to R+ can be done thus: If the number is greater than or equal to -1 add 2 to it Otherwise map the number to -1/num Thus 1.1 becomes 3.1, -0.5 becomes 1.5, -100.0 becomes 0.01 If you don't like this, map x onto e^x Alan From: Android Subject: P.O.D. Number 20 from 1993 AHSME Consider the equation 10z^2 - 3iz - k = 0, where z is a complex variable and i^2 = -1. Which of the following statements is true? (A) For all positive real numbers k, both roots are pure imaginary. (B) For all negative real numbers k, both roots are pure imaginary. (C) For all pure imaginary numbers k, both roots are real and rational. (D) For all pure imaginary numbers k, both roots are real and irrational (E) For all complex numbers k, neither root is real Enjoy, Benjie From: David G Radcliffe Subject: Bijection between R and R^2. (spoiler) It is easy to find an injection (1-1 function) from R into R^2; just take f(x) = (x,x). I will assume the fact that Q^2 is countable. Let {q_n} be an enumeration of Q^2, and write q_n = (a_n , b_n). If (x,y) is a point in R^2, define S(x,y) = { n | x < a_n and y < b_n }. Note that S(x,y) = S(x',y') only when (x,y)=(x',y'). Now, define g(x,y) = Sum { 10^(-n) | n is in S(x,y) }. Clearly (?) g is an injection from R^2 to R. The Schroeder-Bernstein theorem asserts that if there is an injection of A into B, and an injection of B into A, then A and B have the same cardinality. Therefore, we have shown that R and R^2 have the same cardinality. Dave From: kubo@math.harvard.edu (Tal Kubo) Subject: maximum product (2nd attempt to post -- first one didn't show up on the mailing list as received at my site.) Someone asked how to prove that a product with fixed sum of terms is largest when all terms are equal, without calculus. One way is to use the arithmetic mean/geometric mean inequality. It has a slick proof by "reverse induction". It is a special case of Jensen's inequality on convex functions, which is in turn a special case of the majorization inequality, both of which don't need calculus and are found in Hardy-Littlewood-Polya "Inequalities". Another way is to assume a maximum exists and use the sum/product principle for any pair of terms to show that they must be equal. This is cheating a bit, but then the existence of the maximum relies only on topological arguments which in a sense are more basic than calculus. (My apologies in case the previous version of this message did in fact get posted -- if it did, it didn't arrive at my site.) From: Android Subject: P.O.D. Points A, B, C and D are on a circle of diameter 1, and X is on diameter AD. If BX = CX and 3(angle BAC) = angle BXC = 36, how long is AX? Enjoy, Benjie From: Android Subject: Function problem Given 0 <= x_0 < 1, let 2x_(n-1) if 2x_(n-1) < 1 x_n = 2x_(n-1)-1 if 2x_(n-1) >= 1 for all integers n > 0. For how many x_0 is it true that x_0 = x_5? Enjoy, Benjie From: David Michael Tuller Subject: SPOILER Function Problem The only solution is x_0=0. Suppose x_n>=1. Then x_(n+1)>=1 since x_(n+1)= 2x_n-1. Since x_0<1, x_1, ... x_5 must all be less than 1. But this gives x_5=32x_0 so if x_5=x_0, x_0=0. David M. Tuller tulled@rpi.edu From: Android Subject: SPOILER -- Solution Summary to Yesterday's POD -- SPOILER Here is a summary to yesterday's pod. This is the first time I am doing this, and hope this will help to keep the traffic down. If you don't want to see the answer or the solution, press Ctrl-C now and save this letter. SPOILER Follows The answer is 31 Given 0 <= x_0 < 1, let 2x_(n-1) if 2x_(n-1) < 1 x_n = 2x_(n-1)-1 if 2x_(n-1) >= 1 for all integers n > 0. For how many x_0 is it true that x_0 = x_5? (SPOILER) Answer: 31 x_n - 2 x_(n-1) is an integer; hence x_5 - 32 x_0 is an integer. If x_5 = x_0, then 31 x_0 is an integer. However, if x_0 = k/31 (0<=k<31), then x_5 IS equal to x_0. % Given 0 <= x_0 < 1, let % % 2x_(n-1) if 2x_(n-1) < 1 % x_n = % 2x_(n-1)-1 if 2x_(n-1) >= 1 % % for all integers n > 0. For how many x_0 is it true that x_0 = x_5? the sequence is equivalent to x_n = frac(2x_(n-1)) so the question is equivalent to say For how many x_0 it is true that frac(2^5 x_0) = x_0? or if you prefer, For how many x_0 an integer m exists, such that 32 x_0 = x_0 + m ? whose answer is: for 31 such values, of the form k/31, k=0,..,30. .mau. > >Given 0 <= x_0 < 1, let > > 2x_(n-1) if 2x_(n-1) < 1 > x_n = > 2x_(n-1)-1 if 2x_(n-1) >= 1 > >for all integers n > 0. For how many x_0 is it true that x_0 = x_5? > This exactly is the procedure for converting a decimal faction into binary. E.g., Let us convert 0.6 into binary, double the fraction till we get the original number. 0.6 -> 1.2 -> 0.4 -> 0.8 -> 1.6 so 0.6 = 0.1001(recurr) Your question reduces to 'How many number (between 0 and 1) have a binary representation whose periodicity is 5?' . In the above example periodicity is 4. Hence the answer is 31 and if you include the trivial case of 0, it will be 32. The 31 answers are x_0 = n/31 (n=0,1,2,...,30) --- ramana@svl.cdc.com --- From: Android Subject: Result of Round 8, Contest 2 -- SPOILER Problem 8: For how many paths consisting of a sequence of horizontal and/or vertical line segments, with each segment connecting a pair of adjacent letters in the diagram below, is the word CONTEST spelled out as the path is traversed from the beginning to end? C COC CONOC CONTNOC CONTETNOC CONTESETNOC CONTESTSETNOC Answer: 127 Solution: All admissible paths end at the center "T" in the bottom row of the diagram. Our count is easier if we go from the end to the beginning of each path; that is, if we spell TSETNOC, starting at the bottom center and traversing sequences of horizontally and / or vertically upward directed segments. The count becomes easier still if we take advantage of the symmetry of the figure and distinguish those paths whose horizontal segments are directed to the left from those whose horizontal segments are directed to the right. These two sets have the central vertical column in common and contain an equal number of paths. Staring at the bottom corner "T" in our figure, we have at each stage of the spelling the two choices of taking the next letter from above or from the left. Since there are 6 steps, this leads to 2^6 paths in this configuration. We get 2^6 paths also in the symmetric configuration. Since we have counted the central column twice, there are altogether 2 * 2^6 - 1 = 127 distinct paths. Correct Solutions Were Sent In By: dawagner@princeton.edu heiner@drb.insel.de radcliff@csd4.csd.uwm.edu martino@rob.csata.it jhardin@gandalf.pnl.gov c0465193@techst02.technion.ac.il Congrats! From: Leong Weng Ng Subject: Sliding Rod Problem Problem is as follows: Let the positive X and Y axes be a floor and a wall respectively. A rod of length 1 is placed vertically against the wall at (0,0). The rod subsequently slips on the floor until its whole length lies on the X-axis. If the slipping rod were filmed and all the frames were superimposed, you would find that the superimposed rods are enveloped by a curve vaguely resembling y = 1/x in the first quadrant. Find the Cartesian equation for this curve. What would be the answer if a semi-circular wire were placed atop the sliding rod? Have fun! **************************************************************************** Kelly's Reformation of Levy's Law: Nice guys don't finish nice. Cohen's Law: People are divided into two groups -- the righteous and the unrighteous -- and the righteous do the dividing. Christie-Davies Theorem: If your facts are wrong but your logic is perfect, then your conclusions are inevitably false. Therefore, by making mistakes in your logic, you have at least a random chance of coming to a correct conclusion. De Never's Law of Debate: Two monologues do not make a dialogue. (Source: The Complete Murphy's Law -- A Definitive Collection) Only $6.95 Weng Leong Stanford U. *************************************************************************** From: Android Subject: Result - Contest 2 Contest 2 is over. and we have 27 winners. that is, all who participated are winners! but out of the 27, there is only one grand prize, and one first place, and one second place, and one third place! (gezz, i am beginning to sound like pete franklin!) result follows thrid place award winners: tied, t-davidw@microsoft.com and bboru@lobby.ti.com they each scored a 4. congratulations! Second Place Award Winner: arodgers@dcs.qmw.ac.uk Who scored a 5. Congratulations! First Place Award Winner: radcliff@csd4.csd.uwm.edu Who scored a 7. Congratulations! And the grand prize goes to ...... martino@rob.csata.it Who scored a perfect 8. Congratulations! Special Thanks to erick@sfu.ca, who helped me on correcting the solutions. I haven't decide when we are going to have the next contest. I am short of problems. All feed backs are welcome. Once again, congrats to all who participated and especially to those who won awards. Benjie From: Android Subject: P.O.D. If a, b and d are the lengths of a side, a shortest diagonal and a longest diaggonal, respectively, of a nonagon (nine sides), then in terms of a and b, calculate d. Enjoy, Benjie From: "Greg Kuperberg" Subject: Spur-of-the-moment problem about ellipses (spoiler) Interest in my question about ellipses seems to have died after a response claiming that a stretched circle is not an ellipse. I suppose there is some ambiguity in how to stretch a circle. I mean that you should imagine a circle drawn on a sheet and the sheet is stretched linearly and uniformly. In this case you really do get an ellipse. Anyway, here is a complete analysis of the problem: Starting with a circle at the origin x^2 + y^2 = r^2, if you stretch it along the x axis, you get the solutions to the equation x^2/s^2 + y^2 = r^2 or x^2/a^2 + y^2/b^2 = 1 after reparameterization of the constants. Now suppose you have two foci (f,0) and (-f,0) and you consider the ellipse of points whose total distance from the foci is the length l. (Note that any two foci can be moved by isometry to (+-f,0).) Then the ellipse is the locus of the equations d1 + d2 = l (1) d1^2 = (x-f)^2 + y^2 (2) d2^2 = (x+f)^2 + y^2 (3) Multiplying the first equation by d1 and also by d2, we get: d1^2 + d1*d2 = l*d1 (4) d2^2 + d1*d2 = l*d2 (5) Now the equations are set up to eliminate quadratic terms in d1 and d2. Equation 4 minus equation 5 minus equation 2 plus equation 3 yields: 0 = l*d1 - l*d2 + 4*x*f <====> d2 - d1 = 4*x*f/l (6) With equation 1, we get d2 = 2*x*f/l + l/2 (7) d1 = 2*x*f/l - l/2 (8) Plugging equation 7 back into equation 3, l^2/4 - f^2 = x^2*(1-4*f^2/l^2) + y^2 If you divide out by the left side and switch the two sides, this is equivalent to the stretched circle equation, provided that l^2/4 > f^2, or in other words provided that the total allowed length l is bigger than the distance between the foci 2f. If l<2f, you get the hyperbola equation. Exercise: What are the equations saying in this case? So an ellipse is a stretched circle. But is every stretched circle an ellipse? Fixing a total distance to the foci l, if the foci are really close together, the ellipse is very nearly a circle. If they are really far apart, that is close to a distance of l apart, then the ellipse is a long, thin thing. By continuity, all amounts of stretch are covered. This problem illistrates a general method for solving equations with roots in them, such as l = sqrt((x-f)^2+y^2)+sqrt((x+f)^2+y^2) An efficient way to deal with equations like this is to rename the roots as variables (in this case d1 and d2) and give them separate equations. Then you have a system of polynomial equations in several variables. And the way to solve that, or at least chip away at it, is to treat the non-linear monomials as independent linear variables as I have done above. You can genereate extra equations by multiplying by the variables you start with. Greg From: David G Radcliffe Subject: Plane geometry problem Find all functions f satisfying the following conditions: (1) f maps the plane to itself (2) f is 1-1 and onto (3) f maps lines to lines. Prove your result. From: Susan Schwartz Wildstrom Subject: POD 7-30 SPOILER Another super problem for my precalculus students THANX! Call the nonagon--by the way I believe you intend this to be a regular figure--ABCDEFGHI. Each interior angle contains 140 degrees. The longest diagonal is between for example A and E. Draw in diagonals AC and AD as well. AB, BC, CD, and DE are sides of the figure and are a units long. AB is b units long. Triangles ACD and ADE each contain a special angle (120 and 60 respectively) Using the law of cosines on each of these triangles produces nice expressions \ For ACD c^2 = a^2 + b^2 - 2ab cos 120 = a^2 + b^2 - ab (NB cos 120 = .5) For ACD (correction of a sign in above line) c^2 = a^2 + b^2 - 2ab co2 120 = a^2 + b^2 + ab (cos 120 = -.5) For ADE c^2 = a^2 + d^2 - 2ad cos 60 = a^2 + d^2 - ad Setting the expressions for c^2 equal to each other produces: a^2 + d^2 - ad = a^2 + b^2 + ab or d^2 - ad + (-b^2 - ab) = 0 Using the quadratic formula we obtain d = a + b (Steps skipped) See ya! Susan Wildstrom From: Android Subject: SPOILER -- Solutions to nonagon PODs -- Summary SPOILER Follows Answer is d = a + b Let ABCDEFGHI be a regular nonagon inscribed in a circle. Construct line segments AE and BG, and let P be the point where these segments intersect. Each of the angles BAE, ABG, AEG, and BGE measure 60 degrees, because they subtend arcs of 120 degrees. Therefore, triangles ABP and EGP are equilateral. So, AE = AP + PE = AB + EG, i.e. d = a + b. As posed, we know that each angle subtended by two sides is 140 degrees, and continuing in a straightforward manner, we can find all other angles of interest. In particular, we get the following relations (angle in degrees): If we let m be the length of the medium diagonal, then m^2 = a^2 + d^2 -2adcos60 = a^2 + b^2 -2abcos120 But then since cos60=1/2 and cos120=-1/2, we have d^2 - ad - b^2 -ab = 0 --> d = (a+/-sqrt(a^2 + 4b^2 + 4ab))/2 = (a +/- (a + 2b))/2 = a + b (since d>0) So the required answer is d = a + b. From: Android Subject: POD If a, b, c are non-zero real numbers such that (a+b-c)/c = (a-b+c)/b = (-a+b+c)/a and x = [(a+b)(b+c)(c+a)]/abc and x < 0, then, x = ? Enjoy Benjie From: Ariel Landau Subject: POD - SPOILER > > If a, b, c are non-zero real numbers such that > > (a+b-c)/c = (a-b+c)/b = (-a+b+c)/a > > and > > x = [(a+b)(b+c)(c+a)]/abc > > and x < 0, then, x = ? > Let S = a + b + c (S-2c)/c = (S-2b)/b = (S-2a)/a S/c - 2 = S/b - 2 = S/a - 2 aS = bS = cS if S is different from 0 then a = b = c and x = [(a+a)(a+a)(a+a)]/aaa = 8, which is impossible Hence, S = 0, that is, a + b + c = 0 a + b = -c , b + c = -a , c + a = -b x = (-c)(-a)(-b)/abc = -1 The answer is: x = -1 From: sstrklnd@oyster.smcm.edu Subject: Re: Finding a function (Spoiler) Last week, this problem was posed: Can you find a function f such that if n is a positive integer, f(n) is the nth nonsquare? For example, f(1)=2, f(2)=3, f(3)=5,f(4)=6,etc. You can use + - * / roots powers ceiling floor etc. Good luck! David M. Tuller tulled@rpi.edu I don't recall seeing a solution, so here goes: After many moments of playing with this function, here's what I came up with: f(n) = n + k where k is the square root of the closest square to n. As of yet, I haven't found a nice way of expressing k, so please feel free to help me out. Examples: n | 1 2 3 4 5 6 7 8 9 10... nth non-square| 2 3 5 6 7 8 10 11 12 13... So, for example, f(1) = 1 +1 = 2 and f(10) = 10 + 3 = 13 (since 9 is the square closest to 10). Great problem! -Sue- --- ******************************************************** Susan R. Strickland * "If at first * St. Mary's College of Maryland * you do succeed - * St. Mary's City, MD 20686 * try to hide * sstrklnd@oyster.smcm.edu * your astonishment." * ******************************************************** From: williamw@ee.ubc.ca (william wong) Subject: SPOILER: POD (Aug 2) POD (Aug 2): ------------- If a, b, c are non-zero real numbers such that (a+b-c)/c = (a-b+c)/b = (-a+b+c)/a and x = [(a+b)(b+c)(c+a)]/abc and x < 0, then, x = ? Solution ------------- (a+b-c)/c = (a+b)/c - 1 Similarly, (a-b+c)/b = (a+c)/b - 1 and (-a+b+c)/a = (b+c)/a -1. Therefore, (a+b)/c = (a+c)/b = (b+c)/a. It seems to me that the above relation requires that a=b=c. (*) I do not have a proof of (*). On the other hand, (*) is a sufficient condition for the original equations to hold. x = [(a+b)(b+c)(c+a)]/abc = (2a)(2a)(2a)/a^3 = 8. From: Android Subject: SPOILER -- Solution to POD of 8/2 -- Summary SPOILER Follows Problem: If a, b, c are non-zero real numbers such that (a+b-c)/c = (a-b+c)/b = (-a+b+c)/a and x = [(a+b)(b+c)(c+a)]/abc and x < 0, then, x = ? The Correct Answer: -1 My solution: If you study the equality a bit, you should find that a = b = c, which yields two answers, -1 and 8. Since x < 0, x = -1. a+b b+c c+a --- = --- = --- = -k(say) where k is positive (since x=-k^3) c a b det[1 1 k;1 k 1;k 1 1] = 0 => k^3 -3k + 2 = 0 (k-1)^2 (k+2) = 0 k=1 or -2 Therefor x = -1 From: Android Subject: POD 8/3 If triangle A1 A2 A3 is equilateral and A_n+3 is the midpoint of line seqment A_n A_n+1 for all positive integers n, then what is the measure of angle A_44 A_45 A_46 ? Enjoy, Benjie From: Android Subject: Tennis Tournament In a tennis tournament, n women and 2n men play, and each player plays exactly one match with every other player. If there are no ties and the ratio of the number of matches won by women to the number of matches won by men is 7/5, then what does n equals to? Note, a mixed game could be played, I think. Benjie From: bboru@lobby.ti.com (B. Borowicz) Subject: Minimum bisection problem What is the minimum curve which bisects an equilateral triangle? While you're at it, give the length of this curve in terms of sidelength s. Luck! Brian Borowicz bboru@lobby.ti.com From: bboru@lobby.ti.com (B. Borowicz) Subject: sum of squares problem Prove that no two consecutive odd integers can both be expressed as the sum of two squares greater than zero. Go, amateurs, go! Brian Borowicz bboru@lobby.ti.com From: Android Subject: fermat disussions are available from ams through ftp to the items that are available through the e-MATH GOPHER application. To access: ftp e-math.ams.org login: anonymous password: your identity cd fermat mget * quit Please report problems to dlr@math.ams.org From: Android Subject: SPOILER -- Tennis Problem -- Summary SPOILER The answer is: n=3 Here are two typical solutions: There in all 3n(3n-1)/2 matches. These can be broken down into M-M, M-F, an d F-F. The number of M-M matches is n(2n-1). Since all of these must be won by men, n(2n-1) <= (5/12) (9n^2 -3n)/2, which solves to n<= 3. We are then left with three possible scenarios: 6 men; 3 women 4 men; 2 women 2 men; 1 woman One can begin with any of these, but it can be found that the first works in the case that women beat men in all mixed matches. The others do not have enough matches for there to be a 7/5 ratio (i.e. the number of matches is not divisible by 12). The total number of matches is 3n(3n-1)/2. Of these, 5n(3n-1)/8 (5/12 of the total) were won by men. Since this number must be an integer, n = 0 or 3 (mod 8). There were n(2n-1) matches between men, and of course all of these matches were won by men. Therefore, the number of mixed matches won by men is 5n(3n-1)/8 - n(2n-1) = (-n^2 + 3n)/8. The total number of mixed matches is 2n^2, so 0 <= (-n^2 + 3n)/8 <= 2n^2. The right side of the inequality will hold for any n >= 1, and the left side will hold for n <= 3. CONCLUSION: There were 3 women and 6 men. All of the mixed matches were won by women. From: Android Subject: P.O.D. 8/4 If Q1(x) and r1 are quotient and remainder respectively, when the polynomial x^8 is divided by x+0.5, and if Q2(x) and r2 are the quotient and remainder respectively, when Q1(x) is divided by x+0.5, then what is r2? Enjoy, BTW, I have not received a correct solution for yesterday's POD, the triangle problem. Benjie From: ramana@mgv01.svl.cdc.com Subject: probability question Players A and B play a match consisting of several games. Every game results in a win for one of the players. Both the players are equally likly to win a game. Player to win 10 games wins the match. After 13 games, A won 7 and B won 6. What is the probability that A wins the match? --- ramana@svl.cdc.com --- From: ramana@mgv01.svl.cdc.com Subject: probability question Players A and B play a match consisting of several games. Every game results in a win for one of the players. Both the players are equally likly to win a game. After 13 games, A won 7 and B won 6. What is the probability that A wins the match? --- ramana@svl.cdc.com --- From: Android Subject: Hint -- SPOILER -- 8/3 POD SPOILER Here is the answer, see if you could figure out what happens here. The answer is 120 , not 60. Benjie From: Android Subject: SPOILER -- Solution to 8/4 POD -- Summary Problem: >If Q1(x) and r1 are quotient and remainder respectively, when the >polynomial x^8 is divided by x+0.5, and if Q2(x) and r2 are the >quotient and remainder respectively, when Q1(x) is divided by x+0.5, >then what is r2? SPOILER Follows The answer is -1/16 Solutions: Answer: -1/16 By a change of variables (y=x+.5;x=y-.5) the answer is clearly the coefficient of "y" in (y-.5)^8, which is 8 (-.5)^7 = -1/16. r2 = -1/16 x^8 = Q1(x) (x+0.5) + r1 Q1(x) = Q2(x) (x+0.5) + r2 Therefore, x^8 = Q2(x) (x+0.5)^2 + r2 (x+0.5) + r1 Differentiate both sides and put x= -0.5 By twice using synthetic division: x^8 divided by (x+.5) gives x^7 - 1/2*x^6 + 1/4*x^5 - 1/8*x^4 + 1/16*x^3 - 1/32*x^2 + 1/64*x - 1/128 and the remainder is 1/256. On the next division we get x^6 - x^5 + 3/4*x^4 - 1/2*x^3 + 5/16*x^2 - 3/16x + 7/64 with a remainder of -1/16. So the answer is -1/16 From: David G Radcliffe Subject: Midpoint problem Let x(1),x(2),x(3),... be a sequence of points in the plane such that x(n+3) is the midpoint of x(n) and x(n+1) for all n. Let y be the limit point of this sequence. Express y in terms of x(1), x(2), and x(3). From: Android Subject: SPOILER -- Probability question -- SPOILER SPOILER follows Subject: probability question - SPOILER `A' must win three more games and must do it within the next 6 games or less. The problem can be restated - what is the probability that `A' will win 3 or more games in the next six games? Using the binomial formula: P = (n!/(n-r)!r!) * p^r * q^(n-r) n = 6 games r = number of wins p = probability of winning a game = 1/2 I will calculate the cumulative probability for r=3, r=4, r=5 and r=6. P = P(r=3) + P(r=4) + P(r=5) + P(r=6) = (6!/(3!3!)) * p^6 + (6!/(2!4!)) * p^6 + 6 * p^6 + p^6 = 42 * p^6 = 21/32 So the probability that `A' wins the match is 21/32 or 65.6 percent. ...Paul From: Android Subject: POW Just finished reading the paper "Hilbert's 10th Problem" by Marin Davis and Reuben Hersh. They were talking about Hilbert's 10th problem and its relationship with Diophantine equations. Then I remembered this problem from IAMS a couple of days ago. -------------------cut--------------------- From: David Michael Tuller Subject: Finding a function Can you find a function f such that if n is a positive integer, f(n) is the nth nonsquare? For example, f(1)=2, f(2)=3, f(3)=5, f(4)=6, etc. You can use + - * / roots powers ceiling floor etc. Good luck! Solution by Erick : n + round(sqrt(n)). -------------------cut--------------------- The point was that if you have a listable set (such as the set of nonsquare number), then it must corresponds to a Diophantine equation. Therefore I conclude that David Tuller's problem should have a solution in form of Diophantine equation ( (n + round(sqrt(n))) is not, isn't it?). So, here is the POW, Part 1, solve the above problem of David Tuller using Diophantine equation. Part 2, Find a function in Diophantine equation form that represent the fibonacci numbers. In other word, the function that gives the following results: f(1) = 1 f(2) = 1 f(3) = 2 f(4) = 3 f(5) = 5 ... f(11) = 89 Enjoy, Benjie From: kubo@math.harvard.edu (Tal Kubo) Subject: diophantine problems A more precise definition of "Diophantine representation" is needed. A Diophantine representation of a relationship between variables x and y (such as y=F(x) for some given function F) is a finite system of polynomial equations with integer coefficients whose solvability in integers, for given values of x and y, is equivalent to x and y being related in the appropriate way. More generally there are notions of Diophantine representations of relations between several variables, or membership of a single variable in a set. For example, the relation y=x^2 is obviously Diophantine -- take the system consisting of the single polynomial equation y=x^2. By combining equations one can combine relations, e.g. if z>0 is diophantine (it is), then so is x>y, since this is equivalent to x=y+t and t>0, the second one being equivalent to a system of equations. Part 1 of Benjie's question is not too hard, but Part 2 -- don't hold your breath waiting for a solution. It was a major breakthrough, one which solved Hilbert's 10th problem, when Matijasevich found a Diophantine representation of the Fibonacci numbers. It's not hard to give an equation whose solutions are the Fibonacci numbers, i.e. one can express in Diophantine language the concept "X is a Fibonacci number". What is much harder is to express in such terms the concept "X is the N'th Fibonacci number". As an analogy, it's easy to write equations expressing "N is composite": N=xy, x>1, y>1. But it's much harder to express "N is the M'th composite number", using Diophantine or any other type of equations. From: Android Subject: SPOILER -- Midpoint Problem -- Summary SPOILER Follows Problem: Let x(1),x(2),x(3),... be a sequence of points in the plane such that x(n+3) is the midpoint of x(n) and x(n+1) for all n. Let y be the limit point of this sequence. Express y in terms of x(1), x(2), and x(3). Solutions: The coordinates of {x(i)} converge independently, so we first solve for the one-dimensional case. Thus we wish to solve f(0) = a, f(1) = b, f(2) = c, f(n+3) = (f(n)+f(n+1))/2 for real f(i) (indexing from 0 simplifies the following argument, and does not alter the solution). The theory of linear recursions shows that f(i) is a linear combination of geometric sequences whose ratios r solve r^3 = (1 + r)/2. In this case, r is equal to one of x = 1, y = (-1+i)/2, or z = (-1-i)/2, and so we have f(n) = s x^n + t y^n + u z^n = s + t y^n + u z^n Since |y| < 1 and |z| < 1, the last two terms tend to 0 as n increases, so that f(n) approaches s. Hence we must solve for s in f(0) = s + t + u f(1) = s + y t + z u f(2) = s + y^2 t + z^2 u yielding s = (f(0) + 2 f(1) + 2 f(2))/5. Since, in the original problem, convergence in independent for each coordinate of {x(i)}, the sequence approaches (x(0) + 2 x(1) + 2 x(2))/5. The same result holds in higher dimensions. if y=(y1,y2) and x(n)= (x1(n),x2(n)) then y1 is the limit of the sequence x1(n) which satisfies the relations: x1(n+3)= .5(x(n) + x(n+1)) (*) The same is valid also for y2, and the limit y exists if and only if both limits y1 and y2 exist. Then it's enough to find the limit of a sequence of real numbers a(n) which satisfies the relation (*), in terms of a(1), a(2) and a(3) a(n+4) = .5(a(n+1) + a(n+2)) a(n+5) = .5(a(n+2) + a(n+3)) a(n+6) = .5(a(n+3) + a(n+4)) = = .25(a(n+1) + a(n+2)) + .5a(n+3) or [a(n+1)] [a(n+4)] [.5 0 .25] A * [a(n+2)] = [a(n+5)] ,where A = [.5 .5 .25] [a(n+3)] [a(n+6)] [ 0 .5 .5] and then, [a(1)] [a(3k+1)] (A^k) * [a(2)] = [a(3k+2)] [a(3)] [a(3k+3)] Now, a(n) converges to b if and only a(3k+1), a(3k+2) and a(3k+3) converge to b, that is, if and only if [a(1)] [b] (A^k) * [a(2)] converges to [b] [a(3)] [b] [1 -1-i -1+i] If we set P = [2 -1+i -1-i] [2 2 2 ] [ .2 .2 .2 ] we get Q = P^(-1) = [-.1+.3i -.1-.2i .15+.05i] and QAP = D [-.1-.3i .-1+.2i .15-.05i] where D = diag (1,.25(1+i),.25(1-i)). Then (A^k) = [(PDQ)^k] = P(D^k)Q but when k tend to infinite, D^k tends to B = diag (1,0,0) so A^k tends to [.2 .2 .2] PBQ = [.4 .4 .4] , so a(3k+1), a(3k+2) and a(3k+3) tend to [.4 .4 .4] [a(1) + 2a(2) + 2a(3)]/5, and therefore this is the limit of the sequence a(n) Thus, the answer is : y = [x(1) + 2x(2) + 2x(3)]/5 From: Android Subject: SPOILER -- bisecing triangle -- Summary SPOILER Follows Problem: What is the minimum curve which bisects an equilateral triangle? While you're at it, give the length of this curve in terms of sidelength s. Solution: Among all closed curves in the plane of a given perimeter p, the circle encloses the largest area. Therefore, the area enclosed by any closed curve of perimeter p is less than or equal to p^2/(4 pi). Let ABC be an equilateral triangle with area a. Suppose P is a path of length p which divides ABC into two components of equal area. There are three cases to consider: Case 1. P is a closed curve. Then P encloses an area of a/2, so a/2 <= p^2/(4 pi), thus p >= sqrt(2 pi a). Case 2. The endpoints of P lie on the same side of ABC. Assume without loss of generality that the endpoints lie on AB. Reflect P across the line AB. Join P and its mirror image to form a closed curve C. The perimeter of C is 2p, and it encloses an area of a. Therefore, a <= (2p)^2/(4 pi), so p >= sqrt(pi a). Case 3. The endpoints of P lie on different sides of ABC. Assume WLOG that the endpoints lie on AC and BC. Repeatedly reflect P across AC and BC. Join P and its images to form a closed curve C. The perimeter of C is 6p, and it encloses an area of 3a. Therefore, 3a <= (6p)^2/(4 pi), so p >= sqrt(pi a / 3). We conclude that p >= sqrt(pi a / 3). Equality holds when P is an arc of a circle centered at a vertex, so this is the minimal curve which bisects ABC. Now a = sqrt(3) s^2 / 4, so p = sqrt(pi) s / (2 3^(1/4) ). From: Android Subject: POD Here is a problem from the 34th International Math Olympoiad. I am planning on using some of those problems for our contest, but here is a prove problem which is not suitable for our contest. Let f(x) = x^n + 5x^{n-1} + 3 where n>1 is an integer. Prove that f(x) cannot be expressed as the product of two polynomials, each of which has all its coefficients integers and degree at least 1. Enjoy, Benjie From: Android Subject: Linear Recurrences I have received a couple of notes asking for more information on theory of linear recurrences, in connection with the "Midpoint Problem". I do not have a reference, but I suspect that you may find this subject covered under generating functions. At any rate, the general form of the linear recurrences of which I speak is f(k) = a_k if 0 <= k < d (1) d-1 sum (b_j f(k-d+j)) if k >= d (2) j = 0 where d >= 1, a_i and b_i (0 <= i < d) are complex constants. d is called the degree of the linear recurrence. A well known linear recurrence is f(0) = 1 f(1) = 2 f(k) = f(k-2) + f(k-1) if k >= 2 which generates the Fibonnaci sequence: f = (1, 2, 3, 5, 8, 13, 21, ...) This recurrence is of degree d = 2, with a_0 = 1, a_1 = 2, b_0 = 1, and b_1 = 1. The set of functions f satisfying (2) above with arbitrary initial values a_i form a vector space with respect to elementwise addition and multiplication by a complex scalar. This vector space is of dimension d, and has for one basis the set of functions f_i (0 <= i < d) defined by f_i(k) = 1 if k = i 0 if 0 <= k < d, k != i (2) if k >= d Any specific f satisfying (2) may then be represented as the sum d-1 f = sum (a_j f_j) j = 0 ---<>--- One striking feature of linear recurrences is that for the vector space of functions satisfying (2), it is almost always possible to find a basis consisting entirely of geometric sequences, that is, sequences of the form (1, r, r^2, r^3, ...) In other words, functions satisfying (2) are almost always representable as a linear combination of a finite number of geometric series. Suppose, that some function g satisfying (2) is indeed a linear combination of geometric sequences. We can then find basis functions f satisfying (2) which are pure geometric sequences, i.e., f(k) = r^k because it is geometric, and also (2) is true: d-1 f(k) = sum (b_j f(k-d+j)) if k >= d j = 0 which together imply d-1 r^k = sum (b_j r^(k-d+j)) if k >= d j = 0 Choosing k = d gives d-1 r^d = sum (b_j r^j) (3) j = 0 We can easily solve this degree-d polynomial for d values of r. It turns out that our assumption that g is a linear combination of geometric sequences is justified precisely when (3) has no repeated roots. ---<>--- The Fibonnaci example above turns out to be such a sequence. In this case, the recurrence is f(k) = f(k-2) + f(k-1) if k >= 2 In particular, f(2) = f(0) + f(1). Assuming f is geometric, that is, f(k) = r^k, yields r^2 = 1 + r so that the geometric ratio is one of x = (1+sqrt(5))/2 ~= 1.6180339 y = (1-sqrt(5))/2 ~= -.6180339. Since no root is repeated, f is a linear combination of the two possible geometric basis solutions, so that f(k) = p x^k + q y^k for some complex p and q. Indeed, we know the Fibonnaci sequence can be expressed in this form (you supply p and q). ---<>--- A counterexample which shows that a linear recurrence need not be the sum of geometric sequences is f(0) = 0 f(1) = 1 f(2) = 4 f(k) = f(k-3) - 3 f(k-2) + 3 f(k-1) k >= 3 You should be able to identify this sequence with little trouble, prove the recurrence, and show that it is not a linear combination of geometric sequences. It turns out the (3) is r^3 = 1 - 3^r + 3r^3 <==> (r - 1)^3 = 0. which clearly root 1 with multiplicity 3. From: Android Subject: sum of two square problem -- SPOILER SPOILER > Prove that no two consecutive odd integers can both be > expressed as the sum of two squares greater than zero. Squares of odd numbers are odd, and those of even numbers are even. To have an odd sum of two squares, one must be even, and one must be odd. Let 2a be the even number to be quared, 2b+1 the odd one: (2a)^2 + (2b+1)^2 = 4a^2 + 4b^2 + 4b + 1 = 4(a^2 + b^2 + b) + 1 i.e. all such (odd) numbers must be congruent to 1 modulo 4. Two consecutive odd integers cannot do so, one is congruent to 3 (mod 4). Q.E.D. I do not see any reason for the "greater than zero" restriction in the original question. Can someone enlighten me? From: Android Subject: P.O.D. The function f satisfies the functional equation f(x) + f(y) = f(x+y) - xy - 1 for every pair x,y of real numbers. If f(1) = 1, then the number of integers n != 1 for which f(n) = n is _____ ? Enjoy Benjie From: Android Subject: Circle Problem Circles with centers A, B, C each have radius r, where 1 < r < 2. The distance between each pair of centers is 2. If B' is the point of intersection of circle A and circle C which is outside circle B, and if C' is the point of intersection of circle A and circle B which is outside circle C, then length B'C' equals to what in terms of r? Happy mathing, Ben From: Android Subject: SPOILER -- 8/9 POD: function problem -- Summary SPOILER Follows Problem: The function f satisfies the functional equation f(x) + f(y) = f(x+y) - xy - 1 for every pair x,y of real numbers. If f(1) = 1, then the number of integers n != 1 for which f(n) = n is _____ ? Solution: Let g(x)=f(x)-(x^2+x-2)/2. Then g(x)+g(y)=f(x)+f(y)-x^2/2 -x/2 + 1 -y^2/2-y/2 + 1= =f(x+y)-x^2/2 -xy -y^2/2 -x/2 -y/2 +1 =f(x+y)- ((x+y)^2 +(x+y) -2)/2 =g(x+y). g(1)=f(1)=1; hence g(n)=n for all integers n. ("iff" is an abriviation for if and only if) f(n)=n iff n^2+n-2 = 0 iff n=1 or n=-2. Hence, the answers is "1". 1. Let's figure out f(n) for n=1,2,3,... f(1) + f(1) = 2 = f(2) - 1 - 1 ==> f(2) = 4. f(1) + f(2) = 5 = f(3) - 2 - 1 ==> f(3) = 8. f(1) + f(3) = 9 = f(4) - 3 - 1 ==> f(4) = 13. and so on. 2. We can see that f(n) = f(n-1) + f(1) + (n-1) + 1 = f(n-1) + n + 1 (*) If we look for n s.t. f(n) = n ==> f(n-1) + n + 1 = n ==> f(n-1) = -1 (**) 3. For n>1, f(n) > 0 and increases monotonically according to (*). Therefore, no solution exists for n>1. 4. Plug n=1 into (*): f(1) = f(0) + 2 = 1 ==> f(0) = -1 (satisfies (**). Thus f(1) = 1!) Plug in n=0: f(0) = f(-1) + 1 = -1 ==> f(-1) = -2. Plug in n=-1: f(-1) = f(-2) + 0 = -2 ==> f(-2) = f(-1) = -2. Plug in n=-2: f(-2) = f(-3) - 1 = -2 ==> f(-3) = -1 !! (satisfies (**)) ==> f(-2) = -2 !! Plug in n=-3, f(-4) = 1. Plug in n=-4, f(-5) = 4. In fact, since f(n-1) = f(n) - (n+1), for n < -4, f(n) increases monotonically with DECREASING n. We do not expect to find another solution. To conclude, f(n) = n is satified if n = -2. First notice that f(n+1)=f(n)+n+2. Then f(n) is symmetric around n=-1.5, that is, f(-1+j)=f(-2-j) for all integers j. Also f is strictly increasing for n>=-1 and for n<=-1. A quick computation yields that the sequence f(n) looks like n ...,-6,-5,-4,-3,-2,-1, 0, 1, 2, 3, 4, ... f(n) ..., 8, 4, 1,-1,-2,-2,-1, 1, 4, 8,13, ... So f(-2)=-2. Now f(n)>0 for all n<=-4. [This follows from the fact that f(-4)=1 and that f(n) is strictly increasing when n<=-4.] So there does not exist n<=-4 such that f(n)=n. Also, f(n)>n for all n>=2. [This follows from the fact that f(2)=4 and that f(n) is strictly increasing when n>=2.] So we only need to look at the interval [-3,1]. There's only one integer in that interval that satisfies your condition: namely n=-2, for f(-2)=-2. From: Android Subject: # of Roots David Wagner and I have a conjecture here and neither of us was successful on proving it. So here it goes, If p(x) is a polynomial of n degree and p(x)=0 has n real, distinct roots, then p'(x) has i-1 real roots. Is it true? Benjie From: Wlodzimierz Holsztynski Subject: # of Roots / an answer Begin forwarded message: From: Android Subject: # of Roots David Wagner and I have a conjecture here and neither of us was successful on proving it. So here it goes, If p(x) is a polynomial of n degree and p(x)=0 has n real, distinct roots, then p'(x) has n-1 real roots. Is it true? Benjie ================== Over the customary field of real numbers it is true. Indeed, there is a local max or min between every two consecutive roots of f (and that local extremum is different from the roots of f--f'(x) is not 0 at any root of f when all roots are simple, i.e. when the # of diff. roots = deg(f)). Thus we have n-1 local extrema and they are attained at the n-1 diff. roots of f'. On the other hand, consider a finite field F which has q elements. Take product of all binomials x - a where a runs over all elements of F. (The result is x^q - x -- small Fermat!.) Take the derivative. It has no roots! (Actually, derivative is constant -1). Indeed, if t is a simple root of f than f(x) = (x-t)*g(x) where g(t) is not 0. Then f'(x) = g(x) + (x-t)*g'(t) hence f'(t) = g(t) is not 0. Remark. The above argument about simple roots not being roots of the derivative holds for all fields. All this is "texbook". ----- W. Holsztynski From: Android Subject: SPOILER -- Circle Problem -- Summary SPOILER Construct line segment from A to C and from B to B'. Label their intersection D. Angle BAD is 60 degrees. Label angle DAB theta. AD is 1; AB' is r; DB' is sqrt(r^2-1). Sin theta= sqrt (r^2-1)/r Cos theta = sqrt (1/r) B'C' can now be seen as the base of isosceles triangle AB'C', whose other sides are length r and whose vertex angle has measure 60 degrees + 2 theta. B'C' is then 2r sin (30 degrees + theta) = 2r (1 + sqrt ( 3 r^2 -3) / 2r) = 1 + sqrt (3 r^2 - 3). From: Android Subject: # of Roots problem I didn't realize that this was just a simple application of Rolle's theorem. Shame on me. Anyway, how about the following, I doubted it's true, but I can't disprove it neither. If p(x) has n distinct real roots, then p'(x) has n-1 distinct real roots. ^^^^^^^^ ??? Benjie From: Android Subject: P.O.D. Evaluate in terms of pi, Arctan(1) + Arctan(1/2) + Arctan(1/3) Enjoy, Benjie From: Wlodzimierz Holsztynski Subject: be Nieoferma (Polish for Neofermat ) I was recently tinkering evenly with odd integers and even got and proved a few odd things about them. Among others the following theorem about divisibility of some geometric series': p^s | 1 + 2^p^(s-1) + ... + 2^(p^(s-1) * (p-3)/2) for every prime p = 1 or 7 mod 8, s=1,2,.... So, now you may have fun and prove it too. Try. (My own proof is elementary and does not introduce any new methods, too bad.) (For illustration: 7^2 | 1 + 2^7 + 2^14 7^3 | 1 + 2^49 + 2^98 17^2 | 1 + 2^17 + 2^34 + 2^51 + 2^68 + 2^85 + 2^102 + 2^119 etc.) Wlodzimierz Holsztynski From: ttgrq@info.win.tue.nl (Andreas Gammel) Subject: which one is larger ? which of the following two numbers is the largest, pi e (e) or (pi) PS. use of a calculator is not permitted, a proof is required! Andreas (ttgrq@info.win.tue.nl) From: Ariel Landau Subject: Induction problem Here is a may-be-non-trivial problem to be solved by induction: Define the following sequence: a(2) = 3 a(n+1) = [a(n)^2]/n and then prove by induction that a(n) > sqrt(n) for n= 2,3,4,5,... (Remark: sqrt(n) is the positive square root of n) Enjoy Ariel From: a_rubin@dsg4.dse.beckman.com (arthur rubin) Subject: Re: Induction problem (SPOILER) Problem: Here is a may-be-non-trivial problem to be solved by induction: Define the following sequence: a(2) = 3 a(n+1) = [a(n)^2]/n and then prove by induction that a(n) > sqrt(n) for n= 2,3,4,5,... (Remark: sqrt(n) is the positive square root of n) Solution: (SPOILER) Prove, instead, by induction, that a(n) >= (n+1) for n>=2 a(2)=3 =2+1 If a(n) >= (n+1), then a(n+1) >= [(n+1)^2]/n = (n^2+2n+1)/n = n+2+1/n >= n+2. From: a_rubin@dsg4.dse.beckman.com (arthur rubin) Subject: Which one is larger? (SPOILER) ------------------------------------------------------------------ FORWARDED MAIL FOLLOWS: ------------------------------------------------------------------ From: a_rubin (arthur rubin) Subject: Re: which one is larger ? (SPOILER) Cc: iams@quack.kfu.edu Wednesday, August 11, 1993 2:52:08 am (PDT) Problem: which of the following two numbers is the largest, pi e (e) or (pi) PS. use of a calculator is not permitted, a proof is required! Solution (SPOILER) x e Consider the functions f(x) = e , and g(x) = x . e f'(x)/f(x)=1, g'(x)/g(x)=e/x; f(e)=g(e)=e f'(x)/f(x)>g'(x)/g(x), for x>e and f(e)=g(e); hence f(x) >= g(x) for x>=e, and therefore f(pi) >= g(pi), so the first one is larger. Alternatively, if you don't want to use as much calculus, consider / x \ | e | h(x) = log | ----- | = x - e log (x) e | e | e \ x / h(e)=0; h'(x) = 1 - e/x > 0 for x>e; hence h(pi) > 0, and pi e e > pi From: ramana@mgv01.svl.cdc.com Subject: SPOILER - which is larger > >which of the following two numbers is the largest, > > pi e > (e) or (pi) > > >PS. use of a calculator is not permitted, a proof is required! > >Andreas (ttgrq@info.win.tue.nl) Answer is e^pi Proof: Consider f(x) = x^(1/x) f'(x) = f(x)(1-log(x))/x^2 Therefore, f'(x) = 0 => x=e And if x > e, f'(x) < 0 Hence for x > e, f(x) is a monotonically decreasing. e^(1/e) > pi^(1/pi) --- QED I remember having read an interesting generalization in 'American Mathematical Monthly' a few years back. I don't remember the result exactly, but it is something like this: In any such pyramid of e and pi, if e in lower position is exchanged with pi in upper position, the value decreases. For example, e^pi^e^e^pi is greater than pi^pi^e^e^e because the first and last are interchanged! If any one has a nice proof of that please do post to IAMS. Thanks, --- ramana@svl.cdc.com --- From: David G Radcliffe Subject: Re: Which one is larger? (SPOILER) > Problem: > > which of the following two numbers is the largest, > > pi e > (e) or (pi) > > > PS. use of a calculator is not permitted, a proof is required! Yet another solution follows. If x > 0 then e^x > 1 + x. Let x = (pi/e) - 1. Then e^((pi/e)-1) > pi/e, so e^(pi/e) > pi, thus e^pi > pi^e. Alternatively, show that f(x) = x^(1/x) achieves its maximum at x = e. Then e^(1/e) > pi^(1/pi) ==> e^pi > pi^e. From: Android Subject: SPOILER -- POD 8/11 -- Summary SPOILER Follows Problem Evaluate in terms of pi, Arctan(1) + Arctan(1/2) + Arctan(1/3) Solutions: pi/2 tan(Arctan(1/2) + Arctan(1/3)) = (1/2 + 1/3)/ (1 - (1/2)(1/3) ) = 1; 0 0 < atan(1/2) + atan(1/3) < 1 ==> 0 < pi/4 + pi k < 1 ==> 0 < 1/4 + k < 1/pi ==> -1/4 < k < 1/pi-1/4 < 1/3-1/4 = 1/12 ==> k = 0 (since k is integer) ==> atan(1/2) + atan(1/3) = pi/4 which gives atan(1) + atan(1/2) + atan(1/3) = pi/2 as required. From: bboru@lobby.ti.com (B. Borowicz) Subject: Arctan prob I came across an interesting identity while solving yesterday's arctan problem. Somebody tell me if this is well-known: Arctan(x/y) + Arctan((y-x)/(y+x)) = pi/4 I found a relatively simple geometric proof, so I would guess that this were common knowledge, but I don't have trig identity tables around. Incidentally, I think the restrictions on x and y are 0 Subject: atan(1/3)+atan(1/2)=atan(1) arctan(1/3)+arctan(1/2)=arctan(1) see Martin Gardner MG9SA: Mathematical Circus MG9SA: Alfred A. Knopf (1979) New York MG9SA.11.3 Three Squares (elementary geometry) MG9SA.11.3. arctan(1/3)+arctan(1/2)=arctan(1), (3+i)(2+i)=5+5i MG9SA.11.3.a 54 different proofs, JoRM 4 (Apr 1971) 90-99 MG9SA.11.3.b geometrical proof of a result of Lehmer's, Fib. Quar. 11(1973)539 Torsten Sillke From: Android Subject: P.O.D. In triangle ABC, E is the midpoint of side BC and D is on side AC. If the length of AC is 1 and angle BAC is 60, angle ABC is 100, angle ACB is 20 and angle DEC is 80, then what is the area of triangle ABC plus twice the area of triangle CDE ? Enjoy, Benjie From: joe@inuo30.mathematik.uni-jena.de (Johannes Waldmann) Subject: Sum of binomials This is a problem by F. Goetze, Jena, as published in WURZEL 9/93. For integer n >= 0, prove: \sum_{k=0}^n (n \chose k) (k+1)^(k-1) (n-k+1)^(n-k) = (n+2)^n For instance, n=3 gives: 1 1^-1 4^3 + 3 2^0 3^2 + 3 3^1 2^1 + 1 4^2 1^0 = 5^3 64 + 27 + 18 + 16 = 125 There is a NASTY solution involving generating functions and the likes. (I'm not going to type it in.) We'd like to see a NICE solution with generating functions, or a solution WITHOUT such beasts at all. -- Johannes Waldmann, Fakult\"at f\"ur Mathematik und Informatik UHH, Jena, D-07740, Germany, phone (03641) 82 24778, joe@ inuo30.mathematik.uni-jena.de ... Themenwechsel. Themenwechsel ohne Tuwoerter als schlichte Geraeuschbeispiele, nicht mehr. From: joe@inuo30.mathematik.uni-jena.de (Johannes Waldmann) Subject: cubic roots Prove: (4/9)^(1/3) + (25/9)^(1/3) - (80/9)^(1/3) = (6860^(1/3) - 19)^(1/3) and find similar equalities. -- Johannes Waldmann, Fakult\"at f\"ur Mathematik und Informatik UHH, Jena, D-07740, Germany, phone (03641) 6 30793, joe@ inuo30.mathematik.uni-jena.de ... Themenwechsel. Themenwechsel ohne Tuwoerter als schlichte Geraeuschbeispiele, nicht mehr. From: Torsten Sillke Subject: Re: Sum of binomials > For integer n >= 0, prove: > > \sum_{k=0}^n (n \chose k) (k+1)^(k-1) (n-k+1)^(n-k) = (n+2)^n > This is a special case of the Abel identity (1826): \sum_{k=0}^n (n \chose k) x (x - k z)^(k-1) (y + k z)^(n-k) = (x+y)^n set: x = 1, y = n+1, z = -1. Two proofs and many references can be found in: Louis Comtet Advanced Combinatorics, Reidel Publ., 1974 A combinatorial interpretation of a further generalization can be found by: %a Volker Strehl %j Discrete Math. %v 99 %d 1992 %p 321-340 %t Identities of Rothe-Abel-Schlaefli-Hurwitz-Type %o (Special Vol.: Algebraic Combinatorics; I. M. Gessel) %x Zbl. 756.05006 (L. A. Szekely) He made several historical annotations and gives references. Torsten Sillke From: Android Subject: Recent problems Due to the mailing list problem, a lot of you didn't receive problems for the last a couple of days. Here are the probelms posted to the list during the last three-four days, enjoy. Benjie --------cut---------- Latest P.O.D.s 8/11 From: ttgrq@info.win.tue.nl which of the following two numbers is the largest, pi e (e) or (pi) PS. use of a calculator is not permitted, a proof is required! =============================================================================== 8/12 From: benjie@quack.kfu.com In triangle ABC, E is the midpoint of side BC and D is on side AC. If the length of AC is 1 and angle BAC is 60, angle ABC is 100, angle ACB is 20 and angle DEC is 80, then what is the area of triangle ABC plus twice the area of triangle CDE ? =============================================================================== 8/13 From: joe@inuo30.mathematik.uni-jena.de Prove: (4/9)^(1/3) + (25/9)^(1/3) - (80/9)^(1/3) = (6860^(1/3) - 19)^(1/3) and find similar equalities. =============================================================================== Latest P.O.W.s 8/10 From: wlodek@atg.wiltel.com I was recently tinkering evenly with odd integers and even got and proved a few odd things about them. Among others the following theorem about divisibility of some geometric series': p^s | 1 + 2^p^(s-1) + ... + 2^(p^(s-1) * (p-3)/2) for every prime p = 1 or 7 mod 8, s=1,2,.... So, now you may have fun and prove it too. Try. (My own proof is elementary and does not introduce any new methods, too bad.) (For illustration: 7^2 | 1 + 2^7 + 2^14 7^3 | 1 + 2^49 + 2^98 17^2 | 1 + 2^17 + 2^34 + 2^51 + 2^68 + 2^85 + 2^102 + 2^119 etc.) =============================================================================== Misc. Problems 8/11 From: c0465193@techst02.technion.ac.il Define the following sequence: a(2) = 3 a(n+1) = [a(n)^2]/n and then prove by induction that a(n) > sqrt(n) for n= 2,3,4,5,... (Remark: sqrt(n) is the positive square root of n) =============================================================================== 8/13 From: joe@inuo30.mathematik.uni-jena.de For integer n >= 0, prove: \sum_{k=0}^n (n \chose k) (k+1)^(k-1) (n-k+1)^(n-k) = (n+2)^n For instance, n=3 gives: 1 1^-1 4^3 + 3 2^0 3^2 + 3 3^1 2^1 + 1 4^2 1^0 = 5^3 64 + 27 + 18 + 16 = 125 From: t-davidw@microsoft.com Subject: The Gospel according to Knuth I just got Knuth out of our corporate library here and have been reading some of his stuff - it's really nifty! I just thought I'd share one problem from his book that I've been working on, maybe you'll find it interesting too if you haven't seen it yet... You have N independent, uniformly distributed random variables on the interval [0,1]. What's the probability that the smallest of them is less than x? Also, some additional queries that I've added: Ok, now how about the probability that the k-th smallest is less than x? What if the random variables are independently and identically distributed with some general distribution, rather than a uniform one? Of course, this is probably standard introductory probability theory or something, but I've never had a probability class so it's pretty challenging for me :-) From: erickw@sfu.ca Subject: Joint AMS-CMS-MAA Conference The First Joint AMS-CMS-MAA Meeting began today at UBC in Vancouver. Since I was able to attend, I thought I would give you all a little report... :-) The first talk was by our newly visiting professor Jonathan Borwein, on Means, Iterations, and experimentally induced identities. In particular, how Maple helped him (and his brother Peter) find a proof of something they found in the works of Ramanujan (we actually got to see a photocopy of a page!), and the general theory of mean iterations, of the form: a_{n+1} = M(a_n,b_n) b_{n+1} = N(a_n,b_n) where M and N are means, i.e. min(x,y) <= M(x,y),N(x,y) <= max(x,y). I'll post some simple examples if anyone's interested...What's interesting about these mean iterations, is that typically convergence analysis is very easy, but finding the limit is very difficult. He also briefly presented an impressive quartically converging (the number of correct digits roughly quadruples at every iteration) algorithm for Pi! At lunch, I saw a couple of famous faces...Michael Spivak, and I think Donald Knuth (the nametag was a little obscured :-) for example. Sir Michael Atiyah of Cambridge gave a talk on the history of developments between geometry and physics a bit later...It was the 39th MAA Earle Raymond Hedrick Lecture, whose past participants include Paul Halmos, Ivan Niven, N.J.A. Sloane, and John Conway. After that, the talks split up into several areas...I decided to go to the Number Theory and Graph Theory + Combinatorics ones. The Number Theory talks were not that interesting, but a deceptively simple yet unsolved problem caught my eye: Erdos and Straus conjectured that for every integer n >= 2, there exist positive integers x, y, z satisfying 4/n = 1/x + 1/y + 1/z. In the Graph Theory + Combinatorics talks, N.J.A. Sloane gave a talk on coding theory (I only saw the last half), and Donald Snow of Brigham Young University gave an elementary, slick new way of getting the formulas for the kth powers of the first n integers, and generalizations (again, I'll post more if anyone's interested). By far, the anticipated event was Barry Mazur's (Harvard) talk on Fermat's Last Theorem. The room was packed almost half an hour before it started, and we had to sit on the stairs! He discussed the development which led up to Andrew Wiles' proof, including the ABC Conjecture, Serre's Conjecture, and of course the Shimura-Taniyama-Weil Conjecture. And he was greeted by an enormous round of applause when it was finally over. Well, that's about it for today's report! I didn't get to see Erdos today, but I hope to meet him tomorrow, as he is scheduled to give a number theory talk. -- Erick From: erickw@sfu.ca Subject: Cute number theory problem... Here's a problem I thought of during one of the less interesting talks at today's conference (see previous message :-). Enjoy! Prove that for any integer n, there are only finitely many sets S of at most n positive integers, such that x divides P(x)+1 for every element x of S, where P(x) denotes the product of all members of S excluding S. On the other hand, show that for each n >= 1 there exists such a set S with exactly n elements. In other words, there are an infinite numbers of these sets, but only finitely many of a given cardinality. What I'm not sure of, is whether this set is unique (we have to forbid 1 as a member, of course). I know it is for n=3, and I think it is for n=4, but I haven't thoroughly checked it. -- Erick From: t-davidw@microsoft.com Subject: More from Knuth... Here's another nifty little tidbit I just read. Define frac(x) to be the fractional part of x; then 0 <= frac(x) <= 1. Now create a sequence a_n such that a_0 = (sqrt(5)-1)/2 and a_{n+1} = frac(a_n). [a_0 is the golden ratio.] For each value of the sequence, plot it on the interval [0,1] and mark off the remaining intervals. So you'd start with just the interval [0,1]. Then next would be the intervals [0,a_0], [a_0, n]. Repeat until dizzy. Knuth tells us that after we've marked off the points a_0, a_1, ..., a_n then the point a_{n+1} will fall into one of the largest remaining intervals, and in fact if that interval was [x, x+y], then a_{n+1} = x + a_0 y. In other words, the new point will divide the largest interval, and will divide it in the golden ratio. Now does anyone have any idea why this should be true? Knuth mentioned that it had to do with Fibonacci numbers... Dave Wagner dawagner@princeton.edu From: joe@inuo30.mathematik.uni-jena.de (Johannes Waldmann) Subject: still more Knuth I once saw this in sci.math, I think it was taken from Knuth's Concrete Mathematics (but I don't have the book handy at the moment): Given \sum_1^\infty 1/(n*(n+1)) = 1, is it possible to tile a unit square into a sequence of rectangles with sides 1/n and 1/(n+1)? -- Johannes Waldmann, Fakult\"at f\"ur Mathematik und Informatik UHH, Jena, D-07740, Germany, phone (03641) 6 30793, joe@ inuo30.mathematik.uni-jena.de ... Themenwechsel. Themenwechsel ohne Tuwoerter als schlichte Geraeuschbeispiele, nicht mehr. From: Van@cup.portal.com Subject: SPOILER to Knuth problem SPOILER? ====== From: t-davidw@microsoft.com Subject: The Gospel according to Knuth > You have N independent, uniformly distributed random variables >on the interval [0,1]. What's the probability that the smallest of >them is less than x? ======== The probability of any number being < x is x, and The probability of any number being > x is (1-x). The only way that the smallest number is > x is if all are > x, which has prob (1-x)^n for n numbers. Thus the probability of at least one number being less than x is 1 - (1-x)^n (the smallest being among one or more numbers less than x). ======= For a general distribution P(x), p(x) == Integral[0,x, P(y) dy] is the probability of the number being less than x. Then the probability of at least one number being less than x is 1 - (1-p(x))^n ============== I never took a class in probablity either, and I like these problems too. I've heard that Knuth is good, but never seen it, so please post anything of interest you come across. Van van@cup.portal.com From: "A.FARRELL, WRIGHT ST. U., DAYTON, OH 45435" Subject: Read Don's message From: IN%"dhanlen@beta.tricity.wsu.edu" "Don A. Hanlen" 15-AUG-1993 02:07:09.63 Subj: RE: Sum of binomials From: "Don A. Hanlen" Subject: RE: Sum of binomials Message-id: <199308150556.AA02547@quack.kfu.com> Dear Benjie: What follows is an example of the type of stuff I am *still* receiving from the Internet Amateur Mathematics Society (IAMS). It comes from: Torsten Sillke I suspect it got to me via: The Internet Amateur Mathematics Society When I "reply to all recipients", Herr Sillke's name appears on the "To" line, and IAMS on the "Cc" line. I am going to leave the "reply" addressing alone. I suggest that all who read this line forward this message to Benjie so he will become aware of the scope of whatever kind of addressing software he is using. I suggest a forward with the following line at the top: " read Don's message". -- Don A. Hanlen computer-geek =-=-=-=-=-=-=-=-=-=--=-= received message follows =-=-=-=-=-=-=-=-=-=--=-= On Fri, 13 Aug 1993, Torsten Sillke wrote: > > For integer n >= 0, prove: > > > > \sum_{k=0}^n (n \chose k) (k+1)^(k-1) (n-k+1)^(n-k) = (n+2)^n > > > This is a special case of the Abel identity (1826): > > \sum_{k=0}^n (n \chose k) x (x - k z)^(k-1) (y + k z)^(n-k) = (x+y)^n > > set: x = 1, y = n+1, z = -1. > > Two proofs and many references can be found in: > > Louis Comtet > Advanced Combinatorics, Reidel Publ., 1974 > > A combinatorial interpretation of a further generalization can be found by: > > %a Volker Strehl > %j Discrete Math. > %v 99 > %d 1992 > %p 321-340 > %t Identities of Rothe-Abel-Schlaefli-Hurwitz-Type > %o (Special Vol.: Algebraic Combinatorics; I. M. Gessel) > %x Zbl. 756.05006 (L. A. Szekely) > > He made several historical annotations and gives references. > > Torsten Sillke *********************************** Ann M. Farrell Dept. of Mathematics and Statistics Wright State University Dayton, Ohio 45435 email: afarrell@desire.wright.edu *********************************** From: Android Subject: P.O.D. In a triangle with sides of lengths a, b and c, (a+b+c)(a+b-c)=3ab The measure of the angle opposite the side of length c is ______ ? Enjoy, Benjie From: Android Subject: Series & Sequences A sequence {a_n} is a function whose domain is the set of positive integers. The functional values a_1, a_2, a_3, ......, a_n, ... are called the terms of the sequence. A series is an expression in terms of a_1 + a_2 + a_3 ... , or a_1, ra_2, ... etc. Many times we talk about sequence of partial sums (such as the sequence {S_n} where S_n = a_1 + a_2 + ... + a_n), which is a type of "sequence of series". Just wondering if there is any property about the "series of sequence of series" or even the "sequence of series of sequence of series" ??? Benjie From: bullofes@risc5.unisa.ac.za (FES Bullock) Subject: SPOILER - P O D I hope that's enough blank lines. Here's a solution to the following POD: a, b, c are the lengths of the sides of a triangle and (a+b-c)(a+b+c)=3ab. Find the angle opposite side c. Solution. Let \theta be the angle. By cosine rule for triangles cos(\theta)=(a^2 +b^2 - c^2)/(2ab) But the given equality implies that (a^2 + b^2 - c^2)/(2ab) = 1/2. So \theta = 60 degrees. From: Android Subject: SPOILER -- Solution to POD 8/19 -- Summary SPOILER Follows l Problem: In a triangle with sides of lengths a, b and c, (a+b+c)(a+b-c)=3ab The measure of the angle opposite the side of length c is ______ ? Solutions: 60 degrees. Multiply the above equation out and get a^2 + b^2 - ab = c^2 Remember (or in my case, rederive) the law of cosines: a^2 + b^2 - 2abcos(AB) = c^2 conclude that cos(AB) = 1/2 so the angle is 60 degrees. For a sanity check plug in some values for a, b, and c and check. Multiplying out the equation results in: a^2 + b^2 - c^2 - ab = 0 or, equivalently: c^2 = a^2 + b^2 - ab (1) Now apply the law of cosines for the desired angle (call it gamma): c^2 = a^2 + b^2 -2ab cos(gamma) (2) Substitute (1) into (2) for: 2 cos(gamma) = 1 ==> gamma = pi/3 From: Android Subject: P.O.D. The lengths of the sides of a triangle are consecutive integers, and the largest angle is twice the smallest angle. What is the cosine of the smallest angle? Enjoy, Benjie From: Android Subject: SPOILER -- POD 8/19 -- Summary SPOILER Follows Let alpha be the smallest angle, and let n be the length of the smallest side. Apply law of cosines and simplify to result in: n+5 cos(alpha) = ----- (1) 2n+4 Apply law of sins to the smallest and largest angles/sides to result in: sin(alpha) sin(2*alpha) 2 sin(alpha) cos(alpha) ---------- = ------------ = ----------------------- n n + 2 n + 2 Solve for cos(alpha) (assume sin(alpha) != 1): n+2 cos(alpha) = ----- (2) 2n Now, solve 1 and 2 simultaneously for n, resulting in n=4. Substitute back into (1), resulting in cos(alpha) = 3/4 Let n, n+1, n+2 be the lengths of the sides of the triangle. Let theta be the smallest angle, opposite side n, then the largest angle is 2*theta, opposite side n+2. By the cosine rule for triangles n^2=(n+1)^2 + (n+2)^2 - 2(n+1)(n+2)cos(theta) which gives cos(theta)=(n+5)/(2(n+2)). By the sine rule for triangles (sin(theta))/n = (sin(2*theta))/(n+2) = (2sin(theta)cos(theta))/(n+2) and therefore cos(theta)=(n+2)/(2n). So (n+5)/(2(n+2)) = (n+2)/(2n). Solving for n gives n=4 and hence cos(theta) = 3/4. From: Android Subject: P.O.D. I remember doing the following problem in a contest a couple of years ago, I don't remember the wordings, but it was something like the following. A rectangular shaped farm land has length of x and width of y, where x and y are integers. Assume the farm land is being divided into 1x1 squares (see the following picture). -------------------------- B | | | | | | -------------------------- | | | | | | y -------------------------- | | | | | | -------------------------- | | | | | | -------------------------- A x A legal move is either an upward, or rightward move when moving from A to B, and is either a downward or leftward move when moving from B to A. A man starts from A and choose a random route to B, moving legally, then returns from B back to A in a random route, moving legally. What is the propability that the total number of turns he makes, excluding the turn at point B, equals to x*y. Enjoy, Benjie From: Android Subject: Number Theory Problem Find the units digit in the decimal expansion of (15 + sqrt(220))^19 + (15 + sqrt(220))^82 Happy mathing, Benjie From: Android Subject: SPOILER -- Solutions to POD 8/21 -- Summary SPOILER Problem: Find the units digit in the decimal expansion of (15 + sqrt(220))^19 + (15 + sqrt(220))^82 Solutions: From: radcliff@csd4.csd.uwm.edu Consider the function f which satisfies the following conditions: f(n+2) = 30 f(n+1) - 5 f(n) for n >= 0; f(0) = 2, f(1) = 30. It is not hard to show that f(n) = (15 + sqrt(220))^n + (15 - sqrt(220))^n for n >= 0. (Equations of this type were discussed recently on this list, so I won't include the derivation. Send me email for more information.) One can prove by induction that f(n) is divisible by 10 for all n > 0. Therefore, (15 + sqrt(220))^19 + (15 + sqrt(220))^82 + (15 - sqrt(220))^19 + (15 - sqrt(220))^82 is divisible by 10. Now, 0 < (15 - sqrt(220))^19 + (15 - sqrt(220))^82 < 1, so the units digit of (15 + sqrt(220))^19 + (15 + sqrt(220))^82 is nine. From: a_rubin@dsg4.dse.beckman.com r_1 = 15 + sqrt(220), and r_2 15 - sqrt(220) are solutions of x^2 - 30 x + 5 == 0 Consider the sequence a_n = (15+sqrt(220))^n + (15-sqrt(220))^n a_0 = 2 a_1 = 30 a_{n+2) = 30 a_(n+1) - 5 a_n One can easily see that the unit's digit of a_n is 0, for n >= 1. v = (15+sqrt(220))^19 + (15 + sqrt(220))^82 = a_19 + a_82 - r2^19 - r2^82. But, as 0 < r2 < 1, the units digit of v is 9. From: Android Subject: POD 8/23 If a >= 1, then the sum of the real solutions of sqrt(a-sqrt(a+x)) = x is ___? Enjoy, Benjie From: Android Subject: SPOILER -- Solution to POD 8/23 -- Summary SPOILER Problem: If a >= 1, then the sum of the real solutions of sqrt(a-sqrt(a+x)) = x is ___? Solution: Successive equivalent formulations (with b,c positive) a-sqrt(a+x) = x^2 and x = b a-sqrt(a+b) = b^2 and x = b sqrt(a+b)=a-b^2 and x = b a+b = (a-b^2)^2 and a-b^2 = c and x = b a^2 - 2 a b^2 + b^4 -a -b = 0 and a-b^2 = c and x = b a^2 - (2b^2+1)a + b^4 - b = 0 and a-b^2=c and x = b Noting (2b^2+1)^2 - 4 (b^4-b) = 4b^2 + 4b + 1 = (2b+1)^2, (a = 1/2 ((2b^2+1)+2b+1) or a = 1/2 ((2b^2+1)-2b-1) ) and a-b^2=c and x=b (a= b^2+b+1 or a = b^2-b) and a-b^2=c and x=b (a=b^2+b+1 and b+1=c and x=b) or (a=b^2-b and -b=c and x=b) Now, eliminating b and c, and solving for x, we get: (a>=1 and x = (1+sqrt(4a-3))/2) or (a=0 and x=0) So, the answer is (1+sqrt(4a-3)))/2 From: Android Subject: POD I've got myself a IMO problem book. So I will be posting some IMO questions in next couple of days. m and n are natural numbers with 1 <= m < n. In their decimal representations, the last three digits of 1978^m are equal, respectively, to the last three digits of 1978^n. Find m and n such that m+n has its least value. Enjoy, Benjie From: Android Subject: Algebra Problem Three roots of the equation x^4 - px^3 + qx^2 - rx + s = 0 are tan A, tan B, and tan C, where A, B, C are the angles of a triangle. Determine the fourth root as a function of (only) p, q, r, and s. Enjoy, Benjie From: Android Subject: Further Reading I haven't receive any solution to any of yeseterday's problems yet. I do think those questions are hard. So if you want to read more about them, see the following post. --------------------Hint------------------------- > Three roots of the equation > x^4 - px^3 + qx^2 - rx + s = 0 > are tan A, tan B, and tan C, where A, B, C are the angles of a > triangle. Determine the fourth root as a function of (only) p, q, r, > and s. The fourth side of the triangle: Es waere unvernuenftig, dem Dreieck die 4. Seite abzuerkennen. Ivan Paasche see Paasche's papers: - Die vierte Dreiecksseite, PM 5 (1963) 113-123 - Steckenmessungen mittels e-Funktion und Logarithmus, PM 9 (1967) 237-243 - sin-tan Transformation, Polarisation und Pseudopolarisation, Elemente der Mathematik 21 (1966) 61-63 - PM 32 (1990) 89 - Lorenztransformation, Vektorquotienten (Diophantik), 4. Dreiecksseite Abstract, DMV Jahrestreffen 1991, Bielefeld and many other From: Android Subject: SPOILER -- POD 8/25 (Power problem) -- Summary SPOILER Problem: m and n are natural numbers with 1 <= m < n. In their decimal representations, the last three digits of 1978^m are equal, respectively, to the last three digits of 1978^n. Find m and n such that m+n has its least value. Solutions: As only the last 3 digits are of interest, the rest is done modulo 1000. Since 978^3 = 978^103 (=352) is the first repetition, there is none with a smaller sum (continues cyclically). Hence: m=3 and n=103. Proof by UNIX: print powers of 978 (mod 1000), pipe to sort and uniq ... :-) Here is how I solved the problem. Since 1978^n = 1978^m (mod 1000), 1978^n - 1978^m = 0 mod 1000. 1978^n - 1978^m = 1978^m1978^(n-m) - 1978^m = 1978^m(1978^(n-m)-1) 1000 = 2^3 * 5^3, and 1978^m = 2^m 989^m m >= 3 so for the smallest m+n, we let m = 3, and look for smallest n. 1978^(n-m)-1 = 0 mod 5^3 or 1978^(n-m)-1 = 0 mod 125 or 1978^(n-m)=1 mod 125 Let x = n-m, we need to find 1978^x = 1 mod 125 Use a computer we see x would be 100. So n-m=100 m=3 n+m=106. Of course on a contest you don't have computers, but I can't figure out an easier way. From: Android Subject: SPOILER -- Algebra Problem -- Summary SPOILER Problem: Three roots of the equation x^4 - px^3 + qx^2 - rx + s = 0 are tan A, tan B, and tan C, where A, B, C are the angles of a triangle. Determine the fourth root as a function of (only) p, q, r, and s. Solution: Let D be the other root. Then (x - tan A)(x - tan B)(x - tan C)(x - D) = 0. Expand this and equate coefficients to get p = tan A + tan B + tan C + D q = tan A tan B + tan A tan C + tan B tan C + (tan A + tan B + tan C) D r = tan A tan B tan C + (tan A tan B + tan A tan C + tan B tan C) D s = (tan A tan B tan C) D. Since A + B + C = 180, tan C = tan(180 - (A+B)) = - tan(A + B) = - (tan A + tan B) / (1 - tan A tan B), from which it follows that tan A + tan B + tan C = tan A tan B tan C = p - D. Now q - s = tan A tan B + tan A tan C + tan B tan C, so r = (p - D) + (q - s)D = p + q - (s + 1)D. ^^^^^^^^^^^^^^^^^ (%) Therefore, D = (p + q - r) / (s + 1), provided s != -1. ^^^^^^^^^^^^^^^^^^^^^^^^^ (%) NOTE: (%) There was a mistake there. The correct equation should be r = p + (-1+q-s)D and D = (p-r)/(1-q+s) From: Android Subject: POD In triangle ABC, AB=AC. A circle is tangent internally to the circumcircle of triangle ABC and also to sides AB, AC at P,Q, respectively. Prove that the midpoint of segment PQ is the center of the incircle of triangle ABC. Enjoy, Benjie From: a_rubin@dsg4.dse.beckman.com (arthur rubin) Subject: Re: SPOILER -- POD 8/25 (Power problem) -- Summary Problem: m and n are natural numbers with 1 <= m < n. In their decimal representations, the last three digits of 1978^m are equal, respectively, to the last three digits of 1978^n. Find m and n such that m+n has its least value. SPOILER (and addendum to benjie's solution) Here is how I solved the problem. Since 1978^n = 1978^m (mod 1000), 1978^n - 1978^m = 0 mod 1000. 1978^n - 1978^m = 1978^m1978^(n-m) - 1978^m = 1978^m(1978^(n-m)-1) 1000 = 2^3 * 5^3, and 1978^m = 2^m 989^m m >= 3 so for the smallest m+n, we let m = 3, and look for smallest n. 1978^(n-m)-1 = 0 mod 5^3 or 1978^(n-m)-1 = 0 mod 125 or 1978^(n-m)=1 mod 125 Let x = n-m, we need to find 1978^x = 1 mod 125 Use a computer we see x would be 100. So n-m=100 m=3 n+m=106. Of course on a contest you don't have computers, but I can't figure out an easier way. --- a_rubin@dsg4.dse.beckman.com comments: It is "clear" that if a is relatively prime to 125, then a^100 = 1 (mod 125) (Proof: a^4 = 1 (mod 5) (little Fermat theorem or inspection of 1^4,2^4) a^20 = 1 (mod 25) (binomial expansion) a^100 = 1 (mod 125) (binomial expansion) ) Hence, you only need to show that 1978^50 and 1978^20 are not 1 (mod 125), as the set of integers x such that a^x = 1 (mod n) is closed under addition and subtraction. 1978^2 = -1 (mod 5); so 1978^10 = -1 (mod 5), 1978^50 = -1 (mod 5) 1978 = 3 (mod 25) 1978^4 = 81 = 16 (mod 25) 1978^20 = (example of binomial expansion in "clear" proof above) (1 + 5 (3 + 5t))^5 = 1 + 5 5 (3+5t) + 10 5^2 (3+5t)^2 + 10 5^3 (3+5t)^3 + 5 5^4 (3+5t)^4 + 5^5 (3+5t)^5 = 1 + 5 5 (3 + 5 t) (mod 125) = 76 (mod 125) QED From: Android Subject: POD 8/26 The set of all positive integers is the union of two disjoint subset {f(1),f(2),...,f(n),...}, {g(1),g(2),...,g(n),...}, where f(1) < f(2) < ... < f(n) < ..., g(1) < g(2) < ... < g(n) < ..., and g(n) = f(f(n))+1 for all n>= 1 Determine f(240) Enjoy, Benjie From: Android Subject: POD P is a point inside a given triangle ABC. D, E, F are the feet of the perpendiculars from P to the lines BC, CA, AB respectively. Find all P for which BC/PD + CA/PE + AB/PF is least. Enjoy, Benjie From: erickw@sfu.ca Subject: Re: Conference Sorry I took so long, I started replying and almost forgot to continue later... Most of this post was written about 10 days ago, on the second day of the conference. The following two days were not very exciting...The fifth and last day was not bad...There were a few good number theory lectures (and a few very bad ones :-), and one in particular about "Continued fractions, Chebyshev polynomials, and Chaos" was pretty good, but I don't remember enough about it to summarize. (Thankfully they were in a different room! :-) >If you don't mind, I'd love to hear about the combinatorical/graph theoretical >talks given. I believe the conjecture you mentioned is the Egyptian fraction >conjecture... Okay, here's a summary of Donald Snow's talk on a slick way of getting the formulas for the sums of the kth powers of the first n numbers. It's the only combinatorics/graph theory seminar I've attended in full...There were several people who didn't show up...Including Erdos, who was scheduled to give a talk on two problems in memory of E.G. Straus (who is, if I recall correctly, singlehandedly responsible for giving Einstein an Erdos number of 2 :-), but left a waiting crowd disappointed...I couldn't stand the heat of the room (if I ever find out who picked the Biological Sciences building for the number theory talks... ;-), so I left soon after. Come to think of it, I hardly went to any talks at all today...Except for Sir Michael Atiyah's, who continued his series of three lectures by discussing the 3-dimensions case, in particular, knot theory: the Alexander and Jones polynomials, and how they relate to quantum field theory (sorry, don't remember enough to comment). Oh right, back to the combinatorics talk...He started out by handing out a sheet of paper to each person attending: A SLICK NEW WAY OF GETTING THE SUMS OF THE POWERS FORMULAS We are looking for the closed-form polynomial formulas for S_0(n) = 1^0 + 2^0 + ... + n^0 = n S_1(n) = 1^1 + 2^1 + ... + n^1 = n/2 + n^2/2 S_i(n) = 1^i + 2^i + ... + n^i = ? Then came the "magic formula": Make the following table of the coefficients: n n^2 n^3 n^4 n^5 n^6 n^7 S_0(n) 1 S_1(n) 1/2 1/2 S_2(n) 1/6 1/2 1/3 S_3(n) S_4(n) S_5(n) S_6(n) To get the next row, we use the following procedure. First, to get the entry diagonally down and to the right of one that you already have, multiply the previous one by the new row number, and divide by the new column number. In other words, C(i,j) = i/j C(i-1,j-1). Then, since S_i(1) = 1, we get the n coefficient by noting that the sum of the coefficients along a row must be 1. Try it out, and see that it works! (He said that if you got bored during the lecture you could fill out the rest of the table ;-). Of course, we want to know *why* it works. The above procedure can be more succinctly expressed by the following differential recurence relation: S'_i(x) = i S_{i-1}(x) + b_i, S_i(0) = 0 and S_i(1), for all i>=1. So, we just have to prove this relation (by the way, the b_i's stand for "almost-Bernoulli numbers": they agree except for a 1/2 instead of -1/2 :-). We begin by a simple expansion of S_i(x+y): S_i(x+y) = S_i(y) + \sum_{j=1}^{x} (y+j)^i = S_i(y) + \sum_{j=1}^{x} \sum_{k=0}^{i} C(i,k) y^k j^(i-k) = S_i(y) + \sum_{k=0}^{i} C(i,k) y^k \sum_{j=1}^{x} j^(i-k) = S_i(y) + \sum_{k=0}^{i} C(i,k) y^k S_{i-k}(x). Now partial both sides with respect to y: S'_i(x+y) = S'_i(y) + \sum_{k=1}^{i} k C(i,k) y^{k-1} S_{i-k}(x), and set y to 0...All the terms drop out except for k=1, leaving: S'_i(y) = S'_i(0) + C(i,1) S_{i-1}(x) = i S_{i-1}(x) + S'_i(0). And there you have it! He also showed how to generalize this to \sum_{j=1}^{n} (ax+b+j)^i, i.e. sums of ith powers of arbitrary arithmetic progressions, and stated that you can with a minor change you can get the Euler polynomials, and a whole bunch of other ones which I don't recall :-). -- Erick From: Android Subject: SPOILER -- POD 8/26 -- Summary SPOILER Problem: The set of all positive integers is the union of two disjoint subset {f(1),f(2),...,f(n),...}, {g(1),g(2),...,g(n),...}, where f(1) < f(2) < ... < f(n) < ..., g(1) < g(2) < ... < g(n) < ..., and g(n) = f(f(n))+1 for all n>= 1 Determine f(240) Solutions: f(240) = 388 (oh, you want a proof) Let G be the golden ratio, (sqrt(5)+1)/2 Claim: f(n) = [G n] (integer part) g(n) = [G^2 n] As 1/G + 1/G^2 = 1, these sequences are known to partition the integers. To verify g(n)=f(f(n))+1 Write G n = m + a (m an integer, 0 < a < 1) f(n) = [G n] = m G^2 n = (G + 1) n = G n + n = n + m + a g(n) = [G^2 n] = n + m Hence, we need to prove that. But, m = G n - a, so G m = G^2 n - G a = G n + n - G a = n + m + a - G a = n + m - a/G So f(f(n))= f(m) = [G m] = n + m - 1 An incomplete solution follows: THEOREM: Let x,y be any two irrational positive numbers satisfying 1/x + 1/y = 1. Then the two sequences x, 2x, 3x, 4x, . . . y, 2y, 3y, 4y, . . . together contain exactly one number between N and N+1, for each positive integer N. PROOF: The number of multiples of x which lie below N is [N/x], and the number of multiples of y which lie below N is [N/y]. Altogether then there are [N/x] + [N/y] terms of our sequences which lie between 1 and N. Since N/x and N/y are not integers, we have N/x - 1 < [N/x] < N/x and N/y - 1 < [N/y] < N/y. Adding the inequalities gives N/x + N/y - 2 < [N/x] + [N/y] < N/x + N/y. Since 1/x + 1/y = 1, N-2 < [N/x] + [N/y] < N. Therefore, [N/x] + [N/y] = N-1. So, there are N-1 terms of the sequences lying between 1 and N. Similarly, there are N terms lying between 1 and N+1. Thus, exactly one term lies between N and N+1. (This proof is in Essay 12 of the book "Ingenuity in Mathematics" by Ross Honsberger.) Now to solve the problem. Let x = (1 + sqrt(5))/2 and y = (3 + sqrt(5))/2. You can check that x is irrational and 1/x + 1/y = 1. Define f(n) = [nx] and g(n) = [ny]. By the previous result, {f(n)} and {g(n)} are disjoint sets whose union is the natural numbers. It remains to prove that g(n) = f(f(n)) + 1 for all n, and that f and g are unique. f(f(n)) = [[nx]x] = [(nx-r)x] for some 0 < r < 1 = [nx^2 - rx] = [nx + n - rx] (since x^2 = x + 1) = n + [nx - rx] = n + [[nx] + r - rx] = n + [nx] + [r(1-x)]. Now, -1 = [1-x] <= [r(1-x)] < 0, so [r(1-x)] = -1. Therefore, f(f(n)) + 1 = n + [nx] = [nx+n] = [n(x+1)] = [ny] = g(n) . I haven't found a proof of uniqueness yet. Assuming that f is unique, f(240) = 388. From: kubo@math.harvard.edu (Tal Kubo) Subject: Re: SPOILER -- POD 8/26 -- Summary The problem becomes simpler if we shift coordinates by 1, i.e. consider F(n)=f(n+1)-1, G(n)=g(n+1)-1 which partition the non-negative integers and satisfy G(n)=F(F(n))+1. F(n) and G(n) can be described in terms of Fibonacci numbers: F(n): write n as a sum of Fibonacci numbers Fib(i) using the greedy algorithm. Then replace each Fib(i) by Fib(i+1) G(n): same, but replace each Fib(i) by Fib(i+2) and add 1 e.g. f(n)=1 + F(n-1) f(240)=1 + F(239) 1 + F(233 + 5 + 1) = 1 + 377 + 8 + 2 =388 Clearly this satisfies G(n)=F(F(n)+1. F,G partition the non-negative integers according to whether or not the Fibonacci expansion ends in 1. As a bonus we get an extra functional equation F(F(n))=F(n)+n from which it follows that G(n)=F(n)+n and the same for f,g: g(n)=f(n)+n. This can be seen without the Fibonacci stuff: from the given equation g(n)=f(f(n))+1, we see that among {1,...,g(n)} there are exactly n values of g and f(n) values of f, so that n + f(n)=g(n). From: Android Subject: POD The function f(x,y) satisfies (1) f(0,y) = y+1 (2) f(x+1,0) = f(x,1) (3) f(x+1,y+1) = f(x,f(x+1,y)) for all non-negative integers x, y. Determine f(4,1981). Enjoy, Benjie From: Android Subject: Function Problem The function f(n) is defined for all positive integers n and takes on non-negative integer values. Also, for all m,n f(m+n)-f(m)-f(n)=0 or 1 f(2)=0, f(3)>0, and f(9999)=3333. Determine f(1982) Benjie From: a_rubin@dsg4.dse.beckman.com (arthur rubin) Subject: Function problem (SPOILER) ------------------------------------------------------------------ FORWARDED MAIL FOLLOWS: ------------------------------------------------------------------ From: a_rubin (arthur rubin) Subject: Re: Function Problem (SPOILER) Cc: iams@quack.kfu.edu Monday, August 30, 1993 4:15:25 pm (PDT) The function f(n) is defined for all positive integers n and takes on non-negative integer values. Also, for all m,n f(m+n)-f(m)-f(n)=0 or 1 f(2)=0, f(3)>0, and f(9999)=3333. Determine f(1982) SPOILER Let eps_i denote numbers always known to be 0 or 1. f(2 x 3)=2f(3)+eps_2 f(3 x 3)=f(2 x 3)+f(3)+eps_3 From: a_rubin@dsg4.dse.beckman.com (arthur rubin) Subject: Function problem (SPOILER -- retry) The function f(n) is defined for all positive integers n and takes on non-negative integer values. Also, for all m,n f(m+n)-f(m)-f(n)=0 or 1 f(2)=0, f(3)>0, and f(9999)=3333. Determine f(1982) SPOILER Let eps_i denote numbers always known to be 0 or 1. f(2 x 3)=2f(3)+eps_2 f(3 x 3)=f(2 x 3)+f(3)+eps_3 . . . f(3333 x 3)=f(3332 x 3)+f(n)+eps_3333 Accumulating, f(9999)=3333f(3)+eps_2+eps_3+...+eps_3333 so f(3)=1; and eps_2 = eps_3 = ... = eps_3333 = 0, so f(3n)=n for 1<=n<=3333. (As an aside, f(2)=0 now follows from: f(4)=2f(2)+eps_A f(6)=f(2)+f(4)+eps_B, so 2=f(6)=3f(2)+eps_A+eps_B, hence f(2)=0, eps_A = eps_B = 1) f(1982)=f(1980)+f(2)+eps_1 = 660+0+eps_1 = 660+eps_1 f(3964)=2f(1982)+eps_a = 1320+2eps_1 + eps_a f(5946)=f(1982)+f(3964)+eps_b= 1980+3eps_1+eps_a+eps_b, but f(5946)=1982, so eps_1=0 and f(1982)=660 From: Android Subject: SPOILER -- Solution to POD 8/30 SPOILER Follows Problem: The function f(x,y) satisfies (1) f(0,y) = y+1 (2) f(x+1,0) = f(x,1) (3) f(x+1,y+1) = f(x,f(x+1,y)) for all non-negative integers x, y. Determine f(4,1981). Answer: Real Big (see below) Solution: f(1,0)=f(0,1)=2 f(1,y+1)=f(0,f(1,y))=f(1,y)+1, so f(1,y) = y+2 f(2,0)=f(1,1)=3 f(2,y+1)=f(1,f(2,y))=f(2,y)+2, so f(2,y) = 2y+3 f(3,0)=f(2,1)=5 f(3,y+1)=f(2,f(3,y))=2f(3,y)+3, so f(3,y) = 2^(y+3)-3 f(4,0)=f(3,1)=13 f(4,y+1)=f(3,f(4,y))=2^(y+3)-3, so f(4,y) = 2^2^....^2^2^2 - 3 -------------- y+3 2's Hence, f(4,1981) = 2^2^...^2^2 - 3 ----------- 1984 2's From: Android Subject: POD Factor the number 5^1985 - 1 into a product of three integers, each of which is larger than 5^100. Enjoy, Benjie , From: Android Subject: POD A closed convex set F lies inside a circle with center O. The angle subtended by F from every point of the circle is 90 degree. Prove that O is a center of symmetry of F. Enjoy, Benjie From: Android Subject: SPOILER -- Solution to yesterday's POD SPOILER We first consider the factorization x^5 - 1 = (x-1)(x^4 + x^3 + x^2 + x + 1), where x=5^397. x^4 + x^3 + x^2 + x + 1 = (x^2 + 3x + 1)^2 - 5x(x+1)^2. Since x = 5^397, the right side of above equation is the difference of two squares and can be factored. Rest should follows easilly. Benjie From: Android Subject: POD Find the max value of S=sin^2(theta1) + sin^2(theta2) + ... + sin^2(thetan) subject to the restrictions 0<= thetai <= pi, the sum of thetas = pi. Benjie From: Android Subject: Taking logs many times I just made this problem up. Let's assume you take log of x n times, and you get a real number. You take the log of this number again, the result is DNE. Can you express n in relation with x? Just a thought, Enjoy, Benjie From: a_rubin@dsg4.dse.beckman.com (arthur rubin) Subject: POD 8/30 (SPOILER) and new problem The function f(x,y) satisfies (1) f(0,y) = y+1 (2) f(x+1,0) = f(x,1) (3) f(x+1,y+1) = f(x,f(x+1,y)) for all non-negative integers x, y. Determine f(4,1981). New problem: What are its last 5 digits? New problem to which I have no solution; what is its first digit. SPOILER to original problem f(4,1981) = 2^2^...^2^2 - 3 ----------- 1984 2's From: Android Subject: PODs This should be easy. It's one of the POWS for an algebra class in my school. Find all x,y,z such that x+y=2 xy-z^2=1 Not tricky, straight forward algebra. Benjie From: Android Subject: Sequence I have sequence for all you math wiz, 1 11 21 1211 1231 131221 132231 What's the next term and what's the pattern? Benjie From: Android Subject: SPOILER -- POD 9/2 -- Summary SPOILER Follows Problem: Find the max value of S=sin^2(theta1) + sin^2(theta2) + ... + sin^2(thetan) subject to the restrictions 0<= thetai <= pi, the sum of thetas = pi. Solutions: answer: n=1, S=0, theta1 = pi n=2, S=2, theta1 = theta2 = pi/2 n>=3, S=9/4, theta1=theta2=theta3=pi/3, all others 0, and symmetric configurations Let g(x) = (d/dx) sin^2(x) = 2 sin(x) cos(x) = sin(2x) By standard calculus arguments, for all i, g(theta_i) = C or theta_i = 0. If C < 0, then all thetas are either 0 or strictly between pi/2 and pi, so cannot some to pi. If C = 0, all thetas are 0, pi/2, or pi, and we have: n>=1 theta1 = pi; S=0 n>=2 theta1=theta2=pi/2; S=2 If C = 1, all thetas are 0 or pi/4, and we have: n>=4 theta1=theta2=theta3=theta4; S = 4 sin^2(pi/4)=4 (1/sqrt(2))^2 = 2 If 0 < C < 1, writing phi = 1/2 arcsin(C) (< pi/4) , all thetas are 0, phi, or psi=pi/2-phi. Now, consider the operation of replacing (theta, theta') by (0, theta+theta') among the theta. sin^2(theta+theta') = (sin(theta)cos(theta')+cos(theta)sin(theta'))^2 = sin^2(theta)cos^2(theta')+cos^2(theta)sin^2(theta') + 2 sin(theta)cos(theta)sin(theta')cos(theta') = sin^2(theta) + sin^2(theta)(cos^2(theta')-1) + sin^2(theta') + sin^2(theta')(cos^2(theta)-1) + 2 sin(theta)cos(theta)sin(theta')cos(theta') = sin^2(theta) - sin^2(theta)sin^2(theta') + sin^2(theta') - sin^2(theta')sin^2(theta) + 2 sin(theta)cos(theta)sin(theta')cos(theta') = sin^2(theta) + sin^2(theta') + 2 sin(theta)cos(theta)sin(theta')cos(theta') - 2 sin^2(theta)sin^2(theta') = sin^2(theta) + sin^2(theta') + 2 sin(theta)sin(theta') (cos(theta)cos(theta')-sin(theta)sin(theta') ) = sin^2(theta) + sin^2(theta') + 2sin(theta)sin(theta')cos(theta+theta'), so this operation offers an improvement (or no change) if 0<=theta,theta' and theta+theta'<=pi/2. Hence, if there are two phi's we could combine them for an increase in S. If there is a phi and and psi, we can combine them for no change. If there is only one phi, and no psi's, the sum condition cannot hold. Hence there are no phi's and (as pi/4 < psi < pi/2) 3 psi's and we have: n >= 3, theta1=theta2=theta3=pi/3, S = 3 sin^2(pi/3) = 3 (sqrt(3)/2)^2=9/4 First assume that n > 3. If one takes dS/d(theta_i) = 0, one gets sum{i=1,n} sin(2thetha_i) = 0, and the constraint is satisfied if theta_1 = theta_2 = pi/2 and theta_3 = ... = theta_n = 0. This gives S = 2, which I think is the best that can be done with n > 3. For n = 1, theta_1 = pi, and S = 0. For n = 2, theta_1 = theta_2 = pi/2, and S = 2. The only exception is n = 3. Consider what happens if we let theta_i = pi/n. For large n, sin(pi/n) --> pi/n, and we get S -->(pi)^2/n < 2, but for n = 3 only, S = 3 sin^2(pi/3) = 9/4 > 2. For n = 4, both methods give S = 2, and for n > 4, the best we can do is use the method above to get S = 2. From: Van@cup.portal.com Subject: RE: Spoiler POD 9/2 Problem: Find the max value of S=sin^2(theta1) + sin^2(theta2) + ... + sin^2(thetan) subject to the restrictions 0<= thetai <= pi, the sum of thetas = pi. RE: SPOILER The soln given by a_rubin@dsg4.dse.beckman.com is obviously correct. I should have seen that the thing to do is to extend the soln for n= 3 to all n > 3: > n>=3, S=9/4, theta1=theta2=theta3=pi/3, all others 0, and symmetric > configurations. I failed to extend this to n > 3 in the obvious way. van@cup.portal.com From: David G Radcliffe Subject: Last digits of f(4,1981) (SPOILER) Arthur Rubin asked for the last 5 digits of f(4,1981), which was defined in POD 8/30. Solution below: Let x(1) = 2 and x(n) = 2^x(n-1) for n > 1. It has been shown that f(4,1981) = x(1984)-3. I will show that x(n) = 48736 mod 100000 for all n > 6, thus the last five digits of f(4,1981) are 48733. We need to apply Euler's theorem, which states that a^phi(n) = 1 mod n when gcd(a,n)=1. Recall that phi(n) is the number of integers k such that 0 < k < n and gcd(k,n) = 1. Now phi(5^(n+1)) = 4*5^n, so if x = y mod 4*5^n, then 2^x = 2^y mod 5^(n+1). Suppose that n > 0, x = y mod 10^n, x = y mod 4, and 2^n divides x. Then x = y mod 5^n, so x = y mod 4*5^n. Consequently, 2^x = 2^y mod 5^(n+1). But 2^x = 2^y = 0 mod 2^(n+1), so 2^x = 2^y mod 10^(n+1). Let n >= 0. Then x(n+2) = 0 mod 4, so x(n+3) = 1 mod 5 by Euler's Theorem. Since x(n+3) is even, x(n+3) = 16 mod 10. We now apply the previous result repeatedly: x(n+4) = 2^16 mod 100 = 36 mod 100 x(n+5) = 2^36 mod 1000 = 736 mod 1000 x(n+6) = 2^736 mod 10000 = 8736 mod 10000 x(n+7) = 2^8736 mod 100000 = 48736 mod 100000 Therefore, x(n) = 48736 mod 100000 for all n > 6. These calculations can be done quite rapidly on a computer. For instance, the last 20 digits of x(n) for n > 21 are 98615075353432948736. It occurs to me that one could repeat this process indefinitely, and get an infinite "number" x = ....48736 such that 2^x = x. We could think of x as a 10-adic number, I guess, but I am not sure if 2^x is meaningful in this context. Is there a natural way to define b^x, where x is a p-adic number, and is it useful to do so? Dave Radcliffe From: David G Radcliffe Subject: yet another problem I got this problem in my email: > Prove or disprove: > Let G be an abelian group of order n and choose any n > elements from G with repetitions allowed. Let S denote this > multiset. > Then there is sub- multiset T of S such that the sum of the > elements of T equals zero. Here is a special case of this conjecture: Let S be a set of n integers. Then there is a nonempty subset T of S such that the sum of the elements of T is divisible by n. From: Chris Long Subject: Solution Let the n elements be x_i, 1<=i<=n. Consider the n sums S_i = { x_1 + ... + x_i }; if S_i=0 for some i we are done. If not, by the Pigeonhole Principle we must have S_i=S_j for some i Subject: Yet another problem -- SOLUTIONS > > Let G be an abelian group of order n and choose any n > > elements from G with repetitions allowed. Let S denote this > > multiset. > > Then there is sub- multiset T of S such that the sum of the > > elements of T equals zero. I got two solutions by email: ------------------------------------ Actually you do not need to asume that G is abelian to do it. Here is my solution. SPOILER: Arrange S as a sequence a_1,...,a_n. Now consider the sequence a_1, a_1a_2, ..., a_1a_2...a_n. If the identity e appears in that sequence then we are done. Otherwise by the pidgeonhole principle there exist i and j different with i ----------------------------------------------------- This theorem holds for all groups (non-abelian and abelian). I'll use additive notation anyway. Let f(1),...,f(n) be elements of the group. Consider: f(1) f(1)+f(2) ... (f(1)+...+f(n) If all above sums are different then all elements of the group appear among them, in particular 0. If the sum of k and of m>k terms are equal then f(k+1)+...+f(m) = 0. That's it, qed. Wlodek (Wlodzimierz Holsztynski) From: Android Subject: Spoiler -- Sequence Problem SPOLER SPOILER From: Heiner Marxen > 1 11 21 1211 1231 131221 132231 > What's the next term and what's the pattern? Next term is 232221 Pattern is: In the previous term count the occurrences of each digit, sort them by decreasing digit value, and concatenate the (non-zero) counts and the counted digit. I.e 232221 stands for "two 3s, two 2s and two 1s". From: Android Subject: SPOILER -- Solution to PODs -- Summary SPOILER Problem: find x and y such that 1000 = 47 x + 19 y 1000 = 47 x + 19 y 1000 = 50 = -7 (mod 19) 47 = 9 = -1/2 (mod 19) Hence x = 14 is acceptable. 1000 - 14 x 47 = 1000 - 658 = 342; y = 18 2 minutes 33 seconds; no calculator or computer used. 47a + 19b = 1000 9a == 12 (mod 19) 18a == 24 (mod 19) -a == 5 (mod 19) a == -5 (mod 19) a == 14 (mod 19) Let a = 14. Then b = 18. All in under 2 minutes. From: Android Subject: P.O.D. I don't know if I had this problem up here before or not, but it's an interesting one. Let say you have a circle. And let say you have a point outside the circle. Let say that you know one diameter of the circle, and you extended the diameter so that it runs below the exterior point (the key word is BELOW). Use only straight edge, construct a perpendicular line from that point to the extent of the diameter. Enjoy, Benjie From: Abraham S. Mantell Subject: Continued Fraction Hello, Does anyone have any ideas on how to determine the EXACT value of: 1 ------------------------------------------------ 2 + 1 ---------------------------------------- 4 + 1 -------------- 8 + 1 -------- 16 + . . . (it is approx. = 0.445934640512) Any suggestions will be greatly appreciated!! Thanks in advance!! Abe mantell@rpi.edu From: Android Subject: P.O.D. This is one of the five problems of this year's first round USAMTS questions. The problems are due Sept.13th, I sent them out today. They are all interesting, I will post them one by one. Question 2: A point P and two straight line segments are given on a rectangular piece of paper in such a way that the intersection point Q of the straight lines does not lie on the paper. How can we construct the straight line PQ with the help of a straight edge if we are allowed to draw only within the limits of the paper? Enjoy, Benjie From: Android Subject: SPOILER -- Construction Problem -- Summary SPOILER > Let say you have a circle. And let say you have a point outside the > circle. Let say that you know one diameter of the circle, and you > extended the diameter so that it runs below the exterior point (the > key word is BELOW). Use only straight edge, construct a perpendicular > line from that point to the extent of the diameter. This is beautiful! Let the diameter be AB, and the exterior point C, with C closer to B. Construct line AC, and let D be the point where it intersects the circle. Construct line CB, and extend it until it crosses the circle again at a point E. Construct lines AE and DB, and extend them so that they intersect at a point F. Finally, construct line CF, and let G be the point where CF and AB intersect. I claim that AB and CF are perpendicular. Why? Since AB is a diameter, angles ADB and AEB are right angles. Consequently, CE and FD are altitudes of the triangle ACF. It is well known that the three altitudes of a triangle are concurrent. Therefore, AG is also an altitude of the triangle ACF, hence AB is perpendicular to CF. From: Android Subject: Problem of the Day Problem 4 from the first round USAMTS A triangle is called Heronian if its sides and area are integers. Determine all five Heronian triangles whose perimeter is numerically the same as its area. Again, the first round of USAMTS was due Sept. 13. Any HS student interested should send a email to BERZSENY@CMA.ROSE-HULMAN.EDU for more info. Enjoy, Benjie From: Android Subject: Combinatoric Problem A 2x2x12 hole in a wall is to be filled with 24 1x1x2 bricks. In how many different ways can this be done if the bricks are indistinguishable? Happy mathing, Benjie From: Android Subject: Contest Problems I want to start contest 3. But I need a collection of problems. Therefore, I am making a CFCP (call for contest problems). Please submit (send to me) any interesting problems, hopefully with solutions. Benjie From: Android Subject: SPOILER SPOILER Problem: A 2x2x12 hole in a wall is to be filled with 24 1x1x2 bricks. In how many different ways can this be done if the bricks are indistinguishable? From: a_rubin@dsg4.dse.beckman.com Let a_n be the number of ways of filling a 2x2xn hole with 1x1x2 bricks. Let b_{n+1} be the number of ways of filling a 2x2xn hole with a 1x2x1 distiguished brick alreadyh placed on an end. Clearly, by considering the posible placement of bricks on the distiguished end, a_n = 2 a_{n-1} + a_{n-2} + 4 b_{n-1} b_n = a_{n-1} + b_{n-1} a_0 = 1, a_{-1} = 0, b_0 = 0 Formal solution produces: a_n = ( (2+sqrt(3))^(n+1) + (2-sqrt(3))^(n+1)) / 6 + (-1)^n / 3 = nearest integer to ((2+sqrt(3))^(n+1)/6 Using this, or evaluating the individual terms, we get: a_12 = 4,541,161 From: Android Subject: P.O.D. An m x n grid is placed so that it has it's corners at (0,0) and (m,n). A legal move is defined as a move either one unit in the positive y direction or one unit in the positive x direction. The point (i,j), where 0<= i <= m and 0<= j <= n, and (i,j) differs from (0,0) and (m,n), is removed from the grid so that it is no longer possible to pass through this point. How many possible paths are there from (0,0) to (m,n)? Enjoy, Benjie From: ramana@mgv01.svl.cdc.com Subject: Power of 2 Prove (or disprove): There exists a power of 2 whose decimal expansion starts with any given string of digits. --- ramana@svl.cdc.com --- From: Android Subject: SPOILER -- Summary -- Decimal expansion problem SPOILER Question: Prove (or disprove) that there exists a power of 2 whose decimal expansion begins with any arbitrary set of digits. Notation: l2 is log base 2. Proof: Let S be the arbitrary initial set of digits. The question is equivalent to proving that there exists n such that S * 10^a <= 2^n < (S+1) * 10^a Equivalently, l2(S) + a l2(10) <= n < l2(S+1) + a l2(10) Equivalently, l2(S) <= n - a l2(10) < l2(S+1) At this point, we note that l2(10) is an irrational number, so we can approximate any real as n - a l2(10) with an appropriate choice of integral n and a. Therefore, we can always find n and a to satisfy this equation. QED From: Android Subject: SPOILER -- Summary -- Moves in Grid Problem SPOILER An m x n grid is placed so that it has it's corners at (0,0) and (m,n). A legal move is defined as a move either one unit in the positive y direction or one unit in the positive x direction. The point (i,j), where 0<= i <= m and 0<= j <= n, and (i,j) differs from (0,0) and (m,n), is removed from the grid so that it is no longer possible to pass through this point. How many possible paths are there from (0,0) to (m,n)? The answer is /m+n\ /i+j\ /m+n-i-j\ | | - | | | | \ m / \ i / \ m-i / where the strange looking thing is the binomial coefficient. Why. The total number of paths is the number of ways of choosing m 'ups' out of m+n 'ups or rights.' The number passing through (i,j) is the number going from (0,0) to (i,j) times the number going from (i,j) to (m,n). The same argument shows why these two magnitudes are the binomial coefficients shown above. Herbert Gintis Represent a move to the right as a binary '1', and a move up as a binary '0, so a move is simply a binary string. Then, the number of paths from (0,0) to any point (p,q) is simply the number of p+q bit binary strings with exactly p 1's. Thus, there are C(p+q,p) paths from the origin to (p,q). Thus, there are C(m+n,m) paths from the origin to (m,n) (including those going through (i,j)). Now consider all the paths from the origin to (m,n) which go through (i,j). Each path can be decomposed into two paths - one from the origin to (i,j), and one from (i,j) to (m,n). There are C(i+j,i) paths from the origin to (i,j) and C(m+n-i-j,n-i) paths from (i,j) to (m,n). Thus, there are a total of C(i+j,i) * C(m+n-i-j,n-i) paths from the origin to (m,n) going through (i,j). Thus, there are: C(m+n,m) - C(m+n-i-j,n-i) * C(i+j,i) paths from the origin to (m,n) not going through (i,j). I didn't try to simplify this. From: Android Subject: SOILER -- An other solution to the hole in the wall problem SPOILER A 2x2x12 hole in a wall is to be filled with 24 1x1x2 bricks. In how many different ways can this be done if the bricks are indistinguishable? Without factoring out any symmetry: 4541161 I have done this computationally, without any theoretic thought. With a bit symmetry reduction and subproblem caching this is no problem for 2x2xN while N<=20. E.g. 2x2x20: 170902040409 Nevertheless I would prefer larger problem instances, forcing me to solve the problem sybolically rather than numerically. From: Android Subject: P.O.D. Problem: A Convex polygon has 1993 vertices which are colored so that neighboring vertices are of different colors. Prove that one can divide the polygon into triangles with non-intersecting diagnoals whose endpoints are of different color. Enjoy, I lost track of David Wagner, he is lost somewhere? Any one know somethings tht I don't know about Dave? Is he on vacation? I haven't got an answer for the line construction problem yet. I and a couple friends of mine are very eager to see if somebody could solve that. The problem is: construct a line from P to Q if P is a point on a paper, and Q is a point outside of the paper that is also the intersection point of two line segment in the paper. You could only use straight edges. Happy mathing, Benjie From: TKIDD@CLEMSON.CLEMSON.EDU Subject: SPOILER--Heronian triangles ---------------------------- Text of forwarded message ----------------------- a BSMTP) (UCLA/Mail V1.423 M-SMTP-0532-43); Fri, 17 Sep 93 10:25:47 EDT with TCP; Fri, 17 Sep 93 10:25:40 EDT From: crharmo@HUBCAP.CLEMSON.EDU(C. Reid Harmon Jr.) Subject: Triangles Cc: >A Heronian triangle is a triangle whose area and sides are all >integers. Find all 5 Heronian triangles whose area is numerically >the same as its perimeter. > >-Travis Hmm. Well, p = a + b + c, and area = 1/2 ab sin C, and sin C = sqrt(1-(cos C)^2), and cos C = (a^2+b^2-c^2)/2ab, so area^2 = 1/16 (4 a^2 b^2 - (a^2 + b^2 - c^2)^2) p^2 = (a + b + c)^2 a, b, c > 0, so area > 0 and p > 0, so for all solutions area^2 = p^2, then area = p. So set area^2 = p^2, and by inspection: (6,8,10): 24 (5,12,13): 30 (9,10,17): 36 (7,15,20): 42 (6,25,29): 60 -- C. Reid Harmon Jr. crharmo@hubcap.clemson.edu "If it's not Love, then it's the Bomb which will bring us together." From: "mfriedma.US1" Subject: Re: SPOILER--Heronian triangles Whoa. That last step - the by inspection piece - isn't it a bit tough to do by inspection unless you are some kind of idiot savant or use a computer? If there is an easy way to find these solutions can we get an explanation? Thanks Mike ---- Included Message ---- From: WRPYR:iams-request@quack.kfu.com Subject: SPOILER--Heronian triangles ---------------------------- Text of forwarded message ----------------------- a BSMTP) (UCLA/Mail V1.423 M-SMTP-0532-43); Fri, 17 Sep 93 10:25:47 EDT with TCP; Fri, 17 Sep 93 10:25:40 EDT From: crharmo@HUBCAP.CLEMSON.EDU(C. Reid Harmon Jr.) Subject: Triangles Cc: >A Heronian triangle is a triangle whose area and sides are all >integers. Find all 5 Heronian triangles whose area is numerically >the same as its perimeter. > >-Travis Hmm. Well, p = a + b + c, and area = 1/2 ab sin C, and sin C = sqrt(1-(cos C)^2), and cos C = (a^2+b^2-c^2)/2ab, so area^2 = 1/16 (4 a^2 b^2 - (a^2 + b^2 - c^2)^2) p^2 = (a + b + c)^2 a, b, c > 0, so area > 0 and p > 0, so for all solutions area^2 = p^2, then area = p. So set area^2 = p^2, and by inspection: (6,8,10): 24 (5,12,13): 30 (9,10,17): 36 (7,15,20): 42 (6,25,29): 60 -- C. Reid Harmon Jr. crharmo@hubcap.clemson.edu "If it's not Love, then it's the Bomb which will bring us together." From: Android Subject: SPOILER -- Polygon Problem -- Summary SPOILER Problem: A Convex polygon has 1993 vertices which are colored so that neighboring vertices are of different colors. Prove that one can divide the polygon into triangles with non-intersecting diagnoals whose endpoints are of different color. From: TavenerS@lilhd.logica.com 1. For any polygon with an odd number of vertices, coloured so neighbouring vertices are different colours, there are at least 3 colours 1 colour, clearly impossible, 2 colour => colours alternate, but can't alternate with odd number of vertices 2. Consider a diagonal with endpoints of different colours, which divides the polygon into a smaller polygon and a triangle, then a) the new polygon has 1 less vertex than the old one b) the new polygon still has no adjacent vertices of the same colour 3. There is at least one vertex with either a) 2 vertices of different colours to both the left AND right or b) 3 vertices of different colours to one side Assume false, then consider a polygon with 2n + 1 (>= 5) vertices and at least one vertex of colour X. Choosing an arbitrary vertex, consider the possible sequences of 7 consecutive vertices, going round clockwise and wrapping round if necessary, we have: X - - X - X - - X - - X - X - X X - X - X - - X X - X - X - X - X - X - - X - X - - X - X - - X - - X - X - X - - X - - X - X - - X - X - - X - - X - X - X - - - X - X - X - X The minimum density of X is 3/8 vertices. Since we have at least 3 colours, this leads to a contradiction, since we have accounted for >= 9/8 of the vertices. triangles using diagonals with end points of different colours polygon has an odd number of vertices, and neighbouring vertices are of different colours. By induction, any convex polygon with an odd number of vertices which are colored so that neighboring vertices are of different colors can be divided into triangles with non-intersecting diagonals whose endpoints are of different color. Since 1993 is odd, the vertices are at least in 3 different colors. Thus let me prove the thesis for arbitrary n-gon (n>=3) colored in at least 3 different colors in such a way that the neighboring vertices are colored differently. (This will cover the case of all n-gons, with odd n>2, with neighbors colored differently). A moment of thought is sufficient to see that there are three consecutive vertices a,b,c which are colored in 3 different colors. Consider also the next vertex d (i.e. let a,b,c,d be consecutive). Then, Case 1. the vertices, with b removed, still use 3 different colors. In this case diagonal ac divides our polygon into 3-