From: Android Subject: Sample Corelation and Linear Algebra I learned this from the Linear Algebra class I am taking, I thought it's interesting. If you have a set of data called X = {x1, x2, ..., xn} and another set Y = {y1, y2, ... yn} which is a result of having X. In other words, Y depends on X. The relation between X and Y, called sample correlation, is denoted by r. Usually, it is being calculated as sum of ((xi - x-mean) * (yi - y-mean)) r = ----------------------------------------------------------- sqrt(sum of (xi - x-mean)^2) sqrt(sum of (yi - y-mean)^2) Where x-mean and y-mean are the averages of the x's and y's. Anyway, if we define D to be (x1 - x-mean, x2 - x-mean, ..., xn - x-mean) and E to be (y1 - y-mean, y2 - y-mean, ..., yn - y-mean), in other words, let D be the deviation vector of x and let E be the deviation vector of y. Then, the sample correlation r is the cosine of the angle between D and E. It's shown easilly if you expand D dot E and derive the formula for cos(t) where t is the angle between D and E. Benjie From: abrahams_d@maths.su.oz.au (Derek Abrahams) _____ \ \ / /____ UMS The Sydney University Mathematical Society would like to contact other undergraduate University Mathematics clubs and societies (especially in Australia) with the main aims of (i) Exchanging magazines/newsletters (ii) Possibly having a joint function later in the year or early next year. The Sydney University Mathematical Society publishes its Journal, (Sigma)UMS + PLUS, (the + is silent) at regular (but not equally spaced) intervals. After a lengthy break from publication at least two issues have been or will be produced this semester. The society may be contacted on email at sums@maths.su.oz.au or by writing to SUMS, c/- School of Mathematics and Statistics, F07, University of Sydney, NSW 2006 Derek Abrahams From: Android Subject: POD Let x1 be sqrt(6), let x2 be sqrt(6+x1), in general, let xn be sqrt(6+x(n-1)). If the limit of xn and x(n+1) equals to L as n approaches infinity, what is L? Benjie From: Android Subject: Misc. Problem Find all integers x and y such that 1/x + 1/y = 1/14 Enjoy, Benjie From: Todd Vance Subject: Solve: 1/x + 1/y = 1/14 (x, y integers) 14x + 14y = xy, so 14x = xy - 14y => y = 14x/(x - 14). Thus, 14|x, or x = 14n. Then, y = (14^2)n/[14(n-1)] = 14 n/(n-1), so n-1 | n, which only happens if n-1 = 1 or -1, i.e. n = 0 or 2. If n=0, x=0, which can't happen. so, n=2, x = 28, and y = 28. From: Wlodzimierz Holsztynski Subject: Solve: 1/x + 1/y = 1/14 (x, y integers) / spoiled spoiler The following message (by Todd) should've been sent, as I understand, to Benjie (address: Android ) or at least marked "SPOILER". But the solution it provides is flawed anyway: ********************************** Begin forwarded message: From: Todd Vance Subject: Solve: 1/x + 1/y = 1/14 (x, y integers) 14x + 14y = xy, so 14x = xy - 14y => y = 14x/(x - 14). Thus, 14|x, or x = 14n. Then, y = (14^2)n/[14(n-1)] = 14 n/(n-1), so n-1 | n, which only happens if n-1 = 1 or -1, i.e. n = 0 or 2. If n=0, x=0, which can't happen. so, n=2, x = 28, and y = 28. ********************************** True: 1/28 + 1/28 = 1/14. But also: 1/14 = 1/7 - 1/14 = 1/12 - 1/84 = 1/13 - 1/182 = 1/10 - 1/35 = 1/21 + 1/42 = 1/16 + 1/112 = 1/15 + 1/210 = 1/18 + 1/63 (I'll check later whether or not these are all solutions. It's fun to chase them without a general machinery. Independently, I have a reduction to a few simple cases. Then I stopped not out of laziness but because I dislike to have several cases. They can be covered by one or two more general considerations. Perhaps others will provide full solution. Or I will, if I don't get lazy :-) Wlodek From: Android Subject: SPOILER -- 1/x + 1/y problem -- Solutions and Followups SPOILER From erickw@sfu.ca 1/x + 1/y = 1/14 (x+y)/xy = 1/14 xy = 14(x+y) (x-14)(y-14) = 196 The above equation is feasible iff x-14 is an integer divisor of 196, and this leads to a solution as long as x is non-zero. Thus there are 17 solutions, 9 of which are distinct (1/x + 1/y = 1/y + 1/x). These are: 1/13 - 1/182 = 1/14 1/12 - 1/84 = 1/14 1/10 - 1/35 = 1/14 1/7 - 1/14 = 1/14 1/15 + 1/210 = 1/14 1/16 + 1/112 = 1/14 1/18 + 1/63 = 1/14 1/21 + 1/42 = 1/14 1/28 + 1/28 = 1/14 From radcliff@csd4.csd.uwm.edu To save typing, I will only give the solutions with x <= y. Multiply both sides of the equation by 14xy, giving 14y + 14x = xy. This equation can be rewritten as (x-14)(y-14) = 196. By writing 196 as a product of two integers in every possible way, we determine that the solutions are (-182,13), (-84,12), (-35,10), (-14,7), (15,210), (16,112), (18,63), (21,42), and (28,28). (Now, how many solutions are there to 1/x + 1/y = 1/40320 ?) From: Android Subject: SPOILER -- Sqrt problem -- summary SPOILER From khare@eng.buffalo.edu Assume x(n) = x(n+1) x(n+1)=x(n)=sqrt(6+x(n)) [square on both sides] x(n)*x(n)=6+x(n) x(n)*x(n)-x(n)-6 = 0 x(n)=3 or x(n) = -2 since sqrt cann't be -ve, x(n) = 3. From luzeaux@etca.fr If L is the limit of (x_n), this limit shoud satisfy: L=sqrt(6+L), i.e. L=3 It is then easy to show that the sequence indeed converges, as the function: x \mapsto sqrt(6+x) is stricty increasing on its domain, therefore x_n < x_{n+1} and for all n, it is obvious that x_n < 3 As a stricty increasing bounded sequence converges, the limit exists, and as we previously saw, this limit then has to be 3. From: Wlodzimierz Holsztynski Subject: Re: SPOILER -- 1/x + 1/y problem -- Sol's ... Begin forwarded message: From: Android Subject: SPOILER -- 1/x + 1/y problem -- Solutions and Followups >From erickw@sfu.ca 1/x + 1/y = 1/14 ... (x-14)(y-14) = 196 ... >From radcliff@csd4.csd.uwm.edu ... This equation can be rewritten as (x-14)(y-14) = 196. ... (Now, how many solutions are there to 1/x + 1/y = 1/40320 ?) =============================================== ==== end of the (fragments of the) forwarded message ====== =========================================================== WARNING. The text below might be considered something of a "spoiler". The above solutions are as simple as the solution which Alex Heneveld has sent me privately (and they are just a tinge more elegant). All three allow an automatic generalization to: [*] 1/x + 1/y = 1/n which in the style of the above two netters, erickw & radcliff, has the same solutions as: (x-n)*(y-n) = n^2 minus the (x,y)=(0,0) solution. Thus the set of solutions of eq. [*] is: { (n+d, n + (n^2)/d) : d|n^2 } --Wlodek PS. to Alex: Alex, I had another silly error in my letter to you, but I didn't want to bother you with another letter :-) From: Wlodzimierz Holsztynski Subject: a generalization of 1/x + 1/y = 1/n Equation 1/x + 1/y = 1/n is essentially equivalent to n*x + n*y = x*y (but for (0,0) solution). Thus equation: a*x + b*y = x*y is more general. In the "ericw & radcliff style", it can be rewritten as: (x-b)*(y-a) = a*b The set of integer solutions is: { (b+t,a+a*b/t) : t|a*b } --Wlodek From: David G Radcliffe Subject: Solve y^2 = x^4 + 3x^3 + 5x^2 + 4 in integers Find all integer solutions to y^2 = x^4 + 3x^3 + 5x^2 + 4 . From: Wlodzimierz Holsztynski Subject: Last remark about 1/x +1/y=1/14 Perhaps the simplest (but not efficient numerically) method of solving eq. 1/x + 1/y = 1/n is to observe that max(1/x,1/y) > or = 1/(2*n). Hence we just compute y for each x=1,...,2n. Whenever y is an integer we get a solution. Then we swap x's and y's to get the symmetric solutions. When n=14 then it's not so bad--one makes 28 computations. For n=9^9^9 this method is not practical. Nevertheless, this is a general solution of 1/x + 1/y = 1/n (for each FIXED n) since it reduces the problem to a definite finite computation (of a priori bounded size). Wlodek From: Torsten Sillke Subject: heron triangles (hint) Heronian Triangles: they have integral sides and area. If you want perimeter = area, see Dickson, Theory of Numbers II, 195-196 let: a = l+m, b = l+n, c = m+n you end with the condition 4(l+m+n) = lmn -------------- the rest is for you. Torsten Sillke From: Wlodzimierz Holsztynski Subject: Re: heron triangles (hint) / Hint? -- ugh! > > > Begin forwarded message: > > From: Torsten Sillke > Subject: heron triangles (hint) References are nice. But, frankly, I don't like posts with hints. Of course, if anyone likes to post them, then sure, go on, there are worst things than hints. > Heronian Triangles: > > they have integral sides and area. > > If you want perimeter = area, see > Dickson, Theory of Numbers II, 195-196 > > let: a = l+m, b = l+n, c = m+n > you end with the condition > > 4(l+m+n) = lmn > -------------- Nice! :-) (It was also nice to have the definition of Heron triangles provided--just one line but how useful! Many of us would enjoy several of the math. articles posted on net if def's & results referenced to, were stated.) > the rest is for you. How generous of you. > Torsten Sillke ********************************************** Some info about Heron triangles and further references are in ""Old & new unsolved problems in Plane Geom. & N.Th." by Victor Klee & Stan Wagon (published by The Math. Asso. of Amer., (c)1991). In particular they mention (p.205, Ex.6) that R.H.Buchholtz & R.L.Rathbun discovered(1987) an example of Heron triangle with two medians of integer length--the lengths of the sides of their triangle are: 52,102,146. It is not known if all three medians of a Heron triangle can be integral (ibidem, p.174,Problem 14.2). J.Leech came up with an example of "Heron tetrahedron" which has all faces Heronian and integral volume (ibidem, p.205, Ex.7). Alex H. mentioned (in a letter to me) the famous diphantine equation 1/x + 1/y + 1/z = 3/A (or was it 4/n or 1/w + 1/x + 1/y + 1/z = 4/A). I hoped to find it in the book by Klee & Wagon but without a success. In past it had solutions for A within the possible computer range. Can anybody post the exact statement (and the state of affairs)? Regards, Wlodek From: Android Subject: POD 9/30 From alex@armstrong.edu Find all solutions in positive integers to: 1/a + 1/b + 1/ab = k From: Wlodzimierz Holsztynski Subject: Solve y^2 = x^4 + 3x^3 + 5x^2 + 4 in integers Hi David, thank you for your nice problem: ************************************* Begin forwarded message: From: David G Radcliffe Subject: Solve y^2 = x^4 + 3x^3 + 5x^2 + 4 in integers Find all integer solutions to y^2 = x^4 + 3x^3 + 5x^2 + 4 . ************************************* Let's rewrite the equation in an equivalent form: y^2 = (x^2)*(x^2 + 3*x + 5) + 4 Of course (x,y) = (2,-8), (0,-2), (-2,-4), (-3,-7) (2,8), (0,2), (-2,4), (-3,7) are all solutions for x = 2, 1, 0,-1,-2,-3,-4. from now on let x > 2 or < -4 Then f = x^2 + 3*x + 5 is strictly between (x+1)^2 and (x+2)^2 --for x > 2 : (x+1)^2 < f < (x+2)^2, and for x < -4 : (x+1)^2 > f > (x+2)^2 -- as seen from: x^2 + 3*x + 5 = (x+1)^2 + (x+4) = (x+2)^2 + (-x+1) Thus f is not a square, i.e. it differs from any square by at least 1. And |x|>2 hence (x^2)*f differs from any square by more then 4. Thus we see that there is no solution of: y^2 = (x^2)*(x^2 + 3*x + 5) + 4 for x<-4 or >2. We have proved: Theorem. For integer x,y: {(x,y) : y^2 = x^4 + 3x^3 + 5x^2 + 4 } = { (2,-8), (0,-2), (-2,-4), (-3,-7) (2,8), (0,2), (-2,4), (-3,7) } Best regards, --Wlodek From: Wlodzimierz Holsztynski Subject: Re: Solve y^2 = x^4 + 3x^3 + 5x^2 + 4 / was redirected! My solution of the problem in the subject line showed up on iams like I sent it there. But these appearances are misleading. I've sent it to Dave, who has posed the problem. I am guessing that he redirected (somehow :-) my letter to iams. I am writing this "disclaimer" in support of Benjie's iams policy of sending the "spoilers" (solutions of "Problems Of the Day" or POD's, to the one who proposes the problem or to Benjie). Regards, Wlodek PS. I am not a hacker hence I am impressed that it's possible for a person X to post an article so that it looks like a person Y did (with X \ne Y) but it's also a little worrisome. From: Android Subject: SPOILER -- Solution to POD SPOILER 9/30 From alex@armstrong.edu Find all solutions in positive integers to: 1/a + 1/b + 1/ab = k From a_rubin@dsg4.dse.beckman.com Solution: Clearly, k<=3 as the left hand side of the original equation is <= 3. k ab = a + b + 1 k^2 a b - k a - k b - k = 0 (ka -1) (kb -1) = k+1 (*) If k=1, we have (a-1)(b-1)=2, or (a,b)=(2,3) If k=2, we have (2a-1)(2b-1)=3, or (a,b)=(1,2) If k=3, we have (3a-1)(3b-1)=4, or (a,b)=(1,1) Hence, (a,b,k)=(2,3,1),(3,2,1),(1,2,2),(2,1,2),or (1,1,3). 1/a+1/b+1/ab = 1/k may be more interesting. Clearly, a and b > k. a similar multiplication produces: ab-ka-kb-k=0 (a-k)(b-k)=k(k+1), so the solutions are: (a,b,k)=(x+z,y+z,z) where xy=z(z+1). where k <= 3 From erickw@sfu.ca WLOG a <= b. First of all, we'll eliminate the a=1 case, where 1 + 2/b = k, so b = 1,2 and k = 3,2. Now, suppose a > 2. Then k <= 1/3 + 1/3 + 1/9 < 1. Therefore the only other solution has a = 2, and 1/2 + 3/2b = k, and since k <= 1/2 + 1/2 + 1/4 < 2, k = 1, and b = 3. Thus the only positive solutions are: (1,1,3) (1,2,2) (2,1,2) (2,3,1) (3,2,1) From: Android Subject: POD 10/2 From: alex@armstrong.edu Solve a/b + b/a + 1/ab = k, for all variables positive integers. From: Android Subject: POD A fair coin is tossed repeatedly until there is a run of an odd number of heads followed by a tail. Determine the expected number of tosses. Benjie From: Wlodzimierz Holsztynski Subject: new? proof of infinitude of primes First let me recall a known thm: gcd(2^n - 1, 2^m - 1) = 2^gcd(n,m) - 1 for arbitrary natural numbers n,m=1,2,... ******************** I have posted the following proof a couple months ago on sci.math under title: ONLY ONE PROOF OF INFINITUDE OF PRIMES based on the magic of 2. Let P be a finite collection of primes which includes 2. Let M be the Mersenne numbers corresponding to P, i.e. members of M are M(p)=2^p-1, where p runs over P. The members of M are pairwise relatively prime hence each has its own odd prime divisor. We got one more odd prime than in P. PS. Is this proof known? *********************** Here is a variation: Lemma. No Fermat prime p = 2^2^a + 1 divides a Mersenne number M(q) = 2^q - 1 for any odd q. Proof. Let p = 2^b + 1, where b=2^a. Then 2^b = -1 mod p. Suppose that also 2^k = 1 mod p. Then 2^(u*k + w*b) = (-1)^w mod p for arbitrary integers u,w, hence 2^gcd(k,b) = 1 or -1 mod p But 1 < 2^gcd(k,b) \le 2^b = p-1 hence gcd(k,b) = b is the only possibility, i.e. b divides k. Then obviously k/b is even, hence 2*b | k. This shows that p cannot divide M(q) when q is assumed odd. QED THEOREM (Euclid) There are infinitely many primes. PROOF. Let P be any finite collection of odd primes, which includes at least one Fermat prime (e.g.3). Let M = { 2^q -1 : q \in P } be the corresponding set of Mersenne numbers. Members of M are relatively prime and each has at least one prime divisor. None of these divisors is a Fermat prime, and there are at least |M| = |P| of them. Thus at least one of them does not belong to P. This shows that no finite collection of primes includes all primes. QED. Remark. When one looks for primes of the form 2^n-1 then one quickly forms the necessary condition about n being prime. And for the primes 2^n+1 that n must be a power of 2. In this sense Mersenne primes and Fermat primes seem to be on the opposite ends of a spectrum of a set of primes. From: Wlodzimierz Holsztynski Subject: Re: new? proof of infinitude of primes I forgot to add that I am truly curious whether or not my proofs which I have presented to you in my previous posting are new. It's very unlikely. But if you have any reference then please let me know (either write straight to iams or to me and I'll repost the gathered info). I mentioned that I posted the first (and cuter) proof on sci.math. I got no response from there so far. However, I am cut off netnews already 2 weeks (a bummer). Otherwise I'd try now sci.math.research too. Wlodek (Wlodzimierz Holsztynski) From: Wlodzimierz Holsztynski Subject: new? proof...primes / Summary I got several responses to my question "new? proof of infinitude of primes". Before I sent my article to iams I got a response from a serious number theoretist/algebraist. My proof was new to him but he'll keep asking and looking around. Like myself, he was intrigued by the way 2 "pumps" new primes. Let me say that both the old Euclid's proof and the one (by Erdos?) based on relative primality of Fermat numbers are simpler. I'll present the later one below, at the end of this posting. =============================================================== Steve Wildstrom guesses: Probably the reason you got no response on sci.math is that the title of your post made readers think it was related to the prattlings of Ludwig Plutonium... It was! :-) For those who don't know, Ludwig Plutonium is a harmless crank except that he is the greatest byte-spitter on sci.math. He claimed to have several solutions to the most famous problems (Riemann Conjecture, Fermat Thm, twin primes, perfect numbers, Poincare Conjecture,... you name it). I was impressed with the people, our Ben Tilly among them, who seriously were pointing to the numerous holes in Ludwig's "proofs". Unfortunately, some other people were just calling Ludwig names and claimed to have him in their "kill file" (but still responding to him :-). Then Ludwig would super-politely ask each of them to provide a proof of the infinitude of primes. I was not addressed by Ludwig (since I never gave him hard time) but I obliged anyway. It's good that in addition to monitored math groups there are also "free for all" math groups; in the light of a past discussion on iams, iams is at the moment not monitored but may turn into one if needed (as long as Benjie, the founder, runs iams, it's really up to him)--we have a nice sensible situation on iams. =============================================================== Benjie finds my proof interesting, doesn't know whether or not it's new and asks about the pattern of primes, mentioned on sci.math ("A couple of years ago someone posted to sci.math"), in the 2-dim arrangement: 7 8 9 ... 6 1 2 5 4 3 I think that this even appeared in print (Sci.Am.?) together with the graphical representation--there seemed to be some surprizingly dense and long "rays" of primes. I don't recall any tangible mathematical substance formulated on this occasion. =============================================================== Dave Radcliffe has a feeling that he saw my(? "my"?) proof, possibly in "The Book of Prime Number Records" by Paulo Ribenboim. Can anybody verify? =============================================================== Finally but not leastly, Ben Tilly associates the said proof with the one which uses Fermat numbers only. For this and several other proofs he provides _The Theory of Numbers_ by Hardy and Wright. I also remeber that book as a very pleasant reading. =============================================================== So, let's prove that every two different Fermat Numbers F(n) = 2^2^n + 1 are relatively prime (n=0,1,2,...). For n>0: F(n) - 2 = F(0)*...*F(n-1) is a product of all previous fermat numbers. Thus any common divisor of F(n) and F(k) for any k I've definitely seen both proofs (and related variations) many times before, generally as exercises. For example, in Ireland & Rosen _A Classical Introduction to Number Theory_, chapter 2 problem 4 wants you to show that if a is a nonzero integer and m>n then (a^{2^m}+1, a^{2^n}+1)=1 or 2, depending on whether a is odd or even. Problem 5 wants you to use this to prove that there are infinitely many primes, and credit for this proof is given to Polya. -Chris From: Wlodzimierz Holsztynski Subject: primes (we are still short on references) > Begin forwarded message: > > From: Chris Long > > I've definitely seen both proofs (and related variations) many > times before, ... Do you mean also the proof+variation involving Mersenne numbers, which I have presented? Could you provide a definite reference? > For example, in Ireland > & Rosen _A Classical Introduction to Number Theory_, _A Classical Introduction to Number Theory_ ? > chapter 2 problem 4 wants you to show that if a is a nonzero > integer and m>n then (a^{2^m}+1, a^{2^n}+1)=1 or 2, > depending on whether a is odd or even. Indeed (I happened to have this book and am looking at it now). And the prood is the same as for a=2. Just let F(n)=a^2^n. Then F(n)-2 = F(0)*...*F(n-1) for n>0. > Problem 5 wants you to use this to prove that > there are infinitely many primes, and credit for this proof is > given to Polya. Thank you--Ben Tilly also has informed me that the above argument should be credited to Polya (not to Erdos, as I vaguely misremembered; and Ben might share more historical goodies with us). > > -Chris Exercises 6-8 of the same book by Ireland & Rosen outline still another proof which shows that here are infinitely many primes; it's a proof by Eckford Cohen (see pp26-27 of the 1982 (c) edition, published by Springer-Verlag): Ex.6 Prove that ord(p,n!) = [n/p] + [n/(p^2)] + ... (where ord(a,b) is the greatest integer e such that a^e divides b, e.g. ord(2,80)=4; and [x] is the integer part of x, called the floor of x by computer nerds and APL programmers). Ex.7 Deduce from Ex.6 that ord(p,n!) \le n/(p-1) and that (n!)^(1/n) \le Product(p^(1/(p-1)) : p|n). E.g. (6!)^(1/6) is less or equal (\le) than 2^1 * 3^(1/2). Ex.8 Use Ex.7 to show that there are infinitely many primes. [Hint: (n!)^2 \ge n^n.] (This proof is due to Eckford Cohen.) Besides the Euclid thm there is the much harder Dirichlet Thm about each infinite arithmetic progression a, a+d, ... with the gcd(a,d)=1 containing 1/Theta(d) of all primes (in Dirichlet sense; hence infinitely many)--special cases admit simple elementary proofs. For (3,7,...) and (5,11,...) a slight extension of the Euclid argument is sufficient. Other arithmetic progressions get progressively harder. The general proof is analytic (meaning, it uses complex analitic functions) or "elementary" and hard. But to get the right proportion of primes in even special "easy" arithmetic progressions one perhaps already needs to use the Dirichlet extension of the Euler formula, and it's easy and fun. Wlodek From: Benjamin.J.Tilly@Dartmouth.EDU (Benjamin J. Tilly) Subject: Re: new? proof...primes / Summary --- Wlodzimierz Holsztynski wrote: Is my recollection about Erdos being the author of this via Fermat Numbers proof correct? --- end of quoted material --- Since I was prodded in another post, I will comment on this. This particular proof was by Polya, not Erdos. The proof by Erdos that may have been coming to mind was the proof that uses the factorization properties of 2n choose n to show that not only are there infinitely many primes, but pi(n) = O(n/log(n)), and furthermore there is always a prime between n and 2n. (These are all from variations of the same proof.) Of course the first was proven a long time before, but to the best of my knowledge he was the first person to give an elementary proof of the second 2 facts. The last one in particular I am pretty sure had not been done by elementary means previously. He came up with this proof while still an undergrad. :-) Of course he is also one of the first two people to come up with an elementary proof of the PNT. (Different people debate about whether he finished it before Selberg or not, but there is no doubt that Selberg was the first to get the crucial lemma.) BTW how many papers is he up to now? I think he is over 1500 which is something like twice what anyone else has done. Ben Tilly From: Android Subject: POD -- Toss Problem -- SPOILER SPOILER From wlodek@atg.wiltel.com Let x be the expected number of tosses. (i) if 1st toss is tail then we expect x more tosses--this happens with probability 1/2; (ii) if 1st toss is heads and second tail then we have 2 tosses-- this happens with probability 1/4; (iii) if first two tosses are heads then we expect x more tosses--this happens with probability 1/4. The above cases cover each successful sequence of tosses exactly one time. Thus: x = (1+x)*1/2 + 2*1/4 + (2+x)*1/4 hence x=6 is the expected number of tosses. Remark. We know in advance that x is well defined because we are dealing with a countable union of elementary events. From a_rubin@dsg4.dse.beckman.com We can consider this as a Markov process with states: A {T,init}H^2n B {T,init)H^(2n+1) With transitions: A -> 1/2 A, 1/2 B B -> 1/2 A, 1/2 done and with initial state A. This gives us the equations: A = 1/2 A + 1/2 B + 1 B = 1/2 A + 1 which has solution A = 6, B=4, so the answer is 6. From: Android Subject: POD 10/7 10/7 From a friend of mine in caltech, hopefully a future member If p is a prime number and n is an integer greater than or equal to p, prove: nCp - [n/p] is a multiple of p. where nCp is combinatorial notation, and [] stands for the greatest-integer function. From: "David A. Wagner" Subject: Graph Theory Hello all again! Classes started fairly recently here, and I'm in one cool class by the name of Graph Theory and Combinatorics. I thought I'd mention a little overview of what we've been doing recently, and if anyone's interested I'll post some more... The neatest result is a theorem by Erdos (and someone else who's name I've forgotten) proved in class yesterday: it says that there exists a function f such that for any set of f(n) points in the plane (with no 3 points collinear) there is a n-subset of the points which forms a convex polygon. The proof of the theorem is pretty simple given Ramsey Theory. [Exercise: find f(4), with proof.] Ramsey Theory seems pretty neat, too. Suppose you look at graphs [well, I haven't defined what a graph is, but if you're interested and don't know, ask :-] that have all their edges colored either red or blue. AA clique is a set of vertices which have all edges between them colored just one color. It turns out that there's a function r(s,t) where all graphs of size at least r(s,t) have either a red-clique of size s or a blue-clique of size t. Apparently you can do all sorts of neat stuff with this, I'm told - we haven't gotten very far yet; but our prof. did mention that Erdos offered $500 (I think) for anyone who could prove that (r(s,s))^(1/s) converges as s->infinity. Also, we defined an analogue to the laplacian, on a graph and it turns out that it has tons of neat properties. Cool linear algebra left and right here... For instance, this operator has a repeated eigenvalue of 0 iff the graph is connected, and the product of its non-zero eigenvalues divided by the number of vertices in the graph gives you the number of spanning trees on the graph... So, if anyone sounds like they might be interested in this kinda thing, gimme a yell and I'll try to post some excerpts [hopefully semi-coherently]! -------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From: Android Subject: SPOILER -- POD proof problem -- Solutions and Challenge SPOILER I have the following proofs, can anyone do a simpler one? Is there a simplier one? Problem: If p is a prime number and n is an integer greater than or equal to p, prove: nCp - [n/p] is a multiple of p. where nCp is combinatorial notation, and [] stands for the greatest-integer function. From a_rubin@dsg4.dse.beckman.com I will use x == y (mod p) to indicicate x congruent to y modulo p. There is a general theorem (which proof I will not give here) that if k (k-1) 1 0 k (k-1) 1 0 nCm == a Cb x a Cb x ... x a Cb x a Cb (mod p). k k k-1 k-1 1 1 0 0 In this case (m=p), we have nCm = a (mod p), which was to be proved. 1 For this case, we have a more specific proof (the general proof is similar): n (n-1) (n-2)...(n-p+1) nCp = ---------------------- p (p-1) (p-2) ... 1 Now, the p-1 terms in the numerator not divisible by p are congruent to all p-1 non-zero residues mod p, as are the p-1 terms in the denominator not divisible by p. Hence nCp == (p [n/p])/p = [n/p] (mod p) From Benjamin.J.Tilly@Dartmouth.EDU We can do this directly. If pm is the largest multiple of p that is less than or equal to n, then factoring out mp from the top, and p from the bottom, then the other factors in nCp are congruent mod p to (p-1)! on both top and bottom. Therefore (mod p) we have nCp is congruent to m=[n/p]. There is a generalization that can be proved combinatorially. To be precise if n is a_0 + p a_1 + ... + p^k a_k and m is b_0 + p b_1 + ... + p^k b_k with the a's and the b's all integers that are at least 0 and at most p-1 (ie write both numbers out base p) then nCm is obviously implies the previous result. For a proof take a set of n elements and break it up into a_0 rows of 1 element, a_1 rows of p elements, a_2 rows of p^2 elements, and so on. Let G be a direct sum of a_1 cyclic groups of order p, a_2 of order p^2 and so on. Have G act on your set of n by having each of the cyclic subgroups that it is composed of rotate the elements in one entire row. Now we know that the action of G on our set induces in a natural way an action of G on the set X of subsets of size m of our set with n elements. This action then breaks X up into orbits. Since G is a p-group, each orbit has size a power of p. However X has size the sum over the orbits of the size of that orbit. Therefore mod p the size of X is congruent to the number of fixed points. However if any of the rows has some elements in a subset and some not, then it is easy to show that that subset is not a fixed point. And vica versa a fixed point is a subset which each row either all in, or completely not in the subset. A quick argument on the sizes now shows that this is only possible if b_0 of the a_0 rows with one element are in the subset, and b_1 of the a_1 rows of size p are in, and so on. Therefore the number of fixed points is clearly (a_0 C b_0)(a_1 C b_1)...(a_k C b_k) which is what we wanted to show was congruent mod p to nCm, which is exactly the size of X. Therefore we are done. From: "David A. Wagner" Subject: Graph Theory Ok, a coupla people said they were interested in hearing more about graph theory, so I'll try and do my best to summarize some of the stuff we've talked about in class. I hope I don't screw up too much [maybe someone out there will know this stuff so they can correct me :-] First, what's a graph? A graph is (intuitively) a bunch of points (vertices) that have connections between them (called edges). You can define a graph [sorta] formally as a set V of vertices and a set E that's contained in VxV, with the property that (v,w) is in E iff (w,v) is in E, and (v,v) is never in E. Ok, now, we make a few definitions. Write v ~ w if v and w are two vertices with (v,w) in E. Two vertices v and w are connected if there's a path from v to w, ie if there's a set of vertices v_1, v_2, ..., v_n where v ~ v_1, v_1 ~ v_2, v_2 ~ v_3, ..., v_n ~ w. A graph is called connected if for any two vertices v and w, v is connected to w. Also, the adjacency matrix of a graph is an important concept. Number the vertices v_1, v_2, ..., v_n, where n is the number of vertices. The adjacency matrix A is a n x n matrix such that A_ij is 1 if v_i ~ v_j, and 0 otherwise. Define the degree of a vertex v to be the number of other vertexes w with v ~ w. Define \delta to be the n x n diagonal matrix with \delta_ii = degree(v_i). Now lemme define the Laplacian on a graph, and then I'll justify why it's somewhat analogous to the Laplacian you've all come to know and love. First, look at the space C^0 of all functions from the vertices to the real numbers. This can be considered a n-dimensional vector space, and the natural basis are the functions e_1, ..., e_n where we have e_j(v_k) = 1 if j = k, 0 otherwise. Now the Laplacian is a linear map on this space. Call the Laplacian L for now. Then I define (Lf)(v) = degree(v) - \sum_{w ~ v} f(w). The matrix of L (in the natural basis for C^0) can then be written as A - \delta. L is symmetric, and therefore has real eigenvalues. Now for a justification of why I'm calling this the Laplacian. First of all, in the one dimensional case, the Laplacian of g:R->R is g'', and as an approximation, g''(x) is about 2 g(x) - g(x-1) - g(x+1). But now you can picture x as being joined to x-1 and x+1 by an edge, and so x has "degree" 2. You can also factor L into div and grad, where div and grad have some nice meaning on a graph, but I didn't quite understand this very well in class. If anyone's really interested, I'll ask the prof. to explain this again during office hours or something - I probably should know it anyhow. Ok, this is getting long, so I'll leave you with a few introductory problems, and write some more in a bit. These are stolen from a problem set, etc... First of all, prove that L always has the eigenvalue 0. Next, find a condition for L to have a repeated eigenvalue 0 with proof. If you're still bored, you can find the eigenvalues of L on the complete graph K_n (a graph with n vertices and with v_i ~ v_j for all 1 <= i < j <= n), or on the graph with n vertices and n edges such that v_1 ~ v_2, v_2 ~ v_3, ..., v_{n-1} ~ v_n, v_n ~ v_1. Oh yeah, and there's one more really neat puzzle that was on my first problem set, but I gave it to Benjie for future use on contests, etc... Well, I hope that made a little sense - send me some mail with corrections, complaints, questions, etc! -------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From: Android Subject: Proof Problem -- Possible SPOILER Possible SPOILER --------------- From radcliff@csd4.csd.uwm.edu > I have the following proofs, can anyone do a simpler one? Is there > a simplier one? Probably not. The key fact is that Z_p is a field. That is, every element except zero has a multiplicative inverse. Suppose a != 0 mod p, and consider the set S = {a,2a,3a, ... , (p-1)a}. None of the elements of S are divisible by p, and no two elements of S are congruent to each other mod p. (If ja = ka mod p, then (j-k)a = 0 mod p.) By the pigeonhole principle, there is a k so that ka = 1 mod p. Therefore, k = a^{-1} mod p. Let me illustrate the problem with a specific example. I will calculate C(40,7) mod 7. 40 * 39 * 38 * 37 * 36 * 35 * 34 C(40,7) = ---------------------------------- 7 * 6 * 5 * 4 * 3 * 2 * 1 35 40 * 39 * 38 * 37 * 36 * 34 = ---- * ----------------------------- 7 6 * 5 * 4 * 3 * 2 * 1 5 * 4 * 3 * 2 * 1 * 6 = 5 * ----------------------- (mod 7) 6 * 5 * 4 * 3 * 2 * 1 = 5 (mod 7) From: "David A. Wagner" Subject: Re: Graph Theory I got a question about what I wrote last night, so I obviously wasn't very clear. Lemme try and explain with an example or two - tell me if it makes sense! > > >C^0 of all functions from the vertices to the real numbers > ^^^^^^^^^^^^^^ ? > I followed you except for this part. I don't have a clear picture. > I have gotten used to thinking of the vertices as being values (or > whatever) and not having functional properties. > Ahh, ok, a vertex is a point. For instance, in the graph represented by this picture, the asterisks are vertices, and the lines are edges: *----* | | *----* Now a function from the vertices to the real numbers is a function (call it f) that assigns a real number to each vertex. For example, lemme relabel the graph so that the vertices have names: a----b | | d----c Then V={a,b,c,d} and I could (as a silly example) let f:V->R be defined by f(a)=1, f(b)=-0.5, f(c)=10, f(d)=0. The set of all such functions from V to R can be viewed as a vector space. The following vectors (in this vector space, each vector is a function from V to R) form a basis: e_1(a)=1 e_1(b)=0 e_1(c)=0 e_1(d)=0 e_2(a)=0 e_2(b)=1 e_2(c)=0 e_2(d)=0 e_3(a)=0 e_3(b)=0 e_3(c)=1 e_3(d)=0 e_4(a)=0 e_4(b)=0 e_4(c)=0 e_4(d)=1 Then I could write f = e_1 - 0.5e_2 + 10e_3. Also, the Laplacian of f(a) = degree(a) - f(b) - f(d) = 2-(-0.5)-0 = 2.5. Note that the Laplacian can be written in matrix form under the natural basis given above, and for this graph it is: 2 -1 0 -1 -1 2 -1 0 0 -1 2 -1 -1 0 -1 2. You can work out that the eigenvectors of this matrix are 0, 2, 2, and 4. -------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From: David G Radcliffe Subject: a/b + b/a + 1/(ab) = k (Spoiler) The following problem was posted on October 2. Find all solutions to a/b + b/a + 1/(ab) = k in positive integers. A solution is outlined below. This equation is equivalent to a^2 + b^2 - kab + 1 = 0. It is not hard to verify that if (a,b,k) is a solution, then (b,kb-a,k) is also a solution. Now, (1,1,3) is a solution, so we can iterate this process to get an infinite sequence of solutions: S = { (1,1,3), (1,2,3), (2,5,3), (5,13,3), (13,34,3), (34,89,3), . . .} I claim that there are no other solutions with a <= b. The minimum value of a/b + b/a is 2, so k >= 3. If a = 1, then k = 3 and b = 1 or 2. Assume that a >= 2. Solve the original equation for b using the quadratic formula. b = ka/2 + (1/2)sqrt(k^2 a^2 - 4a^2 - 4) (the other root is < 1) < ka/2 + (1/2)sqrt(k^2 a^2) = ka, and b >= ka/2 + (1/2)sqrt(k^2 a^2 - 5a^2) = (k + sqrt(k^2 - 5)) a / 2 > (k + (k - 2)) a / 2 (since k >= 3) = ka - a. Therefore, 0 < ka - b < a. Now, suppose there is a solution which is not in S. Choose a solution (a,b,k) not in S so that a is as small as possible. Then a >= 2. It is easy to verify that (a-kb,a,k) also satisfies the equation. If (a-kb,a,k) is in S, then (a,b,k) is the next element of S, which is a contradiction. Therefore, (a-kb,a,k) is not in S. But 0 < a-kb < a, contradicting the minimality of a. Therefore, the set of solutions to the equation is exactly S. From: David G Radcliffe Subject: Re: a/b + b/a + 1/(ab) = k (CORRECTION) I made a mistake. Replace a-kb with ka-b in the last two paragraphs of my previous message. Dave From: mgriffin@il.us.swissbank.com (Mike Griffin) Subject: Easy-looking problem Friends in IAMS, Start with a positive integer n, and write down infinitely many lists: list 0: n list 1: n+1, n(n+1) list 2: n+2, (n+1)(n+2), n(n+1)+1, n(n+1)(n(n+1) +1) ... In general, list k+1 is obtained from list k by replacing each member N on list k with the pair N+1, N(N+1). The problem: if n = 2, prove or disprove that the 2^k members of list k are all distinct, for every k. For what n is this true? Mike Griffin From: "David A. Wagner" Subject: Re: laplacian on a graph A correction here, I just got this in the mail: > > I'm reading your interesting posting on laplacians. You defined > (Lf)(v) = degree(v) - \sum_(w ~ v) f(w). > Should'nt this definition be > (Lf)(v) = f(v)degree(v) - \sum_(w ~ v) f(w) ? > This would agree with your analogy with g''(x). > Also, a function on the graph with the property that Lf=0 would then have > the property that the value of the function at a vertex v would equal the > average of the function on the vertices adjacent to v, analogous to > harmonic functions. > Ay-eeh! Yes, of course you're right. I suck! Ok, sorry guys, there's the correct definition... -------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From: Android Subject: P.O.D. triangle problem If the lengths a, b, c of the sides of a triangle satisfy 2(bc^2 + ca^2 + ab^2) = b^(2)c + c^(2)a + a^(2)b + 3abc, prove that the triangle is equilateral. Prove also that the equation can be satisfied by positive real numbers that are not lengths of sides of a triangle. Enjoy, Happy mathing, Benjie From: Android Subject: POD If a, b, c are the roots of the equation x**3 + x**2 + x + 7 = 0, then what is the equation that has the root -a, -b, and -c. Benjie From: ejajko@hertz.elee.calpoly.edu (Edward Jajko) Subject: Not quite a math 'puzzle', but... worthy of a good look. Okay: After a bit of puzzling, I've come up with an iterative approach to solving nth roots for a given number by hand through division & addition. Curiousity leads me to ask: (1) Where was this previously documented and by whom? Was it?? (2) Is there a non-iterative (i.e. single step) process to achive the same? (besides calculcators) Sincerely Curious, -Edward W. Jajko From: Wlodzimierz Holsztynski Subject: Intro to Number Th. (I) (18KB long) Wlodzimierz Holsztynski N U M B E R T H E O R Y (I) I hope that some of you will enjoy my introductory article to number theory. It's elementary--I am not introducing complex numbers or algebraic numbers... (Only at one moment I refer to Lagrange theorem about orders of subgroups being divisors of the order of their groups. These days I consider it a must or else material is obscured and the achievements of the past 150 years of algebra wasted.) At the end this text is a little less elementary, when some of Euler's results involving infinite sums and products are presented. ************************************************** Notation: \le less or equal \ge greater or equal iff if and only if x|y x divides y gcd(x,y) the greatest common divisor of x and y Prod(t:C) the product of all t over condition C Sum(t:C) the sum of all t over condition C In this article a prime is an integer > 1 which which satisfies a condition formulated by Euclid (see below, Def. 3); here I want to say that I don't consider in this article negative primes (or primes which are not rational numbers, as done in algebraic number theory--possibly I'll write some about them later but I am not promising :-). ************************************************** 1. Euclid --------- Hilbert liked Archimedes axiom: If x and t are positive real numbers then there exists a natural number n such that n*t>x. Indeed, this axiom has a clear geometric meaning. Accepting Archimedes axiom, as well as one of the form of induction: every non-empty set of natural numbers has an element smaller than all other elements of the set. we see that the set of natural numbers for which n*t > x is non-empty hence it has the smallest element m. Call q=m-1 the quotient, and r=x-t*q the remainder of the division of the real x by positive real t. Obviously (i.e. go ahead and check that) 0 \le r < t. In the case of natural numbers x,t it was Euclid who claimed that such q and t (quotient and remainder) exist, they satisfy: [E] x = q*t + r where 0 \le r < t LEMMA 1. If x,t are positive real numbers then the non-negative integer q and non-negative real r from [E] are unique i.e. if also [E'] x = q'*t + r' where q' and r' are an integer and a real number such that 0 \le r' < t then q'=q and r'=r. PROOF (outline). Subtract [E] from [E']: (q'-q)*t = r'-r and the rest is not difficult. Just remember that |q' - q| is at least 1. The notion of the quotient and remainder pair, together with their uniqueness is a fundamental stone for the whole number theory. When, above, remainder r in [E] is 0 then we say that t divides x and we write t|x. REMARK 1. In above definitions and considerations x can be an arbitrary real number, q an arbitrary integer (possibly negative). But it's important to assume that t is positive and r non-negative (or else one gets a horribly messy exposition). Let x,y be two integers. Consider expressions L = u*x + w*y (linear combinations of x and y), where u,w are arbitrary integers (possibly negative). If a natural number d divides both x and y then it divides L as well (hence |L| \ge d). Does L divide x and y? Hardly ever. Can it? Let's find out. When sign of u is the same as that of x, and of w as of y, then L is non-negative, and L is then positive when x and y are not both 0. If they are then L=0 divides both of them. Otherwise among all positive L's let's choose the smallest one, i.e. we choose integers u,w, so that L=u*x+w*y is the smallest possible but positive. Let x = q*L + r where 0 \le r < L. Then r = x-q*L = (1-q*u)*x - (q*w)*y is another linear combination of x and y, and r1 and n is not a product of two natural numbers which are both > 1. DEFINITION 3. A natural number n is called prime if n>1 and if for arbitrary natural numbers x and y such that n divides x*y, n divides x or n divides y. The following theorem shows the greatness of the ancient Greek mind: THEOREM 3. (Euclid) A natural number n is indecomposable iff n is prime. PROOF. First let n be a prime. If n=x*y for some natural numbers x and y then n|x*y hence n|x or n|y. But for natural numbers divisibility a|b implies inequality a \le b. We see that n=x and y=1 (when n|x) or n=y and x=1. Thus x is indecomposable. Now let's assume that n is indecomposable. We want to show that n is prime. Let n|x*y. Then gcd(n,x)=1 or n. In the later case n divides x and we are done. In the former we apply theorem 2: n = gcd(n,x*y) = gcd(n,y) hence n|y. QED REMARK 3. Our reference to inequalities when proving implication prime --> indecomposable was not essential. More importantly, when a|b and b|a then a/b is an invertible integer (b/a being the integer inverse)--in the case of our (rational) integers this means that a=b or a=(-1)*b, i.e. a=e*b where e is invertible. Let's add that it's the other implication: indecomposable --> prime which is truly profound. LEMMA 2. Every integer n>1 is divisible by a prime. PROOF. n|n hence there exists a smallest integer d>1 which divides n. Such d is indecomposable hence prime. THEOREM 4. Every natural number 1,2,... is a finite product of prime terms (the same prime may appear more than once). PROOF. 1 is the product of zero (prime) terms. If n>1 then by lemma n is divisible by a prime p hence, by induction, the smaller integer n/p is a finite product of primes. And so is n = p*(n/p). QED THEOREM 5. (Euclid) There are infinitely many primes among natural numbers. PROOF. Let P be the product of a finite collection of natural prime numbers. Let q be a prime divisor of P+1. Then q does not divide P (indeed, the remainder is unique and equal to q-1>0) henceforth q is not any of the primes of the collection. This shows that no finite collection of primes has all primes. QED 2. Modern variations of Euclid's argument ----------------------------------------- THEOREM 6. There are infinitely many primes in the infinite arithmetic progression 3,7,...,4*n-1,... PROOF. Let P be the product of a finite collection of primes of the form 4*n-1 (n=1,2,...). Then prime divisors of 4*P-1 cannot be all of the form 4*n+1 or else 4*P-1 would also be of this form but it can't--the remainder from division by 4 cannot be both 1 and -1 (uniqueness!). Thus there is a prime divisor q of 4*P-1 which is of the form 4*n-1. Obviously q does not belong to the original collection. We see that no finite collection of primes of the form 4*n-1 has all of them. QED THEOREM 6'. There are infinitely many primes in the infinite arithmetic progression 5,11,...,6*n-1,... PROOF. As above. Arithmetic progressions with difference 2 are not too exciting in relation to primes. Integers 3, 4 and 6 as differences of arithmetic progressions are unique in the context of primes-- the are the only integers n>2 for which the set {0,1,...,n-1} has only two members relatively prime to n: 1 and n-1 (the later being -1 mod n). The case of arithmetic progressions which have difference 3 is superfluous in the presence of difference = 6; indeed, every other term of the former progressions is even--remove them and what remains is a progression which has difference 6. But what about the 1,5,...,4*n+1,... and 1,7,...,6*n+1,... arithmetic progressions? They also have infinitely many primes. But the proof in this case goes significantly beyond whatever was done in the ancient times. 3.Arithmetic progression 1,5,...,4*n+1,... ------------------------------------------ Let n>1 be a natural number. In the set Z_n={0,...,n-1} we define Add(x,y) and Mpl(x,y) as the remainders of x+y and x*y when divided by n. The Euclid theorem about existance and uniqueness of the (quotient and) remainder quickly allows to prove that operations Add and Mpl have the familiar properties: associativity, commutativity and distributivity. Also Add(0,x)=Add(x,0)=x and Mpl(1,x)=Mpl(1,x)=x. Let n be a prime, and 02 be a prime hence Z_p is a field. THEOREM 7. (Fermat) x^(p-1) = 1 in Z_p for every 01, repetitions allowed) such that their products are equal: p_1*...*p_m = q_1*...*q_n. Then m=n and p_k = q_k for every k=1,...,m. PROOF. Let t = p_1*...*p_m = q_1*...*q_n. If t=1 then both sequences are empty, m=n=0, and the theorem holds in this case. Now let n>1. Let p be the smallest prime which divides n. Then, by the very definition of primes, p divides p_1 or p divides p_2*...*p_m. By induction one can prove that p divides one of the primes p_1,...,p_m. But p can't divide a prime p' unless p=p'. Hence p=p_1. By the same token, p=q_1. Let t' = t/p, i.e. t' = p_2*...*p_m = q_1*...*q_n. Then t'1 then the above series converges. Indeed: 1 = 1 1/(2^z) + 1/(3^z) < 2/(2^z) = 2^(1-z) 1/(4^z) + ... + 1/(7^z) < 4^(1-z) 1/(8^z) + ... + 1/(15^z) < 8^(1-z) ... ... Adding up the convergent geometric progression on the right above, we get: dzeta(z) < 1+2^(1-z)+4^(1-z)+... = 1/(1-2^(1-z)) for real z>1. We can get, in similar way, a lower estimate of dzeta(z). This would allow us to show for z=1 the series dzeta(1) = 1 + 1/2 + 1/3 + ... diverges. Let's do it but in a more subtle way. Let e_n = (1 + 1/n)^n and E_n = (1 + 1/n)^(n+1). Then one can prove it (let it be left as a rather interesting exercise) that e_1 < e_2 < e_3 < ... and ... > E_3 > E_2 > E_1. Obviously e_n < E_n and limit(E_n - e_n) = 0 for n approaching infinity. Thus there exists a unique real number e such that [#] e_n < e < E_n for every n=1,2,... Let ln be the logarithm based on e (the natural logarithm). By taking the log of [#] (and gently rearranging it) we get: [##] ln(n+1) - ln(n) < 1/n < ln(n) - ln(n-1) for every n=2,3,...; also, for n=1, ln(2) < e. By adding all above inequalities [##] for n=(1),2,...,N we get: ln(N+1) < 1/1 + 1/2 + ... + 1/N < 1 + ln(N) We see that the infinite series dzeta(1) = 1/1 + 1/2 + ... diverges as advertised. REMARK 4. Euler proved that limit ln(N) - (1/1 + ... + 1/N), as N approaches infinity, exists--it is the famous Euler's constant gamma about which to this day we don't know whether or not it's rational (does Plutonium? :-) Let's multiply expressions 1/(1 - 1/p) for all primes p less or equal N. Since 1/(1 - 1/p) = 1 + 1/p + 1/(p^2) + 1/(p^3) + ... we can formally multiply all these geometric progressions using the distributivity law. The product will be a sum of inverses of some natural numbers. Since every n \le N is a product of primes \le N, our sum of inverses of natural numbers will include 1/n for every n \le N, i.e. Prod(1/(1-1/p) : prime p \le N) \ge 1/1 + ... + 1/N When N approaches infinity then so does the product hence there are infinitely many primes--this is one of the versions of Euler's proof of the infinitude of primes. We didn't even use the uniqueness of the prime decomposition of integers. The more complete argument does. The fact that the uniqueness of the prime decomposition was not formulated at the time didn't stop Euler from his discovery: THEOREM 11. (Euler) For real numbers z>1 the following equality holds, both sides of which being well defined: dzeta(z) = Prod(1/(1-p^(-z)) : p - prime) (This time the product is taken over all primes.) PROOF. For the prove you may consider the above product only over primes p \le N. The formal multiplication of the respective geometric progressions will give you a sum of terms n^(-z) where thanks to the uniqueness of the prime decomposition each n will occur at the most one time, while all n \le N will definitely do. Thus for every N=1,2,... we get dzeta(z) \ge Prod(1/(1-p^(-z)) : p - prime \le N) \ge 1^(-z) + ... + N^(-z) The last sum approaches dzeta(z) when N-->infinity which proves Euler Theorem. QED COROLLARY. The infinite product Prod(1-1/p: p-prime) diverges (to zero). REMARK. When an infinite product of positive numbers converges to zero or infinity then we say in Calculus that such a product diverges. With this convention in mind let's recall a classical result: Thm. Let |x_n|<1 for n=1,2,... Then Prod(1+x_n : n=1,2,...) converges iff Sum(x_n: n=1,2,...) does. Thus now we get immediately the following wonderful theorem: THEOREM 12. (Euler) The sum Sum(1/p : p-prime) diverges (is infinite). Thus once again we see that there are infinitely many primes. And we even see that there are many of them or else the sum 1/2 + 1/3 + ... + 1/p + ... would converge despite having infinitely many terms. Some years later Mertens showed that the partial sum Sum(1/p: p-prime \le N) is approximately ln(ln(N))--but that's a new story. From: wlawton@iss.nus.sg (Wayne Lawton) Subject: Intro to Number Th. (I) (18KB long) Dear Wlodek, thanks for your number theory notes - i'll pass on a copy to the math dept folks when i go to lecture there this afternoon Zai Jian, Wayne From: hermann@uran.informatik.uni-bonn.de (Hermann Stamm-Wilbrandt) Subject: Re: POD | |If a, b, c are the roots of the equation x**3 + x**2 + x + 7 = 0, then |what is the equation that has the root -a, -b, and -c. | ==> (x-a)*(x-b)*(x-c)=0 ==> (x+a)*(x+b)*(x+c) is desired equation From: jmlm@dit.upm.es (Joaquin Maria Lopez Munoz) Subject: Re: POD The equation is -x**3 + x**2 -x + 7 = 0 ------------------- Joaquin Maria Lopez Munoz. ETSI de Telecomunicacion de Madrid, Spain. e-mail address: jmlm.bosco.dit.upm.es From: Leigh Blue Caldwell Subject: re: POD ouch!! Please put the word 'spoiler' in the subject line of mail with answers in it, or else about 20-25 blank lines in the content, so we don't read it by accident. thanks leigh From: Wlodzimierz Holsztynski Subject: WARNING: this is about a spoiler for POD (re: x**3 + x**2 + x + 7 = 0) Hermann Stamm-Wilbrandt has posted a "spoiler" to the following POD (Problem Of the Day): Begin forwarded message: > hermann@uran.informatik.uni-bonn.de (HermannStamm-Wilbrandt) > Mathematics Society > > If a, b, c are the roots of the equation > > x**3 + x**2 + x + 7 = 0, > > then what is the equation that has > the root -a, -b, and -c. The solutions for PODs should be sent to Benjie but anyway, let's have a look at it. Partial SPOILER follows. > ==> (x-a)*(x-b)*(x-c)=0 > > ==> (x+a)*(x+b)*(x+c) is desired equation That was there whole text but where is the desired equation? We know the coefficients of the original equation: 1 1 1 7 but we still don't have the coefficients of the new equation. Of course the "solution" above is the important first step and the rest is easy. Have fun, Wlodek From: BANDA@ausvm1.vnet.ibm.com Subject: "Cauchy Sequence -- What is it ? Hi Folks, In an effort to find out more about p-adic numbers I was reading Neal Koblitz's book "p-adic Numbers, p-adic Analysis & Zeta Functions". He uses the term Cauchy Sequence. Can somebody explain what a Cauchy Sequence is? many Thanks in advance Cheers, Venu From: " Craig Jones" Subject: Re: "Cauchy Sequence -- What is it ? > From: BANDA@ausvm1.vnet.ibm.com > He uses the term Cauchy Sequence. Can somebody explain what a Cauchy Sequence > is? many Thanks in advance > > > Cheers, Venu > > vega.irus[64]: webster cauchysequence Cau-chy sequence \ko--,she^--\ n [Augustin-Louis Cauchy +1857 Fr. mathematician] (1955) :a sequence of elements in a metric space such that for any positive number no matter how small there exists a term in the sequence for which the distance between any two consecutive or nonconsecutive terms beyond this term is less than an arbitrarily small number Craig. --- Craig Jones Imaging Research Robarts Research Institute E-mail: craigj@irus.rri.uwo.ca University of Western Ontario London, Ontario From: BANDA@ausvm1.vnet.ibm.com Subject: Cauchy Sequence -- II Many many thanks to everyone for the definition of a cauchy sequence.... but I still have not completely understood it !!! (bear with me, please) My question is why is it that the field of rational numbers, Q is not analytically complete, i.e, has "holes", given the following: a) Betwen any two rational numbers there are infinitely manu rational numbers. b) Suppose I have a cauchy sequence {a1, a2, ... }. Given any arbitrarily small yet positive e>0, we can always find a K and a rational aK such that aK < e and hence the difference between two elements beyond K is also less than e, right. I know I am wrong but I am trying to understand why !!!. many tahnks for your patience.... Cheers, Venu From: Wlodzimierz Holsztynski Subject: "Cauchy Sequence -- What is it ? Begin forwarded message: > From: BANDA@ausvm1.vnet.ibm.com > Subject: "Cauchy Sequence -- What is it ? > > Hi Folks, > > In an effort to find out more about p-adic numbers I was > reading Neal Koblitz's book "p-adic Numbers, p-adic Analysis > & Zeta Functions". He uses the term Cauchy Sequence. Can > somebody explain what a Cauchy Sequence is? many Thanks in > advance > > Cheers, Venu > Let M be a metric space, with the distance function d: MxM-->R; e.g. M can be the straight line or euclidean space. Remember that y = lim(x(n) : n-->infinity) in M iff lim(d(y,x(n)): n-->infinity) = 0 (it's just a definition). Let x = (x(1), x(2),...) be a sequence of points (elements) of M. Sequence x is called a Cauchy sequence iff diameters of the tails (x(n), x(n+1), ...) converges to 0 -- the diameter of a set A is diam(A) = sup(d(x,y) : x,y \in A). Every convergent sequence is a Cauchy sequence. The converse holds for the real line R and for euclidean spaces but fails for general metric spaces. Metric spaces for which convergent sequences coincide with Cauche sequences are called **complete metric spaces**. Of course the constant sequences a^ = (a,a,a,a,...) are Cauchy. Every metric space can be extended or imbedded in a complete space. Given a metric space (M,d) let M^ be the set of all equivalence classes of Cauchy sequences in M, where sequences x=(x(1),x(2),...) and y=(y(1),y(2),...) are called equivalent iff limit(x(n),y(n)) = 0 as n approaches infinity. The distance d^([x],[y]) between two classes of Cauchy sequences is defined uniquely (i.e. independently of the choice of the representatives x,y) as: d^([x],[y]) = lim( d(x(n),y(n)) : n --> infinity) With every point a in M associate the constant sequence a^ = (a,a,a,...) in M^. Obviously: d^(a^,b^) = d(a,b) for every a,b in M. In this sense M is a part of M^ (identify a and a^, so to speak) and every point of M^ is the limit of a sequence of points of M: indeed, let x = (x(1),x(2),...) be a Cauchy sequence in M, i.e. [x] is an arbitrary point of M^. Then [x] = lim(x(n)^ : n-->infinity) It's not difficult to show that metric space M^ is complete. Furthermore, if f:M-->X is a uniformly continuous function into a complete metric space X then there exists a unique continuous function f^:M^-->X such that f^(x^)=f(x) for every point x in M; such f^ is uniformly continuous (and has the same modulus of continuity as f). In particular, completion of a metric space M is essentially unique. Enjoy, Wlodek From: Benjamin.J.Tilly@Dartmouth.EDU (Benjamin J. Tilly) Subject: Re: Cauchy Sequence -- II --- BANDA@ausvm1.vnet.ibm.com wrote: Many many thanks to everyone for the definition of a cauchy sequence.... but I still have not completely understood it !!! (bear with me, please) My question is why is it that the field of rational numbers, Q is not analytically complete, i.e, has "holes", given the following: a) Betwen any two rational numbers there are infinitely manu rational numbers. b) Suppose I have a cauchy sequence {a1, a2, ... }. Given any arbitrarily small yet positive e>0, we can always find a K and a rational aK such that aK < e and hence the difference between two elements beyond K is also less than e, right. I know I am wrong but I am trying to understand why !!!. many tahnks for your patience.... Cheers, Venu --- end of quoted material --- Think about this. The usual decimal representation of sqrt(2) gives rise to a Cauchy sequence in the rationals converging to sqrt(2). That Cauchy sequence in the rationals does not converge to any rational, although there are rationals that are arbitrarily close to what it does converge to. If you can understand that, then you will understand the answer to your question. Ben Tilly From: tulled@rpi.edu (David Michael Tuller) Subject: Primes of the form 4k+3 Does anyone know of the proof that there are infinitely many primes of the form 4k+3? I would prefer one that does not resort to using quadratic reciprocity but instead is similar to Euclid's proof of the infinitude of primes. Thanks. David M. Tuller tulled@rpi.edu From: mgriffin@il.us.swissbank.com (Mike Griffin) Subject: Re: "Cauchy Sequence -- What is it ? A sequence {x_n} in a metric space X is called Cauchy if it has the following property: For every epsilon > 0, there exists a positive integer N such that if m and n > N, then d(x_m, x_n) < epsilon. Intuitively, this is saying that the terms of the sequence are getting arbitrarily close together. In fact, you can force two terms to be as close together as you want by going out far enough in the sequence. If the sequence converges to a limit, then it has the Cauchy property. There are sequences that are Cauchy but not convergent: take a convergent sequence in a metric space X and delete the limit of the sequence to define a new metric space X'. Then the sequence is Cauchy in X' but does not converge. A metric space in which every Cauchy sequence has a limit is called complete. Every metric space may be imbedded as a dense subspace of a complete metric space. Hope this helps... Mike Griffin From: Benjamin.J.Tilly@Dartmouth.EDU (Benjamin J. Tilly) Subject: Re: Primes of the form 4k+3 --- You wrote: Does anyone know of the proof that there are infinitely many primes of the form 4k+3? I would prefer one that does not resort to using quadratic reciprocity but instead is similar to Euclid's proof of the infinitude of primes. Thanks. --- end of quoted material --- It is quite simple. The first thing that you have to prove is that if n is congruent to 3 mod 4 then there is a prime factor of n congruent to 3 mod 4 also. (2 can't be a factor, and things congruent to 1 mod four when multiplied stay congruent to 1 mod 4 so it is easy.) The rest of the proof is along the same lines as Euclid's and I leave it to you to fill in the details. Ben From: Kenneth Rietz Subject: Re: Not quite a math 'puzzle', but... It's hard to say whether it's been done before if you won't say what it is. On the other hand, Newton's method (also called Newton-Raphson method in numerical analysis) gives a method of finding nth roots that ends up using only addition, division, and multiplication. It also is iterative. The formula you get for the nth root of Q is (n-1) (n-1)*(x_m) + Q x_{m+1} = ------------------------ (n-1) n*(x_m) The convergence properties of this are phenomenal. If what you have come up with is this, it's been done, by Newton. There is another method of finding square roots, using a little-known procedure called CORDIC, which is in fact what calculators use for finding square roots. (The same strategy is used in all calclulator function evaluations.) Calculators use it because it is suited to their limited capabilities. If I remember correctly, it uses only additions, subtractions, shifts (multiplications by 10^N), and comparisons - avoiding divisions entirely. I do not know if there are similar methods for higher roots, but I suspect they exist, too. Hope this helps. Ken Rietz | The real world is a special case krietz@ms.uky.edu | of the theoretical, Asbury College, Dept. of Math. | albeit an important one. From: Wlodzimierz Holsztynski Subject: Primes of the form 4k+3 > Begin forwarded message: > > From: tulled@rpi.edu (David Michael Tuller) > Subject: Primes of the form 4k+3 > > Does anyone know of the proof that there are infinitely > many primes of the form 4k+3? I would prefer one that does > not resort to using quadratic reciprocity but instead is > similar to Euclid's proof of the infinitude of primes. > Thanks. > > David M. Tuller > tulled@rpi.edu See "Intro to Number Th. (I) (18KB long)" posted on iams the day before. The case of (4n+3) is the easiest of all arithmetic progressions but (n)=(1,2,...). It's not natural to use anything as powerful as quadratic reciprocity just for this case and I never saw anybody doing it. Did you? Wlodek From: tulled@cii3130-13.its.rpi.edu (David Michael Tuller) Subject: Primes of the form 4k+1 When I sent my post before on primes of the form 4k+3 I meant 4k+1. I already knew the proof based on Euclid's proof of the infinitude of primes. However, it does not work exactly the same for primes of the form 4k+1 since all of its prime factors may be of the form 4k+3. I am pretty sure that I have seen a proof based on Euclid's but I can't remember it. Anyone know about this proof? Thanks. David M. Tuller tulled@rpi.edu From: Android Subject: SPOILER -- Remainder problem, two good proofs -- SPOILER SPOILER follows Problem: What is the remainder when 3^(33^32) is divided by 7? From cei@access.digex.net Let == represent equivalence mod 7. If 3^(33^32)==a, where a is an integer between 0 and 6, then a is the desired answer. Lemma. If x==a, then x^n==a^n. Lemma. If x==a and y==b, then xy==ab. Lemma. (Fermat's Little Theorem). If p is a prime and == represents equivalence mod p, and x is an integer between 0 and p-1, then x^(p-1)==1. Solution. Instead, let === represent equivalence mod 6. 33^32 === 3^32 = 81^8 === 3^8 = 81^2 === 3^2 = 9 === 3. So 3^(33^32) = 3^(6x+3) = (3^6)^x (3^3) == (1^x)(3^3) = 3^3 = 27 == 6. So the remainder of 3^(33^32), when divided by 7, is 6. The proofs of the first two lemmas are trivial. The proof of Fermat's Little Theorem can be easily dug up by me in my Algebra textbook, but it has to do with rings. From dazuma@cco.caltech.edu 32 33 is a multiple of three, and is odd. Thus, it can be written as 3k, where k is some odd integer. 3k k k So, we get 3 = 27 = (28 - 1) . When you expand that binomial, every term except the last is a multiple of 28, and thus is a multiple of 7. Thus, the last term is the remainder. k -1 = -1 when k is odd. So the remainder is -1, which is equivalent to 6. From: benjie%wales@hip-hop.suvl.ca.us (Android) Subject: Change of Address Hi Everybody, If you are using my hip-hop.suvl.ca.us address (benjie@wales%hip-hop.suvl.ca.us or benjie@hip-hop.suvl.ca.us), please notice the following change. The hip-hop.suvl.ca.us domain will be changed to hip-hop.sbay.org. Which means my new address will be benjie@hip-hop.sbay.org, or benjie%wales@hip-hop.sbay.org or benjie@wales%hip-hop.sbay.org. You could always reach me at benjie@quack.kfu.com still. Benjie Benjie Chen Join IAMS math club, email Homestead High School, Cupertino, California me for detail. benjie%wales@hip-hop.sbay.org HAM Call Sign: KE6BCU From: tvo Subject: Problem by D.E. Knuth (and others) In the book 'concrete mathematics' the following prbolem is mentioned: Is it possible to cover a unit square completely with rectangles each having the size 1/n x 1/(n+1), with n from 1 to infinity. The sum of all tiles converges to 1, the surface of the square. Does anyone know an answer to this ? Computer iteration for the first several thousand tiles shows a good chance that a new tile willl always fit into the puzzle. -- +-------------------+--------------------+----------------------------------+ | if in danger | Thomas Vogler | software ag, uhlandstr. 12 | | or in doubt, | tvo@software-ag.de | d-64297 darmstadt | | run in circles +--------------------+-------+--------------------------+ | twist and shout ! | Phone: [49]-(6151)-92-1380 | FAX: [49]-(6151)-92-1612 | +-------------------+----------------------------+--------------------------+ From: hermann@uran.informatik.uni-bonn.de (Hermann Stamm-Wilbrandt) Hello! I have a nice little problem concerning the summation of inverse binomial coefficiants: Proof, that $$ \sum_{i=4}^\infty \sum_{j=2}^{i-2} \frac 1 {{i \choose j}} = \sum_{j\geq 2}^\infty \,\sum_{i\geq j+2}^\infty \frac 1 {{i \choose j}} = \frac 3 2 $$ !! I have a proof and can make it available afterwards. It consists of 4 (!) pages in TeX. Have fun, Hermann. hermann@holmium.informatik.uni-bonn.de Hermann Stamm-Wilbrandt Institut fuer Informatik III Universitaet Bonn Germany P.S.: Hint: It seems to be useful to proof and use ----- $$ \forall j\geq 2:\,\,\,\sum_{i\geq j+1}^\infty \frac 1 {{i \choose j}} = \frac 1 {j-1} $$ . From: jmlm@dit.upm.es (Joaquin Maria Lopez Munoz) Subject: LAMBDA-CALCULUS Has anybody heard about Lambda-calculus? There are nice problems concerning Lambda_terms and their Beta-graphs. I would like to contact people interested in the subject. If many persons are curious bout Lambda-calculus but know little or nothing, I could write write a little introductory matter, just the necessary to have some fun playing with Beta-graphs. Joaquin. --------------------- Joaquin Maria Lopez Munoz. ETSI de Telecomunicacion, Madrid, Spain. e-mail address: jmlm@bosco.dit.upm.es From: Android Subject: Coming up during the weekends, I hope, UCSB math/physics contests I took the UCSB math and physics contests for hs students yesterday and today, extra copies of the tests should be available by thurs. I will, hopefully, try to post the questions during the weekends. Just let you guys know that the contests season is starting. Anyone know when the Putnam and Math Olympiad will start? Benjie From: Abraham S. Mantell Subject: Re: Coming up during the weekends, I hope, UCSB math/physics contests The Putnam Exam is given on the first Saturday of December. Which will be December 4 this year. Abe From: BANDA@ausvm1.vnet.ibm.com Subject: Simple Question Problem: Let || || denote the norm on a field F with the usual properties of a norm. Show that ||-1|| = 1 Cheers, Venu From: Android Subject: Next Contest I want to start the next contest soon. Here is my idea of format. One round each week, a minimum of 6 rounds, may be more. Each round, there is one big problem, or a set of small problems. Solutions will be due at the end of the week (I will specify a deadline). Each round has a total score based on the number of questions and their difficulties. Scores from all 6 rounds are added together to determine the winner. In case a tie, the person who got the most number of problems completely correct is the winner. In case of a tie again, the person who got the fewest number of problems completely wrong is the winner. In case of a tie again, I will rescore the solutions (that is, rescore the ones that weren't completely correct). In that case, I will look for help from other people. Partial credits are given to those who send in something as their solutions. Problems will be available through the mailing list and the mail server. I will use questions submitted by other people as well, in which case one single free point will be awarded to the original sender of the problem. Send me any suggestions, 73, Benjie From: benjie@hip-hop.sbay.org (Benjie Chen) Subject: UCSB Tests will be delayed for the contest I will not be able to post the ucsb tests because 1. I am too busy and I haven't got around things that I need to do, 2. I will save those questions for the contest. If I don't hear some serious complaint next week, I will start the contest on thur or fri. BTW, DO NOT POST solutions to contest questions to the LIST. Benjie From: BARTHOLDI Laurent Subject: Lambda calculus Dear netters, well I for one would be interested in lambda-calculus. I hack a scheme system at u. of Geneva, and makes me interested in more 'formal' aspects of LISP and friends. larry From: Android Subject: Galois theory probelm From dawagner@phoenix.Princeton.EDU Suppose an arbitrary function f:R->R is infinitely differentiable and let g(x) = f(x) + f'(x) + f''(x) + f'''(x) + ... Assume that the sum converges absolutely. Is there a way to recover the original function f, given only g? If your answer is yes, describe how to do so. From: "David A. Wagner" Subject: Re: Galois theory probelm I should add - this came from a proof I read while I was studying Galois theory today, but it has nothing to do with Galois theory, and you don't need to know any to solve it. Just thought I'd mention it, so you don't get scared off. :-) -------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From wgd Tue Oct 26 04:32:42 1993 From: wgd (Bill Dillon) Subject: Re: Galois theory probelm ----- Begin Included Message ----- >From wgd Tue Oct 26 09:24:53 1993 From: wgd (Bill Dillon) Subject: Re: Galois theory probelm >>From dawagner@phoenix.Princeton.EDU >Suppose an arbitrary function f:R->R is infinitely differentiable and >let >g(x) = f(x) + f'(x) + f''(x) + f'''(x) + ... >Assume that the sum converges absolutely. Is there a way to recover >the original function f, given only g? If your answer is yes, >describe how to do so. Spoiler: OK, I'll take a shot at it. I believe the answer is yes. Here's how I would recover f(x): If g(x) = f(x) + f'(x) + f''(x) + ... g'(x) = f'(x) + f''(x) + ... then f(x) = g(x) - g'(x) Regards, Bill ----- End Included Message ----- From: BANDA@ausvm1.vnet.ibm.com Subject: Norm Properties Ok, I was the original poster of the norm question. Apologies for not appending the norm properties. Here they are: Definition of a NORM: A Norm || || on a field F is a mapping from F to +ve real numbers with the following properties. 1. ||x|| = 0 , if x=0 2. ||x*y|| = ||x|| * ||y|| 3. ||x+y|| <= ||x|| + ||y|| Question : Show that ||-1|| = 1 Cheers, Venu From: Competitive Enterprise Institute Subject: Re: Norm Properties On Wed, 27 Oct 1993 BANDA@ausvm1.vnet.ibm.com wrote: > A Norm || || on a field F is a mapping from F to +ve real numbers with the > following properties. > > 1. ||x|| = 0 , if x=0 > 2. ||x*y|| = ||x|| * ||y|| > 3. ||x+y|| <= ||x|| + ||y|| 1. I presume you mean a mapping from F to non-negative real numbers, since ||x||=0 if x=0. 2. Question: Do you mean ||x||=0 iff x=0? If not, I can define ||x||=0 for all x; all three properties are satisfied, and ||-1||=0. - Alexander "Sasha" Volokh From: BANDA@ausvm1.vnet.ibm.com Subject: Norm Properties ok, I goofed !!!!, Alex rightly points out that the first should be a iff statement. (and yes, the norm properties are really just this simple !!, the absolute value is just one example of || || ) 1. ||x|| = 0 iff x=0 2. ||x*y|| = ||x|| * ||y|| 3. ||x+y|| <= ||x|| + ||y|| and ofcourse the || || is a map from field F to "non-negative Reals". Cheers, Venu From: Android Subject: Policy People, please remember (from FAQ) > Keep the good discussions, but when they get too detailed, discuss > them off the list. Not everybody is interested in these discussions. If you want to discuss them, do it w email. One other option, I could start a discussion list for group discussions. Benjie From: Wlodzimierz Holsztynski Subject: Norm Properties of field Q and not only Begin forwarded message: > From: BANDA@ausvm1.vnet.ibm.com > Subject: Norm Properties > > > > ... !!!!, Alex rightly points out that the first should be > a iff statement. (and yes, the norm properties are really > just this simple !!, the absolute value is just one example > of || || ) > > > > 1. ||x|| = 0 iff x=0 > 2. ||x*y|| = ||x|| * ||y|| > 3. ||x+y|| <= ||x|| + ||y|| > > and ofcourse the || || is a map from field F to "non-negative Reals". > > Cheers, Venu ****************************** Cheers :-) (i) The non-negativeness follows from axioms 1-3. (ii) If an element x of the field is a root of 1 (x^n=1 for some n=1,2,...) then ||x||=1 (iii) Every rational number, x in Q, admits a unique prime decomposition, x = Prod(p^(e(x,p) : p-rational prime), where integers e(x,p) are 0 for all but a finite number of primes p. For instance: e(132,2) = 2 e(132,3) = 1 e(132,11) = 1 and e(132,p) = 0 for every other prime p; also e(3/2,2) = -1, e(3/2,3) = 1 e(3/2,p) = 0 for every prime p>3. Define |x|_p = p^(-e(x,p)) for every rational x and rational prime p. Then every | |_p : Q --> R is a norm (in the sense of axioms 1-3 above). And there is only one extra norm which is not equivalent to any of these, namely the absolute value (two norms are called equivalent when one is a power of the other; for instance, the square root of any norm is another norm but equivalent). Obviously: |x| * |x|_2 * |x|_3 * |x|_5 * ... * |x|_p * ... = 1 "Obviously or not" but this is an important property which holds, in a proper form, also for other number fields. (iv) Norms | |_p are non-archimedean, meaning that they satisfy the triangle inequality (axiom 3 above) in a stronger form: 3'. ||x+y|| \le max(||x||,||y||) (v) Consider any norm || || in any field K. Then d(x,y) = ||x-y|| is a distance function in K, i.e. (K,d) is a metric space. Consider a new metric space (K',d') which has classes of equivalent Cauchy sequences as its points (two sequences (x_n), (y_n) of points of K are equivalent if limit(d(x_n, y_n)) = 0 as n-->infinity). The distance d'(X,Y) between X represented by a Cauchy sequence (x_n) and Y by (y_n), is defined as lim(d(x_n,y_n)) as n-->infinity. Every element x of K is identified with the element X=x' of K', represented by the constant Cauchy sequence (x,x,...). We add, subtract, multiply and divide (when possible) two Cauchy sequences term by term in K. This in turn induces properly operations in K'. We get (x+y)' = x'+y', (x-y)' = x'-y', (x*y)' = x'*y', (x/y)' = x'/y' (for y different from 0) with no sweat; and 0' and 1' are the neutral elements for addition and multiplication in K'. In this sense K is considered a subfield of K'. (vi) In the case of Q the completion with respect to the absolute value norm | | yields the field of all real numbers R; the other norms in Q yield the p-adic fields Q_(p). EXAMPLES. Let b_n = 1 + 3 + 3^2 + ... + 3^n. Then 2*b_n = -1 + 3^n, hence |2*b_n - (-1)|_3 = 3^(-n). Also |2|_3 = 1. By axiom 2., |b_n - (-1/2)|_3 = 3^(-n) --> 0 as n-->infinity. Thus the class [(b_n)] is an element of Q_(3) equal to -1/2. Or we simply write: -1/2 = 1 + 3 + 3^2 + ... in Q_(3) REMARK. It's only natural to consider -1/2 to be an integer in Q_(3). Let d_n = 1 - 3 + 3^2 - ... + 3^(n). Then 4 * d_n = 1 + (-1)^(n+1) * 3^n hence |d_n - 1/4|_3 = 3^(-n) --> 0 as n--> infinity. We see that [(d_n)] = 1/4 in Q_(3): 1/4 = 1 - 3 + 3^2 - 3^3 + ... in Q_(3). In general, if x is a rational number such that |x|_p \ge 0 then x can be represented as the sum of a geometric progression in Q_(p) which has quotient of the form p^k, e.g. 1/4 = (-2) * (1 + 3^2 + 3^4 + 3^6 + ...) This is a pretty generic example. Let me end with an example of a square root computation, of sqrt(7) in Q_3. r_1 = 1 is a good start: |1^2 - 7|_3 = 1/3 Suppose that r_n is a rational integer such that: (r_n)^2 = 7 + q_n * 3^n for a rational integer q_n hence |(r_n)^2 - 7|_3 \le 3(-n) Let r_(n+1) = r_n * (1 + q_n * 3^n) Then, computing mod 3^(n+1), and remembering that integer n is positive (hence 3^(2*n)=0 mod 3^(n+1)), we get: (r_(n+1))^2 = (7 + q_n * 3^n) * (1 + 2 * q_n * 3^n) = 7 + 5 * q_n * 3^(n+1) mod 3^(n+1) hence |(r_(n+1))^2 - 7|_3 \le 3^(-(n+1)) Obviously |r_n - r_m|_3 = 3^(-min(n,m)) for n,m not equal each other. This means that (r_n) is a Cauchy sequence w.r. to | |_3; it represents an element r = [(r_n)] of Q_(3). Obviously r^2 = [((r_n)^2)] = 7 in Q_(3) Enjoy (if didn't spoil it for you), Wlodek From: hermann@uran.informatik.uni-bonn.de (Hermann Stamm-Wilbrandt) Subject: Puzzle: uniform random generation of wff's Hello all! The number of well formed formulas on n pairs of parentheses is given by the nth Catalan number C(n) = Choose(2n,n)/(n+1) . After having started with a prefix of a wff the target is to choose the next "(" or ")" with probability leading to uniform generation of the complete wff. Proof that being left with n open and m closed parentheses (n<=m) the following probabilities are correct: Prob("(" as next,n,m) = (m-n+2)n / ( (m-n+1)(m+n) ) Prob(")" as next,n,m) = (m-n)(m+1) / ( (m-n+1)(m+n) ) ( special cases: Prob(")" as next,n,n) = 0 Prob("(" as next,0,m) = 0 ) Have fun, Hermann. P.S.: Below you can find a simple implementation for testing purposes using the LEDA-package. The generation of wff's is done in pure ANSI-C. This is followed by an example run for 5 pairs with 1000000 tests. --------------------------------------------------------------- #include #include // form here until start of main() pure ANSI-C typedef unsigned long number; /* * generate uniformly a random well formed formula * on n pairs of parentheses. */ char *wff(number n) { char *s = (char *) malloc((2*n+1)*sizeof(char)); char *p = s; number m = n; while (n+m>0) { if ( ( random() % ((m-n+1)*(m+n)) ) < (m-n+2)*n ) { n--; *p++='('; } else { m--; *p++=')'; } } *p='\0'; return s; } /* * return the xth Catalan number: 1/(x+1) (2x choose x) */ number C(number x) { number z,n,p; for(p=1,z=2*x,n=1; n<=x; z--,n++) { p*=z; p/=n; } return p/(x+1); } int main(int argc, char*argv[]) { LEDA MY_LEDA; d_array N(0); // nice way of counting strings ! number i,n,s,t,min,max; string S; char *p; if (argc<3) error_handler(77,"format: wff n t"); n=atoi(argv[1]); t=atoi(argv[2]); for(i=0; imax) max=t; cout << S << ": " << t << "\n"; i++; } cout << "#wff(" << n << ") = Catalan(" << n << ") = " << C(n) << "\n"; cout << "found = " << i << "\n"; cout << "#min = " << min << "\n"; cout << "#max = " << max << "\n"; cout << "#avg = " << ((double) s)/i << "\n"; return 0; } ---------------------------------------------------------------------------- "wff 5 1000000" leads to eg. ((((())))): 23456 (((()()))): 23534 (((())())): 23708 (((()))()): 23727 (((())))(): 23661 ((()(()))): 23711 ((()()())): 23841 ((()())()): 23740 ((()()))(): 23821 ((())(())): 23900 ((())()()): 23769 ((())())(): 23925 ((()))(()): 23996 ((()))()(): 23988 (()((()))): 23804 (()(()())): 23808 (()(())()): 24007 (()(()))(): 23658 (()()(())): 23800 (()()()()): 23958 (()()())(): 23762 (()())(()): 24111 (()())()(): 23742 (())((())): 23614 (())(()()): 24035 (())(())(): 23829 (())()(()): 23695 (())()()(): 23804 ()(((()))): 23778 ()((()())): 23861 ()((())()): 23648 ()((()))(): 23679 ()(()(())): 23658 ()(()()()): 23849 ()(()())(): 23788 ()(())(()): 24032 ()(())()(): 23848 ()()((())): 24015 ()()(()()): 23869 ()()(())(): 23812 ()()()(()): 23853 ()()()()(): 23906 #wff(5) = Catalan(5) = 42 found = 42 #min = 23456 #max = 24111 #avg = 23809.5 From: Maxime V. Zakharov Subject: Re: PODS > > 10/22 From: BANDA@ausvm1.vnet.ibm.com > > Problem: Let || || denote the norm on a field F with the usual > properties of a norm. > > Show that ||-1|| = 1 > Trivial norm: R - ring ||0|| = 0 for all x from R and such that not exist y from R such that xy = 0 ||x||=1 Max. From: Wlodzimierz Holsztynski Subject: About non-negativeness of a norm // a correction from M.Griffin I was wrong when claiming that the norm in a field as defined for us by Venu, is automatically non-negative. I got fooled because in a similar sutuation in functional analysis there is one axiom "optically" similar to but different from axiom 2 below. Also, a similar situation in metric space axiomatization gives non-negativeness from straight axioms (it somewhat irritated me over years to see authors adding the inelegant "non-negative" in the def. of metrics). And the end of this article I'll provide the two other case and show that they are non-negative. Sorry for my mishap. I hope that all this is of a value to this group (at least has a chance since it's still math and not just rambling). Begin forwarded message: From: mgriffin@il.us.swissbank.com (Mike Griffin) Subject: Re: Norm Properties of field Q and not only > > Begin forwarded message: > > > > > > > 1. ||x|| = 0 iff x=0 > > > 2. ||x*y|| = ||x|| * ||y|| > > > 3. ||x+y|| <= ||x|| + ||y|| > > > > > > > > and ofcourse the || || is a map from field F to "non-negative > > > Reals". > > > > > > > > Cheers, Venu > > > > ****************************** > > > > (i) The non-negativeness follows from axioms 1-3. > > > > I don't see how. Doesn't the map > > || || : R --> R > > defined by > > || x || = x > > satisfy axioms 1 - 3 ? > > Mike Griffin > ====================================== True! Thank you Mike. In functional analysis we deal with a linear (called also vector) space L over the field of real (or complex) numbers. Then the axioms of a norm ||x|| are: (1) ||x||=0 iff x=0 (2) ||t*x|| = |t| * ||x|| (3) ||x+y|| \le ||x|| + ||y|| for arbitrary x,y from L and real(resp. complex) t (where |t| is the standard absolute value). Then ||x|| > 0 for every x in L different from 0. Indeed, in the light of the above axioms: ||x|| = (1/2) * ( ||x|| + ||(-1)*x|| ) \ge (1/2) * ||x-x|| = (1/2)*||0|| = 0 And in the theory of metric spaces a distance function d : XxX --> R is supposed to satrisfy: (i) d(x,y)=0 iff x=y (ii) d(x,y) = d(y,x) (iii) d(x,y) + d(y,z) \ge d(x,z) for arbitrary points x,y,z in X. Then: d(x,y) = (1/2) * (d(x,y) + d(y,x)) \ge (1/2) * d(x,x) = 0 Cheers, Wlodek From: benjie@wales.sbay.org (Android) Subject: Contest 3, Round 1 The following questions are for contest 3, round 1. Complete answer should be send to benjie@quack.kfu.com ONLY ^^^^^^^^^^^^^^^^^^^^^^^^^ Posting solutions to IAMS list will automatically disqualify you for the ^^^^^^^^^^^^^^^^^^^^^^^^ entire contest. ^^^^^^^^^^^^^^ Answers are due on Nov. 6th. 1. What is the real part of the roots of the quadratic equation (x-10)^2 + (x-9)^2 + ... + (x-1)^2 + x + (x+1)^2 + ... + (x+9)^2 + (x+10)^2 = 0 2. How many different ways can you arrange 5 boys and 5 girls in a row for a group photo so that no boy is next to another boy and no girl is next to another girl? 3. What is the closest distance of the point (3,4) to the circle x^2 + (y+1)^2 = 1? 4. How many real roots are there of the equation x(x-1)(x-2)=log_10 x? 5. Two circles, of radii 6'' and 17'', respectively, have centers 46'' apart. What is the length of the shortest line segment tangent to both circles between the two points of tangency? 6. How many 3 digit integers are there (in decomal notation) between 100 and 999 with no two consecutive digits equal? (For example, you would count 123, but not 113) Round 2 questions will be posted on Nov.5th or 6th, and will be harder. Good luck, and happy mathing, Benjie From: Android Subject: Correction to Problem 1 As some of you pointed out, the mid term for problem one is x^2 rather than x. Benjie From: Van@cup.portal.com Subject: semi-norms From wlodek@atg.wiltel.com >In functional analysis we deal with a linear (called also vector) >space L over the field of real (or complex) numbers. Then the >axioms of a norm ||x|| are: >(1) ||x||=0 iff x=0 >(2) ||t*x|| = |t| * ||x|| >(3) ||x+y|| \le ||x|| + ||y|| If (1) is omitted, we have a semi-norm. (2) and (3) imply ||x|| >= 0 and ||0|| = 0, but not ||x|| = 0 implies x = 0. Usually one speaks of a family of semi-norms, and the topology induced by the family, which is different than the topology induced by a norm. Van van@cup.portal.com From: Android Subject: Contest Info This is a reminder, Partial credits will only be given to submissions with complete solutions. Benjie From: Competitive Enterprise Institute Subject: A division problem Suppose that two robbers want to divide their loot. Unfortunately, the loot is all in the form of heterogeneous articles, so that any two "halves" are difficult to compare. A bit of terminology here: Given a division into parts, a robber is "happy" if he perceives his part to be no smaller than anyone else's. Is there a way of dividing the loot in such a way that both robbers are guaranteed to be happy? What about if there are 3 robbers? What about if there are n robbers? - Alexander "Sasha" Volokh From: BANDA@ausvm1.vnet.ibm.com Subject: ||-1|| = 1 Hi Folks, First off this was not a Homewrok problem......I am just reading it for my own interest. The proof given by Radcliffe et. all is really simple and the reason I stumbled is as follows. The proof of ||-1| = 1, as given on teh net was: a) ||-1|| ** 2 = || (-1) ** 2|| = ||1|| = 1 b) Since ||-1|| is +ve we can conclude that ||-1|| = 1 The problem I had was concluding (b) from (a) for the following reason. If x is an element in F, ||x|| ** 2 = 1 does not necessarily imply that ||x|| = 1. Consider F to be Zp (The Galois Field corresponding to the prime p). Let us take p=5, then ||x|| ** 2 = 1 => x=1, or x=4. I realise that 4 is really -1 in Z5. But 4 is +ve !! . So, How can one conclude (b) from (a). I am confused please help !!!... Cheers, Venu From: "David A. Wagner" Subject: Repeating decimals Everyone knows that fractions of the form 1/n (with n some integer) can be expressed as repeating decimals. For example, 1/3=0.333..., 1/7=0.142857142857..., 1/11=0.090909... But how long will the repeating block be, for any particular n, and how do the properties of the number n determine the length of the repeating block? For example, 1/3 has a block of length 1, 1/7 has a block of length 6, 1/11 has a block of length 2, etc... -------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From: BANDA@ausvm1.vnet.ibm.com Subject: ||-1|| = 1 Hi Folks, First off this was not a Homewrok problem......I am just reading it for my own interest. The proof given by Radcliffe et. all is really simple and the reason I stumbled is as follows. The proof of ||-1| = 1, as given on teh net was: a) ||-1|| ** 2 = || (-1) ** 2|| = ||1|| = 1 b) Since ||-1|| is +ve we can conclude that ||-1|| = 1 The problem I had was concluding (b) from (a) for the following reason. If x is an element in F, ||x|| ** 2 = 1 does not necessarily imply that ||x|| = 1. Consider F to be Zp (The Galois Field corresponding to the prime p). Let us take p=5, then ||x|| ** 2 = 1 => x=1, or x=4. I realise that 4 is really -1 in Z5. But 4 is +ve !! . So, How can one conclude (b) from (a). I am confused please help !!!... Cheers, Venu From: "David A. Wagner" Subject: Repeating decimals Everyone knows that fractions of the form 1/n (with n some integer) can be expressed as repeating decimals. For example, 1/3=0.333..., 1/7=0.142857142857..., 1/11=0.090909... But how long will the repeating block be, for any particular n, and how do the properties of the number n determine the length of the repeating block? For example, 1/3 has a block of length 1, 1/7 has a block of length 6, 1/11 has a block of length 2, etc... -------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From: BANDA@ausvm1.vnet.ibm.com Subject: ||-1|| = 1 Hi Folks, First off this was not a Homewrok problem......I am just reading it for my own interest. The proof given by Radcliffe et. all is really simple and the reason I stumbled is as follows. The proof of ||-1| = 1, as given on teh net was: a) ||-1|| ** 2 = || (-1) ** 2|| = ||1|| = 1 b) Since ||-1|| is +ve we can conclude that ||-1|| = 1 The problem I had was concluding (b) from (a) for the following reason. If x is an element in F, ||x|| ** 2 = 1 does not necessarily imply that ||x|| = 1. Consider F to be Zp (The Galois Field corresponding to the prime p). Let us take p=5, then ||x|| ** 2 = 1 => x=1, or x=4. I realise that 4 is really -1 in Z5. But 4 is +ve !! . So, How can one conclude (b) from (a). I am confused please help !!!... Cheers, Venu From: BANDA@ausvm1.vnet.ibm.com Subject: "Proof of ||-1|| = 1" Looks like my old post got lost....so here goes again. First off, the problem is not a homework question !!!. I am learning the stuff out of my own interest. I am still having a problem with the proof given by some of you for the above problem. Let me re-type your proof so I can point out exactly where I am having a problem. The proof was as follows: a) ||-1|| ** 2 = || (-1) ** 2 || = ||1|| = 1 b) since ||-1|| is +ve the above imples that ||-1|| = 1 Question: The problem I am having with the above proof is the conclusion of (b) from (a). Let me explain. For x an element of a field F, x**2 = 1 and x is +ve does not necessarily mean that x = 1, because consider F to be Z5 (i.e, teh Galois Field corresponding to teh prime 5). Here we see that both 1 and 4 satisfy x**2 = 1. I realise that 4 is really the same as -1 in Z5, but 4 is +ve. So , x**2 = 1 should mean that x=1 or x=4. I am confused about the conclusion of (b) from (a). Hhhhhelp !! Many many thanks for your patience. Cheers, Venu From: Wlodzimierz Holsztynski Subject: "Proof of ||-1|| = 1" Begin forwarded message: > From: BANDA@ausvm1.vnet.ibm.com > Subject: "Proof of ||-1|| = 1" > > Looks like my old post got lost....so here goes again. > > First off, the problem is not a homework question !!!. I am > learning the stuff out of my own interest. > > I am still having a problem with the proof given by some of > you for the above problem. Let me re-type your proof so I > can point out exactly where I am having a problem. > > The proof was as follows: > > a) ||-1|| ** 2 = || (-1) ** 2 || = ||1|| = 1 > > b) since ||-1|| is +ve the above imples that ||-1|| = 1 > > > Question: The problem I am having with the above proof is the conclusion > of (b) from (a). Let me explain. > > For x an element of a field F, x**2 = 1 and x is +ve does not > necessarily mean that x = 1, because consider F to be Z5 > (i.e, teh Galois Field corresponding to teh prime 5). Here > we see that both 1 and 4 satisfy x**2 = 1. I realise that > 4 is really the same as -1 in Z5, but 4 is +ve. So , x**2 = 1 > should mean that x=1 or x=4. > > I am confused about the conclusion of (b) from (a). Hhhhhelp !! > > > Many many thanks for your patience. > > Cheers, Venu ||-1|| is, like any ||x||, a non-negative REAL number (that's how you yourself presented the notion of the norm to us--it's not the only kind of a norm in algebraic number theory, and the one I have mentioned has values indeed in the ground field). So, by (a), ||-1|| is a real number which has 1 as its square, and it's non-negative, hence ||-1||=1. Wlodek From wlodek@atg.wiltel.com Mon Nov 1 07:44:17 1993 (5.67a8/IDA-1.5 for ); Mon, 1 Nov 1993 13:48:30 -0600 From: Wlodzimierz Holsztynski Subject: Rep. decimals / Use Euler's generalisation of "small Fermat" > Begin forwarded message: > > From: "David A. Wagner" > Subject: Repeating decimals > > Everyone knows that fractions of the form 1/n (with > n some integer) can be expressed as repeating decimals. For > example, 1/3=0.333..., 1/7=0.142857142857..., 1/11=0.090909... > But how long will the repeating block be, for any particular > n, and how do the properties of the number n determine the > length of the repeating block? For example, 1/3 has a block > of length 1, 1/7 has a block of length 6, 1/11 has a block > of length 2, etc... > > ---------------------------------------------------------------- > David Wagner Let me do the "pure" case of n relatively prime to 10. Then 10^T(n)-1 is divisible by n, where T(n) is the Euler's number of integers from {1,...,n-1} which are relatively prime with n. Let q = (10^T(n)-1)/n. Then: n = q/(10^T(n)-1) = = q/10^T(n) + q/(10^T(n))^2 + q/(10^T(n))^3 + ... which is a periodic decimal representation of 1/n (but not always the shortest). Now one may study the general k/n and several related questions. ************** An open problem. In 1959 J.Halaj asked whether or not there is a real number between 0 and 1 (0infinity, for those x for which limit exists) is truly amazing!! I still never did one thing and for a reason which I don't understand, I didn't even really try. But the problem is interesting (!)--it was also asked by Jerzy Halaj after I supplied the solution to the earlier version: is there a RATIONAL x between 0 and 1 which is equal to its average binary digit? Wlodek From: Wlodzimierz Holsztynski Subject: Rep. decimals / Use Euler's generalisation of "small Fermat" > Begin forwarded message: > > From: "David A. Wagner" > Subject: Repeating decimals > > Everyone knows that fractions of the form 1/n (with > n some integer) can be expressed as repeating decimals. For > example, 1/3=0.333..., 1/7=0.142857142857..., 1/11=0.090909... > But how long will the repeating block be, for any particular > n, and how do the properties of the number n determine the > length of the repeating block? For example, 1/3 has a block > of length 1, 1/7 has a block of length 6, 1/11 has a block > of length 2, etc... > > ---------------------------------------------------------------- > David Wagner Let me do the "pure" case of n relatively prime to 10. Then 10^T(n)-1 is divisible by n, where T(n) is the Euler's number of integers from {1,...,n-1} which are relatively prime with n. Let q = (10^T(n)-1)/n. Then: n = q/(10^T(n)-1) = = q/10^T(n) + q/(10^T(n))^2 + q/(10^T(n))^3 + ... which is a periodic decimal representation of 1/n (but not always the shortest). Now one may study the general k/n and several related questions. ************** An open problem. In 1959 J.Halaj asked whether or not there is a real number between 0 and 1 (0infinity, for those x for which limit exists) is truly amazing!! I still never did one thing and for a reason which I don't understand, I didn't even really try. But the problem is interesting (!)--it was also asked by Jerzy Halaj after I supplied the solution to the earlier version: is there a RATIONAL x between 0 and 1 which is equal to its average binary digit? Wlodek From: Ingi A. Ford Subject: "Proof of ||-1||" Re Banda's Question-- Reprinted Below Question: The problem I am having with the above proof is the conclusion of (b) from (a). Let me explain. For x an element of a field F, x**2 = 1 and x is +ve does not necessarily mean that x = 1, because consider F to be Z5 (i.e, teh Galois Field corresponding to teh prime 5). Here we see that both 1 and 4 satisfy x**2 = 1. I realise that 4 is really the same as -1 in Z5, but 4 is +ve. So , x**2 = 1 should mean that x=1 or x=4. I am confused about the conclusion of (b) from (a). Hhhhhelp !! Answer: In Z5 The number -1 is the same as 4 so ||4||=||1||. If you are in in Z7 then ||6||=||1||. So we have no problem with the proof. From: Wlodzimierz Holsztynski Subject: A division problem / let's have a cake > > > Begin forwarded message: > > From: Competitive Enterprise Institute > Subject: A division problem > > Suppose that two robbers want to divide their loot. > Unfortunately, the loot is all in the form of heterogeneous > articles, so that any two "halves" are difficult to compare. > > A bit of terminology here: Given a division into parts, a > robber is "happy" if he perceives his part to be no smaller > than anyone else's. > > Is there a way of dividing the loot in such a way that both > robbers are guaranteed to be happy? > > What about if there are 3 robbers? What about if there are > n robbers? > > - Alexander "Sasha" Volokh Perhaps the classical formulation about dividing a cake is preferable. Such a cake has all kind of irregularly shaped stuff in it, and different people (robbers :-) like them differently!. It's important that with a knife you may cut with arbitrary precision. Actually, simple cuts will do the job--there is no need for any intricate cutting. This is a very optimistic situation (for a change :-). Each of n persons likes everything in the cake but some (interposed perhaps) parts better than others. And still, they all can end up with at least 1/n share in their own opinion. If anything, the differences in taste can only help, if you think about it. Wlodek From: Android Subject: POD -- Construction From ELKOMJ@f1groups.fsd.jhuapl.edu Using only a straight edge and compass, construct a square that has an AREA equal to an arbitrary rectangle of length L and width W. (Note: No measurements can be determined using a straight edge and compass. Only the ordinary operations of extending parallel lines, drawing perpendiculars, bisecting lines and angles, drawing arcs and circles, etc... are permitted). From: BARTHOLDI Laurent Subject: RE: "Proof of ||-1||" Dear Folks, I think the confusion around here stems from the different definitions of norms: There are norms for vector spaces and for euclidean rings, and they don't have the same definition. On an euclidean ring R, a norm is a function N : R \ {0} -> N = {1, 2, 3, ...} satisfying N(ab) >= N(a) for all a, b \in R\{0} and forall a, b \in R\{0}: there are r and q such that r + qb = a, and either q=0, or r=0, or N(r) < N(b) (euclidean division). Then there may be many different norms, and some norms may even not be multiplicative (e.g. on polynomials, take deg(f)+1) larry From: ssigur@aol.com Subject: Re: Rep. decimals > Everyone knows that fractions of the form 1/n (with > n some integer) can be expressed as repeating decimals. For > example, 1/3=0.333..., 1/7=0.142857142857..., 1/11=0.090909... > But how long will the repeating block be, for any particular > n, and how do the properties of the number n determine the > length of the repeating block? For example, 1/3 has a block > of length 1, 1/7 has a block of length 6, 1/11 has a block > of length 2, etc.. Decimal expansion of prime numbers is the question. Every prime divides a number in the set {11, 111, 1111, ...}. The number it divides determines the period of its decimal expansion. Since 11111111 = 239 times 4649, 239 and 4649 are the only two primes with a decimal expansion of period 7. Steve From: Android Subject: POD sets Let S = {1, 2, 3, 4, 5, 6, 7, 8} we all know that subsets of S are {}, {1}, {2}, {3} ..., {1,2,3,4,5,6,7,8} and there are 2^8 = 256 of them. If you add up all the digits appeared in the set of subsets of S, what would this number be? Benjie From: Android Subject: SPOILER -- POD of yesterday -- Construction SPOILER From wilson@web.ctron.com Tue Nov 2 06:00:01 1993 > From ELKOMJ@f1groups.fsd.jhuapl.edu > > Using only a straight edge and compass, construct a square that has an > AREA equal to an arbitrary rectangle of length L and width W. (Note: > No measurements can be determined using a straight edge and compass. > Only the ordinary operations of extending parallel lines, drawing > perpendiculars, bisecting lines and angles, drawing arcs and circles, > etc... are permitted). Given rectangle R with sides L and W, to construct a square of equal area to R. On separate line L, place points A, B, and C, in order, with |AB| = L and |BC| = W. Bisect AC at D, and draw semicircle S from A to C, centered at D. Construct perpendicular bisector M through B, letting M meet S at E. BE is then a side of the required square. From ELKOMJ@f1groups.fsd.jhuapl.edu Let the rectangle have a length of L and a width of W. Position the rectangle such that length (the longer side) is horizontal and the width (shorter side) is vertical. Use the compass to find the intersection of the width on the line passing through the length. You should now have a line that is (W+L) long. Define the points A,B, and C such that is the line segment of length W and is the line segment of length L. Bisect the line which is length (W+L) and call the point of bisection P. Use the compass to create a circle centered on P, with radius (or ). At this point the line segment is the diameter of the circle. Extend a line perpendicular to from point B. Where this intersects the circle, label it point D. Now, since triangle is similar to triangle we can state that: ------- = -------- Thus, * = * = ^2 and since = W and = L it must be the case that equals SQRT(W*L). And since W*L is the area of the rectangle, must be the length of the side of the square that also has area W*L. Use the compass and straight edge to complete the square using as the length of the side. The End. From: Competitive Enterprise Institute Subject: Re: Rep. decimals > > > > Everyone knows that fractions of the form 1/n (with > > > > n some integer) can be expressed as repeating decimals. For > > > > example, 1/3=0.333..., 1/7=0.142857142857..., 1/11=0.090909... > > > > But how long will the repeating block be, for any particular > > > > n, and how do the properties of the number n determine the > > > > length of the repeating block? For example, 1/3 has a block > > > > of length 1, 1/7 has a block of length 6, 1/11 has a block > > > > of length 2, etc.. > > > > > Decimal expansion of prime numbers is the question. Every prime divides a > > ^^^^^^^^^^^ > > > number in the set {11, 111, 1111, ...}. The number it divides > > > determines the period of its decimal expansion. Since 11111111 = 239 times > > > 4649, 239 and 4649 are the only two primes with a decimal expansion of period > > > 7. > > > > A quibble, but don't you mean every prime > 2. All those numbers look odd > > to me. And, of course, 1/2 terminates. > > > Another quibble (or a quibble and bit). the first member of the above set > that 3 divides is 111. But 1/3 has period 1 not 3. Well, here's the more complete story. The first quibble should have been "don't you mean every prime other than 2 or 5." This is because 2 and 5 are not relatively prime to 10. Suppose we have 1/n where n is relatively prime to 10. Then if the period has length k, and we denote the period by P, we can write the fraction x = 0.PPPPP and x*(10^k) = P.PPPPP. So x*(10^k - 1) = P, so x = P / (10^k - 1). In other words, 1/n = P / (10^k - 1), or P = (10^k - 1)/n. But since P is an integer, n must divide 10^k - 1. (Note: You might say, "Wait a minute, what if there's a pre-period -- that is, what if we can write x = 0.QPPPP..., like 1/6 = 0.16666?" Ah, but only 1/n for n NOT RELATIVELY PRIME TO 10 has a pre-period. Proof left to the reader. :) ) So that means that you take the set {9, 99, 999, 9999,...} and you find the first one of these that n divides. Then let k be the number of 9's in that number (and that number will, of course, be 10^k - 1). 1/n has period of length k. 1/3: 3 divides 9. So 1/3 has period of length 1. Incidentally, the only divisors of 9 are 3 and 9. So only 1/3 and 1/9 have period of length 1 (out of the fractions 1/n with n relatively prime to 10). 99 = 3 x 3 x 11. So its divisors are 3, 9, 11, 33, and 99. 3 and 9 already divide 9, so 1/11 = 0.(09), 1/33 = 0.(03), and 1/99 = 0.(01) are the only fractions 1/n (with n relatively prime to 10) with period 2. 999 = 3 x 3 x 3 x 37. Its divisors are 3, 9, 27, 37, 111, 333, and 999. So 1/27 = 0.(037), 1/37 = 0.(027), 1/111 = 0.(009), 1/333 = 0.(003), and 1/111 = 0.(001) have periods of length 3. And so on, and so on, and so on.... It would be interesting to work out how this works with numbers that aren't relatively prime to 10, or to develop a way to find *which* number of the form 10^k - 1 something divides without czeching them all. I haven't looked into this, though I suspect that if m = n*(2^k)*(5^l) where n is relatively prime to 10, the period of 1/m is the same as that of 1/n. Though I'm not prepared to state that with any degree of certainty. Anyone? - Alexander "Sasha" Volokh Oh, and another quibble. First line of this message: Many people don't know it. From: Android Subject: POW Here is a physics/math pow...... a friend and I made this up..... You have a cup of water h cm deep. the cup is a perfect cylinder with radius r. You start to rotate the cup with respect to the center of the cup, that's, the cup doesn't move left-right nor up-down, but it's just rotating. Assume the rotational velocity (rad/s) is w. Derive the curve the surface of the water forms if viewed from side of the cup. Happy mathing Benjie From: Android Subject: Contest 3, Round 2 Here is round 2 of contest 3, enjoy...... Benjie ------------cut------------- The following questions are for contest 3, round 2. Complete answer should be send to benjie@quack.kfu.com ONLY ^^^^^^^^^^^^^^^^^^^^^^^^^ Posting solutions to IAMS list will automatically disqualify you for the ^^^^^^^^^^^^^^^^^^^^^^^^ entire contest. ^^^^^^^^^^^^^^ Answers are due on Nov. 12th. I. "SUM" Additional Problems Let L_n = r^n + s^n for all positive integers n, where r = (1+sqrt(5))/2 and s = (1-sqrt(5))/2. A. Show that L_{n+1} = L_{n} + L_{n-1} B. Calculate r^2, r^5, r^8 C. Conjecture on how you could obtain L_n by using only r_n D. Compute the number of digits in L_201 E. Compute the smallest integer n for which L_n has 21 digits. What about 200 digits. F. The fibonacci number can be obtained from the formula F_n = 1/(sqrt(5)) (r^n - s^n), for all positive integers n. Compute the smallest integer n for which F_n has 21 digits and write the first four digits of that F_n. II. Three roots of the equation x^4 - px^3 + qx^2 - rx + s = 0 are tan A, tan B, 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. From: Android Subject: SPOILER -- Set POD Some people said that they didn't get a spoiler for the set pod, so may be there was a problem with the list. Well, here is the SPOILER...... SPOILER Here is a basic summary of all the solution I got, no time to list all names and solutions because there were a lot of them. Method 1: every number appears in half of the 256 sets, so (1+2+...+8)*128 = 4608 Method 2: average number in a set is 36/2 = 18, 18*256 = 4608 Method 3: the last y sets of all n-element subset could be used to fill out the first x sets of all n-element subset. x+y=nC8 and ny = (8-n)x so the total number of {1,2,3,4,5,6,7,8} sets we could obtain is {8C8, 7C8-y_7, 6C8-y_6...., 0C8-y_0} = 128 128*256 = 4608. If anyone needs more detailed solution, please email me. Benjie From: Android Subject: SOLUTIONS TO CONTESTS WILL BE AVAILABLE THROUGH EMAIL SERVER Solutions to Round 1 will be available through the mail server from Sat, Nov. 6th. Email iams-request@quack.kfu.com with SOLUTION as the subject to receive the solutions. From: Android Subject: Results of Contest 3, Round 1 Contest 3, Round 1 is now over. I have received 24 entries, most of them are good. Solutions are available through the email server. I will also post a solution to the net. There are a total of 17 points for this round, and for future rounds too. Partial credits are given. Due to the mailing-list problem, some people might have never received the questions! But don't worry, the final evaluation is based on the average (of minimum 5 rounds). Here is the current standing, if you have any questions, please email me. cei@access.digex.net 17/17 elessar@hermes.acm.rpi.edu 17/17 gintis@econs.umass.edu 17/17 gt0095a@prism.gatech.edu 17/17 Kwok-Shing.Leung@GS133.SP.CS.CMU.EDU 17/17 luzeaux@etca.fr 17/17 pasquale@xsft2.ico.olivetti.com 17/17 radcliff@csd4.csd.uwm.edu 17/17 Benjamin.J.Tilly@Dartmouth.EDU 17/17 wgd@houston.geoquest.slb.com 17/17 wlodek@atg.wiltel.com 17/17 mau@beatles.CSELT.STET.IT 16/17 TavenerS@lilhd.logica.com 16/17 STBC@music.cc.uga.edu 15/17 clong@cnj.digex.com 14/17 craigj@irus.rri.uwo.ca 14/17 Van@cup.portal.com 14/17 alanm@outage.efi.com 13/17 gaps05@udcf.gla.ac.uk 13/17 darglass@owlnet.rice.edu 12/17 was@sunset.cse.nau.edu 12/17 mic@cs.ucsd.edu 11/17 mknapp@isp.nwu.edu 11/17 relyea@seas.smu.edu 8/17 From: Android Subject: Solutions to IAMS Contest 3 Round 1 Solutions follows...... SPOILER Contest 3, Round 1 Solutions 1. What is the real part of the roots of the quadratic equation (x-10)^2+(x-9)^2+...+(x-1)^2+x^2+(x+1)^2+...+(x+9)^2+(x+10)^2=0 Answer : 0 Solution: Simplify the equation, note that the 2xn terms will be dropped. Answer follows easily. Totl Pts: 2 Notes : I gave 1 points to people who sent in -1/40. There was a problem with the email list, so may be they didn't receive the correction post 2. How many different ways can you arrange 5 boys and 5 girls in a row for a group photo so that no boy is next to another boy and no girl is next to another girl? Answer : 28800 or 2*5!*5! Solution: There are 5! ways to arrange boys, 5! ways to arrange the girls, and two ways (see drawing) to combine them together such that no boy is next to another boy and no girl is next to another girl. B G B G B G B G B G or G B G B G B G B G B Totl Pts: 3 3. What is the closest distance of the point (3,4) to the circle x^2 + (y+1)^2 = 1? Answer : sqrt(34)-1 Solution: The shortest distance between the point to the circle is the distance between the point and the center of the circle minus 1 (the radius). The distance to the center is sqrt(34), therefore the shortest distance between the point and the circle is sqrt(34)-1 or 4.83 Totl Pts: 3 4. How many real roots are there of the equation x(x-1)(x-2)=log_10 x? Answer : 2 Solution: If you draw the curve x(x-1)(x-2) and log_10 x, you would find two intersectionss. Thus two real roots. Or we could exame the equation as follows: (1) Exame the interval (-inf, 0], the equation is undefined because log of negative number is undefined. (2) Exame interval (0, 1], In this interval, 1 is a solution since 0=0, when x < 1, the left side is a positive number but the right side is a negative, thus no roots exist. (3) Exame interval (1, 2), In this interval, left side of the equation is less than or equal to 0, right side is greater than 0, so no real roots. (4) Exame interval [2, +inf), we see that when x = 2, x(x-1)(x-2) - log_10 x = 0 - log_10 x which is less than 0. But when x = 10, x(x-1)(x-2) - log_10 x = 720-1 > 0. So between the interval [2, 10], there must be another real roots. It is easily shown that after 10, the function increases upward continuously (derivative exist). Totl Pts: 4 5. Two circles, of radii 6'' and 17'', respectively, have centers 46'' apart. What is the length of the shortest line segment tangent to both circles between the two points of tangency? Answer : 23*sqrt(3) Solution: The shortest tangent segment to both circles is the tangent line that goes from the upper part of one circle to the bottom part of the other. Construct a line between the centers, which should be 46'' long, construct a tangent line descripted above intersecting the previously constructed line, draw radii from centers of two circle to the tangent points. Use pythagorean theorem to find out the length of that tangent line. Totl Pts: 3 6. How many 3 digit integers are there (in decomal notation) between 100 and 999 with no two consecutive digits equal? (For example, you would count 123, but not 113) Answer : 729 Solution: Nine possible numbers (1-9) for the first digit, nine possible numbers (0-9 excluding the previous one) for the second digit, nine possible numbers (0-9 excluding the previous one) for the third digit. Thus there are a total of 9*9*9 3-digit integers between 100 and 999 with no two consecutive digits equal. Or, we could count the number of disqualified numbers in each hundred, which came out to be 19, 900 - 9*19 = 729. Totl Pts: 2 Total Points: 17 (Partial Credits are Given) From: Android Subject: Email Problem, Fixed I hope I think the problem with the email list is fixed now. So let's me make some notes here. The Solutions to COntest 3 Round 1 were posted. They are also available from the mail server. I will repost contest 3 round 2 questions. I have posted the contest 3 round 1 result. If you didn't get that, email me. Ignore any test emails send to IAMS by either me or mrapple@quack.kfu.com, we are trying to fix the bugs. Benjie From: Android Subject: Results of Round 1, in case you didn't get it. Here is the repost of result of round 1 ...... Contest 3, Round 1 is now over. I have received 24 entries, most of them are good. Solutions are available through the email server. I will also post a solution to the net. There are a total of 17 points for this round, and for future rounds too. Partial credits are given. Due to the mailing-list problem, some people might have never received the questions! But don't worry, the final evaluation is based on the average (of minimum 5 rounds). Here is the current standing, if you have any questions, please email me. cei@access.digex.net 17/17 elessar@hermes.acm.rpi.edu 17/17 gintis@econs.umass.edu 17/17 gt0095a@prism.gatech.edu 17/17 Kwok-Shing.Leung@GS133.SP.CS.CMU.EDU 17/17 luzeaux@etca.fr 17/17 pasquale@xsft2.ico.olivetti.com 17/17 radcliff@csd4.csd.uwm.edu 17/17 Benjamin.J.Tilly@Dartmouth.EDU 17/17 wgd@houston.geoquest.slb.com 17/17 wlodek@atg.wiltel.com 17/17 mau@beatles.CSELT.STET.IT 16/17 TavenerS@lilhd.logica.com 16/17 STBC@music.cc.uga.edu 15/17 clong@cnj.digex.com 14/17 craigj@irus.rri.uwo.ca 14/17 Van@cup.portal.com 14/17 alanm@outage.efi.com 13/17 gaps05@udcf.gla.ac.uk 13/17 darglass@owlnet.rice.edu 12/17 was@sunset.cse.nau.edu 12/17 mic@cs.ucsd.edu 11/17 mknapp@isp.nwu.edu 11/17 relyea@seas.smu.edu 8/17 From: Android Subject: Contest 3 Round 2 Questions Repost Subject: Contest 3, Round 2 The following questions are for contest 3, round 2. Complete answer should be send to benjie@quack.kfu.com ONLY ^^^^^^^^^^^^^^^^^^^^^^^^^ Posting solutions to IAMS list will automatically disqualify you for the ^^^^^^^^^^^^^^^^^^^^^^^^ entire contest. ^^^^^^^^^^^^^^ Answers are due on Nov. 12th 9am. I. "SUM" Additional Problems Let L_n = r^n + s^n for all positive integers n, where r = (1+sqrt(5))/2 and s = (1-sqrt(5))/2.