From: Android Subject: P.O.D. Here is a neato problem: The island of Bluebrownblack is inhabited by 13 blue, 15 brown, and 17 black chameleons. If two chameleons of different colors meet, they simultaneously change to the third color. Can all the chameleon turn the same color after a number of such meetings? Benjie From: Wlodzimierz Holsztynski Subject: chameleon SPOILER BS: did you see my mood improver about convex polyhedra with quadrilateral faces. I asked to show that it has to have more than 5 faces. On the other hand I've shown that it may have any number n>5 of faces (all faces must be quadrilaterals) except for the 2 case about which I don't know: n=7,9. > Begin forwarded message: > > The island of Bluebrownblack is inhabited by 13 blue, 15 > brown, and 17 black chameleons. If two chameleons of > different colors meet, they simultaneously change to the > third color. Can all the chameleon turn the same color > after a number of such meetings? Answer: they cannot ------------------- Consider a sequence of color changes consisting, in any order and alternations, of a changes into blue, b into brown, and c into black. This will change the (blue,brown,black)=(13,15,17) "color vector" by the "difference vector": a*(2,-1,-1) + b*(-1,2,-1) + c*(-1,-1,2) = (2*a-b-c, -a+2*b-c, -a-b+2*c) If the result became (45,0,0) then the difference vector would be (32,-15,-17). Then looking at the second coordinate minus the first coordinate (at y-x so to speak :-) we get: 3*(b-a) = -15 - 32 = -47 hence b-a would not be an integer--a contradiction. If the resulting color vector were (0,45,0) then the difference vector would be (-13,30,-17) and we would have: 3*(b-a) = 30 - (-13) = 43 --again a contradiction. Finally, if the color vector became (0,0,45) then the difference vector would be (-13,-15,28) and 3*(b-a) = -15 - (-13) = -2 --impossible once again. We see that it's not possible for chameleons to become monochromatic. Wlodek PS. My BS was not any bs but "Before Scriptum" (just like PS is "postscriptum"). From: TKIDD@CLEMSON.CLEMSON.EDU Subject: I can prove Fermat's Last Theorem. Let me clean it up, make sure it's free of errors, have it checked by math faculty here, and I'll post it as soon as possible. -Travis From: efedula@aol.com Subject: Re: I can prove Fermat's Last Theorem. On the subject of FLT, what do ya'll think of Marilyn vos Savant's claim that Wiles' proof is bogus? I believe the idea is that it doesn't work because it is based on hyperbolic geometry. I don't really know enough to confirm the proof or the "disproof," but I fail to see why using hyperbolic geometry makes things any different (unless there's some deeply embedded circular reasoning). I've heard from one person (a math professor at UT) that Savant knows nothing about (high level) math, and that she should just be ignored. Does anybody out there know enough to shed some more light on this issue? From: Android Subject: Re: I can prove Fermat's Last Theorem. My opnion, after reading Marilyn Vos Savant's claim, was that the original Fermat's Last Theorem had nothing to do with geometry. It was an algebra probelm that suppose to work in this universe, regardless of what geometric system you are you. Thus, if you prove it with hyperbolic geometry, you proved the algebra part of the problem. Benjie From: "Bradley Scott Slavik" Subject: Re: I can prove Fermat's Last Theorem. Yeah. I know that Savant is a Bozo when it comes to math. She is generally correct in her calculations when it comes to basic math, but her justifications are almost always shaky. If you ever want a real laugh, look up her old column where she answered "what happens when an irresistable force meets an immovable object". Yeah, right. Whatever, Marilyn. Bradley From: solan@math.uio.no (Svein O.G. Nyberg) Subject: Mathematics lists Below is a message I sent out to sci.math. I then got to know that this list also exists, so now I know about four. If any of you know of more lists, please inform me, and I'll try to keep the list of mathematics lists complete. Also, a short description like the ones below would be appreciated. = = = = = = = = = = = = = = = = = = = = = = = I just want to direct your attention towards the fact that there are now a total of 3 mathematics lists in the whole world. The oldest is SAMATH which is a Saudi based list oriented to computer assisted teaching. + + + + + + + + + + + + + + + + + + + + + + + Second, this autumn there appeared the list l-math@math.uio.no which is centered on the history and philosophy of mathematics and probability. It has a separate request address, l-math-request@math.uio.no + + + + + + + + + + + + + + + + + + + + + + + Also appearing this autumn is Galaxy, which is the first pure mathematics list. Galaxy is meant to be a forum for mathematicians working with nonstandard analysis. Its address is galaxy@cage.rug.ac.be which functions both as the address to which you send letters, and - due to a smart programmer - the address for subscription. To subscribe, write X-NSA-Admin: join - - - - - - - - - - - - - - - - - - - - - - - Svein Olav Nyberg (solan@math.uio.no) From: Steve Wildstrom Subject: Re: I can prove Fermat's Last Theorem. For those of you in the Washington-Baltimore area who are interested in the actual status of Wiles's proof rather than the silly debate over Marilyn vS, his Princeton colleague John Conway is lecturing at the Smithsonian on Jan. 13. Contact the Smithsonia Resident Associates Office for more information. ---------------------------------------------------------------------- Steve Wildstrom Business Week Washington Bureau wild@access.digex.net "These opinions aren't necessarily mine or anyone else's." ----------------------------------------------------------------------- From: mgriffin@il.us.swissbank.com (Mike Griffin) Subject: Marilyn vos Savant -- response For those who might be interested, here is a letter I wrote to Marilyn vos Savant in response to her column on Wiles' proof. Dear Marilyn vos Savant, I am distressed that you chose to use your access to a large-circulation magazine to promulgate fundamental misconceptions about current mathematical ideas (November 21). It is clear to me that you do not understand (and may not have even tried to understand) the approach Andrew Wiles has taken to Fermat's last theorem, so I will not ask about his ideas. I do have a question growing out of your article: how can Fermat's conjecture be interpreted as a question about Euclidean geometry? The conjecture makes a statement about integers, and a priori, it has no geometric content. It is true that solutions to the equation x^2 + y^2 = z^2 correspond to planar right triangles whose sides have integer lengths, but I see no obvious geometric interpretation of the solutions to x^n + y^n = z^n. Thanks for any light you can shed on this mystery. ---------------------------------- On a more substantive level, Andrew Wiles has acknowledged a problem with his proof, in the following posting to sci.math: From: wiles@rugola.Princeton.EDU (Andrew Wiles) Newsgroups: sci.math Subject: Fermat status Organization: Princeton University In view of the speculation on the status of my work on the Taniyama-Shimura conjecture and Fermat's Last Theorem I will give a brief account of the situation. During the review process a number of problems emerged, most of which have been resolved, but one in particular I have not yet settled. The key reduction of (most cases of ) the Taniyama-Shimura conjecture to the calculation of the Selmer group is correct. However the final calculation of a precise upper bound for the Selmer group in the semistable case (of the symmetric square representation associated to a modular form) is not yet complete as it stands. I believe that I will be able to finish this in the near future using the ideas explained in my Cambridge lectures. The fact that a lot of work remains to be done on the manuscript makes it still unsuitable for release as a preprint . In my course in Princeton beginning in February I will give a full account of this work. Andrew Wiles. ------------------------------------------- Finally, those in the Chicago/South Bend area may wish to drop in on two lectures by Alice Silverberg, a number theorist at Ohio State, today and tommorrow at Notre Dame: 4:30 pm, rm. 226 of the Mathematics/Computer Science building. Silverberg and Karl Rubin have written an expository paper on Wiles' proof. The .tex and .ps files are available by anonymous FTP from math.ohio-state.edu, in the directory pub/users/silver. The amslatex file is called wiles_fermat.tex and the postscript file is wiles_fermat.ps. Enjoy! Mike Griffin From: claxnes@nwer.sandia.gov (Carl L. Axness) Subject: Re: Fermat's Last Theorem. > From: efedula@aol.com > Subject: Re: I can prove Fermat's Last Theorem. > > On the subject of FLT, what do ya'll think of Marilyn vos Savant's claim that > Wiles' proof is bogus? I believe the idea is that it doesn't work because it > is based on hyperbolic geometry. I don't really know enough to confirm the > proof or the "disproof," but I fail to see why using hyperbolic geometry > makes things any different (unless there's some deeply embedded circular > reasoning). > I've heard from one person (a math professor at UT) that Savant knows nothing > about (high level) math, and that she should just be ignored. Does anybody > out there know enough to shed some more light on this issue? > I have only heard the gist of the vos Savant antiproof, but from what I hear it sounds as if the same logic could be applied to the proof that an angle cannot be trisected using Euclidean tools by Galois theory. Perhaps Marilyn should leave mathematics to real mathematicians. From: claxnes@nwer.sandia.gov (Carl L. Axness) Subject: another chameleon spoiler Here is a simple SPOILER to the chameleon problem In order for a solution to occur to the problem, at some point in the process we must be at a point where there is an equal numbers (>0) of chameleons of two colors. But we note that any encounter in essence changes all numbers in the population by the same modulus =2mod(3). Note subtracting 1 from a number mod3 is the same as adding 2 mod(3). So the numbers maintain their initial modulus of 13=1 mod(3), 15=0 mod(3), and 17 = 2mod(3), and equality between two populations cannot occur. The argument can be extended to any three numbers of different modulus. From: tkidd@hubcap.clemson.edu (kidd travis danemon) Subject: Proof of FLT Hi! I will send you my proof of FLT. Let's assume that sum((n-i-1)/i) as i goes from 1 to n-2 is not a multiple of n. This can be proven. Lemma: If n,x,y,a are natural numbers such that n is an odd prime, x and y are not multiples of n, x+y is a multiple of n, and x^n + y^n + na(x+y) = (x+y)^n, then a is not a multiple of n. (x+y)(x+y)^(n-1) - (x+y)[x^(n-1) - x^(n-2)y + x^(n-3)y^2 ... - xy^(n-2) + y^(n-1)] na = --------------------------------------------------------------------------- (x + y) = (x+y)^(n-1) - [x^(n-1) - x^(n-2)y + x^(n-3)y^2 ... - xy^(n-2) + y^(n-1)] = {[x^(n-1) + (n-1)x^(n-2)y + [(n-1)(n-2)x^(n-3)y^2]/2 + ... + [(n-1)(n-2)(n-3)...*3*2*1]y^(n-1)] - [x^(n-1) - x^(n-2)y + x^(n-3)y^2 ... - xy^(n-2) + y^(n-1)]} = {[(n-1) + 1]x^(n-2)y + ([(n-1)(n-2) - 2]x^(n-3)y^2)/2 + ([(n-1)(n-2)(n-3) + 6]x^(n-4)y^3)/6 ... ([(n-1)(n-2)...[n-(n-3)][n-(n-2)] + (n-2)!]xy^(n-2))/(n-2)!} = {nx^(n-2)y + ([n^2 - 3n]x^(n-3)y^2)/2 + ([n^3 - 6n^2 + 11n]x^(n-4)y^3)/6 etc. etc. up to the term containing xy^(n-2).} So-- a = {x^(n-2)y + [(n-3)/2]x^(n-3)y^2 + [(n^2 - 6n + 11)/6]x^(n-4)y^3 etc. etc.} Now -- since x+y is a multiple of n, let k=(y+x)/n. So y=kn-x. Substituting, we get a = {x^(n-2)(kn-x) + [(n-3)/2]x^(n-3)(kn-x)^2 + [(n^2 - 6n + 11)/6]x^(n-4)(kn-x)^3 etc. etc.} Notice that calaulating each term yields only the following non-multiples of n: {-[x^(n-1)] , -(3/2)[x^(n-1)] , -(11/6)[x^(n-1)] , etc.} So it is sufficient to show that the sum of these terms is not a multiple of n. Without affecting the proof, let the above terms be positive instead of negative. We know that [x^(n-1)] is not a multiple of n, so ... we need only show that 1 + 3/2 + 11/6 etc. is not a multiple of n. The first term is 1/1. The second is 1/1 + 1/2. The third is 1/1 + 1/2 + 1/3. The last ((n-2)th) term, is 1/1 + 1/2 + 1/3 + ... + 1/(n-2). Therefore, the sum of all the terms is sum((n-i-1)/i): i goes from 1 to n-2. Since (n-2)! is not a multiple of n, multiplying the above by (n-2)! will not change its status as a multiple of n. This product is not a multiple of n-- therfore the above sum is not a multiple of n, therefore a is not a multiple of n -- which is what we wanted to show. QED. Fermat's Theorem Applied to odd prime n: There are no integers x,y,z,n such that n>2 is an odd prime and x^n + y^n = z^n. The proof is by contradiction. Proof. Assume there are such integers. Let z be the smallest possible. There- fore x and y are mutually prime. By Fermat's little theorem, we know that x+y = z + kn, where k is some natural number (not meant to be the same k as in the above proof). We also know that x+y is a factor of z^n, since z^n = (x+y)(x^(n-1) - x^(n-2)y ... - xy^(n-2) + y^(n-1)). Therefore every prime factor of x+y is a factor of z. Since zf2 are mutually prime factors of z. So z + kn = [f1/f2]z. So kn = z([f1/f2] - 1). Let f3 = f1 - f2. (We know that f1,f2,f3 are mutually prime.) kn=[f3/f2]z, so z=[f2/f3]kn. Since f3 is not a factor of either f2 or n, f3 is a factor of k. So z = f2[k/f3]n. So z is a multiple of n. Therefore, so is x+y. Now, by our lemma above, we know that z^n + na(x+y) = (x+y)^n, where a is not a multiple of n. Let p1=z/n, p2=(x+y)/n. p1^n*n^n + na(x+y) = p2^n*n^n Dividing by n: p1^n*n^(n-1) + a(x+y) = p2^n * n^(n-1). Since a is not a multiple of n, x+y must be a multiple of n^(n-1). We know that x+y=f1[k/f3]n. So f1*k must be a multiple of n^(n-2). Since f1 is a factor of z, zk must be a multiple of n^(n-2). Since z + kn = x+y, either both z and kn are multiples of n^(n-1), or both z and kn are multiples of EXACTLY THE SAME POWER of n. If it is the former, skip this part. ......... Assume the latter. Let kn be a multiple of n^w. z must be a multiple of n^(w+1). So k, which is a multiple of n^(2w+1), is a multiple of n^(n-2). So 2w + 1 >= n-2. So w >= (n-1)/2. So z must be a multiple of n^[(n+1)/2]. Now, both z and x+y are multiples of n^[(n+1)/2]. Now let p1=z/n^[(n+1)/2] and p2=(x+y)/n^[(n+1)/2]. Using the above lemma, we get: p1^n*n^(n[(n+1)/2]) + na(x+y) = p2^n*n^(n[(n+1)/2]) Since a is not a multiple of n, x+y must be a multiple of n^[(n^2 + n)/2 - 1] or n^[(n^2 + n - 2)/2]. Inductively, we can show that x+y must be a multiple of n to the power of every number in the sequence n^v + sum(n^(i)*2^(v-1-i)):i=1 to v-1 q(v)=------------------------------------- - 1 2^(v-1) Since n>2, this sequence has no maximum--therefore since x+y is finite, it cannot be a multiple of every term in the sequence. This is our contradiction. QED. Since I have proven Fermat's Last Theorem when n is an odd prime, the proof of the entire theorem is complete. -Travis Kidd (tkidd@clemson.clemson.edu) From: tkidd@hubcap.clemson.edu (kidd travis danemon) Subject: I forgot something in my proof... There is a part to skip given a certain assumption...I forgot to mark the end of it. It is right after where it is proven that z must be a multiple of n^[(n+1)/2]. -Travis From: tkidd@hubcap.clemson.edu (kidd travis danemon) Subject: Proof of FLT Hi! I will send you my proof of FLT. Let's assume that sum((n-i-1)/i) as i goes from 1 to n-2 is not a multiple of n. This can be proven. Lemma: If n,x,y,a are natural numbers such that n is an odd prime, x and y are not multiples of n, x+y is a multiple of n, and x^n + y^n + na(x+y) = (x+y)^n, then a is not a multiple of n. (x+y)(x+y)^(n-1) - (x+y)[x^(n-1) - x^(n-2)y + x^(n-3)y^2 ... - xy^(n-2) + y^(n-1)] na = --------------------------------------------------------------------------- (x + y) = (x+y)^(n-1) - [x^(n-1) - x^(n-2)y + x^(n-3)y^2 ... - xy^(n-2) + y^(n-1)] = {[x^(n-1) + (n-1)x^(n-2)y + [(n-1)(n-2)x^(n-3)y^2]/2 + ... + [(n-1)(n-2)(n-3)...*3*2*1]y^(n-1)] - [x^(n-1) - x^(n-2)y + x^(n-3)y^2 ... - xy^(n-2) + y^(n-1)]} = {[(n-1) + 1]x^(n-2)y + ([(n-1)(n-2) - 2]x^(n-3)y^2)/2 + ([(n-1)(n-2)(n-3) + 6]x^(n-4)y^3)/6 ... ([(n-1)(n-2)...[n-(n-3)][n-(n-2)] + (n-2)!]xy^(n-2))/(n-2)!} = {nx^(n-2)y + ([n^2 - 3n]x^(n-3)y^2)/2 + ([n^3 - 6n^2 + 11n]x^(n-4)y^3)/6 etc. etc. up to the term containing xy^(n-2).} So-- a = {x^(n-2)y + [(n-3)/2]x^(n-3)y^2 + [(n^2 - 6n + 11)/6]x^(n-4)y^3 etc. etc.} Now -- since x+y is a multiple of n, let k=(y+x)/n. So y=kn-x. Substituting, we get a = {x^(n-2)(kn-x) + [(n-3)/2]x^(n-3)(kn-x)^2 + [(n^2 - 6n + 11)/6]x^(n-4)(kn-x)^3 etc. etc.} Notice that calaulating each term yields only the following non-multiples of n: {-[x^(n-1)] , -(3/2)[x^(n-1)] , -(11/6)[x^(n-1)] , etc.} So it is sufficient to show that the sum of these terms is not a multiple of n. Without affecting the proof, let the above terms be positive instead of negative. We know that [x^(n-1)] is not a multiple of n, so ... we need only show that 1 + 3/2 + 11/6 etc. is not a multiple of n. The first term is 1/1. The second is 1/1 + 1/2. The third is 1/1 + 1/2 + 1/3. The last ((n-2)th) term, is 1/1 + 1/2 + 1/3 + ... + 1/(n-2). Therefore, the sum of all the terms is sum((n-i-1)/i): i goes from 1 to n-2. Since (n-2)! is not a multiple of n, multiplying the above by (n-2)! will not change its status as a multiple of n. This product is not a multiple of n-- therfore the above sum is not a multiple of n, therefore a is not a multiple of n -- which is what we wanted to show. QED. Fermat's Theorem Applied to odd prime n: There are no integers x,y,z,n such that n>2 is an odd prime and x^n + y^n = z^n. The proof is by contradiction. Proof. Assume there are such integers. Let z be the smallest possible. There- fore x and y are mutually prime. By Fermat's little theorem, we know that x+y = z + kn, where k is some natural number (not meant to be the same k as in the above proof). We also know that x+y is a factor of z^n, since z^n = (x+y)(x^(n-1) - x^(n-2)y ... - xy^(n-2) + y^(n-1)). Therefore every prime factor of x+y is a factor of z. Since zf2 are mutually prime factors of z. So z + kn = [f1/f2]z. So kn = z([f1/f2] - 1). Let f3 = f1 - f2. (We know that f1,f2,f3 are mutually prime.) kn=[f3/f2]z, so z=[f2/f3]kn. Since f3 is not a factor of either f2 or n, f3 is a factor of k. So z = f2[k/f3]n. So z is a multiple of n. Therefore, so is x+y. Now, by our lemma above, we know that z^n + na(x+y) = (x+y)^n, where a is not a multiple of n. Let p1=z/n, p2=(x+y)/n. p1^n*n^n + na(x+y) = p2^n*n^n Dividing by n: p1^n*n^(n-1) + a(x+y) = p2^n * n^(n-1). Since a is not a multiple of n, x+y must be a multiple of n^(n-1). We know that x+y=f1[k/f3]n. So f1*k must be a multiple of n^(n-2). Since f1 is a factor of z, zk must be a multiple of n^(n-2). Since z + kn = x+y, either both z and kn are multiples of n^(n-1), or both z and kn are multiples of EXACTLY THE SAME POWER of n. If it is the former, skip this part. ......... Assume the latter. Let kn be a multiple of n^w. z must be a multiple of n^(w+1). So k, which is a multiple of n^(2w+1), is a multiple of n^(n-2). So 2w + 1 >= n-2. So w >= (n-1)/2. So z must be a multiple of n^[(n+1)/2]. Now, both z and x+y are multiples of n^[(n+1)/2]. Now let p1=z/n^[(n+1)/2] and p2=(x+y)/n^[(n+1)/2]. Using the above lemma, we get: p1^n*n^(n[(n+1)/2]) + na(x+y) = p2^n*n^(n[(n+1)/2]) Since a is not a multiple of n, x+y must be a multiple of n^[(n^2 + n)/2 - 1] or n^[(n^2 + n - 2)/2]. Inductively, we can show that x+y must be a multiple of n to the power of every number in the sequence n^v + sum(n^(i)*2^(v-1-i)):i=1 to v-1 q(v)=------------------------------------- - 1 2^(v-1) Since n>2, this sequence has no maximum--therefore since x+y is finite, it cannot be a multiple of every term in the sequence. This is our contradiction. QED. Since I have proven Fermat's Last Theorem when n is an odd prime, the proof of the entire theorem is complete. -Travis Kidd (tkidd@clemson.clemson.edu) From: Wlodzimierz Holsztynski Subject: Re: another chameleon ... / + their minitheory Carl posted the following beautiful solution of the neat POD posted by Benjie: > The island of Bluebrownblack is inhabited by 13 blue, 15 > brown, and 17 black chameleons. If two chameleons of > different colors meet, they simultaneously change to the > third color. Can all the chameleon turn the same color > after a number of such meetings? Carl said (SPOILER): > ... note that any encounter in essence changes > all numbers in the population by the same modulus =2mod(3). ... > So the numbers [of chameleons of for each color] maintain > their initial modulus of: > > 13=1 mod(3), 15=0 mod(3), and 17 = 2mod(3), > > and equality between two populations cannot occur. The > argument can be extended to any three numbers of different > modulus. Let, in general, integers x,y,z and X,Y,Z be such that x+y+z = X+Y+Z. Is there a sequence of chameleon transformations which leads from the (x,y,z) color configuration to (X,Y,Z)? I provide a complete answer below. Each of the chameleon transformations adds to any color configuration one of the three difference vectors: dx = (2,-1,-1) dy = (-1,2,-1) dz = (-1,-1,-2) Remark: dx+dy+dz=(0,0,0) hence dz = -(dx+dy). Thus the question above can be reformulated as: is the difference vector (X,Y,Z)-(x,y,z) = (X-x,Y-y,Z-z) equal to a linear combination of vectors dx and dy? Of course the difference vector belongs to the "lattice" L of all integer vectors (u,v,w) such that u+v+w=0. And so do vectors dx and dy (and dz too) as well as all their linear combinations--they all belong to L. Once again, we are in effect asking which of the vectors of lattice L belong to the sublattice M spanned by dx and dy? The main part of Carl's argument may be stated as follows: the necessary condition for a vector (u,v,w) \in L to belong to M is: u=v mod 3 (then v=w mod 3 and u=w mod 3 follow since u+v+w=0 and 3 is such a funny small number). Indeed, this condition is satisfied by dx and dy hence by their every linear combination. Is the above condition also sufficient?, i.e. do we have: THEOREM. (u,v,w) \in L belongs to M iff u=v mod 3 We do. Bear with me because we are almost done. Since for (u,v,w) \in L we have: (u,v,w) = u*(1,-1,0) + (u+v)*(0,1,-1) we see that Dx = (1,-1,0) and Dy = (0,1,-1) form a linear basis of L; hence every vector fo L is of the form a*Dx + b*Dy. Such a vector has its first two coordinates congruent mod 3 iff a+b=0 mod 3. But 3*Dx = 2*(dx-dy) belongs to M, hence vector a*Dx + b*Dy = (a+b)*Dx + b*dy (the above equality is certified for having no typo) belongs to M when a+b=0 mod 3. This completes the proof. ====== Remark. Let E=(1,1,1). Then det(dx,dy,E)=9 while det(Dx,Dy,E) = 3. This means that the area of the parallelogram [0,dx,dy,dx+dy] has area 3 times larger than parallelogram [0,DX,DY,DX+DY]. This observation amounts to a proof of the above theorem (of the sufficient condition) granted that that some basic results about lattices (i.e. about discrete additive subgroups of the cartesian spaces) are established first (not too much). Wlodek Wlodzimierz Holsztynski From: mic@cs.ucsd.edu (Michelangelo Grigni) Subject: another chameleon ... / + their minitheory Wlodek wrote: > Thus the question above can be reformulated as: is the > difference vector (X,Y,Z)-(x,y,z) = (X-x,Y-y,Z-z) > equal to a linear combination of vectors dx and dy? [He characterizes such differences (u,v,w): u+v+w=0 and u=v=w (mod 3)] You may also need to worry about keeping the integers non-negative as you go from (x,y,z) to (X,Y,Z). In general such problems are not easy (may need to compute something like a Groebner basis), but in this case I do not see any problems. But the problem also had a second restriction: the transformation was not symmetric: i.e. if two different chameleons meet, then they switch to the third color. However if you have two chameleons of the same color, they do not change further. So in particular, there is no way to get from (3,0,0) to (0,3,0) with this restriction. So, next puzzle: characterize "reachability" (X,Y,Z) -> (x,y,z) under this further restriction. For completeness, here is the Benjie's original puzzle: > The island of Bluebrownblack is inhabited by 13 blue, 15 > brown, and 17 black chameleons. If two chameleons of > different colors meet, they simultaneously change to the > third color. Can all the chameleon turn the same color > after a number of such meetings? From: jillstev@aol.com Subject: Inverse trig functions On most calculators if you try to find inverse sine of 7 you would get an error message since the range of sine is from -1 to 1 inclusive. On the TI-85 you get a complex number. Why? From: efedula@aol.com Subject: Re: Inverse trig functions --- On most calculators if you try to find inverse sine of 7 you would get an error message since the range of sine is from -1 to 1 inclusive. On the TI-85 you get a complex number. Why? --- We've spent some time in my precal class trying to figure out just how calculators arrive at some of their answers, and I believe that it uses power series to do trig stuff. I'm not really an expert on this, but if you take the number that it gives you, and plug it into the power series for sin (which I think is x-(x^3)/3!+(x^5)/5!-...), you should get 7. On the subject of calculators, does anyone know how to get the factorial of a non-integer? I know that the curve y=sqrt(2*pi*x)*(x^x)*(e^-x) is asymptotic to y=x!, but I want something more exact. Is there a power series for this (if so, what is it)? From: tarrant dennis wayne/jr. Subject: Marsenne pseudoprimes When new Marsenne pseudoprimes are determined of (2^p)-1, does there necessarily follow a factorization of (x^p)-1? If so, how does one determine the factorization? Specifically, do there exist two polynomials (other than (x-1)(x^10+x^9+...+1) such that their product is (x^11)-1? And can you generalize this? From: efedula@aol.com Subject: Re: Inverse trig functions --- My HP 42 does not do the factorial of a non-integer, in fact basically no calculator does that so I think they don't use a power series to do that. But it would be interesting to derive a exact power series for x! ! Why do you need to know? --- My HP48S does, and I was just wondering what formula I could use to do it myself (not that I ever need to, but I like learning seemingly meaningless mathematical truths, since you never know when they'll come in handy). I had heard of the gamma function before, but didn't know exactly what it was. Thanks to the two people who responded with the actual definition/formula. E From: mgriffin@il.us.swissbank.com (Mike Griffin) Subject: Re: Marsenne pseudoprimes x^11 - 1 = (x-1)(x^10 + x^9+ ... + 1) is a factorization into irreducibles over the rationals. The reason is that, in general, x^n - 1 factors as x^n - 1 = product(phi_d(n)) over d such that d | n where phi_d(x) (excuse the typo above) is the d-th cyclotomic polynomial, i.e. the minimial polynomial of a primitive d-th root of unity. Another way to define phi_d(x) is as phi_d(x) = (x-z_1)(x-z_2)...(x-z_k) where z_i are all the distinct primitive d-th roots of unity, (hence k = phi(d), the Euler phi-function counting the number of integers <= d which are relatively prime to d.) It is then a theorem that phi_d(x) is irreducible over the rationals. The point is that the factorization of x^n - 1 is known, it is the product of cyclotomic polynomials of the appropriate degree. (If n is prime, then the n-th cyclotomic polynomial is x_(n-1) + x^(n-2) + ... + x + 1.) From: Competitive Enterprise Institute Subject: Re: Inverse trig functions On Sat, 11 Dec 1993 jillstev@aol.com wrote: > On most calculators if you try to find inverse sine of 7 you would get an > error message since the range of sine is from -1 to 1 inclusive. On the > TI-85 you get a complex number. Why? 1) Because the TI-85 is awesome? 2) Because since (e^iz)=cos z + i sin z and (e^(-iz))=cos(-z) + i sin(-z)=cos z - i sin z, we have: sin z = (e^iz - e^(-iz))/2i. To solve sin z = 7, we set: (e^iz - e^(-iz))/2i = 7 e^iz - e^(-iz) = 14i How can we solve this? Let's try saying that z = x + iy. Then: e^(-y + ix) - e^(y - ix) = 14i e^-y e^ix - e^y e^-ix = 14i Set r = e^-y and R = e^y; then we have: r e^ix - R e^-ix = 14i. The argument of the first term is x; the argument of the second term is -x. Since the difference between the terms is 14i, which is a vertical vector in the complex plane, it seems to me that we have two cases: 1) R=r -> e^-y = e^y -> y=0 -> z is real. Then we have R e^ix - R e^-ix = 14i, so: R (cos x + i sin x - cos(-x) - i sin(-x)) = 14i, so: 2 i R sin x = 14 i -> R sin x = 7. I almost forgot; R = 1 because R = e^y and y = 0. So sin x = 7, where x is real: no solution. 2) x = pi/2. e^i(pi/2) = cos pi/2 + i sin pi/2 = i, and e^-i(pi/2) = cos(-pi/2) + i sin(-pi/2) = -i. So the equation r e^ix - R e^-ix = 14 i simplifies to ir + iR = 14 i, or r + R = 14, or e^y + e^-y = 14. This can be easily solved because it's basically a quadratic equation in e^y. Set z = e^y; then z + 1/z = 14 -> z^2 + 1 = 14z -> z^2 - 14 z + 1 = 0. The discriminant here is 192, which is 64*3, so z = 1/2 * (14 +- 8 sqrt(3)) = 7 +- 4 sqrt 3. Of course, x needn't be pi/2. x could be -pi/2 -- in general, x could be pi/2 + k pi where k is any integer, and I suppose the result would be changed accordingly. This makes sense anyway, since sin z is a function of e^z, and e^z is periodic with period 2 pi i. In any case, one solution of sin z = 7 seems to be x + iy = pi/2 + i (7 + 4 sqrt 3). Though I may be wrong. - Alexander "Sasha" Volokh From: Competitive Enterprise Institute Subject: Re: Inverse trig functions On Sat, 11 Dec 1993 efedula@aol.com wrote: > On the subject of calculators, does anyone know how to get the factorial of a > non-integer? I know that the curve y=sqrt(2*pi*x)*(x^x)*(e^-x) is asymptotic > to y=x!, but I want something more exact. Is there a power series for this > (if so, what is it)? Factorials in general are gotten using the gamma function. Its definition is a bit complicated: Gamma (z) = integral(0,inf) [t^(z-1) e^(-t)] dt I'm using z as a variable because this is defined for all complex numbers. But it's also used in its real form -- Gamma (x) -- in probability theory, where you have the gamma distribution involving that formula. Now, let's look at Gamma (1) = int(0,inf) [t^0 e^(-t)] dt = int(0,inf) [e^-t] dt = -e^-inf + e^-0 = 1. In other words, Gamma (1) = 0! Now we can prove that Gamma (z+1) = z Gamma (z). Consider the function G(z) = int(0,R) [t^(z-1) e^-t] dt. This is like the gamma function, only the integral is to R, not infinity. Now integrate by parts, differentiating e^-t and integrating t^(z-1). Then you get: G(z) = [1/z e^-t t^z]{0,R} + 1/z int(0,R) [t^z e^-t] dt Now make R go to infinity. The first term drops out completely because t^z = 0 at t=0, and e^-t t^z = 0 at t=inf. The second term is just 1/z Gamma (z+1). Therefore, Gamma (z+1) = z Gamma(z). We've just proved by induction that for Gamma (z+1) = z! for z with positive real part -- or, for real numbers, Gamma (x+1) = x! for x>0. The gamma function was originally invented as a continuous form of the factorial function. So we can take "factorials" of any positive number. We can also take factorials of non-positive numbers, but this function is undefined at {0, -1, -2, -3, ...} -- non-positive integers. An interesting thing is that Gamma (1/2) = "-1/2 !" = sqrt(pi). This comes from the equality that Gamma (z) Gamma (1-z) = pi/sin(pi*z). Take z = 1/2, and the result follows immediately. Why the equality is true is more complicated and involves a bit of contour integration -- very beautiful, but I'll only do it if someone asks me to. This is how we can use the gamma function to evaluate the factorials of all real numbers except non-positive integers. Another interesting note about factorials: Gamma(x) -> inf as x -> inf. As x-> 0+, Gamma -> inf. As x-> 0-, Gamma -> -inf. In general, the function is defined on lots of vertical "strips": the LARGE strip x>0, and the strips x in (-1,0), x in (-2,-1), x in (-3,-2), etc. In each of those strips, Gamma looks like a "horseshoe" or U-shape. It's right-side up on (0,inf); upside-down on (-1,0); right-side up on (-2,-1), etc. It's very beautiful. Oh, and how can you evaluate it? I don't know. I think you need to use tables. In general, if you want x!, you can just write out Gamma(x+1) and evaluate the integral using numerical methods (approximations). - Alexander "Sasha" Volokh From: Competitive Enterprise Institute Subject: Re: Marsenne pseudoprimes On Sat, 11 Dec 1993, tarrant dennis wayne/jr. wrote: > When new Marsenne pseudoprimes are determined of (2^p)-1, does there necessarily > follow a factorization of (x^p)-1? If so, how does one determine the > factorization? > Specifically, do there exist two polynomials (other than (x-1)(x^10+x^9+...+1) > such that their product is (x^11)-1? > And can you generalize this? 1) What's a Marsenne pseudoprime? 2) Yes. Basically, every polynomial can be factored into linear polynomials (x-a) and quadratic polynomials (x^2 + ax + b) where the discriminant (a^2 - 4b) is negative. To show this in this example, consider the complex function f(z) = z^11 - 1. f(z) = 0 -> z^11 = 1. In the complex plane, every real number has n nth roots -- so 1 has eleven 11th roots. This is because the complex representation of 1 is e^0*pi*i. But 1 is also e^2*pi*i, e^4*pi*i, ..., e^20*pi*i. So the eleventh roots of 1 are: e^ pi*i*0/11 e^ pi*i*2/11 e^ pi*i*4/11 ... e^ pi*i*20/11 Note: if you continue to e^ pi*i*22/11, this is e^2*pi*i = e^0*pi*i. This is because e^z is periodic, with period 2*pi*i. Now if you number these roots z1, z2, ..., z11, clearly z1 = 1. Also, z2 and z11, z3 and z10 -- in general, all pairs z_i and z_(13-i) -- are conjugates of each other. So their product is an irreducible quadratic. In other words: f(z) = (z-z1)(z-z2)(z-z3)(z-z4)(z-z5)(z-z6)(z-z7)(z-z8)(z-z9) (z-z10)(z-z11) = (z-1) (z-z2)(z-z11) (z-z3)(z-z10) (z-z4)(z-z9) (z-z5)(z-z8) (z-z6)(z-z7) But each of these pairs separated by spaces in the previous lines are irreducible quadratics, because they're complex conjugates of each other (i.e., a + ib and a - ib. (z-(a+ib))(z-(a-ib)) = z^2 - 2a + (a^2 - b^2) or something like that, which is a real function). Therefore, x^11 - 1 can be factored into 6 polynomials. The question, though, was are there TWO other polynomials. Well, you can arbitrarily muliply certain factors together until you get 2 polynomials. There are a lot of ways of doing that. For instance: f(x) = f1 f2 f3 f4 f5 f6 = (f1 f2 f3) (f4 f5 f6) = (f1 f2) (f3 f4 f5 f6) = (f1 f3 f5) (f2 f4 f6), etc. To generalize this: Let f be a polynomial of degree n with r real roots (if one root appears twice -- as if (x-a)^2 -- count it as 2 roots). Clearly, n-r must be even, because of complex conjugates. Since there are n-r complex roots, you can multiply complex factors two by two to get real quadratics -- and there are, of course, (n-r)/2 such quadratics. So the number of polynomials that you can factor it into is r + (n-r)/2. - Alexander "Sasha" Volokh From: Android Subject: Contest 3 Round 5 Solutions to Round 5 are available through the mail server. Email iams-request@quack.kfu.com with SOLUTION as the subject to receive the solutions. Subject: Contest 3, Round 6 The following questions are for contest 3, round 6. Complete answers and solutions 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 Dec. 17th, 9:00am PST I. For what values of a does there exist a positive b such that the equation x^2 + a = 2b ln x II. What is the probability that a power of a given positive integer l taken at random begins with a digit q (in decimal notation)? Enjoy, Benjie From: tarrant dennis wayne/jr. Subject: Marsenne pseudoprimes Sorry I wasn't specific enough. A Marsenne pseudoprime is a number of the form (2^p)-1, where p is a prime, but (2^p)-1 is not. Since (2^11)-1(=2047)=23*89, M11 is the first pseudoprime. What I'm asking is why does 2047=23*89 rather than being a prime? There is a base two representation of both 23 and 89. Multiply these two together and you get 111111111111(two). Why can't this be generalized to real polynomial factors (I never intended to deal with complex factors) of (x^p)-1 (where p is the same p in the Marsenne pseudoprime)? Or, can it be factored in the same way? I'll look into "repunits"? Thanks for the help. Wayne Tarrant From: David G Radcliffe Subject: Re: Marsenne pseudoprimes A prime of the form 2^p - 1 is called a Mersenne prime (not Marsenne). If 2^p - 1 is prime, then p must also be prime, because 2^(mn) - 1 = (2^m - 1) (2^(m(n-1)) + 2^(m(n-2)) + . . . + 1). The largest known prime number is 2^756839 - 1, which is Mersenne. If p is prime but 2^p - 1 is composite, then 2^p - 1 is called a Mersenne pseudoprime. Now I will answer the original question. There is a basic result in algebra called Eisenstein's Criterion. It says the following: Let f(x) = a_n x^n + . . . + a_1 x + a_0 be a polynomial with integer coefficients, and let p be a prime number. Suppose that the following conditions hold: (1) p does not divide a_n, (2) p divides all of the other coefficients, (3) p^2 does not divide a_0. Then f is irreducible over the rational numbers. We can use this result to prove that f(x) = (x^p - 1)/(x - 1) is irreducible when p is prime. Let g(x) = f(x+1) = [(x+1)^p - 1]/x. Then g(x) = x^{p-1} + p x^{p-2} + . . . + p. Each coefficient (except for the leading coefficient) is divisible by p, and the constant term is not divisible by p^2. Therefore g(x) is irreducible, so f(x) is irreducible. Most introductory abstract algebra texts give proofs of Eisenstein's criterion. I suggest "Contemporary abstract algebra" by Joseph Gallian, or "A first course in abstract algebra" by John Fraleigh. -- Dave Radcliffe From: Android Subject: Correction to Round 5 The first question should read: to what value of ....... does the equation ..... has only a unqiue solution Sorry. Benjie From: Android Subject: result, Contest 5, round 5 Here are the results of contest 3, round 5, congrats to all who participated and those who tried but did not turn the solutions in. From TavenerS@lilhd.logica.com 17/17 From radcliff@csd4.csd.uwm.edu 17/17 From wgd@houston.geoquest.slb.com 15/17 From pasquale@xsft2.ico.olivetti.com 12/17 From rose@garnet.acns.fsu.edu 11/17 Benjie From: Android Subject: Solutions to Contest 3, Round 5 SPOILER I. Find all positive integer solutions (x,y) of the equation x^y - y^x=x+y. Answer: (2,5) Total Points: 8 Solution: Since both x and y are positive, x^y > y^x, or (ln x)/x > (ln y)/y. Using derivative of (ln x)/x, which is (1-ln x)/x^2, we find that the function is increasing on (1,e] and decrease for x >= e. Since 2 < e < 3 and (ln 4)/4 = (ln 2)/2 < (ln 3)/3, we get the following list of pairs of (x,y) that satisfy the inequality x^y > y^x (1) (x, 1) with x > 1 (2) (2, y) with y >= 5 (3) (3,2) (4) (x,y) with 3<= x < y Assume w = x^y - y^x - x - y. for (1) and (3), w != 0. For (2), w = 0 only with y = 5. So (2,5) is an answer. For 3 <= x <= y, x^y-x > y^x+y, so w > 0. Therefore, the only solution is (2,5). II. Is it possible to divide a pentagon into two congruent pentagons? Answer: Yes Points: 9 Solution: (0,3) + | \ | \ (2,2) | \ + | \ | \ | (1,1) \ | \ | +-----+ \ | | (2,1) \ | | \ +-----+-----------------+ (0,0) (1,0) (4,0) or ones with similar angle is a possibility. or /\ 5:angle b /5 \ /\ / \ / x / \ 2:angle a-b / \/2 3 \ 3:angle 360-a / -y- \ \ / z 1 4\ 4:180-angle a /--------------\---w-- 1:angle a side x, y, z and w are equal From: Ariel Landau Subject: Re: Inverse trig functions On Sat, 11 Dec 1993 jillstev@aol.com wrote: > On most calculators if you try to find inverse sine of 7 you would get an > error message since the range of sine is from -1 to 1 inclusive. On the > TI-85 you get a complex number. Why? > The answer is easy: The trigonometric functions can be generalised as to be defined on the whole complex plane, and not only in the real line The usual definitions are sin z = (exp (iz) - exp (-iz))/2i coz z = (exp (iz) + exp (-iz)/2 where exp(z) = 1 + z + z^2/2! + ... + z^n/n! + ... With this definition is NOT true that |sin z| <= 1 for every z That is, there IS a complex number z which satisfies the equation sin z = 7 (I guess that one of those complex numbers is given by your calculator when you ask for the inverse sin of 7) The situation may be compared to the following one: Most calculators give an error message when you ask for the square root of -9, but some calculators (may be your calculator is one of them) give the answer 3i Ariel From: Ariel Landau Subject: Re: Inverse trig functions On Sat, 11 Dec 1993 efedula@aol.com wrote: > On the subject of calculators, does anyone know how to get the factorial of a > non-integer? I know that the curve y=sqrt(2*pi*x)*(x^x)*(e^-x) is asymptotic > to y=x!, but I want something more exact. Is there a power series for this > (if so, what is it)? > There exist the so called 'Gamma Function' (I shall denote it by g(x)) which is defined for all the positive reals and has the property that g(x+1) = x! for every non-negative integer x. The best known representation of g(x) (which is not the only one) is: integral from 0 to infinity of ( (t^x)exp(-t)dt ) There is a power series in NEGATIVE powers of x, called 'the Stirling asymptotic formula' which also represents the Gamma function. The formula for the curve you gave is just the first term of that expansion. Ariel From: Kermit Rose Subject: factorials and gamma function revisited Derivation of power series for gamma function. infinity gamma(p) = integral ( e^[-t] t^[p-1] dt ) t = 0 x define gamma(p,x) = integral ( e^[-t] t^[p-1] dt ) t=0 Then gamma(p) = lim gamma(p,x) x --> infinity infinity gamma(p,x) = [e^(-x)] [ x^p ] sum x^k /[p(p+1)(p+2)...(p+k) ] k = 0 Note that if p is a positive integer then infinity gamma(p,x) = e^(-x) (p-1)! sum x^(k+p)/[ (k+p)!] k = 0 p-1 = (p-1)! e^(-x) [ e^x - sum x^k/k! ] k=0 and thus gamma(p) = (p-1)! From: Android Subject: POD Find all real numbers a for which there exist non-negative real numbers x_1, x_2, x_3 ... x_5 satisfying the relations k=5 sum(k*(x_k)) = a k=1 k=5 sum(k^3 * (x_k)) = a^2 k=1 k=5 sum(k^5 * (x_k)) = a^3 k=1 Enjoy and happy mathing, Benjie From: Android Subject: SPOILER - Summation Problem SPOILER Follows >From a_rubin@dsg4.dse.beckman.com POD 12/15/93 Find all real numbers a for which there exist non-negative real numbers x_1, x_2, x_3 ... x_5 satisfying the relations k=5 sum(k*(x_k)) = a k=1 k=5 sum(k^3 * (x_k)) = a^2 k=1 k=5 sum(k^5 * (x_k)) = a^3 k=1 SPOILER Answer: a = 0,1,4,9,16,25 Proof: Clearly a=0 is possible (all x_k = 0), and a < 0 is not possible, so assume a > 0. Write x_k = a y_k / k Then, sum (y_k) = 1 sum (k^2 y_k) = a sum (k^4 y_k) = a^2 Hence the condition is that (a,a^2) is in the convex hull of the points (k^2,k^4), k=1..5. But the curve y=x^2 is convex, so no point on the curve is a non-trivial convex combination of points on that curve. Hence one y_k is 1, and the rest 0, so a = k^2. From: Android Subject: P.O.D. Determine m so that the equation in x x^4 - (3m + 2)x^2 + m^2 = 0 has four real roots in arithmetic progression. Enjoy, Benjie From: Android Subject: Results of Contest 3 Round 6 Here is the result of the last round of the contest. Congrats to everybody. ivoigt@rz.uni-leipzig.de 17/17 radcliff@csd4.csd.uwm.edu 17/17 pasquale@xsft2.ico.olivetti.com 15/17 wgd@houston.geoquest.slb.com 9/17 Benjie From: Android Subject: SPOILER -- Solutions to Contest 3, Round 6, Also Available Through Mailserver Here are the solutions for contest 3 round 6, I used the ones submitted by ivoigt@rz.uni-leipzig.de for that he did most of the work the way I did and the solution book did. Anyway, here is the solution: From ivoigt@rz.uni-leipzig.de I. For what values of a does there exist a positive b such that the equation x^2 + a = 2b ln x (*) has only a unique solution? If (*) has a unique solution y for some a, b, the two functions f(x) = x^2 + a and g(x) =2b ln x must touch each other in the point with the abscissa y, i.e. f(y) = g(y) and f'(y) = g'(y). We get the equations y^2 + a = 2b ln y 2y = 2b/y ===> y^2 = b. Plugging this into the first equation: b + a = b ln b, a = b (ln b - 1) We have to determine for which a there exists a b such that this equation holds, i.e. the range of the function h(x) = x(ln x - 1). We have h'(x) = ln x h''(x) = 1/x > 0, i.e. h is convex. Because of h'(1) = ln 1 = 0 h will have a global minimum at x = 1. The value of this minimum is -1. Since h(x) goes to infinity if x goes to infinity, the range of h will be the interval [-1, oo). That is, the values a can take to fulfil the conditions of the problem are the real numbers >= -1. II. What is the probability that a power of a given positive integer l taken at randum begins with digit q (in decimal notation)? Be this probability denoted by P(q). If your integer l is 1 or a power of 10 the answer is obvious: P(1) = 1, P(q) = 0 for q <> 1. Suppose now l is not 1 or a power of 10. In that case lg l is an irrational number. The n-th power of l begins with q if and only if lg q <= Frac(n lg l) < lg (q+1). The fractional parts of the multiples of any irrational number are uniformly distributed over [0,1]. Therefore, the probability that a fractional part lies within [r,s] will be s-r (for s>=r, of course). Thus we get: P(q) = lg (q+1) - lg q independently of l. ------------ Benjie's Comments: Note that in the last part a theorem was indirectly used: Fractional Parts Theorem: Let a be an irrational number and b an arbitrary real number; let I be an interval of length h contained in the segment [0,1]. Consider the infinite arithmetic sequence a+b, a+2b, ..., na + b, ... then the probability that the fractional part of an arbitrary term of the sequence belongs to the interval I is equal to h. Benjie From: Android Subject: Results -- CONTEST 3 -- Results Here is the result of contest 3. I say it is a success. I had so many good solutions sent in and so many people deserved to win, and I could only make ...... Okay, I will stop that boring speech. Here are the winners, they get our undivided respects. I hope people will keep on posting interested problems, ideas and solutions. Happy mathing, Benjie --------------Merry Christmas and Happy New Year--------------- ----------------------- To Everybody -------------------------- Place | Rnds | Email Address | Total Score ----------------------------------------------------------------------- Grand Prize | 5 | radcliff@csd4.csd.uwm.edu | 85/85 ----------------------------------------------------------------------- Runner-Ups Division I (participated in at least at least four rounds) ----------------------------------------------------------------------- First Place | 6 | pasquale@xsft2.ico.olivetti.com | 95/102 Second Place | 5 | TavenerS@lilhd.logica.com | 72/85 Third Place | 4 | wgd@houston.geoquest.slb.com | 49/68 Division II (participated in three rounds) ----------------------------------------------------------------------- First Place | 3 | cei@access.digex.net | 46/51 Second Place | 3 | gt0095a@prism.gatech.edu | 44/51 Third Place | 3 | dawagner@phoenix.Princeton.EDU | 40/51 Division III (participated in two rounds) ----------------------------------------------------------------------- First Place | 2 | elessar@hermes.acm.rpi.edu | 34/34 Second Place | 2 | wlodek@atg.wiltel.com | 34/34 Third Place | 2 | mau@beatles.CSELT.STET.IT | 33/34 Division IV (participated in one round) ----------------------------------------------------------------------- Tie For | 1 | Benjamin.J.Tilly@Dartmouth.EDU | 17/17 First Place | | gintis@econs.umass.edu | | ivoigt@rz.uni-leipzig.de | | Kwok-Shing.Leung@GS133.SP.CS.CMU.EDU | | luzeaux@etca.fr Winners: The following people (include above) sent in solutions, they are all winners. List is in alphabetical order. alanm@outage.efi.com Benjamin.J.Tilly@Dartmouth.EDU cei@access.digex.net clong@cnj.digex.com craigj@irus.rri.uwo.ca darglass@owlnet.rice.edu dawagner@phoenix.Princeton.EDU efedula@aol.com elessar@hermes.acm.rpi.edu gaps05@udcf.gla.ac.uk gintis@econs.umass.edu gt0095a@prism.gatech.edu ivoigt@rz.uni-leipzig.de Kwok-Shing.Leung@GS133.SP.CS.CMU.EDU lip@maths.mu.oz.au luzeaux@etca.fr mau@beatles.CSELT.STET.IT maxime@srcinf.sochi.su mic@cs.ucsd.edu mknapp@isp.nwu.edu pasquale@xsft2.ico.olivetti.com radcliff@csd4.csd.uwm.edu rajeev@cs.utk.edu relyea@seas.smu.edu rose@garnet.acns.fsu.edu STBC@music.cc.uga.edu TavenerS@lilhd.logica.com Van@cup.portal.com was@sunset.cse.nau.edu wgd@houston.geoquest.slb.com wlodek@atg.wiltel.com Congrats to All. From: pasquale%xsft2@Olivetti.Com (Pasquale Petrosino) Subject: SPOILER - POD 12/17/93 POD 12/17/93 Determine m so that the equation in x x^4 - (3m + 2)x^2 + m^2 = 0 has four real roots in arithmetic progression. Enjoy, Benjie SPOILER Follows Answer: The four real roots must be of the form: -3a, -a, +a, +3a, because the equation is bi-quadratic, and the roots have to be in arithmetic progression. More: x_1 * x_2 * x_3 * x_4 = 9 a^4 = m^2 , so: a^2 = abs(m)/3 Next: x_1 * x_2 + x_1 * x_3 + x_1 * x_4 + + x_2 * x_3 + x_2 * x_4 + + x_3 * x_4 = -(3m + 2) = -10 a^2. Finally: 3m + 2 = 10 abs(m)/3, 10 abs(m) - 9m = 6 ; with two solutions: (m>=0): m = 6 (m<0) : m = -6/19 Actual roots can be derived by: x^4 - 20 x^2 + 36 = 0 ==> -3 sqr(2), -sqr(2), sqr(2), 3 sqr(2) x^4 - 20/19 x^2 + 36/361 = 0 ==> -3 sqr(2/19), -sqr(2/19), sqr(2/19), 3 sqr(2/19) From: Kermit Rose Subject: submission Define sum_k(x) by sum_k(0)=0 sum_k(1)=1 sum_k(x-1) + x^k = sum_k(x) note that sum_0(n) = 1 + 1 + 1 + .... 1 = n sum_1(n) = 1 + 2 + 3 + ... + n = (1/2) n^2 + (1/2) n sum_2(n) = 1^2 + 2^2 + ... + n^2 = (1/3) n^3 + (1/2) n^2 + (1/6) n Prove that the first two terms of the polynomial for sum_k(n) are [ 1/(k+1)] n^(k+1) and [1/2] n^k From: Android Subject: SPOILER -- Arithmetic Progression POD I still prefer to have solutions to POD send to me. So ...... SPOILER FOLLOWS >From tulled@rpi.edu > Determine m so that the equation in x > > x^4 - (3m + 2)x^2 + m^2 = 0 > > has four real roots in arithmetic progression. Well if r is a solution, -r is a solution so the roots are -s, -r, r, s where r Subject: P.O.D. 12/21 From: benjie@quack.kfu.com Find the probability that a randomly chosen power of a number l, distinct from a power of ten, begins with a given combination of digits q1, q2, ... qr, where q1 != 0. Derive, in particular, the fact that a power of l can begin with any combination of digits q1, q2, ... qr with q1 != 0. From: Chris Long Subject: Re: P.O.D. (SPOILER) I don't know what is meant by a random power, but l^n starts with c \in Z+ if c*10^m <= l^n < (c+1)*10^m for some m \in Z+, so m+log(c) <= n*log(l) < m+log(c+1) or log(c) <= n*log(l)-m < log(c+1). But if l is an integer not a power of 10 log(l) is irrational and hence n*log(l) is uniformly distributed modulo 1, thus this occurs with probability (defining this to be natural density) log(c+1)-log(c) = log(1+1/c). -Chris {clong@cnj.digex.com} From: Competitive Enterprise Institute Subject: Re: Brainteasers - SPOILER for B99 On Wed, 22 Dec 1993, Android wrote: > B99. Three line segments are drawn in a convex quadrilateral: a > diagonal and both midlines (the segments that join the midpoints of > opposite sides). The other diagonal divides one of these segments in > half. Prove that it bisects the other two segments as well. SPOILER..... Let A, B, C, D be the vertices of the quadrilateral in some coordinate system. Let E, F, G, H be the midpoints of AB, BC, CD, and DA, respectively. One diagonal is AC, and the two midlines are EG and FH. The other diagonal is BD. We are given that BD bisects either AC, EG, or FH. Note: 1/2 (E+G) = 1/2 (1/2 (A+B) + 1/2 (C+D)) = 1/4 (A+B+C+D) and 1/2 (F+H) = 1/2 (1/2 (B+C) + 1/2 (A+D)) = 1/4 (A+B+C+D). So EG and FH bisect each other. If BD bisects one, it must bisect the other. * Suppose that BD bisects AC. Then 1/2 (A+C) = k B + (1-k) D. So 1/2 (E+G) = 1/4 (A+B+C+D) = k/2 B + (1-k)/2 D + 1/4 B + 1/4 D = (1/4 + k/2) B + (1/4 + (1-k)/2) D The coefficient of B and that of D add up to 1, so BD bisects EG. Hence BD bisects FH. * Suppose that BD bisects EG and FH. Then 1/2 (E+G) + 1/4 (A+B+C+D) = k B + (1-k) D. So 1/2 (A+C) = 2 (k B + (1-k) D - 1/4 B - 1/4 D) = (2k - 1/2) B + (2(1-k) - 1/2) D. The coefficient of B and that of D add up to 1, so BD bisects AC. There's probably a much simpler solution, but I didn't have the heart to look for it. - Alexander "Sasha" Volokh From: Competitive Enterprise Institute Subject: Re: Brainteasers - SPOILER for B98 On Wed, 22 Dec 1993, Android wrote: > B98. A chessboard is covered with 32 dominoes so that each domino > covers exactly two squares. After counting the dominoes oriented > horizontally and vertically, it was found that there are evenly many > dominoes with each orientation. Will this be true for any covering of > the chessboard with 32 dominoes? SPOILER.... Suppose that there are H horizontal dominoes and V vertical dominoes, where H + V = 32. Either H and V are both even or they are both odd. The horizontal dominoes each take up 2 columns. Let's say that they "start" in column i if they take up columns i and i+1. Let v1, ..., v7 be the number of vertical dominoes that start in columns 1, ..., 7. (v1 + ... + v7 = V.) Now, the number of horizontal dominoes that occupy any column must be even. This is because the remaining spaces in that column are occupied by vertical dominoes, each of which use 2 spaces in that column. The number of horizontal dominoes occupying column 1 is v1. column 2 v1 + v2. column 3 v2 + v3. ... column 7 v6 + v7. column 8 v7. Therefore, v1 is even. v1 + v2 is even, so v2 is even. v2 + v3 is even, so v3 is even, etc. So v1, ..., v7 are all even. Therefore, V is even so H is even. From: Competitive Enterprise Institute Subject: Re: SPOILER FOR DOMINO QUESTION Whoops! I transposed the words "vertical" and "horizontal," I think, in my spoiler. Pretend I said h1, ..., h7, with h1 + ... + h7 = H, and each of THOSE are even! A SIMPLER ANSWER, PROVIDED BY MY BROTHER, FOLLOWS: Color the chessboard rows alternating black and white. Then a horizontal domino will take up 0 or 2 white spaces, and a vertical domino will take up 1 white space. Therefore, both the number of horizontal dominoes and the number of vertical dominoes must be even. - courtesy of Eugene Volokh From: Android Subject: Huebert's Probelms I meant Problems...... Anyway, I was wondering if anyone could post a summary on the famous set of problems Huebert(sp?) gave. I think there are 21 of them, and it would be interesting to see the actual problems and progresses. Just a thought, Benjie H^2 to everybody (H^2 (H squared) = Happy Holidays) From: Android Subject: POD Dec. 28 Let p and be natural numbers such that p/q = 1 - 1/2 + 1/3 - 1/4 + ... - 1/1318 + 1/1319 Prove that p is divisible by 1979. Enjoy, Benjie From: Android From jir@MIT.EDU Wed Dec 29 21:57:37 1993 Subject: Irreproducible Results Benjie -- I noticed your posting on one of the USENET news groups, and thought your club members might be interested in some of the things we are up to here at the Journal of Irreproducible Results. I first got involved with JIR at the suggestion of Martin Gardner, a fellow whom you probably know well. The club sounds like a terrific idea. Sincerely and irreproducibly, Marc Abrahams, editor, The Journal of Irreproducible Results (jir@mit.edu) ==================================================================== Please forward the item below to anyone who might be interested ==================================================================== The Mini-Journal of Irreproducible Results ("Mini-JIR") The Official Electronic Mini-Organ of The Society for Basic Irreproducible Research Mini-JIR is produced jointly by The Journal of Irreproducible Results (JIR) and The MIT Museum. Mini-JIR publishes news about overly stimulating research and ideas. It contains abstracts and news from JIR, the world's oldest, largest, and best-known science humor journal. =--------------------------- How to Subscribe Mini-JIR is an electronic publication, available over the Internet, free of charge. We expect to publish 6-12 issues per year. To subscribe, send a brief E-mail message to either one of these addresses: LISTSERV@MITVMA.MIT.EDU or LISTSERV@MITVMA The body of your message should contain ONLY the words "SUBSCRIBE MINI-JIR" followed by your name. Here are two examples: SUBSCRIBE MINI-JIR Irene Curie Joliet SUBSCRIBE MINI-JIR Nicholai Lobachevsky =----------------------------------------------------------------- Soon after you have signed on, you should receive an automatic confirmation notice (written in LISTSERV jargon, I'm afraid) that will also tell you how to obtain back issues. [If you do NOT receive a confirmation notice the same day, it might mean that LISTSERV has decided to be cranky and pretend that it doesn't understand your e-mail address. If you are met only with silence, please don't hesitate to let me know (my address is jir@mit.edu), and I'll manually add you to the list.] --Marc Abrahams, editor From: s.virtes@genie.geis.com Subject: FLT & hello Dear Travis, (TKIDD) I very much enjoyed your proof of FLT. Such proofs are always a good test of wits. I had to break it into lines and look at the lines one at a time. I do some topics on local BBSs, and recommend writing proofs with one result per line, with the lines numbered to make discussion easier. Anyway ... in the LEMMA, in going from > = (x+y)^(n-1) > - [x^(n-1) - x^(n-2)y + x^(n-3)y^2 ... - xy^(n-2) + y^(n-1)] to > = { [x^(n-1) + (n-1)x^(n-2)y + [(n-1)(n-2)x^(n-3)y^2]/2 + ... > + [(n-1)(n-2)(n-3)...*3*2*1]y^(n-1)] } > - [x^(n-1) - x^(n-2)y + x^(n-3)y^2 ... - xy^(n-2) + y^(n-1)] you seem to be using an identity (x+y)^(n-1) = x^(n-1) + (n-1)x^(n-2)y + [(n-1)(n-2)x^(n-3)y^2]/2 + ... + (n-1)!*y^(n-1). Although this looks like the Binomial Theorem, when I applied the Binomial Theorem, I got (x+y)^(n-1) = x^(n-1) + (n-1)x^(n-2)*y + (n-1)(n-2)x^(n-3)*y^2/2! + ... + (n-1)!xy^(n-2)/(n-2)! + y^(n-1). In any case, the first & last terms of the expansion MUST be x^(n-1) and y^(n-1). I haven't checked to see how this affects the lines that follow. Looks like FLT is still a pain, after all these years. - scv From: Android Subject: You could think of it as a P.O.W. or just a discussion topic. I got this out of the current issue of Quantum, it's very interesting, I have been able to solve the first couple of questions, but not the last two. ------Here we go----------- (BTW, the original article was written by George Berzsenyi) We are looking at a periodic sequence of 0's and 1's defined by the equation a_n = (1-((-1)^f(n)))/2, n = 0,1,2,... where f(n) is to be specified. For a simple choice, we could have f(n)=n and we have a sequence of (0,1,0,1,...) For f(n)=n+1 we have (1,0,1,0,...) If f(n) = [n/2], where [x] denotes the greatest integer less than or equal to x, we have (0,0,1,1,0,0,1,1,...) Questions: 1. Prove that the choice f(n) = [ (n^3)/2 ] produce the sequence (0,0,0,1,0,0,0,1,...) 2. Construct the functions that will similarly generate the two other nontrivial sequences of period length 4: (0,1,1,0,0,1,1,0...) and (1,0,0,1,1,0,0,1,...) 3. Do all polynomials f(n) lead to periodic sequences a_n? 4. Can one determine from the degree and/or coefficients of f(n) the period length of a_n? 5. Can one construct in such manner all periodic sequences of 0's and 1's? Enjoy, Benjie From: TKIDD@CLEMSON.CLEMSON.EDU Subject: Divisibility by 7. I think a number is divisible by 7 if the number that is written the same way in base 3 is also divisible by 7. (Note, if a number base 10 is not a valid base 3 number, you can make it so by sub- tracting any digit greater than 2 by 3 and adding 1 to the digit immediately to the left (if there is no digit, assume 0). Do this until you have a valid base 3 number. -Travis From: Android Subject: POD - Solid Geometry Problem 1/4 From: benjie@quack.kfu.com The sum of all the face angles at all but one of the vertices of a given simple polyhedron is 5160. Find the sum of all the face angles of the polyhedron. Benjie From: "Mr C. Brown" Subject: [Q] 3D values from 2D images Please mail any results, comments, flames to me ...thank you. I am involved in a research project to measure the sizes of heart valves. Conventional morphometry of heart valves has employed a hands on approach which may distort the anatomy. I aim to use captured video images and a measuring program on a P.C. The idea is to look at the heart from 3 orthoganal points and grab an image. These 3 images analysed to give distances,circumferances and areas. The problem is how to convert the measurements from the three 2D images into a value for the 3D object? One nice thing is that the objects being measured can be treated as a flat plane in the 3D space (unless somebody very clever know how to do this for a non-flat plane?!!) To be honest I do have answers for point to point distances and area, it is circumferances that are causing the problem. Any suggestions welcome as well as solutions to each of the problems. Be warned my math is basic and I hope to turn these solutions into something which will work on a spraedsheet! TIA Chris Brown ============================================================================ | Cardiac Unit, R.L.C.H., Alder Hey, Eaton Rd, Liverpool, L12 2AP | | chris47@liverpool.ac.uk | ============================================================================ From: Competitive Enterprise Institute Subject: Some problems 1) Prove that e is irrational. (Very simple and elegant proof!) 2) Prove that if you write a computer program to calculate the digits of pi, this program must produce a wrong digit eventually. - Alexander "Sasha" Volokh From: a_rubin@dsg4.dse.beckman.com (arthur rubin) Subject: Re: Some problems The original message: 1) Prove that e is irrational. (Very simple and elegant proof!) 2) Prove that if you write a computer program to calculate the digits of pi, this program must produce a wrong digit eventually. - Alexander "Sasha" Volokh Reply: (1) I haven't seen a simple proof. I have seen a proof of the full result that Sum(a_i e^b_i) = 0 for algebraic a_i and distinct algebraic b_i, implies all a_i are 0. (2) There is a computer _program_ that will, for a given N, calculate N digits of pi correctly. For any computer, and for sufficiently large N, the program won't run on that computer because of memory constraints. From: Competitive Enterprise Institute Subject: Re: Some problems On Wed, 5 Jan 1994, arthur rubin wrote: > 1) Prove that e is irrational. (Very simple and elegant proof!) > > 2) Prove that if you write a computer program to calculate the digits of > pi, this program must produce a wrong digit eventually. > > Reply: > > (1) I haven't seen a simple proof. I have seen a proof of the full result > that Sum(a_i e^b_i) = 0 for algebraic a_i and distinct algebraic b_i, > implies all a_i are 0. There *is* a very simple proof, in a few lines, easily understandable by someone with no knowledge of calculus or exponentials! > (2) There is a computer _program_ that will, for a given N, calculate N > digits of pi correctly. For any computer, and for sufficiently large N, > the program won't run on that computer because of memory constraints. Let me rephrase the question. Why is it impossible to generate computer output (assuming no user input) that does not repeat itself (i.e., that is not periodic)? - Alexander "Sasha" Volokh From: Chris Long Subject: Spoiler for #1 Using Taylor series w/ remainder e = 1/0! + 1/1! + ... + 1/i! + c/(i+1)!, where 0=q. But e*n! = z (\in Z+) + c/(n+1); hence if n is large enough 0 < c/(n+1) < 1 (that such an n exists follows from the finiteness of e, e.g. take n = ceil(e)) and so e cannot be rational. -Chris From: Chris Long Subject: Spoiler for #2 Assuming a totally finite machine, it can only have a finite number of states (albeit large), hence any program must be eventually periodic. This is assuming no tricks (e.g. Geiger counter or thermometer, breakdown of some kind), of course. Then again, any given computer will eventually stop working, and so every program is trivially eventually periodic. -Chris From: Android Subject: SPOILER -- Polyhedron problems SPOILER Follows >From wilson@web.ctron.com > 1/4 From: benjie@quack.kfu.com > > The sum of all the face angles at all but one of the vertices of a > given simple polyhedron is 5160. Find the sum of all the face angles > of the polyhedron. I assume that by "simple polyhedron" is meant "convex polyhedron". Now, (the degree measure of) the angles of any given face add up to 180(s-2), where s is the number of sides of the face. The sum of all the face angles of the polyhedron is then A = 180(S-2n), where S is the total number of face sides, and n is the number of faces. Since two faces meet at each edge of the polyhedron (by convexity), the total number of face sides must be even. Hence S = 2k for some integer k. Thus A = 180(2k-2n) = 360(k-n) = 360j, for some integer j. Now let V be the sum of the face angles at the vertex in question. Since 0 < V < 360 (by convexity), we have 5160 < 5160+V < 5520. But 5160+V = A = 360j, so 5160 < 360j < 5520 ==> 14.333... < j < 15.333... ==> j = 15 since j is an integer. This gives A = 5400, the required value. It remains only to show that a suitable polyhedron exists. Let P be a right pyramid with a regular 16-gon base, whose lateral sides have 15 degree apex angles. The sum of the face angles at all vertices by the apex is 5160, while the sum of all vertices is 5400. Puzzle: Does these exist a nonconvex polyhedron fulfilling the original conditions for which A is not 5400? From: TKIDD@CLEMSON.CLEMSON.EDU Subject: Is this true?? Is it true that if z^p + x | z^(p+1) then z^p | x ???? -Travis From: Competitive Enterprise Institute Subject: Re: Is this true?? On Mon, 10 Jan 1994 TKIDD@CLEMSON.CLEMSON.EDU wrote: > Is it true that if z^p + x | z^(p+1) then > z^p | x ???? > > -Travis No, for instance 3^3 + 18 = 27 + 18 = 45, and 45 | 3^2. But 27 is not divisible by 18. - Alexander "Sasha" Volokh (I hope that | means "divisible by," and that z and x are just integers and p is supposed to be a prime.) From: "David A. Wagner" Subject: Re: Is this true?? > > On Mon, 10 Jan 1994 TKIDD@CLEMSON.CLEMSON.EDU wrote: > > > Is it true that if z^p + x | z^(p+1) then > > z^p | x ???? > > No, for instance 3^3 + 18 = 27 + 18 = 45, and 45 | 3^2. But 27 is not > divisible by 18. > > (I hope that | means "divisible by," and that z and x are just integers > and p is supposed to be a prime.) > Uhh.. I believe standard notation is that | means "divides"; that is, d|n iff there is an integer k with n=dk. For example, 2|8, 3|21, and 1|n for all n. Back to the original statement: it is still false. Take z=6, p=2, x=18. Then z^p+x=54, z^(p+1)=216, and since 54|216 we do indeed have z^p+x|z^(p+1). But z^p=36, x=18, and 36 does not divide 18, so this is a counterexample... This counterexample might suggest that z^p+x|z^(p+1) implies x|z^p. The latter assertion isn't true, either. Let z=3, p=2, x=18. Then z^p+x=27, z^(p+1)=27, and indeed 27|27. On the other hand, we have that x=18, z^p=9, and 18 does not divide 9. Does that answer your question, I hope? ------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From: s.virtes@genie.geis.com Subject: How is the Society these days Greetings, I was receiving the IAMS mailing a few months ago, and enjoying it quite a bit. One day, it just stopped. I would like to receive the mailings again ... I wasn't exactly an inactive member ... what should I do to keep in touch? - scv s.virtes@genie.geis.com From: Android Subject: Integration Problem Integrate or prove that it is impossible to do so explicitely, \int tan( e^x ) dx Have fun, Benjie From: garridok@land.vf.ge.com (Kenneth L. Garrido - MMC) Subject: Determining error in interpolated quaternions You have a series of time-ordered quaternions. They are evenly spaced. You desire a quaternion at a time which is inclusive to the profile but not exactly represented (i.e. series is on the even second, you want value at 0.5 second). So you do an interpolation. That interpolation includes a term which describes the error (order of mag or maximum, whatever). The interpolation was done in a element-wise fashion, so you have four of these error values. How do you bound the angular error in the interpolated quaternion? Is this approach feasible or should a different method be used: like decomposing the quaternions within the profile into alpha, beta, gamma angles (axis of rotation) and a delta (rotation angle) and then interpolating the angles ? -- Kenneth Lee Garrido Landsat 7 High Resolution Multi-Spectral Imager Geometry Algorithms (whew!). garridok@land.vf.ge.com From: efedula@aol.com Subject: A physics problem... There are 2 point masses of mass m kg, spaced r meters apart. Assuming that there are no external forces act ing on this system, find t, the time (in seconds) at which they will collide if they are at rest at t=0. E From: csaba@teleport.com (Csaba Gabor) Subject: Re: A physics problem... I like this problem. I have what I think is a nice solution. I set as the origin the collision point, then figure out the diff EQ for the distance between the two masses as a function of time. My final answer is time of collision = pi * sqrt (r^3/(8 * G * (m1 + m2))) where the (point) masses have weight m1, m2 and G is the gravitational constant. Csaba From: "David A. Wagner" Subject: Rubik's subcubes I just got done with some take-home finals, and I noticed the list is pretty quiet, so I thought I'd share a problem I discovered over Christmas break... My dad loves playing with the Rubik's cube - we've got a 4x4x4. He idly mentioned that a 4x4x4 was all you needed, since you could use it as a 3x3x3 if you wished - of the four rows that you can turn, pretend the two middle ones are joined together; that is, if you turn one of the middle rows, turn the other the same way. [Pretend they are glued together if you wish.] Of course I immediately noticed that you could use a 4x4x4 as a 2x2x2 or a 1x1x1, as well. But a 3x3x3 cannot be used as a 2x2x2. In a sense, the 2x2x2 is a ``subcube'' of the 4x4x4 cube, but not of the 3x3x3 cube. Ahh, enough setup - now for the questions: When is the MxMxM cube a subcube of the NxNxN cube? How many different ways is the MxMxM a subcube of the NxNxN? Do you notice the pattern forming? Can you prove why it happens? [Here's what I mean by ``different ways the MxMxM is a subcube of the NxNxN'': If you have a 5x5x5, you can turn it into a 3x3x3 by mentally gluing the middle three rows together, or you can pretend to glue the left two rows together and the right two rows together. You schematically indicate this by saying a 5x5x5 becomes a 3x3x3 with the two patterns 1-3-1 and 2-1-2: each number indicates how many rows of the 5x5x5 become one row of the 3x3x3. I hope that's clear. If not, send me some email and I'll try to explain it better...] Good luck! Have fun! ------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From: Android Subject: P.O.D. From Quantum, Jan 1994 M101 Thirty Plus. The siz most active students in a class formed 30 different committees, every two of which intersected with each other - that is, had at least one member in common. Prove that it's possible to form one more committee intersecting with each of these 30 committees. Enjoy, Benjie From: Android Subject: Probability and/or Genetics If a couple was to stop having babies after they've got both boy and girl, in other word, they would stop right after they have had kids in both sex, then what would be the average number of kids in an average family? I got this problem from a contest I was participated in, I thought it was intriguing. I had a solution, but I wasn't sure. Enjoy, Benjie From: Steve Wildstrom Subject: Re: Probability and/or Genetics SPOILER SPOILER SPOILER Three. First we have to make a couple of assumptions: 1) Our probability space consists of thoses couples who want to have a boy and a girl and are successful in having as many children as they want. In other words, we're ignoring everyone else and ingnoring the difficulty anyone may have conceiving. 2) The probability of having a boy or a girl is equal. In fact, the probability of having a boy is a very little bit greater. Given those assumptions, consider all couples having two children. There are four possible outcomes: BB, BG, GB, GG. So the probabability of having one of each sex is .5. The half of couples who get two of the same sex will go on. Their possibilities are BBB, BBG, GGB, GGG. So again, the probability of reaching your goal with this kid is .5, but the population has been be halved, so the overall probability is .24. Similarly, the probability declines by a power of two at each step. The average number of children is the sum of the probability of having n children times n. This works out to the infinite sum of +inf sum (1/2^i)*(i+1) = 3 i=1 ---------------------------------------------------------------------- Steve Wildstrom Business Week Washington Bureau wild@access.digex.net "These opinions aren't necessarily mine or anyone else's." ----------------------------------------------------------------------- From: s.jacques@genie.geis.com Subject: SPOILER? Prob/Genetics Sub: SPOILER ? : Probability and/or Genetics If a couple was to stop having babies after they've got both boy and girl, in other word, they would stop right after they have had kids in both sex, then what would be the average number of kids in an average family? ========= SPOILER ? ================== I get 3 kids. The probability of having n children is P(n) = (1/2)^(n-1), since there is a probability of 1/2 for each child, and a factor of 2 since there are 2 ways of achieving both sexes: BBB ... G or GGG ... B. Clearly the total Sum(n = 2, oo) P(n) = Sum(n = 2, oo) (1/2)^(n-1) = 1, since Sum(n = 1, oo) (1/2)^n = 1. Recall Sum(n = 1, oo) x^n = x/(1 - x) = 1 for x = 1/2. = Sum(n = 2, oo) [n P(n)] = Sum(n = 2, oo) [n x^(n-1)] = Sum(n = 1, oo) [n x^(n-1)] - 1 with x = 1/2. d/dx{Sum(n = 1, oo) x^n} = Sum(n = 1, oo) [n x^(n-1)] = d/dx{x/(1-x)} = 1/(1-x)^2 = 4 for x = 1/2. Thus = 4 - 1 = 3. Van s.jacques@genie.geis.com From: s.jacques@genie.geis.com Subject: A physics problem Re: A physics problem: >There are 2 point masses of mass m kg, spaced r meters apart. Assuming that there are no external forces acting on this system, find t, the time (in seconds) at which they will collide if they are at rest at t=0.< Csaba gave an answer, but here is some more explanation. If one places the masses on the x axis at +/- r/2 at t = 0, the origin x = 0 is the center of mass which does not move. Replace the r of the problem by r_o = r(t=0), so that r = r(t) varies with time t. One uses conservation of energy and to solve this problem: mv^2/2 + mv^2/2 - Gm^2/r = mv^2 - Gm^2/r = - E = constant total energy, where E = Gm^2/r_o > 0. v = dx/dt = (1/2) dr/dt since the velocity w.r.t. the center of mass x = 0 is 1/2 the relative velocity. Or, using the eqns. for the 2 body problem, the reduced mass is m/2, and we get the same eq.: (m/4) (dr/dt)^2 - Gm^2/r = - E = constant total energy so we get the same eq. for dr/dt either way: dr/dt = 2 sqrt{Gm(1/r - 1/r_o)} ; and 2 sqrt(Gm) t = Integral{r_o, 0, dr/sqrt(1/r - 1/r_o) Let cos a = r/r_o and do the integration from a = 0 to pi/2, yielding t = (pi/4) sqrt[r_o^3/(Gm)] Csaba gets t = pi * sqrt (r^3/(8 * G * (m1 + m2))), the same as my result for m1 = m2 = m. (It would be interesting to use general relativity (GR) to do this and compare with the Newtonian result, but the GR 2 body problem is very difficult and can only be done approximately, and is beyond my experience.) Van s.jacques@genie.geis.com From: s.jacques@genie.geis.com Subject: Prob/Genetics From CBARRON@genie.geis.com The prob/genetics problem. Its a negative binomial distribution with a minor adjustment. That and Expected_n(p) = 1/(1-p), for this distribution, yields the answer = 1 + 1/q = (q+1)/q = 3/2 / 1/2 = 3. One trial to determinine 'success' and 1/q trials until the first failure. Simple, eh.... ====== This is a little sparse for me. Van s.jacques@genie.geis.com From: claxnes@nwer.sandia.gov (Carl L. Axness) Subject: problem Here is a short problem. I use the result in the solution of a problem submitted Dec. 20 by rose@garnet.acns.fsu.edu. Show that the function x^q q=>1, x=>0 is convex. A function f(x) is convex on the interval [x,y] if tf(x) + (1-t) f(y) => f(tx + (1-t)y) 0<=t<=1 => means "greater than or equal to" above. From: claxnes@nwer.sandia.gov (Carl L. Axness) Subject: SPOILER to Kermit Rose problem Kermit Rose submitted the following problem: > Define sum_k(x) by > > sum_k(0)=0 > sum_k(1)=1 > > sum_k(x-1) + x^k = sum_k(x) > > note that sum_0(n) = 1 + 1 + 1 + .... 1 = n > > sum_1(n) = 1 + 2 + 3 + ... + n = (1/2) n^2 + (1/2) n > > sum_2(n) = 1^2 + 2^2 + ... + n^2 = (1/3) n^3 + (1/2) n^2 + (1/6) n > > Prove that the first two terms of the polynomial for > > sum_k(n) are [ 1/(k+1)] n^(k+1) and [1/2] n^k SPOILER . . . . . . Note I use q for k in the original problem. First, It should be noted that the exact solution to this problem may be found in for example TABLE OF INTEGRALS, SERIES, AND PRODUCTS by Gradshteyn and Rhyzik, Academic Press. In the 1992 Ed. it can be found on pg. 1. I do not know how the expression in the above reference is derived, however. The following (somewhat elementary) method may be used to solve the problem stated by Kermit Rose. Basically we proceed by bounding the sum with integrals. The following figure (not to scale) will be helpful in exhibiting the solution. q | 3 + -----*-----x | | * x | |* x | * x | * | x q| * | x 2 + -----*----x | | * x | * x | | x q| * | x 1 +----*-----x | * x * x | x 0 x---------+----------+----------+----------+ 1 2 3 4 1) UPPER BOUND Let s=sum_{i=0}^{n} i^q. We first show that s <= int_{0}^{n} (x+1/2)^q dx = n^(q+1)/(q+1) + n^q/2 + O(n^(q-1)) (1) where O(x) denotes terms on the order of x and <= denotes "less than or = to". Note that s is illustrated as the sum of the rectangles in the figure. In order to show that the area under the function (illustrated by * above) is greater than the sum, we must show that the area bounded by (x+1/2)^q below and k^q above for k-1<=x<=k-1/2 is less than the area bounded above by (x+1/2)^q and below by k^q for k-1/2<=x<=k for all 1<=k<=n. We note k^q/2 - int_{k}^{k+1/2}(x+1/2)^q dx <= int_{k+1/2}^{k+1}(x+1/2)^q dx - k^q/2 is true if and only if k+1/2 k+1 | | k^q - (x+1/2)^(q+1)/(q+1) | <= (x+1/2)^(q+1)/(q+1) | | | k k+1/2 or k^q + (k+1/2)^(q+1)/(q+1) <= (k+3/2)^(q+1)/(q+1). Expanding the power terms above gives polynomials on either side of the equationwith the same k^(q+1) and k^q terms but the terms of order k^(q-1) and less on the right hand side all have larger coefficients (due to the 3/2) than those on the left hand side. Since the above inequality is true for any 1<=k<=n, the inequality of (1) is true. 2) LOWER BOUND For the next part of the proof we must find a good enough lower bound so that s => n^(q+1)/(q+1) + n^q/2 + O(n^(q-1)). The first candidate, say f(x)=x^q, illustrated by the x in the above figure, isn't tight enough since it only gives info about the highest order term. However, if x^q is convex at integer values (that is, x^q for k<=x<=k+1 lies below the line segment connecting the points (k,k^q) and (k+1,(k+1)^q) then one can add the sum of the areas of the triangles formed by the points (k,k^q), (k,(k+1)^q), and (k+1,(k+1)^q) for 0<=k<=n-1 to the integral for a tighter lower bound. But, x^q is convex for q=>1 and x=>0 (I thought this would be a good problem for iams, and have submitted it as a problem). Thus the sum s is bounded below by, s => 1^q/2 + (2^q-1^q)/2 + ... + (n^q-(n-1)^q)/2 + int_{0}^{n} x^q dx ----- sum of triangles ------------------- + lower integral = n^q/2 + n^(q+1)/(q+1). (2) Combining (1) and (2) gives the final result. That is, sum_{i=0}^{n} i^q = n^(q+1)/(q+1) + n^q/2 + O(n^(q-1)). From: csaba@teleport.com (Csaba Gabor) Subject: SPOILER (showing x^q convex) Problem: We want to show x^q is convex for q >= 1, x >= 0, where f(.) is convex on an interval, D, if tf(b) + (1-t)f(a) >= f(tb + (1-t)a) for each a,b in D, and t in [0,1] (note slight change in notation from original prob (x->b, y->a). All this inequality says is that each segment connecting any two points of f(.) on D lies above or on f(.).) My solution: q = 1 is trivial. In what follows, assume q > 1 The slope of the line connecting f(a) to f(b) is constant over [a,b]: (1) (f(b) - f(a)) / (b - a) = (b^q - a^q) / (b - a) Now the slope of f(x) = x^q is (2) qx^(q-1), which is monotonic increasing over [a,b]. Thus, if we can show that the initial slope of f(x) at a, (3) qa^(q-1), is less than (1) we are done since there will only be one intersection of f(x) with the line connecting f(a) to f(b) (by the monotonicity of the derivative), namely at (b,(f(b)). To this end, we show (1) < (3) in the following For z > 1 we have z^(q-1) > 1 hence: q(z^(q-1) - 1) > 0 or qz^(q-1) - qz > 0 The left hand side is the derivative of z^q + (q - 1) - qz (which is 0 at z=0) Hence, Lemma 1: z^(q - 1) + (q - 1)/z > q (for z > 1, with equality at z = 1) Now set z = b/a (from (1), assuming WLOG that b > a), and multiply through Lemma 1 by ba^(q-1): b^q + (q - 1)a^q > qba^(q-1) Hence b^q - a^q > qba^(q-1) - qa^q or (b^q - a^q) / (b - a) > qa^(q-1) QED Csaba From: David G Radcliffe Subject: Favorite elementary math books? Hello folks! I recently received the following request by email: > Thanks for your kind explanation. If you can recommend a good mathematics > book or mag. pls do so (I have an engr. background), if it's not too much > a bother. Ie., is there a Scientific American type mag. for math? I would like to know what your favorite math books or journals are. I am looking for material which could be understood by a bright American high school student. Please send your list to me, not the mailing list. I will post a summary on Monday. Thanks in advance, Dave radcliff@csd4.csd.uwm.edu From: johndanbre@aol.com Subject: SPOILER?? Prob/Genetics If a couple was to stop having babies after they've got both boy and girl, in other word, they would stop right after they have had kids in both sex, then what would be the average number of kids in an average family? ================= SPERLER! TWO. If we are to assume that the couple is able to "stop having babies after they've got both boy and girl", then we must assume that they can tell the sex of an unborn child, and therefore have the ability to abort the unwanted. This is a problem that will often arise in the future when unwanteds can be excluded from our society. Jack. From: Paul G Mullan Subject: Prob./Genetics Isn't everyone ignoring the possibility of twins, triplets,etc. in this boy/girl problem? From: jmlm@dit.upm.es (Joaquin Maria Lopez Munoz) Subject: Re: SPOILER?? Prob/Genetics I dont see why must the couple abort unwanted children in order to stop having them after a boy and a girl, they could use contraceptive methods. In other problems (like stop in such a way that they dont have two girls) it is necessary aborting. ---------------------------------------------------------------------------- Joaquin Maria Lopez Munoz. / ETSI de Telecomunicacion, Madrid, Spain. / Email address: jmlm@bosco.dit.upm.es ____/ ___ ___ _________ ___ ___ / / / \ \ / / \ \ \__/ /___/___/ / /___/___/ | \____/