December 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

[math-fun] Negative money
by Steve Gray 01 Jan '04

01 Jan '04

The proposed Reagan dime should have negative value (-$.10), just like his presidency. But this would cause massive confusion. If you give someone an RD, you might immediately owe them $.10. Therefore you have to keep your RD's carefully guarded, to avoid theft, which would cause you debt. But you want to get rid of all your RD's because they represent a debt. If you owe the IRS back taxes, they could send you a pile of RD's, but you could throw them away and deny getting them. What are the implications of having negative coins? I'm confused.

6 7

[math-fun] a problem of permutation group(please help me)
by 張家齊 28 Dec '03

28 Dec '03

generators: s1=(57)(68) s2=(56)(78) s3=(34) s4=(37)(48) s5=(26)(48) s6=(24)(68) s7=(78) s8=(68) s9=(48) S={si : i=1~9} <S> means a permutation group generate by S give a=(2345678) (1) is a in <S>??? (2) a=?? (please give power of generator to represent a ;for example we can represent (24)=s6*s8) And more general problem given a permutation group <S> by its generator set S={a,b,c,...} the elements of S has the type like (12);(1324); (13)(24)...etc. if we give a element p which is in the type like the elements in S Is there an algorithm to distinguish whether p in <S>?? and is there an algorithm to write p = the power of the generators ?? Is there som book which had metion some theory about this?? ----------------------------------------------------------------- ¨C¤Ñ³£ Yahoo!©_¼¯ ®üªºÃC¦â¡B·ªº®ð®§¡B·R§Aªº·Å«×¡AºÉ¦b«H¯È©³¹Ï http://tw.promo.yahoo.com/mail_premium/stationery.html

5 4

[math-fun] looking for a non-trivial map on earth
by John McCarthy 27 Dec '03

27 Dec '03

Let's color the map of the 48 states with four colors. Note that California has only three neighbors, and therefore no matter how we color the rest of the map California is colorable, so we postpone California and get a reduced map with the rest of the states. In the reduced map Arizona has only three neighbors and can be postponed as part of coloring the reduced map. We can continue the process of postponement until we get a completely reduced map in which each state has four or more neighbors. In the case of the US, the completely reduced map is empty. This is also true for the maps of Europe and Asia, Africa, South America, and the departments of France. It is easy to construct a map in which every country has four or more neighbors. Indeed, as Kempe proved, there are maps in which every country has five or more neighbors. However, I haven't been able to find a map on the face of the earth in which every country has four or more neighbors. Can anyone find one? I'd be disappointed if the result was achieved with the aid of a disconnected country. The phenomenon can be generalized to the notion of a postponable variable in a constraint satisfaction problem. I discuss postponing countries with four or fewer neighbors in a 1982 paper entitle "Map coloring and the Kowalski doctrine". It's in my 1990 book "Formalizing common sense" and on my web site as http://www-formal.stanford.edu/jmc/coloring.html. I see no reason why our ancestors should have arranged their countries, states, provinces, and counties in such an easy to color way.

3 2

Re: [math-fun] convex lattice 11-gon of minimum area
by Chris Landauer 24 Dec '03

24 Dec '03

hihi, all - well, perhaps two minutes after i sent the previous message, the n=20 case finished, with minimum area 121 in time 64751.638u 94.941s 19:00:58.37 94.7% i'll update the web site later more soon, cal Chris Landauer Aerospace Integration Science Center The Aerospace Corporation cal(a)aero.org

1 0

Re: [math-fun] convex lattice 11-gon of minimum area?
by Chris Landauer 24 Dec '03

24 Dec '03

hihi, all - I have some intermediate results from the programs I wrote for the minimum area convex lattice polygon problem Program Results (so far) n min i min a (as found by my program) 11 17 19.5...21.5 15 45 49.5...51.5 17 68 ...75.5 18 79 ...87 19 98 ...106.5 (n=20 has been running for 18h so far; I have no idea how long it will take) I also have a request for information: are there any explicit upper bounds known for n>16 (the limit of the listing in the OEIS web site that I read)? Steve Finch reported a previous upper area bound of 86.5 for n=17, but I did not find that in the OEIS (perhaps I was looking at an older copy that was cached somewhere else). Because the first program was taking way too much time (the run I mentioned before that was supposed to finish Thursday ran through Sunday last week before I killed it after more than 210 CPU hours), I have made two sets of improvements to the program, including using some suggestions from Dylan Thurston and Dan Hoey (thanx to both of you). The time saving is substantial: with these changes, the time for n=15 (with edge length bound = 10) is reduced from 3606.580 CPU seconds to 221.540 CPU seconds, and the time for n=18 (with edge length bound = 10) is reduced from 169103.840 CPU seconds (over 48 hours) to just 6453.330 CPU seconds. More timing details are on the web site. It turns out that the smallest longest edge length for the minimum area polygons is much smaller than the original edge length bound used to find them (of course, there are infinitely many minimum area polygons with longer edge lengths as well), and as far as I've checked, the results do not change when the edge length bound is increased (at least through n=15, with a few larger cases checked and more large cases and comparisons pending). Edge length 5 suffices at least up to n=19 (it means that the edge length bound of 10 that I used is much larger than it needs to be to find at least one likely minimum area polygon). Full details and explanations will eventually show up on the web. For now, you can just look at URL http://www.cs.umd.edu/~cal/convex/ to see the intermediate results (the archive files are fairly small; they each expand to about 2MB). Unfortunately, there is a lock on raw directory listings at Univ. Md., so accessing any of the sub-directories of convex/ will get a 403 error (I forget just now how to change that behavior). In any case, the archive files can be downloaded to get all of the files in all of these sub-directories to examine. more soon, cal

1 0

[math-fun] Not fun: MAA dues
by Bernie Cosell 22 Dec '03

22 Dec '03

Sorry for the not-fun, OT inquiry... I'm curious if the MAA dues have recently skyrocketed. I just got my renewal and I'm really shocked: Last time I renewed, I did so in 2001 for two years for $72. I now see that my dues to renew are $77 for *one*year*. Can it be that the dues have more than doubled in the last two years? [unless I'm missing something, that's a big enough leap [and indeed, a big enough bite out of my budget] that I'm thinking it is time to let my membership lapse [after nearly 40 years!]] /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--

3 3

Re: [math-fun] convex lattice 11-gon of minimum area
by Dan Hoey 20 Dec '03

20 Dec '03

Here's a better search cutoff than the area bound, though I still don't see how to make the search finite. Theorem: Any convex lattice N-gon that contains K collinear lattice points (x,y), (x+a,y+b), (x+2a,y+2b), ..., (x+(K-1)a,y+(K-1)b) has area at least (K-1)(ceiling(N/2)-1)/2. The proof relies on two lemmas that probably have better proofs than these: Lemma 1: If a and b are relatively prime integers, not both zero, then the lines through lattice points in the direction of the vector (a,b) are at a distance of 1/sqrt(a^2+b^2) from each other. Proof: Take a square WXYZ with no lattice points on its boundary and with WX a translate of the vector (a,b). Every line parallel to WX passing through WXYZ that touches any lattice point must touch exactly one lattice point in WXYZ. There are a^2+b^2 lattice points in WXYZ, so that many lines, with a total separation of sqrt(a^2+b^2), so the separation between any two is 1/sqrt(a^2+b^2) QED. Lemma 2: Suppose a convex plane figure meets parallel lines R,S,T such that the intersection with line R is a line segment of length X, and lines S and T are at a distance of Y from each other. Then the area of the figure is at least XY/2. Proof: Let the intersection with line R be segment AB, and let C,D be points in the figure on S,T respectively. Then by convexity the figure contains triangles ABC and ABD. If R lies between S and T then the triangles are disjoint and have total area XY/2. If R is outside S and T then the larger triangle has total area greater than XY/2 QED. Proof of theorem: Suppose the convex lattice N-gon contains K collinear lattice points on a line parallel to vector (a,b), with a,b relatively prime, not both zero. Consider the lattice lines parallel to vector (a,b) that meet vertices of the N-gon. Since no more than two vertices lie on any line, there are at least ceiling(N/2) such lines. By Lemma 1, two of the lines must be at least (ceiling(N/2)-1)/sqrt(a^2+b^2) apart. Furthermore, the line containing the K collinear lattice points meets the N-gon in a segment at least (K-1)sqrt(a^2+b^2) long. By Lemma 2, the N-gon has an area of at least (K-1)(ceiling(N/2)-1)/2 QED. In searching for an 11-gon of area less than 21.5, we can then rule out any line of 9 collinear lattice points. Furthermore, once we have two vertices X,Y of the polygon, lattice points ruled out by applying the theorem to X will shadow other points from Y, which will be ruled out by convexity, and those points may cast shadows from X, and so on. Furthermore, any P for which the triangle PXY contains a prohibited point will then be prohibited. If we can surround the partial polygon with a ring of points that are angularly close, this will reduce the problem to finitely many cases of choosing vertices from finite sets. Unfortunately, I suspect this not is enough to make the whole problem finite. Using Dylan's observation, it looks like we still have infinitely many points to choose from for the third vertex (though I haven't worked it out in detail). Still, we may be closing in on a final answer to the problem. Dan

2 1

Re: [math-fun] Is there a good Dots & Boxes program?
by Scott Kim 18 Dec '03

18 Dec '03

Thanks all for the leads. I contacted JP Grossman, who'll rewrite his program in Java for me. I'll let you know when it's up, so you can play it. -- Scott

1 0

Re: [math-fun] convex lattice 11-gon of minimum area
by Chris Landauer 17 Dec '03

17 Dec '03

hihi, all - Minimum area convex Z^2 lattice polygons (methods, not results): Longish - If you don't particularly care about this problem, you can delete this message now. It will be posted and explained on the web later anyway. Looking for minimal area, I decided that I could prove that there are no lattice points on the interior of any edge (so the only perimeter lattice points are vertices, i.e., corners). A \ \ B \ \ C | | D (replacing ABCD with ABD stays convex and gets smaller area) I also decided that I could prove that we can start by taking the first point to be the origin and insisting that the first point after the origin must be in the first quadrant, and that all the points are in the upper half-plane. (various translations and rotations can acheive this property) Now the program just uses a simple radius bounded backtracking search for the points in the polygon, with some special processing near the end. At each stage after the origin point, there is a wedge of the lattice that contains candidate lattice points, defined by lower and upper bounding half-lines. The lower bound of the wedge is the line to the previous point from the previous but one point (except when finding the second point, when the line is the positive horizontal axis). The upper bound of the wedge is the line from the previous point to the origin (except when finding the second point, when the line is the positive vertical axis). I think I'll make a couple of postscript pictures and put them where they can be downloaded, to make this description clearer (in addition to the answers and the polygons). The program enumerates lattice points in a simple spiral out to the chosen radius bound, and checks them for wedge membership. Because the polygons are so small, I can use a simple recursive function for the search, and that way the backtracking is entirely managed by the function calls (it helps that the spiral enumeration can be done incrementally, that is, each point in the spiral can be computed from just the previous one). I ran a profile on the program, and it spends over 90% of its time in the function that chooses the next point in the wedge, so that is where time improvements will be most useful. Incidentally, the counts that I posted for the number of minimum area polygons (with each edge length bound) may be incorrect, since I forgot to make the program check the length of the last edge (from the last polygon point chosen to the origin), so the counts may be large by a few. They are right, though, for the few larger polygons I re-checked. I will correct the counts for the rest of the sizes once the new search strategy is fast enough. Dylan Thurston asked about removing SL(2,Z) symmetries, and I am still thinking about that. It should be clear that the program I wrote provides little or no help along those lines, and that a separate program should be written for that problem, using the polygons output by the original search. I am trying to think about that, too (I will make all the polygons available). I thank all of you who sent questions and suggestions about the problem, and I welcome any suggestions for improving the spiral enumeration, improving the wedge enumeration to eliminate the spiral enumeration, and / or organizing the SL(2,Z) program. Some theoretical upper bounds on the minimum perimeter (or maximum edge length) of a minimum area (convex lattice) polygon would help if they were small enough, because that would bound the search usefully. ====

2 1