July 2003 - mathfun@mailman.xmission.com

[math-fun] odometer word game
by Richard Schroeppel 03 Jun '04

03 Jun '04

zimb zinc chromatic chromatid Rich

2 1

FW: Re: [math-fun] distinct and square-free factorizations
by James Tanton 13 Aug '03

13 Aug '03

Let D_k (n) = number of partitions of n with any number repeated at most k times. (Thus D_1(n) = D(n).) O_k (n) = number of partitions of n into numbers none of which is a multiple of k. ( Thus O_2(n) = O(n).) Then D_k (n) = O_(k+1) (n) for all n. The argument using generating functions to establish D(n) = O(n) easily generalises to establish this, but the kids (ages 11 - 17) at the Boston Math Circle recently came up with a nice fun proof of this in terms of representing numbers base k. - JT > [Original Message] > From: R. William Gosper <rwg(a)spnet.com> > To: <math-fun(a)mailman.xmission.com> > Date: 5/18/2003 4:11:57 PM > Subject: Re: [math-fun] distinct and square-free factorizations > > mlb>In fact, recalling this, I'd hoped to retrieve some collective memories! > > acw>> Gosper showed me an absurdly intricate _analytic_ proof of this, and > >>bewailed the lack of a _combinatorial_ proof; > > Here are my memories. Unfortunately, the TeX sources appear to to have been > abandoned at Xerox PARC. Shortly after the announcement of the factorization > of 2^2^2^3+1, I sent a(n unrelated) letter to the the usual gang of maniacs > (Dick Askey, George Andrews, George Gasper (I think), Rich&Hilarie, etc.) > that began: "Dear Thai food lovers and Rich," > answering Hilarie's challenge to find a bijection between the *complements* > of the odd partitions and distinct partitions. I.e., pair the not-all-differents > with the not-all-odds. A very young Peter Weyhrauch and I came up with one, > and then a PARC coworker, Ted Kaehler, came up with a different one! I > then found a generalization of the theorem to residue classes mod k, of which > #(some evens) = #(some duplicates) was the case k=2. This led to a nonobvious > generating function identity. > It would be nice to locate a hardcopy of that letter. > --rwg > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun ========================= James Tanton mathcircle(a)earthlink.net P.O. Box 2344 Acton MA 01720 978 635 8036 FIND *MATH CIRCLE* ON THE WEB AT: www.themathcircle.org

2 1

Re: [math-fun] Re: Kepler conjecture & Flyspeck
by asimovd＠aol.com 11 Aug '03

11 Aug '03

John McCarthy wrote: << When a long computer calculation is an important part of the proof of a mathematical theorem, we should ask for proof (preferably both computer-checked and hand checked) that the program does the advertised calculation. For example, we want a proof that if the calculation comes out, the four color conjecture is true. >> This is of course desirable, but brings up a new question: where does this stop? A typical "verification of correctness" of a sizeable computer program involves the application of another program. Then we need to know that the verification program is valid and was used properly. Etc. --Dan

3 4

RE: [[math-fun] Nim-like game]
by Christian G. Bower 06 Aug '03

06 Aug '03

"Jon Perry" <perry(a)globalnet.co.uk> wrote: > Neat. What do 1 and 2 imply? > For the purposes of a single heap game, 0 implies 2nd player win, anything else implies first player win. The different values 1 and 2 are useful if you wish to sum this game with other games (or copies of itself). I won't go into the details of what that means. A copy of Winning Ways I'm sure will explain that in great detail. I'll give this short technical description. A postion's value is zero if all the moves from that position are zero. The value is one if the current player can move to zero but not to one. Two if the current player can move to zero or one, but not to two. > If the increase range is generalised to l<=i<=r (l=1, r=2 is my original > example - generally l>=0), how can you predict which player will win? That looks easy to model. I can't say what the answer will be until I model it. I expect similar results, but I am concerned that the decision tree can get very complicated as r-l increases. > > For the multiple heaps version, if a player can only remove from 1 heap at a > time, which the additional play that if a player can exhaust a heap this > signifies the end of their turn (i.e. they can pre-empt having to take k > buttons), there are 2 options - the next player only need take i more > buttons than the previous player took, or the pre-empting player can state > how many they took and the next player must take more than this. I don't know how to use the theory for the multiple heaps version other than to consider each case individually. I suspect that for more than 3 heaps it can get very complicated. Additionally, that rule that allows a player to state how many they "took" when emptying a heap can lead to a large number of choices for that player.

3 2

[math-fun] polygons
by Richard Schroeppel 31 Jul '03

31 Jul '03

Carrying Dan Asimov's analysis a litle further, the edges Ek fit a circumcircle of radius R (diameter D=2R) when the product Prod ( sqrt(D^2-Ek^2) + i Ek ) has 0 imaginary part, i.e. is real. This gives a messy algebraic expression for D, and hints that there might not be a closed form when the number of edges is increased, because we run afoul of unsolvable quintics etc. The full permutability of the edges is another hint in that direction. Of course there's nothing that says finding D is equivalent to finding the area of the polygon. Knowing D, we can indeed get the area as the sum of triangles of sides R,R,Ek; but perhaps the reverse direction is more difficult. Rich rcs(a)cs.arizona.edu

1 0

Re: [math-fun] inscribed polygon area
by asimovd＠aol.com 31 Jul '03

31 Jul '03

Andy writes: << I wrote: > Wait -- consider any 3 consecutive (ccw) vertices A,B,C of a > convex n-gon. If the triangle ABC is cut from the n-gon and > re-glued so that they now appear in ccw order C,B,A, then > it's easy to see that doesn't change the circumcircle (by its > symmetry about the perpendicular bisector of AC). Since all > permutations of the cyclic ordeer of the edges are generated > by ones of this sort, Actually, they aren't, if the polygon has an even number of sides. Color the sides alternately red and blue, and note that your permutations always switch edges of the same color. >> What I intended to convey above is the operation of cutting off from the polygon the triangle whose vertices are 3 consecutive vertices A,B,C of the polygon (and therefore containing two consecutive edges AB and BC of the polygon), and gluing ABC back with AC reversed. The net result is that two adjacent edges of the polyong hav e been switched. These operations must generate the group of all permutations of the polygon edges. --Dan

1 0

RE: [math-fun] inscribed polygon area
by Andy Latto 31 Jul '03

31 Jul '03

> > Wait -- consider any 3 consecutive (ccw) vertices A,B,C of a > convex n-gon. If the triangle ABC is cut from the n-gon and > re-glued so that they now appear in ccw order C,B,A, then > it's easy to see that doesn't change the circumcircle (by its > symmetry about the perpendicular bisector of AC). Since all > permutations of the cyclic ordeer of the edges are generated > by ones of this sort, Actually, they aren't, if the polygon has an even number of sides. Color the sides alternately red and blue, and note that your permutations always switch edges of the same color. >that shows the circumcircle and > circumradius are functions purely of the multiset of edge > lengths. But the proof you posted later, implicit in the equation that relates the circumcircle radius to the sequence of edge lengths (which, if you examine it, doesn't depend on edge order), is fine. > (If true, I never realized this independence before.) Think of cutting a circular disk into pieces; one is the polygon, and the others are each bounded by a side and an arc. Discard the polygonal piece. No matter how you rearrange the other pieces, they include a total arc length of 2piR, so they will fit together to form a full circle of the same radius no matter what order you line them up in. Andy >

1 0

Re: [[math-fun] Nim-like game]
by Christian G. Bower 31 Jul '03

31 Jul '03

"Jon Perry" <perry(a)globalnet.co.uk> wrote: > Let there be n buttons. A player may take 1 or 2 buttons MORE than his/her > opponent took. Player 1 can take either 1 or 2 buttons. > > e.g. 28->27->25->21->15->7->0 > > (the last player must take either 8 or 9, as only 7 remain, they must take > them all). I threw this together quickly, so I apologize for any errors: In the case where winner takes the last button: I can model the Nim values as follows: f(n,k) is the Nim value for n buttons remaining, last player took k buttons. If n=0, value is 0 if 1 <= n <= k+1 value is 1 otherwise value is mex( f(n-k-1,k+1), f(n-k-2,k+2) ) where mex is the smallest nonegative integer not in the set [i.e. mex(0,0) = 1, mex(0,1) = 2, mex(1,1) = mex(1,2) = mex(2,2) = 0 With this I get for f(n,0) 1 : 1 2 : 2 3 : 0 4 : 0 5 : 2 6 : 1 7 : 1 8 : 1 9 : 2 10 : 2 11 : 0 12 : 0 13 : 0 14 : 0 15 : 2 16 : 2 17 : 1 18 : 1 19 : 1 20 : 1 21 : 1 22 : 2 23 : 2 24 : 2 25 : 0 26 : 0 27 : 0 28 : 0 29 : 0 30 : 0 For the zeroes of f(n,0) (those n from which the second player can win) I get: 3-4 11-14 25-30 45-52 71-80 103-114 141-154 185-200 235-252... The lower limits seem to follow the pattern: 3 3+8=11 11+14=25 25+20=45 ... with the increment going up by 6 each time. The size of the ranges: 2, 4, 6, 8... If player who takes the last piece loses: the analysis is similar: g(n,k): If n=0, value is 1 if 1 <= n <= k+1 value is 0 otherwise value is mex( g(n-k-1,k+1), g(n-k-2,k+2) ) 1 : 0 2 : 2 3 : 1 4 : 1 5 : 2 6 : 0 7 : 0 8 : 0 9 : 2 10 : 2 11 : 1 12 : 1 13 : 1 14 : 1 15 : 2 16 : 2 17 : 0 18 : 0 19 : 0 20 : 0 21 : 0 22 : 2 23 : 2 24 : 2 25 : 1 26 : 1 27 : 1 28 : 1 29 : 1 30 : 1 with zeroes at 1 6-8 17-21 34-40 57-65 86-96 121-133 162-176 Lower limits 1 1+5=6 6+11=17 17+17=34 ... again the increments incrementing by 6 the ranges being 1, 3, 5, 7... this time > > What are the strategies for various n, with either last button wins/loses? Well, I didn't go the extra distance to detail the strategy, but it doesn't look too difficult. Christian

4 4

[math-fun] Polygon Area: Generalising Asimov's numerical solution
by Guy Haworth 31 Jul '03

31 Jul '03

There is a numerical solution, and there may not be a closed solution for all n-gons. The generalization for n-gons which are not convex is not about "the centre of the circle being inside the n-gon" ... a) the n-gon may circle the centre 'k' times (including k = 0) b) the n-gon may have edges that 'double back', e.g: ABC is a triangle, A' is 'very near' A, B' very near B ABA'B'C is a pentagon with an area very near ABC's. [ Does the concept of area need more careful definition? ] It would appear that one needs a diagram of the n-gon as 'evidence' of the clockwise/counterclockwise 'direction' of the edges ... or can that be deduced too? Guy

1 0

Re: [math-fun] inscribed polygon area
by asimovd＠aol.com 30 Jul '03

30 Jul '03

Rich wrote: << I think one way of expressing the hard problem is "given a set of edge-lengths {Ei}, determine the radius of the circumscribing circle". >> Now it makes sense. Lessee -- a chord of length E in a circle of radius R subtends a central angle ang(E) = 2*arcsin(E / 2R). Since the total central angle subtended by all edges of a cyclic quadrilateral is 2 pi [see below *], it follows that when R is the circumradius, we have (1) pi = f(R) = arcsin(E_1 / 2R) + ... + arcsin(E_n / 2R) given the edge lengths as E_1,..., E_n. Now f(R) is clearly monotonic, so there is a unique value of R making (*) true. (1) is by no means a closed formula for R, but at least it determines R uniquely. It appears that if the formulae for the sine of the sum of n angles is sufficiently cooperative, this could lead to a closed-form expression for R -- which in turn would lead to a closed-form expression for the area of a cyclic n-gon with edges {E_i}. _____________________ * Appropriate adjustments need to be made when the center of the circumcircle does not lie in the polygon's interior. --Dan

1 0