Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 2000/01/06 Subject: Re: Y to K puzzle qs...@aol.com wrote: > Peter L. Montgomery said: > >. Consider the letters on a standard typewriter/keyboard: > >. Q W E R T Y U I O P > >. A S D F G H J K L > >. Z X C V B N M > >. Draw a graph whose vertices are the letters and with an arc from > >. each letter to each neighboring letter (e.g., H connects to Y, > >. U, J, N, B, G). How many paths are there from Y to K which > >. pass through each vertex (i.e., letter) at most once? > with only 26 keys , this is doable with a brute force program (I get > 241036). I can corroborate that answer. I als calculated that if we require that every letter be visited, there are only 394 paths. > But now, count the paths from Y via 2 to K on a 4-row keyboard > with an additional numbers-row ! > 1 2 3 4 5 6 7 8 9 0 > Q W E R T Y U I O P > A S D F G H J K L > Z X C V B N M I find 1,267,520,976 paths, of which 431,364 visit every key. > ... > I remember this URL : http://home.wxs.nl/~faase009/counting.html , > where I once found a nice trick, to solve such problems. I used a similar technique that I developed for counting checkerboard paths a few years ago. It really beats counting them one at a time. Dan Hoey posted and e-mailed (I hope) haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 2000/01/08 Subject: Re: Y to K puzzle qs...@aol.com wrote: [About Y2K paths in >> >. Q W E R T Y U I O P >> >. A S D F G H J K L >> >. Z X C V B N M and >> 1 2 3 4 5 6 7 8 9 0 >> Q W E R T Y U I O P >> A S D F G H J K L >> Z X C V B N M but not about Q W E R T Y U I O P A S D F G H J K L since Bill Taylor didn't mention it until later...] > can you also count paths of length L , L<36 ? I'm glad you asked--thinking about it that way simplifies some of the logic! Including Bill Taylor's two-row keyboard, the number of paths by length are L 2-row 3-row 4-row | L 2-row 3-row 4-row | L 3-row 4-row ---------------------+-------------------------+------------------- 4 3 3 3 | 15 18 6789 93440 | 26 394 121343211 5 8 12 16 | 16 15 11866 220990 | 27 154783422 6 12 30 52 | 17 10 19501 515547 | 28 177539617 7 16 60 128 | 18 6 28736 1175869 | 29 180538090 8 19 109 280 | 19 2 36358 2588774 | 30 160094454 9 20 200 602 | 20 38868 5429928 | 31 121241187 10 19 368 1307 | 21 35286 10749831 | 32 76210607 11 19 663 2929 | 22 27072 20000448 | 33 38145107 12 19 1189 6842 | 23 16951 34912602 | 34 14238878 13 19 2127 16337 | 24 8086 57027480 | 35 3519804 14 19 3797 39158 | 25 2571 86652672 | 36 431364 yielding the totals 224, 241036, and 1267520976. (Sorry, Bill. Kudos, Fred. ObPuzzle: On the 2-row keyboard, which is the extra path of length 9?) > >I used a similar technique that I developed for counting > >checkerboard paths a few years ago. It really beats counting them > >one at a time. > congrats, so the Y2K problem is solved now. > (we might still need another corroboration , though) > can you give your approximate calculation time ? > My UBASIC program took 7:37min on a P1/166. About 0.15 second for the 3-row calculation on a Sparc-20 and 0.6 second for the 4-row one. I assume your UBASIC calculation is by backtracking for the 3-row problem, so at 1.9 ms per path the 4-row count would take 28 days. > Suppose, it takes me 1 hour to implement a simple brute force > algorithm. How long might it take to implement your fast technique? > How many lines/bytes has it ? Can you easily adapt it for similar > problems / other graphs ? It probably took me twenty hours, mostly thinking about it (but I'm not sure I could write the backtracker in an hour). The code is 206 lines (6K bytes) in Lisp. The code requires that the graph be induced on a "skinny" rectangular part of a hexagonal grid. Skinny because the time and storage are more than exponential in the width (number of rows) of the rectangle, but a low polynomial in the length (I think cubic--the number of multiplications is linear in the length, but they operate on big numbers). > Hmm, what if we randomly remove some edges , or we take a completely > irregular graph ; how long might the fastest counting algorithm take > now ? There are still some ideas for possible shortcuts. At its heart, the technique really only requires that the graph have a low-bandwidth vertex ordering (the bandwidth of an ordering v1,v2,...,vn is the maximum over j of the number of edges (vi,vk) with i <= j < k). Finding the minimum bandwidth is NP-complete, but often you can find an ordering that's good enough. Of course, there often is no ordering that has low enough bandwidth to use this technique. But I don't recall off-hand any graphs where the bandwidth is too large for this technique but for which backtracking is feasible. Dan Hoey --- Newsgroups: rec.puzzles From: haoyuep@aol.com (Dan Hoey) Date: 2000/01/08 Subject: Re: Two Envelopes: One has twice as much money as the other . . . >>Nick Wedd wrote: [...] >>> If I am convincingly assured that the expected sum in the envelopes is >>> infinite, and I look in the first envelope, then I will want to switch >>> however much I find there. This is not surprising and only slightly >>> paradoxical. This strategy is optimal in the sense that every strategy is optimal. If the expectation is infinite, then your expected gain is infinite, and no strategy will make it finite. But if you want to choose the envelope with more money more often than the envelope with less, then there is a way to do it, and your way doesn't. >But I suppose you will want the 10 cents in advance, before I peek. OK, >that is paradoxical. No paradox. If you have an infinite expectation, you may pay any finite amount and still have an infinite expectation. Switch, don't switch, throw away finite amounts of money, none of these affects the expected winnings. Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Jan 8, 2000 12:14 AM Subject: Re: penrose tiles Sebastian Ahnert wrote: >what properties must a pair of tiles have, for it to tessellate >non-periodically? I'll take this as a question about a pair of tiles that tiles but admits no periodic tiling. As stated, there are easy examples, such as a 1x2 brick. No one has a characterization of aperiodic tile sets. No one knows if there is a single tile that might do so, or a pair that tiles other than in the golden ratio, or any number of other questions. > what would be another example besides the "kites and darts"? There are a pair of rhombi, and a pair of chickens, and any number of other examples. They are covered in the article by Martin Gardner and any number of other places. >are there pentagonal or triangular examples? None known. >also, [Gerald Edgar writes]: >> they can tile the plane, but cannot tile it periodically >but can't the "kites and darts" tile periodically? (i'm afraid i'm a little >confused here) To make them an aperiodic set, you have to decorate them so that they can't fit together periodically. This can be done by enacting matching rules, or by altering the shape of the edges. Gerald Edgar also wrote: >> "Penrose tiles" might be a generic terms for any set of tiles with >> the property you mention (or, more precisely, they can tile the >> plane, but cannot tile it periodically) ... I wouldn't any aperiodic set "Penrose tiles". Hao Wang (or was it someone disproving Wang's conjectures?) had a (much larger) set long before Penrose. Perhaps Penrose tiles should refer to pairs that deflate and inflate goldenly. Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Jan 10, 2000 9:19 PM Subject: Re: Y to K puzzle About counting paths in hexagonal grids, qscgz@aol.com wrote: [ A lot of stuff. Much of which I have no answers for. But the things I will comment on (some from my own message) are below. ] > Dan Hoey wrote: [...] > > The code requires that the graph be induced on a "skinny" > >rectangular part of a hexagonal grid. Skinny because the time > >and storage are more than exponential in the width (number of > >rows) of the rectangle, but a low polynomial in the length (I think > >cubic--the number of multiplications is linear in the length, but > >they operate on big numbers). Oops--I forgot there are no bignum multiplications, only additions. So the run time is quadratic in the length. > so,what keyboard size can you handle in -say- 1 hour ? My program is memory limited now, so there's nothing I can run it on for an hour. But here are some sample rectangle sizes and times: Width Length Seconds Width Length Seconds 2 400 8 5 10 8 2 800 42 5 20 48 3 80 6 6 4 6 3 160 28 6 6 18 4 25 6 6 8 54 4 50 30 [.... I continued: ] > >At its heart, the technique really only requires that the graph > >have a low-bandwidth vertex ordering (the bandwidth of an ordering > >v1,v2,...,vn is the maximum over j of the number of edges (vi,vk) > >with i <= j < k). Finding the minimum bandwidth is NP-complete, > >but often you can find an ordering that's good enough. [...] Oops--I looked this up in Garey and Johnson, and what I'm using is the "Minimum cut linear arrangement" (even though I think they should say "maximum" or "minimax"). At any rate, what we require is that the graph have a linear arrangement with a small cut width. > you mean : the graph has one , _and_ you have to find it ? > and only total orderings = permutations are allowed here ? The algorithm uses whatever vertex order you give it. The smaller the cut width in whatever arrangement you use, the faster the dynamic programming runs. And yes, they are linear (= total) orderings. > interesting , have you a (short and easy) reference , preferrably > online , where to find such stuff ? Garey and Johnson mention the problem as GT44. The published reference they give is Gavril, "Algoriths on circular-arc graphs," _Networks_ 3, 1977. Possibly a search engine will turn up something on optimal graph-cutting techniques. >But how to find permutations with low bandwidth ? In the case of rectangles in a hexagonal grid, I had in mind listing the vertices from left to right. If the rectangle is skinny (= not tall), the cut width will be small (about twice the height). Dan Hoey haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Jan 10, 2000 9:52 PM Subject: Re: Clive Tooth's newsgroup stalking James Harris wrote: > Dan Hoey wrote: >> ... I'm certainly an agnostic on >> whether there exists a simple proof. But I'm sure it won't be found >> with a drunkard's walk through random algebraic manipulations. >> Especially when performed by a fool who stops every time his >> egregious error frequency leads to a contradiction, and needs >> to wait for someone competent to find his mistakes for him. Sheesh, and I thought I knew better than to answer the fool's ravings. But here goes. >Well, I'm certain that you not only don't have any idea about how to >actually discover anything but that you're a rude and obnoxious >person who has the manners of someone raised in a barn.... I'm amused at being told what I can't discover by such a ridiculous wannabee. I guess it's a lot like a lot of things Harris is "certain" of. But the idea that I'm a meanyhead for calling him a fool is pretty silly. The source of fifty garbage proofs in four years is clearly a fool, either the kind who's just idiotic or the kind who's just acting. I'm charitable enough to believe he's a sincere dolt. Well, he always has to have the last word, and I'd rather not prolong his rant beyond what I've already done, so I hope I can trust the good people of sci.math to treat his response to _this_ message with all the respect it deserves. Dan Hoey --- Newsgroups: rec.puzzles From: haoyuep@aol.com (Dan Hoey) Date: 2000/01/22 Subject: Re: Any one have an apple? amor...@Xenon.Stanford.EDU (Alan Morgan) wrote: >Joe Slater wrote: >>>BB wrote: >>>>My local greengrocer is a would-be mathematician. He likes to >>>>arrange his apples in nice rows. However, when he lays his apples >>>>in rows of 3 he has one left over. When he lays them in rows of 5 >>>>he also has one left over. Remarkably he also has one left over >>>>when he arranges them in rows of 7 and 9. 11 seems to be the magic >>>>number, for, in rows of 11 there are no apples left over. How many >>>>apples does the greengrocer have? >>amor...@Xenon.Stanford.EDU (Alan Morgan) wrote: >>>12828376 apples. >Joe Slater wrote: >>You must have very patient greengrocers in your neighbourhood. I >>thought mine was being quite polite when he agreed to lay a mere 946 >>in rows. Well, _my_ greengrocer solved the problem with only 121 apples. But he heard screams of outrage from the people with more number theory than cleverness when he (rot13 to give you a last chance to be clever) neenatrq gur nccyrf va gjryir ebjf bs frira naq sbhe ebjf bs avar, jvgu bar yrsg bire. Read the problem statement carefully! Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Jan 22, 2000 12:08 AM Subject: Re: Twin Primes (non-hoax) Len Smiley said: > The following theorem, provocative to professional and amateur alike, > appears in the Jan 2000 issue of American Mathematical Monthly: > The number of twin prime pairs is finite if and only if, for n > sufficiently large (integer), > n = 6 |ab| + a + b > for some nonzero integers a and b. Kurt Foster provided a proof just now, as well. I wouldn't call it "provocative" so much as "a simple but non-obvious transformation of a well-known problem", and I'm not too sure about "non-obvious." > The author is Maria Suzuki. She thanks mentors Hajir and Apostol of > Caltech. But did the mentors tell her where they got the reformulation? I've got a strong recollection of ths problem, or something very much like it, on sci.math a few years ago. I seem to recall it asked whether if every sufficiently large n could be so represented (i.e., posing the twin prime conjecture in disguise). Dan Hoey posted and e-mailed --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Jan 27, 2000 10:00 PM Subject: Re: My FLT James Harris wrote: [ Another swan song, full of self-pity, signifying nothing. ] If you are new to sci.math and are considering contributing to this thread you may wish to read this page first: http://www.pisquaredoversix.force9.co.uk/JSH.htm An update: That page does not include Harris's "decision" to stop posting here that he announced two weeks ago. That isn't his first such announcement, and two weeks is a pretty pathetic amount of time to keep to a decision before reneging. One might even suppose that the announcement of leaving is simply a ploy to attempt to garner a little sympathy before going back to the usual offensive behavior. But there is a ray of hope in the observation that two weeks is a relatively long time for Harris to remain consistent. Perhaps he may hang on to it longer this time. I don't for a moment think that he has anything approaching the character it takes to make a permanent decision to quit sci.math. But I sure would appreciate being wrong on that score. I would even apologize for this cynicism, say on 27 January 2001, if he could keep such a resolution for a year. As if. Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Jan 29, 2000 6:10 PM Subject: Re: names of groups >Oliver Pooley wrote: >>A trivial question of terminology really. >>What are the canonical names for >>1) the group of rigid rotations and translations in (3-d) Euclidean space >>2) the above supplemented with spatial inversions >The transformations in (2) are called "isometries." They are also sometimes called "congruences", a name I prefer for all that it is somewhat out of fashion. >The transformations in (1), I suppose, could be called >"orientation-preserving isometries" More commonly they are called "direct isometries" (or direct congruences). Other terms listed by P B Yale (_Geometry and Symmetry_) are "motions", "proper motions", "rigid motions", and "displacements". Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Jan 31, 2000 11:48 PM Subject: Re: geometric dissection problem with rectangles [ Reposted to sci.math--the original went only to rec.puzzles. ] David Bernier writes: >...The general question relates to two rectangles with integral >sides whose areas differ by one square unit; suppose a,b,c and d >are positive integers and that axb = cxd -1; suppose R_1 is an >axb rectangle and R_2 is a cxd rectangle; when can we dissect >R_1 into two pieces along grid lines which, when reassembled, >give R_2 less a hole of size 1x1 ? ... >As a specific instance, what about the case: a=13, b=8, c=21, d=5 ? This case is not possible. For suppose we have a rectangle A consisting of 13 rows of 8 squares. We wish to cut this to cover a shape B consisting of a 21 x 5 rectangle minus one square. Neither piece of A can be longer than 13 squares in any dimension. B must have at least one square on its first row and one square on its 21st row, and these must be covered by separate pieces of A because of the length restriction. The restriction also implies that no part of the top 8 rows of B can be covered by the piece that covers the 21st row, and since there are only two pieces, this 8 x 5 rectangle (minus at most one square) must be covered by one piece of A. Similarly, the bottom 8 rows of B form an 8 x 5 rectangle, minus at most one square, covered by the other piece of A. There are only two ways to cut the two 8 x 5 rectangles from A (even allowing a one-square overcut), and in neither case is any of the unused part of A contained in the oo x 5 strips formed by extending the 8x5 rectangles' long axis. So there is no way to extend the pieces to cover the central 5 rows of B, QED. This is a fairly ad hoc way of deciding a two-piece dissection problem, but it is good enough to show that no skip-2-Fibonacci rectangle (of size F_(n+1) x F_(n-2)) can be cut in two sets of squares to cover the corresponding adjacent-Fibonacci rectangle (F_n x F_(n-1)) minus one square, for F_n > 5. ObPuzzle: Find the part of the proof violated by F_n=5. Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Feb 24, 2000 12:48 AM Subject: Re: Travelling Salesman Problem >1. Assume we are given a set of cities AND the optimal tour for those >cities. If we move ONE point ... I'm afraid I haven't got an answer to this question, though I can imagine you may be able to show it is NP-hard by reducing it to changing a single variable in a SAT problem. Of course, this doesn't show it is TSP-hard (since Euclidean TSP is not known to be in NP). > If this can't be shown true for ANY new location of the given >point, does anyone know if there exists some f(Theta) = Delta -- >(Theta being the angle that the point will be moved at, and Delta >being the distance it is moved) such that the optimal tour is >unchanged?.... The "angle that the point will be moved at" with respect to what? I suspect some widget can be constructed in which a point is arbitrarily close to some critical location that changes the tour in some huge and nonobvous way. >2. If a tour can be constructed that forms an entirely convex figure >(I don't know if this is the right word, what I mean is that all the >interior angles are <= 180), can say that must be the optimal tour? Yes. When the points are all on their convex hull, the optimal tour is the convex hull taken in order. Any other order would cause edges to cross, which is easily seen to be suboptimal. Dan Hoey (posted and e-mailed) --- Math Forum From: Dan Hoey Date: Feb 24, 2000 1:24 AM Subject: Re: Alternative proof of FLT ? Jan Kristian Haugland writes: >I think the only interesting thing about these crank proofs is that >it's a challenge to try to convince the would-be provers that they >are wrong. It's been proven that no "elementary" proof of FLT can >exist. Your later explanation of this statement leads me to believe that it is based upon a definition of "elementary" that implies "equally applicable to the integers and to the p-adics", which does not apply to the crank proofs we usually see. However, it has been shown that no proof of FLT can exist that is composed of ill-defined terms, unfounded assumptions, and gaping non-sequiturs. Those are the kind we get all the time. You can presumably find one cited in this very thread (the presumption arising from observation of a habitual crank poster announcing yet another revision of his habitually botched approach to his habitual subject, absent any apparent amelioration of his habitual incoherence.) Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Mar 2, 2000 10:24 PM Subject: Re: Solution to four-color problem Clifford J. Nelson wrote: >See: >http://www.forum.swarthmore.edu/epigone/geometry-research/kumfrousmy The only reason to read Fuller's obscurantist babbling on this subject is to verify that he had no idea what he was talking about, or that he was intentionally writing in irrational doubletalk to disguise his lack of insight into the problem, or both. The referenced forum offers an additional demonstration that Nelson is no more perceptive, or principled, or both. Dan Hoey "I have found things that are trivial in math but overlooked haoyuep@aol.com and even contradicted in the books I have read." --Cliff Nelson on his sources of inspiration --- Math Forum From: haoyuep@aol.com (Dan Hoey) Date: Mar 6, 2000 9:30 PM Subject: Re: adjacency matrix of isomorphic graphs Boris Hollas writes: >Let G, G' be isomorphic graphs with adjacency matrices A and A'. Why >does then exist a permutation matrix P (i.e. an invertible matrix P >with entries in {0,1}) such that A'=P A P^{-1} ? You haven't quite defined "permutation matrix" correctly. The n x n permutation matrix P_r associated to a permutation function r:{1,...,n}->{1,...,n} is a matrix whose i'th row has a one in column r(i) and zeroes elsewhere. So 1 1 0 1 0 0 0 0 1, while invertible, is not a permutation matrix. With this definition, note that the i'th row of A P_r is the r(i)'th row of A and that the inverse of a permutation matrix is the same as its transpose. Prove that and you will know why. Dan Hoey posted and e-mailed haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Mar 9, 2000 12:17 AM Subject: Re: NP-complete problems & algorithms to solve them David Eppstein writes: > David Bernier asks: >> ... the time growth-rate of the fastest known algorithms for SAT >> (or any other NP-complete problem).... >They are generally of the form 2^(f(n)) for some polynomially bounded >function f, but the function (or the base of exponent) can vary >considerably from problem to problem. I'd say that for just about all the NP-complete problems I've seen there is an algorithm for time O(exp(k n)) = O(alpha ^ n) for some constants alpha=exp(k). It is hard to pin down more closely, because the encoding of the problem affects the parameter--if we can compress the input by a factor of b, we effectively multiply k by b (or raise alpha to the b'th power) using the same algorithm (plus a subexponential-time decompression step). >I think for SAT itself the best algorithm is the obvious O(m 2^n), but >3-SAT is much smaller.... I'm pretty sure SAT is one of the NP-complete problems with the more bloated natural representations, which makes k (or alpha) relatively small. Algorithms reported in 1993 had alpha down to 1.04 or so (k=ln(2)/17) if we measure problem size by the number of variables. I seem to recall there were some people who thought the number of literals was a better measure, and had a fairly small alpha. There's some work on determining the ratio of literals to clauses that makes for hard SAT problems. You may be able to find pointers to these results at ftp://dimacs.rutgers.edu/pub/challenge/; if you can't find anything let me know and I'll see what I can find in my files. Dan Hoey posted and e-mailed --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 2000/03/10 Subject: Re: NP-complete problems & algorithms to solve them David Eppstein writes: >Perhaps you didn't read the part of my message where I noted that >planar and geometric TSP could be solved faster than that, in time >O(alpha ^ sqrt(n)) or O(alpha ^ {sqrt(n) log(n)})?... Indeed, I missed that. And while I thought I was quoting worst-case bounds, on reflection I'm pretty sure they were only experimental data. I apologize for excessively trusing such a vague memory. Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 2000/03/14 Subject: Re: Mr Benschop ad nauseam Robin Chapman writes: >Let's look at the 27 Dec 1999 version of Benschop's non-proof >of FLT. >Page 8.[...] Nice. I didn't get that far. But it's startling how badly he could botch Theorem 3.1. As written, it's a restatement of the definition. I amused myself by proving the slightly nontautological: For invertible elements a,b,c of a ring with identity, consider the four statements: P. a + b^-1 = -1 Q. b + c^-1 = -1 R. c + a^-1 = -1 S. a b c = 1 Then any two of these statements imply the others. It's not hard to prove this by trial and error, though I suspect there's an effective method (is it a Grobner thing?). But Benschop writes down the four statements and doesn't say what he's proving. Can we guess what he's proving from the proof? He reasons that that given S we have P=>Q=>R=>P, but then he concludes S! Dan Hoey haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Mar 14, 2000 8:32 PM Subject: Re: zero (0) knowledge Ken.Pledger@vuw.ac.nz (Ken Pledger) writes: > ram@tiac.net (robert a moeser) wrote: [...] >> I found an interesting book about zero [...] > Could you post the details of that book please? Probably _The Nothing That Is, A Natural History of Zero_, by Robert Kaplan. Oxford, 1999. ISBN 0-19-512842-7. Dan Hoey posted and e-mailed haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Mar 14, 2000 8:45 PM Subject: Re: Finding the median in 5 elements Richard Sze wrote: > Given a set of 5 elements, find the median of it in exactly 6 > comparisons Look for the best of the best, and always reuse your leftovers. First compare two pairs of elements, then compare the two maxima. The maximum of four is too large to be the median. Discard it. Of the remaining elements, one pair has already been compared. Do it again (reusing the leftover compared pair). Three elements remain; we want their maximum. Discard the smaller of the second leftover compared pair and return the larger of the remaining two elements. Dan Hoey posted and e-mailed haoyuep@aol.com --- Math Forum From: haoyuep@aol.com (Dan Hoey) Date: Mar 14, 2000 9:21 PM Subject: Re: Mr Benschop ad nauseam Pertti Lounesto wrote: > Dan Hoey and Robin Chapman, grow up! .... I should have expected to become a target eventually. Let me make my position clear. Lounesto has shown himself to be an obsessively abusive poster who argues his irrelevant topic with a combination of repetition, misdirection, wilful distortion, and dishonesty. Attempting to debate him as if he were a rational human being is a waste of time, and is detrimental to the conduct of mathematics on sci.math, and the pig likes it[*]. Should he continue his campaign of abuse, it would be helpful for someone to produce a web page that can be used to warn newcomers of the inutility of engaging in discussion with him. If he addresses me further, this posting may be taken as my response. Dan Hoey [* Don't mud-wrestle with a pig--you'll get dirty and the haoyuep@aol.com pig likes it. No other resemblance intended.] --- Math Forum From: haoyuep@aol.com (Dan Hoey) Date: Mar 14, 2000 9:56 PM Subject: Re: 1.9...is it 2? On a discussion drawing a distinction between the real number 1 and the integer 1, David W. Cantrell wrote: > Alan, I agree with you (and would guess that Derek would agree > as well) that the point being made is indeed quite insignificant. > Nonetheless, there is no reasonable way to construe "0.999..." as > representing an integer. Of course, it may be construed as the > real number (an "integer" real number, so to speak) which could > be more simply represented as "1". On the contrary, it is quite reasonable to consider the integers a subset of the reals. Many mathematicians, myself included, consider them to be so. I am aware that some other mathematicians consider the integers to be a non-identical isomorphic copy of a subset of the reals. The issue is generally considered moot. That is to say, that mathematics is carried on in such a way that it remains valid whether or not we consider the integers to be a subset of the reals or merely isomorphic to such a subset. In case you are wondering, the foundations of the system I prefer are perfectly sound. Whereas some people (for instance) construct the reals as a partition of the rational Cauchy sequences, I consider such a construction to be only the penultimate step of the construction of the reals. The final step is to take the reals as the union of the rationals and the irrational equivalence classes. To prefer one of these constructions to another is no more material than to prefer a Cauchy sequence construction to Dedekind cuts or Conway options. Of course, there are other systems that have "integers", and perhaps some of those sets of integers can be isomorphic to Z without being usefully identified with Z. There are plenty of other structures with isomorphic copies of well-known structures. But when I speak of _the_ naturals N, _the_ integers Z, _the_ rationals Q, _the_ algebraic reals, _the_ reals R, and _the_ complex numbers C, I am speaking of a tower of subsets. You should understand that they act just like the ones you speak of, except for some equalities that you would treat as isomorphic images. > >1 is a positive integer, a rational, a real, whichever you need > >it to be. > Yes, assuming that you mean that "1" can represent either a positive > integer, or a rational, or a real number, or... No, if you are > thinking that the multiplicative identity elements of Z+, Q, and R > are the same. They are not; they are very different types of entities. It is reasonable for you to consider them different, just as it is reasonable for me to consider them identical. I cannot force you to consider my point of view to be reasonable, but I will consider you unreasonable if you do not. Dan Hoey posted and (hopefully) e-mailed haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 2000/03/15 Subject: Re: from distancetable to position mde" wrote: > suppose n points in 3-space. I know all distances between any > points. How can I determine the positions of the points (of course > up to symmetry). Is there an algorithm for this, as I need this in a > program. any help appreciated. There's probably a better way, perhaps involving Cayley-Menger determinants, but here's a way to find coordinates for n points in the smallest Euclidean space E^k that will hold them. Take two points P, Q with d(P,Q)>0. If there are no such points then all points are at the origin and k=0. Otherwise let the first coordinate of each point R be (d(P,Q)^2 + d(P,R)^2 - d(Q,R)^2) / (2 d(P,Q)) and project the points into E^(k-1). Use the distance function d'(P,R) = Sqrt( (d(P,Q) + d(P,R) + d(Q,R)) * (- d(P,Q) + d(P,R) + d(Q,R)) * (d(P,Q) - d(P,R) + d(Q,R)) * (d(P,Q) + d(P,R) - d(Q,R)) ) / (2 d(P,Q)) to find their coordinates. Note that P and Q will be the same point in E^(k-1). Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 2000/03/15 Subject: Re: from distancetable to position About converting a distance table to an embedding in E^k, I wrote: >Take two points P, Q with d(P,Q)>0. If there are no such points then >all points are at the origin and k=0. >Otherwise let the first coordinate of each point R be > X_R = (d(P,Q)^2 + d(P,R)^2 - d(Q,R)^2) / (2 d(P,Q)) >and project the points into E^(k-1). That's fine, but the distance function to use in E^(k-1) was incomplete. For points R, S, use d'(R,S) = Sqrt( d(R,S)^2 - (X_R - X_S)^2 ). It seems to me that we could conduct the entire computation in exact rational arithmetic using the squares of the distance functions, up to the point of producing the actual coordinates. This would prevent the accumulation of roundoff error. Dan Hoey --- Date: Wed, 15 Mar 00 17:24:45 EST From: Dan Hoey To: spears@AIC.NRL.Navy.Mil (William Spears) Subject: Re: www statistics > Interestingly any number in base-3 (with 0, 1, and 2 digits) can > be written with (-1, 0, and 1 digits). The -1 means the weight is > on the left, the 0 means it isn't on the scale, and the 1 means > the weight is on the right. I have seen that. Knuth has it in volume two, called the "balanced ternary" system. "Perhaps the prettiest number system of all." > I'm sure this is really primitive stuff, but it got me wondering > about similar tricks in other bases (like base 5)... I haven't seen anything done in balanced base 5. Dan --- Date: Wed, 15 Mar 00 17:44:15 EST From: Dan Hoey To: spears@AIC.NRL.Navy.Mil Subject: more math > The transformation I use to go from base 3 to balanced base 3 > is to convert a 2 to a 0 and add 1 to the next higher order digit. Change 2 to -1 and add 1 to the next higher digit. Another way is to add (3^n-1)/2 and subtract one from every digit. > I just played with it and it looks as if to go from base 5 to > balanced base 5 (-2, -1, 0, 1, 2) one converts a 3 to a -2, or > a 4 to a -1, and then add 1 to the next higher order digit. Yes, or add (5^n-1)/2 and subtract 2 from every digit. The cute thing is to design a circuit to add two balanced numbers. I don't remember if you can do it from right to left or not. Dan --- Math Forum From: haoyuep@aol.com (Dan Hoey) Date: Mar 16, 2000 1:24 AM Subject: N as a subset of C (was Re: 1.9...is it 2?) On my contention that the usual sets of numbers may reasonably be considered to intersect each other, David W. Cantrell wrote: > haoyuep@aol.com (Dan Hoey) wrote: > >In case you are wondering, the foundations of the system I prefer > >are perfectly sound. Whereas some people (for instance) construct > >the reals as a partition of the rational Cauchy sequences, I > >consider such a construction to be only the penultimate step of the > >construction of the reals. The final step is to take the reals as > >the union of the rationals and the irrational equivalence classes. > Now you've really got my attention! Thanks so much for bringing up > this possibility. I am at once intrigued and skeptical. I've never > seen it before. Surely it's not widely used. Could you please > mention some sources in the literature describing this "hybrid" > construction of the reals? I'd be very grateful! I learned it as a freshman 30 years ago (and if Garth Gaudry is still around, someone may convey my gratitude). It was just an aside in the foundations sequence, that if anyone could possibly be worried about the foundational distinction between integer integers and real integers, it is a simple exercise in set surgery to make sure they are identical. Perhaps few people completed the exercise. Perhaps it lives only in folklore. > By "rationals" in the last sentence above, would you actually mean > constant sequences of rationals perhaps? Actually, I think I said it right. I may create a set R*, say of equivalence classes of Cauchy sequences of rationals. Some of these, say Q*, correspond to rational numbers in the obvious way. Then the set of real numbers R = Q union (R* setminus Q*). > Might I then infer that in constructing the rationals, your final > step is to union {(n,1) | n in Z} with the set of noninteger > equivalence classes, so to speak? Again, it's the other way. Let Q* be the set of equivalence classes of pairs of integers. Z* is the subset of Q* that contains the classes of (n,1), corresponding to Z. Then Q = Z union (Q* setminus Z*). I may as well point out the odd way this can fail, and how to fix it. If the above construction happens to produce an equivalence class q* in (Q* setminus Z*) that by sheer set-theoretic coincidence is equal to an element of Z, then there would be problems (the union defining Q would not be a disjoint union). If so I decorate all q* in Q with the set Z just in case, and let Q = Z union { (q*, Z) : q* in (Q* setminus Z*) }. Again, this is just set surgery. This sort of thing isn't discussed much because it is so trivial. Set theory is easily capable of building the sets we want with whatever (consistent) identifications we want. It is a triumph of set theory to generate our number systems; this is just bookkeeping. The philosophy here is that while acknowledging the foundational nature of these constructions, I wish to take steps to see that they produce the classical set-inclusion relations, so that no one can quibble over whether real sequences can approach an actual integer or merely a "real integer". I'll also mention that while I am a fan of 0^0=1 in all systems that can express it, this sort of construction does not require agreement with that view. There can certainly be several exponentiational operators to be used in their proper contexts on domains that intersect or are even equal. I gladly accept (-1)^(1/3)=-1 when "^" stands for real exponentiation, and (-1)^(1/3)=exp(pi i/3) when "^" stands for complex exponentiation, even though I maintain that exactly the same -1 and 1/3 are used. In the same way, we can use an extensional exponentiation on the reals that defines 0^0=1, or a continuous exponentiation that leaves 0^0 (and quite a few other values) undefined, and even a bizarro exponentiation for which 0^0=0, or 5, or pi. We can even use them on the same page of the same book, as long as we make it clear which one we are using at each point. This is also true of whatever other operators we choose to define. > >It is reasonable for you to consider them different, just as it is > >reasonable for me to consider them identical. I cannot force you > >to consider my point of view to be reasonable, but I will consider > >you unreasonable if you do not. > I'll need to carefully consider your point of view first! Maybe it > will be sufficiently attractive that it will become my preferred > point of view as well. Of course, I don't expect you to consider things reasonable without reasoning. This is not quite a no-brainer. But I don't think this is rocket science, either. After all, we usually act as if N is a subset of R--why not make it really be so? Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Mar 18, 2000 1:10 AM Subject: Re: Palindromic Sum Conjecture Gerry Myerson writes: >Here's what David Wells says in The Penguin Dictionary of Curious and >Interesting Numbers: > 196 is the only number less than 10000 that by this process has > not yet produced a palindrome.... P. Anderton has taken this up > to 70928 digits.... Poor David Wells. So many good curiosities, so many errors. In fact, if 196 has not produced a palindrome, then neither has 885 = 196+691. I seem to recall there are plenty of other non-palindrome producing numbers between 200 and 1000. There's no reason to suppose they will ever produce palindromes, and certainly some good reasons to suppose they won't. I'd be interested in the sequence a(n) of the largest (finite) number of steps in which an n-digit number has produced a palindrome. I suspect it's not all that fast-growing a function. Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Mar 20, 2000 9:07 PM Subject: Re: from distancetable to position Among many good ideas, Dave Rusin wrote: > First, note that (if the triangle inequality holds at least) the points > _can_ be embedded into a higher-dimensional Euclidean space and > have exactly the measured distances between pairs. That's not quite right. They also have to satisfy the tetrahedron inequality | 0 d12^2 d13^2 d14^2 1 | | | | d12^2 0 d23^3 d24^2 1 | | | | d13^2 d23^2 0 d34^2 1 | > 0 | | | d14^2 d24^2 d34^2 0 1 | | | | 1 1 1 1 0 | and the higher-dimensional simplex inequalities given by the analogous Cayley-Menger determinants. Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 2000/03/21 Subject: Re: unitary (Egyptian) fractions Hugo van der Sanden wrote: > Prompted by a recent reference to the section (D11) on Egyptian > fractions in Guy's 'Unsolved Problems in Number Theory', I noticed > mention of this problem (paraphrased): > Order the rationals a/b, 0 < a/b < 1, (a, b) = 1, by increasing a+b > and then by increasing a: 1/2, 1/3, 1/4, 2/3, 1/5, 1/6, 2/5, 3/4 ... > What is the earliest such rational that cannot be expressed as the > sum of n unit fractions? I'm sure you mean n _distinct_ unit fractions. > I was surprised that so few results were known: 2/3, 4/5, 8/11, 16/17, > 77/79 cannot be expressed as the sum of 1, 2, 3, 4, 5 unit fractions > respectively. So I write a simplistic perl program, which has found > (after just over a mips-year of work) that 732/733 is the first in > the list that cannot be expressed as the sum of 6 unit fractions. > Since this program exercises perl beyond the limits of its integer > accuracy, I cannot guarantee the result - can anyone confirm it for me? I dusted off some old Egyptian fraction code I wrote a couple of years ago. It uses Common Lisp's exact integer arithmetic, so roundoff is not an issue. I verified that all fractions up to 732/733 have six-term representations and that 732/733 requires seven terms. It took about 13 hours on a 296 Mhz Ultra. If a mips is a Mhz, that's almost half a mips-year. I don't how much of the remaining speed difference is due to the programming language/system and how much is due to the algorithm. By the way, I found that 732/733 has 2771 different seven-term representations. The largest denominator appears in the representation (2305193137933140 33397845 4484 45 7 3 2). The smallest maximum denominator appears in (26388 20524 7330 45 7 3 2). Dan Hoey Posted and e-mailed --- Math Forum From: Dan Hoey Date: Mar 22, 2000 10:10 PM Subject: Re: unitary (Egyptian) fractions milogardner@juno.com (Milo Gardner) wrote: > Dear David, Joe, and others: > I can agree that with the first partitions 1/2, 1/3, 1/7 that four > additional partitions are needed to solve the 732/733 problem.... > That is, I will now go onto the 1/2, 1/4, 1/8 first terms.... There are 1456 solutions starting 1/2 + 1/3 + 1/7, 597 solutions starting 1/2 + 1/3 + 1/8, 129 solutions starting 1/2 + 1/3 + 1/9, 111 solutions starting 1/2 + 1/3 + 1/10, 38 solutions starting 1/2 + 1/3 + 1/11, 21 solutions starting 1/2 + 1/3 + 1/12, 4 solutions starting 1/2 + 1/3 + 1/13, 1 solution starting 1/2 + 1/3 + 1/15, 1 solution starting 1/2 + 1/3 + 1/16, 302 solutions starting 1/2 + 1/4 + 1/5, 21 solutions starting 1/2 + 1/4 + 1/6, 9 solutions starting 1/2 + 1/4 + 1/7, 20 solutions starting 1/2 + 1/4 + 1/8, 1 solution starting 1/2 + 1/4 + 1/9, 1 solution starting 1/2 + 1/4 + 1/10, 38 solutions starting 1/2 + 1/5 + 1/6, and 17 solutions starting 1/2 + 1/5 + 1/8. for a total of 2767. My previous report of 2771 was due to a clerical error. Dan Hoey --- Newsgroups: dc.general From: haoyuep@aol.com (Dan Hoey) Date: 2000/03/24 Subject: News of the Weird cartoon in March 24 City Paper In the March 24 D. C. City Paper, the News of the Weird cartoon (p. 20) shows an old guy in coveralls with a trowel (and maybe a perceptible tumescence--you can never tell with Belschwender) being blessed (or greeted) by a bearded longhair in gown and halo, seated on a stack o' bibles (either JHVH or INRI, I'd say, with odds on the latter--those books got crosses on em). So what the HCK does this have to do with paying schoolkids a wage, or feminist divorce/riot control in Egypt/S.Korea? Or is it about one of the other weirdnesses in the column? Or a retread cartoon inserted by accident? Could it possibly be A STORY TOO WEIRD TO PRINT that got yanked at the last minute?? Frugally enquiring minds gots ta know! Dan Hoey --- Math Forum From: Dan Hoey Date: Mar 24, 2000 2:51 AM Subject: Re: unitary (Egyptian) fractions David Eppstein writes: > haoyuep@aol.com (Dan Hoey) writes: >> ... dynamic programming, or some smarts involving factoring. > You at least know about the trick about using factoring for finding > the last two terms, right? So you only have to brute-force the > first five. That's what I was thinking of, but I hadn't worked it out. So far, I think if you want to find a two-term representation of m/n as 1/(ac)+1/(bc), (a,b)=1, you look for a divisor a|n such that a < min(sqrt(n),m/2), and for which (m-a)|(n/a). Then ac=n/(m-a) and bc=n/a. Is that the whole trick, or is there something trickier? Dan Hoey Posted and e-mailed --- Math Forum From: haoyuep@aol.com (Dan Hoey) Date: Mar 24, 2000 2:55 AM Subject: Re: unitary (Egyptian) fractions Hugo van der Sanden wrote: > Bill Taylor wrote: > > I'd like to plump for a slightly different ordering, which seems > > much more natural to me; the Farey ordering. i.e. Order coarsely > > by denominator, then more finely by numerator: 1/2 1/3 2/3 1/4 > > 3/4 1/5 2/5 3/5... > Surely the Farey series is in terms of increasing size, up to a > given maximum denominator? F_5 = [ 0, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, > 2/3, 3/4, 4/5, 1 ] as I remember it. There's also another ordering related to Farey series: 1/2, 1/3, 2/3, 1/4, 2/5, 3/5, 3/4, 1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5, 1/6, 2/9, 3/11, 3/10, 4/11, 5/13, 5/12, 4/9, 5/9, where each term (a+c)/(b+d) is formed from two numerically adjacent predecessors a/b and c/d (including the ghosts 0/1 and 1/1 at the ends). Is there a name for this sequence? Dan Hoey --- Newsgroups: sci.math.num-analysis From: haoyuep@aol.com (Dan Hoey) Date: 2000/04/14 Subject: Re: Q: Inverse of large, sparse boolean matrix [My regrets to anyone who sees this twice. It seems AOL does not do crossposting.] Robert Israel wrote: > A way to produce an NxN matrix with 3 ones in each row and > column, all such matrices being equally likely is this: > 1) Let p be a random permutation of 1 .. 3N. > 2) For i from 1 to 3N let q[i] = ceil(p[i]/3) > (where ceil(x) is the least integer >= x) > 3) If for any i from 1 to N, q[3i-2],q[3i-1] and q[3i] are not > all distinct, reject p and return to step (1). > 4) For i from 1 to N let A[i,q[3i-2]], A[i,q[3i-1]] and > A[i,q[3i]] be 1. Ouch! You're going to spend a long time looking for those needles in that haystack. Lots of needles, but lots and lots of hay. A better way is to calculate the function f(x,y,z) that is the number of ways to adjoin (3x+2y+z)/3 rows of 3 ones and n-3 zeroes to a matrix of which x columns have 0 ones, y columns have 1 one, and z columns have 2 ones, so as to yield a matrix with 3 ones in each column. You can calculate f(x,y,z) by dynamic programming as f(x,y,z) = Sum C(x,i) C(y,j) C(z,k) f(x-i, y-j+i, z-k+j) i,j,k where the sum is taken over the ten triples of nonnegative integers i,j,k with i+j+k=3. (C(n,k) = n!/(k! (n-k)!) is the binomial coefficient). Then to choose such a matrix uniformly, adjoin rows one a time. From a partial matrix as above, choose the triple i,j,k with probability C(x,i) C(y,j) C(z,k) f(x-i, y-j+i, z-k+j) / f(x,y,z). Then choose i columns from the x with 0 ones, j columns from the y with 1 one, and k columns from the z with 2 ones, uniformly over all subsets of the appropriate size. The adjoined row has ones in the chosen columns, and the choice procedure is repeated until the matrix is complete. By the way, a similar incremental approach is the way I use to select uniformly from among the C(n,k) k-subsets of {1,...,n}. In that case, though, the ratio is available as a closed form: Include n with probability C(n-1,k-1)/C(n,k) = k/n and exclude n with probability C(n-1,k)/C(n,k) = (n-k)/n. Then choose the appropriately-sized subset from {1,...,n-1}. Dan Hoey posted and e-mailed --- Newsgroups: sci.math.num-analysis From: haoyuep@aol.com (Dan Hoey) Date: Apr 15, 2000 11:40 PM Subject: Re: Q: Inverse of large, sparse boolean matrix [My regrets to anyone who sees this twice. It seems AOL does not do crossposting.] Robert Israel wrote: > Dan Hoey writes: > > Robert Israel wrote: > > > A way to produce an NxN matrix with 3 ones in each row and > > > column, all such matrices being equally likely is this: > > > 1) Let p be a random permutation of 1 .. 3N. > > > 2) For i from 1 to 3N let q[i] = ceil(p[i]/3) > > > (where ceil(x) is the least integer >= x) > > > 3) If for any i from 1 to N, q[3i-2],q[3i-1] and q[3i] are not > > > all distinct, reject p and return to step (1). > > > 4) For i from 1 to N let A[i,q[3i-2]], A[i,q[3i-1]] and > > > A[i,q[3i]] be 1. > > Ouch! You're going to spend a long time looking for those needles > > in that haystack. Lots of needles, but lots and lots of hay. [ ... my method snipped ... ] > Ouch yourself! You have to calculate Theta(N^3) of these numbers. > My way should be (on the average) only O(N) (assuming your > random-permutation generator is O(N)). > For large N, the probability of a "collision" at i, i.e. q[3i-2],q[3i-1] > and q[3i] not all distinct, is approximately 2/N. Thus a random > permutation will have, on average, 2 collisions. The collisions are > not independent, so approximation by a Poisson distribution is _not_ > justified, but it's probably OK anyway: this would indicate that the > probability of success (i.e. no collisions) is approximately exp(-2). > I tried a numerical example, and this seems to be right. So my method > requires, on average, exp(2) < 7.4 tries to get a good permutation. > Quite feasible. Ouch indeed. I developed my algorithm because I didn't have this analysis, and I wanted to know how many times your method would attempt a permutation before finding an acceptable one. I figured that taking f(N) as the number of NxN three-ones-per-row three-ones-per-column matrices, I should take (3N)! / (f(N) 3!^N) to account for your method ignoring the order of triplets of columns. I could see the number increasing exponentially. But now that you mention it, I should have divided by another 3!^N to account for forgetting the order of triplets of rows. Here are some of the results of the corrected formula: N (3N)! / (f(N) 36^N) 10 8.737951 20 8.010789 50 7.626193 100 7.505789 which indeed seems to be about exp(2) + 11.5/N + 17/N^2. Sorry for my mistaken analysis. Dan Hoey (haoyuep@aol.com) Posted and e-mailed. --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 2000/06/22 Subject: Re: Random coverage of a sphere. math...@math.canterbury.ac.nz (Bill Taylor) wrote: >|> > >> what is the probability that four random hemispheres >|> > >> will cover a sphere? [...] > So using a pseudo-proof by incomplete induction, we see that > P(no complete cover) = (n^2 - n + 2)/2^n . YAY! It's not hard to prove by real induction. Suppose N great circles divide the sphere into f(N) regions. For N>1, the Nth circle intersects the previous N-1 circles in 2N-2 points. Therefore that circle passes through 2N-2 previously formed regions, dividing each of them into two, so f(N) - f(N-1) = 2N-2. From this and f(1)=2 we have f(N) = n^2-n+2. Each of the regions is the intersection of N hemispheres, corresponding to one way (out of 2^N) of not covering the sphere. So the probability of incompletely covering the sphere is f(N)/2^n. >No doubt a cubic over 2-power formula gives the 3-sphere case, and so >on; but I leave this for others to tackle. There's your homework! I seem to recall that this doesn't extend to the 3-sphere, because the number of regions is not determined by the number of great 2-spheres. But I'm somewhat uncertain of this recollection, so maybe someone can confirm or deny it. Dan Hoey haoyuep@aol.com Posted and e-mailed --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Jun 23, 2000 7:15 PM Subject: Re: Random coverage of a sphere. jr@redmink.demon.co.uk (John R Ramsden) writes: > [...] > The main problem I have is that the entire induction + complement > argument can be applied unchanged to n halloween pumpkin surfaces, > each of whose boundaries are 2m great circles regularly spaced round > a common pole, and in this case the total-coverage probability is > ((mn)^2 - mn + 2) / 2^n, which for m sufficiently large relative to > n exceeds 1. Oops :-) > (It's true that with sliced pumpkins (SPs) one can't build up the > regions one circle at a time, as one does with the hemispheres. But > the maximum number of regions formable by combining n SPs is > presumably the same as that of mn hemispheres combined in suitable > orientations.) The argument, as I adapted it from J K Haugland, is that from N great circles we have 2^N equiprobable choices of a set of N hemispheres. For each region R, R is the region left uncovered by exactly one of those choices. (The connectedness of the intersection of hemispheres is a consequence of convexity). So if there are R regions, the probability of there being an uncovered region is R/2^N. SPs are not convex, so there may be more than one region left uncovered by the same set of SPs. In that case fewer than R cases will leave the sphere uncovered. I should mention that I've revised my belief in the applicability of this argument to higher-dimensional spheres. Suppose F(N,D) is the number of regions into which the D-sphere is cut by N great D-1-spheres, and consider what happens to a D-sphere already cut by N-1 D-1-spheres when we cut with the Nth D-1-sphere. That Nth D-1-sphere is cut into F(N-1,D-1) pieces by its intersections with the preceding N-1 D-1-spheres. Each of those pieces cuts one of the F(N-1,D) existing regions of the D-sphere in two parts. So F(N,D) = F(N-1,D-1)+F(N-1,D). This goes together with F(1,D)=2 and F(N,1)=2N to yield a Dth-degree polynomial in N for F(N,D). Presumably this arrives at the same result as the argument by Douglas Zare, that the result is twice a partial row-sum of Pascal's triangle. Dan Hoey haoyuep@aol.com --- Newsgroups: alt.folklore.urban From: haoyuep@aol.com (Dan Hoey) Date: 2000/07/08 Subject: Eddy direction vectored by Savvy Traveler/Uganda The Savvy Traveler, a radio travel show by Rudy Maxa, is broadcast Sundays on WETA-FM in Washington, DC. Today they reported on crossing the equator in Uganda. They reported on an entrepreneur who demonstrates water eddies to tourists. On one side of the equator, his bowl drains clockwise; on the other side counterclockwise. On the equator, they reported that no eddy formed! In view of measurements showing that the Coriolis force is much less than typical random currents in sub-geographic bodies of water (unless the water has been carefully quiesced for hours under laboratory conditions) I assume the tourist amuser was directing the eddy on purpose. But the interviewer showed no skepticism at all, even mentioning that a physicist friend told him something he didn't understand about the Coriolis force. asdfasdfffasdfasdfffasdfasdfffasdfasdfffasdfasdfffasdfasdfffasdfasdfff asdf asdfff 0123456789012345678901234567890123456789012345678901234567890123456789 0123 456789 Dan Hoey --- Newsgroups: rec.puzzles From: haoyuep@aol.com (Dan Hoey) Date: 2000/07/10 Subject: Re: Mikero's brainwrenching grid puzzle #4 (June 29, 2000) dan...@benzedrine.cx (Daniel Hartmeier) wrote: > > Score : 157 [...] > As I already know, my program won't find solutions with loops. > But it finds other solutions pretty fast, which means you might > use it to find local optima to use as pruning limits, etc. My program is guaranteed to find all solutions, and confirms that the score of 157 is optimal. This is achieved by three variants of Daniel Hartmeier's solution, jqrklmtsuvwponghaZY{XQR,RQX,RXQ}fedcWVOHA BIPJCKDEFMLSTUbiNG and two variants of another solution jqrklmtsuvwpongZahibUNGTSLMFEDKJCQXYRfedc WVO{PIBAH,HABIP} (and their reverses, of course). I list only the first visit to each vertex. My program starts at each vertex in turn and does a depth-first search for a minimum-cost path. It prunes the search by using the minimum spanning tree cost of the unvisited nodes as a lower bound for completing the path. The procedure of adding a new vertex and recomputing the spanning tree was performed about 109,000,000 times. Mikero mentoned that he designed the puzzle to be difficult for a program to solve. But what made my approach feasible is the closeness of the minimum path cost to the minimum spanning tree cost (157 and 129, respectively). The gap could be made much larger--nearly a 3:2 ratio, if I recall correctly--and would make it much harder to solve. Dan Hoey haoyuep@aol.com Posted and e-mailed --- Newsgroups: alt.folklore.urban From: haoyuep@aol.com (Dan Hoey) Date: 2000/07/11 Subject: Re: Eddy direction vectored by Savvy Traveler/Uganda I've found the interview on the web at http://savvytraveler.com/Show/Features/2000/07.08/uganda.html The credulous traveler in question was Martin Stott. The relevant portion of the segment goes: Roadside entrepreneur: "When you are in the Northern Hemisphere, the water will go down counter-clockwise." There's an entrepreneurial young man here who, for a few dollars, is showing me a great roadside scientific demonstration. Standing in the Northern Hemisphere he fills a bowl with water and then unplugs his finger from a hole in the bottom. Just like emptying a bath, the water swirls and glugs round. Every time he does it, it goes counter- clockwise. A few footsteps away, on the Southern side of the equator he does the same thing. Roadside entrepreneur: "Now on the Southern Hemisphere, it has to turn clockwise." Martin: "So we're in the Southern Hemisphere, here goes... It is! It's turning the other way. That's incredible. Now on the line, let's see what happens there." Roadside entrepreneur: "It goes down, but there is no movement." I can't believe it, right on the equator, no gluggling, no swirling, and straight down the hole. A physicist tells me later that it's all to do with the earth's spin and the Coriolis force. Don't ask me to explain it though. When it comes to science I'm, as we say in Britain, thick as two short planks. [end quote] What I find curious is that people will pay to see a "scientific demonstration" that purports to demonstrate something false, but would presumably not pay as much to see the experiment showing the truth. But I guess it wouldn't be special to see that water at the equator behaves just like it does at home. Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Jul 11, 2000 9:10 PM Subject: Re: Minimization Question digicomms@my-deja.com wrote: >I wonder if anyone could point me in the >right direction in relation to the following >minimization question - take 50 positive numbers >and imagine generating 2^50 numbers (stored in >the set A) by computing all possible sums and >differences using all 50 each time - (i.e. >x1+x2+..+x50,x1+x2+..+x49-x50,x1+x2+..-x49+x50 >etc). What is the value of Min[Abs[A]] (exhaustive >evaluation isn't an option)? Is there a >computationally efficient way to determine this - >my list of 50 initial numbers may grow.... >Many thanks for any suggestions you might have This is a variant of the well-known "Knapsack Problem". It is NP-complete in the weak sense. If the fifty initial numbers are smallish integers (say, small enough that you could make an array whose size is their sum) then the problem is amenable to dynamic programming. If they are high precision reals or huge integers, you may be out of luck. Dan Hoey haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 2000/07/12 Subject: Re: Periodic functions Siva wrote: >"Massimo Redaelli" wrotet... >> Hi all. >> A very simple question, I think, if you don't mind. >> I need a proof, but I can't find it anywere: they all say that the >> theorem is too obvious, and so one can't find anywere the >> demonstration. >> *** Thm: the sum of two periodic functions, whose periods are >> incommensurable, is not periodic. >I am not sure if the term "incommensurable" is standard but >can guess its meaning in this context. How has it been >defined for you? "Incommensurable" means "not being in rational proportion." A,B are incommensurable exactly when for all rational R,S, AR+BS is never zero except when R=S=0. >> Anyone can help me? Suppose F(x)=G(x)+H(x) be periodic functions. It's easy to show that if two of the periods are commensurable, then so is the third. But assuming the Axiom of Choice we can construct three periodic functions with mutually incommensurable periods. For instance, let B be a basis of the reals over the rationals and let a,b,c,d be elements of B. For any real number x, express x as a rational combination x=ar+bs+ct+du... over B, and define F(x) = (r mod 1) + (u+1) (s mod 1) + u(t mod 1), G(x) = u (r mod 1) + (s mod 1) + (u-1)(t mod 1), and H(x) = (1-u)(r mod 1) + u(s mod 1) + (t mod 1). Then it looks to me as if F, G, and H have periods a, b, and c respectively. But the concept of "the period of a function" may not always be well-defined here. What is the period of K(x)=(r mod 1)+(s mod 1) ? Dan Hoey haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Jul 19, 2000 11:25 PM Subject: Re: Periodic functions On the question of whether, given periodic functions f, g, and h=f+g, the periods of f and g must be commensurable, Eduardo Chappa writes: > Hint: > say $f$ is periodic with period $a$, $g$ is periodic of period $b$ and > $h = f + g$ is periodic of period $c$, then the function > $j(x) = f(x+c) - f(x)$, is also periodic, How does the period of this > function relate to $a$ and $b$? That's a fine hint if $j$ has a unique fundamental period, as will be the case if $j$ is a nonconstant continuous function. But a nonconstant (everywhere) discontinuous function can have two noncommensurable periods $a$ and $b$, at least if we accept the axiom of choice. Then ${am+bn : m,n integers}$ must all be periods of the function. In the given case, we can show that $a$ and $b$ are periods of $j$, but I don't see this leading to a proof of commensurability. Dan Hoey --- Newsgroups: rec.puzzles From: haoyuep@aol.com (Dan Hoey) Date: 2000/07/20 Subject: Re: Mikero's brainwrenching grid puzzle #4 (June 29, 2000) Bob Harris writes: > Spurred by your success, I proceeded to write my own program doing > the same thing-- depth-first search with pruning based on minimum > spanning tree cost, as well as some additional pruning (which I'll > mention in a moment).... > ... there must be > some pruning you're doing that I'm missing. If I knew I was leading you into this, I'd have been more explicit. I was afraid of too much revisiting of vertices, so I transformed the problem slightly. For every pair of vertices i,,j, I calculated d(i,j) as the length of the shortest path from i to j. On the graph with all the edges d(i, j) available, it's not necessary to revisit any vertices. On the other hand, there are a lot of edges out of every vertex. I ordered them by increasing length, so once I found one that was too long to consider I didn't have to try any more. I was still concerned about the number of edges, so I did one more trick to cut down the underbrush. For any pair i, j, let the set of waypoints W(i, j) = { k : d(i, j) = d(i, k) + d(k, j) } be the set of vertices that can be visited on the way from i to j without increasing the cost. If any edge has a waypoint that has not yet been visited, I ignore it, since the same path can be constructed by visiting the waypoint first, explicitly. Other than that, I should mention that the 109,000,000 figure refers to the number of expansions performed when the upper bound of 157 is provided ahead of time. I didn't try it with an a priori bound--it might be interesting to try it to see how many additional expansions are needed. This can be minimized by a fortuitous choice of starting vertex. But we can heuristically choose the vertex with the maximin edge, and that (in this case) is a fortuitous heuristic. Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Jul 24, 2000 11:10 PM Subject: Re: geometry/combinatorics/whatever problem Fred W. Helenius wrote: >In other words, you have a bunch of unit lengths of pipe and >120-degree pipe elbows, and you want to know if an odd number >of them can be joined in a ring. >I looked for a solution with n = 7 by fixing three of the >vertices at (-sqrt(3)/2,1/2,0), (0,0,0) and (sqrt(3)/2,1/2,0), >assuming the remaining four were located in symmetric pairs with >respect to the y-z plane, and solving numerically. One solution >for the remaining points is (a,b,c), (1/2,d,e), (-1/2,d,e), >(-a,b,c), where >a = 1, >b = 1.267949243... = sqrt(6)*sqrt(2 - sqrt(3)), >c = 0.626342434... = 2/sqrt(5 + sqrt(27)), >d = 1.300425797... , >e = 1.491758675... . >b and c were identified by the Inverse Symbolic Calculator, >http://www.cecm.sfu.ca/projects/ISC/ ; d and e can in principle >be determined in closed terms by solving a pair of simultaneous >quadratics with coefficients involving b and c. >-- >Fred W. Helenius Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 2000/07/25 Subject: Re: geometry/combinatorics/whatever problem Fred W. Helenius wrote: >In other words, you have a bunch of unit lengths of pipe and >120-degree pipe elbows, and you want to know if an odd number >of them can be joined in a ring. >I looked for a solution with n = 7 by fixing three of the >vertices at (-sqrt(3)/2,1/2,0), (0,0,0) and (sqrt(3)/2,1/2,0), >assuming the remaining four were located in symmetric pairs with >respect to the y-z plane, and solving numerically. I did the solution symbolically with Mathematica, and got four solutions, approximately > {{0, 0, 0}, {.5, .86602, 0}, {1.26795, 1, .62634}, > {1.30042, .5, 1.49176}, {1.30042, -.5, 1.49176}, > {1.26795, -1, .62634}, {.5, -.86602, 0}}, > {{0, 0, 0}, {.5, .86602, 0}, {1.26795, 1, .62634}, > {2.12222, .5, .48416}, {2.12222, -.5, .48416}, > {1.26795, -1, .62634}, {.5, -.86602, 0}}, and the same two reflected in the x-y plane. (There are also four imaginary solutions). I'm interested, though, in what happens if we drop the requirement of symmetry. After fixing three vertices, we have a system of eleven equations in twelve unknowns, so there should be a set of one-parameter solutions. I haven't been able to get Mathematica to solve such a large system, though. I'm curious about what the topology of the configuration space is. For instance, is it connected? Dan Hoey Posted and e-mailed. [A previous version of this message was sent by mistake. I hope I cancelled it successfully.] --- Newsgroups: rec.puzzles From: haoyuep@aol.com (Dan Hoey) Date: 2000/08/04 Subject: Re: Puzzle: Guards Ilan Mayer writes: > SPOILER > 22011211102211 > 3H* *H H* > 0 H > 3 * H* H* > 1 *H > 1 HH* > 3*H * * > 1 H *H > 1 * H > 3*H H * *H > 1 *H Yes, that's one possibility. The other two are 22011211102211 22011211102211 3HG GH HG 3HG GH HG 0 H 0 H 3 G HG GH 3 G HG GH 1 GH 1 GH 1 HHG and 1 HHG 3GH G G 3GH G G 1 HG H 1 H HG 1 H G 1 G H 3GH GH G H 3GH H G GH 1 GH 1 GH Dan Hoey haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 17 Aug 2000 03:26:22 GMT Subject: Re: Russian math olympiad problem on lattice points John Rickard wrote: > Eli wrote: > : Given convex pentagon with vertices on lattice points. > : Prove, that there is lattice point inside or on the border > : of the "small" convex pentagon, cutted by "large" pentagon > : diagonales. > That's a nice problem! Hint... [Spoiler encoded rot13] > Zneiva gur Ebobg'f bofreingvba, gung gur zvqcbvag bs ng yrnfg bar > qvntbany vf > a lattice point, does indeed help. It may help, but it's not true. If the vertices are (0,0), (1,0), (3,2), (2,3), and (0,1), then none of the diagonals hit a lattice point. I agree it's a nice problem, though. I'm still trying. For a while I thought the intersection of the median vertex-x and median vertex-y must lie in the inner pentagon, but no. Dan Hoey Posted and e-mailed --- Newsgroups: alt.folklore.urban From: haoyuep@aol.com (Dan Hoey) Date: 2000/08/24 Subject: Re: Cigars Deborah Stevenson sez: >wej3715 wrote: >> Deborah Stevenson wrote: >> : ... like "I decided to turn up at their house for dinner, and you >> : wouldn't believe the crap they served me." >> With some people, it doesn't matter whether you drop by >> unannounced or when invited over. >Ah, but only in the latter situation does one have the prerogative of >minding. I was told we weren't going to do mind over matter in this froup. Dan Hoey --- Math Forum From: haoyuep@aol.com (Dan Hoey) Date: Sep 1, 2000 8:36 PM Subject: Re: Re:Sequence Involving Product of Primes Rainer Rosenthal wrote: >Leroy Quet wrote... >| >What can be said about this sequence? >| Here are more terms of the sequence: >| 1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 15, 16, 18, 19, 20, 21, 23, 24, >| 25, 26, 28, 29, 30, 32, 33, 34, 35, 36, 38, 39, 40, 41, 43, 44, 45, >Congratulation, you did submit this as sequence A56127. >Do you know if 56127 is a member ? Surprisingly, it isn't, at least according to my calculations using a leading computational mathematics system*, though I used a coarse enough approximation to logarithms that my result is somewhat suspect. I found the nearby non-members to be 56072, 56090, 56103, 56114, 56127, 56145, 56159, 56171, 56184,.... Can we say that the first differences are always 1 or 2? That the 2s become arbitrarily sparse? For some reason, when I try to frame this as a continuous problem, I get a[n] ~ 2n, but it looks much more like a[n] ~ n. Dan Hoey * But not a leader in the posted and e-mailed field of falsif... [barf]. --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 02 Sep 2000 00:25:03 GMT Subject: Re: 2*m*n, m^2-n^2, m^2+n^2 ?? Only up to a point. Alan Mackenzie writes: >... >Suppose we double a, b, c, so that our Pythagorean triple is 4*m*n, >2*(m^2-n^2), 2*(m^2+n^2). It turns out that these can be expressed, >respectively, as (m+n)^2-(m-n)^2, 2*(m+n)*(m-n), (m+n)^2+(m-n)^2. That's kind of an artifact. To paramaterize all the primitive (i.e., coprime) triples as {m^2-n^2,2mn,m^2+n^2}, we must choose m and n relatively prime, and not both odd. If we have both odd, then (a,b,c)=2. Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 02 Sep 2000 00:36:48 GMT Subject: Re: Re:Sequence Involving Product of Primes Rainer Rosenthal wrote: >Leroy Quet wrote... >| >What can be said about this sequence? >| >| Here are more terms of the sequence: >| 1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 15, 16, 18, 19, 20, 21, 23, 24, >| 25, 26, 28, 29, 30, 32, 33, 34, 35, 36, 38, 39, 40, 41, 43, 44, 45, >Congratulation, you did submit this as sequence A56127. >Do you know if 56127 is a member ? Surprisingly, it isn't, at least according to my calculations using a leading computational mathematics system*, though I used a coarse enough approximation to logarithms that my result is somewhat suspect. I found the nearby non-members to be 56072, 56090, 56103, 56114, 56127, 56145, 56159, 56171, 56184,.... Can we say that the first differences are always 1 or 2? That the 2s become arbitrarily sparse? For some reason, when I try to frame this as a continuous problem, I get a[n] ~ 2n, but it looks much more like a[n] ~ n. Dan Hoey * But not a leader in the posted and e-mailed field of falsif... [barf]. --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 02 Sep 2000 00:48:24 GMT Subject: Re: Is the empty set a finite set? Mike Oliver writes: > ...I concede that there are various properties that zero shares with > certain infinite quantities. > But I don't see any way that these properties can be construed as > properties of *largeness*. And whatever else informal inifiniteness > might be, it's surely a largeness property. Well, ordering by divisibility is considered a "greatness" property, which might be considered akin to largeness. The ordering by divisibility is used in calculating greatest common divisor, using the partial order {(x, y) : x divides y}. In this ordering, zero is greater than all the positive integers. That is how we make sense of GCD({})=0. Don't get me wrong--it isn't the _reason_ GCD({})=0, we would want that anyway to provide important properties like GCD(A union B) = GCD({GCD(A),GCD(B)}). But it's an ordering that lets us conclude that GCD({})=0, so it's the one we use. This same order is sensibly used in field theory: the characteristic of a field is the LCM of all the additive orders of its elements. An element's orders have a divisibility property, so the divisibility ordering is the natural one to use. Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 31 Oct 2000 12:51:31 GMT Subject: Re: The mathematics of dealing cards "Gary Davis" writes: >Ah yes, three responses, so far, for which I thank you all. But they all >deal with SHUFFLING. My problem requires NOT SHUFFLING. The response by Steve Lord was to study permutations. That is correct and pertinent to your problem. Permutations are rearrangements in the order of a set, and are applicable to deterministic rearrangements such as dealing and sorting, as well as to random rearrangements such as shuffling. You would also benefit by investigating the theory of finite groups, which applies to combining permutations by composition, and inversely to analyzing permutations as compositions of other permutations. You may also seek information on the "symmetric group" S_n, which is the group of all permutations on n objects. In a sense these three terms apply to different ways of looking at the same topic, so you will be in the right area no matter which term you read about. You should be able to find information on these topics in any introductory abstract algebra text at the undergraduate level. Be careful not to dismiss discussions of topics that do not seem to apply to your problem, as you did with "shuffling". The applications of group theory arise by surprising pathways. Dan Hoey haoyuep@aol.com --- Math Forum From: Dan Hoey Date: Nov 7, 2000 8:50 PM Subject: Re: What is the point of rigor? ullrich@math.okstate.edu (David C. Ullrich) wrote: > "Martin Green" wrote: >> I actually asked: >>> "By what possible reasoning is the Well Ordering Principle >>> "obviously false"?" > Intentionally misleading citation. Congratulations, this puts you > in a whole new category. > I looked it up. What you actually said was >>> By what possible reasoning is the Well Ordering Principle >>> "obviously false"? Wouldn't most people say that both WOP >>> and AOC are "obviously true"? > When I stated that you'd said that they were both obviously true you > really had no idea I was referring to the second sentence above. > Right. [...] Well, David, I really do think it's possible. We've already seen that Green is somewhat math-challenged, and he already quoted the Prime Pages' nonsensical "definition" from http://venus.utm.edu/research/primes/glossary/WellOrdering.html : > "Well-Ordering Principle > "Every nonempty set S of positive integers contains a least element; > that is, there is some element a of S such that a < b for all > elements b of S...." I don't know if anyone has told him that the above is extremely misleading, and definitely not what the discussion is about. But since he believed the faulty definition, he might have thought he said the above is obvious (which it is) and he wasn't aware that the second sentence had anything controversial in it. If so, though, it's rather a pity that someone so ill-informed thinks he's ready to debate rigor with mathematicians. But at least it's better than being a troll. Dan Hoey Posted and e-mailed. haoyuep@aol.com --- Newsgroups: rec.arts.sf.fandom From: haoyuep@aol.com (Dan Hoey) Date: 17 Nov 2000 02:53:06 GMT Subject: Re: Chad who? Lois Fundis wrote (from a website called yourDictionary.com): >Etymology: Possibly from the last name of the inventor of the Chadless >cardpunch that cut U-shapes in punch cards, rather than open circles >or rectangles. "Chad" would then be a back formation from "Chadless" >misunderstood: if the Chadless keypunch didn't produce it, other >keypunches must produce "chad." I've heard this neat back-formation etymology, first from Brian Reid about 1980, then in the Jargon dictionary additions that were added in the late 80s. But I've never found any evidence that the device actually existed. In today's Washington Post, Rowan Philp considers chad. He consulted Evan Morris, an etymologist who wrote the new book _The Word Detective_. Morris suspects a different origin: I'd say this comes from a Scottish word, which is also spelled `chad,' which means `gravel.' If you take it as metaphorical, it does seem to fit. Going further out on a limb, the cipher machines run by the British during World War II ran on punched tape--perhaps there was a Scotsman on one of the cipher teams who referred to piles of the stuff on the floor as chad. I'd be interested if you hear of other etymological theories or (especially) research on the topic. Dan Hoey --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Nov 22, 2000 7:53 AM Subject: Re: An Unsolved Problem of Mine #3 On July 10,2000 Leroy Quet wrote: >Let H_m = sum_{k=1}^m [1/k]. >The simple continued fractions of the H_m's begin as follows: >H_1 =[1] >H_2 =[1, 2] >H_3 =[1, 1, 5] >H_4 =[2, 12] >H_5 =[2, 3, 1, 1, 8] >H_6 =[2, 2, 4, 2] >H_7 =[2, 1, 1, 2, 5, 5] >H_8 =[2, 1, 2, 1, 1, 5, 7] >H_9 =[2, 1, 4, 1, 5, 1, 1, 7, 1, 3] >H_10 =[2, 1, 13, 12, 1, 3, 1, 2] >H_11 =[3, 50, 3, 4, 6, 1, 5], >H_12 =[3, 9, 1, 2, 4, 1, 1, 1, 15, 4], >The number of terms in each continued fraction form the sequence: >1, 2, 3, 2, 5, 4, 6, 7, 10, 8, 7, 10, 15, 9, 9, 17, 18, 11, 20, 16, >18, 18, 23, 19, 24, 25, 24, 26, 29, 21, 24, 23, 26, 25, 32, 34, 33, >26, 24, 31, 32, 31, 36, 36, 39, 32, 34, 42, 47, 44, 46, 35, 40, 48, >43, 47, 59, 50, 49, 39, 50, 66, 54, 44, 54, 49, 41, 64, 47, 46, 54, >71, 72, 60, 57, 67, 65, 54, 73, 63, 72, 66, 60, 61, 69, 69, 70, 78, >66, 79, 84, 78, 76, 79, 63, 81, 76, 81, 90, 68, 76, 88, 93, 84, 89, >78, 87, 94, 80, 95, 94, 95, 96, 82, 99, 108, 103, 109, 87, 102, 106, >108, 87, 109, 116, 112, 112, 122... >Now, it's known that there is only one integer H_m, which is H_1 =1. >In general, are there a finite number of H_m with any given number of >terms in their simple continued fractions? I'd be surprised if anyone can even prove m>4 => #CF(H_m) > 2. A heuristic argument suggests that the chance that there is an m>4 and integers r,s for which H_m = r + 1/s can be bounded by something like Sum exp(n)^(- exp(n)/(n^2) ) , n>5 the sum starting at the highest n for which it is verified that 4 < m < exp(n) => #CF(m) > 2. So we might expect this to be in the realm of the Goldbach conjecture or the infinite Mersenne composites conjecture--hard to doubt but having no proof, nor any great hope of proof. But I'm no expert in this realm, so there may be more hope than I am holding out. Dan Hoey haoyuep@aol.com --- Newsgroups: geometry.puzzles From: haoyuep@aol.com (Dan Hoey) Date: 25 Nov 2000 01:18:53 -0500 Subject: Re: Maximal triangle in ellipse (Was: correction to mathcad.com URL) After Rouben Rostamian wrote of inscribing a triangle of area 4 A sqrt(3) Pi / 9 in an ellipse of area A (by using a linear transformation mapping between the ellipse and a circle), Zakir F. Seidov wrote: > The trouble is that: > * when we transform the given ellipse to circle > we may do it not by unique way, then > ** in the circle, we may inscribe again not the unique triangle > with maximal area, and now: > *** when we return back - how many triangles with maximal area > we may inscribe in the given ellipse? Given any point of the circle, we can find a maximal triangle with a vertex at that point. So we can map that to a maximal triangle with a vertex at the corresponding point of the ellipse. To show these are the only possible maximal triangles in the ellipse, and that for instance there is only one maximal triangle with a given vertex, we take the inverse linear map, which must yield an equilateral triangle inscribed in the circle. > BTW If we are asked to inscribe in the given ellipse > the some particular triangle (e.g. the REGULAR triangle) > of maximal area - > in this case again the pass_to_circle method works? No, because the linear transformations do not preserve similarity of triangles. In fact, we can model the set of similarity classes of triangles by taking the unique (up to permutations of sides) representative with sides a,b,1-a-b. The similiarity classes are then associated with a region of the Cartesian a,b plane. For a given ellipse, the triangles of maximal area are associated with finitely many paths in this region. So if we pick any of the similarity classes not on those paths, the maximal inscribed triangle of that shape will have area less than 4 A sqrt(3) Pi / 9. In some cases, (e.g., an obtuse triangle in a circle) the maximal triangle of that shape will have only two vertices on the ellipse. Dan Hoey haoyuep@aol.com --- Newsgroups: geometry.research From: haoyuep@aol.com (Dan Hoey) Date: 25 Nov 2000 01:20:05 -0500 Subject: Re: I am doing a reasearch paper on sprouts > Hello! My name is Christina, and I am a freshman at arden City > High School in New York I am doing a research paper on the game of > Sprouts and I am having trouble finding out why the game ends in > more than 2n moves! This is proved by the Moribundity Equation, in volume 2 of Berlekamp, Conway, and Guy's _Winning Ways_ (good luck finding a copy--maybe in a college library). If an n-spot game lasts m moves, then at the end there will be n+m spots, with l=3n-m of them live. Every live spot L has two nearest neighbors D that will be dead, in one of two ways: ---D--- ---D--- | | L .--D--. | ( ) ---D--- `--L--' If either neighbor were live, the game would not be over. And since L is accessible from at least two of the three regions of its dead neighbors, no point can be a dead neighbor of different live points (or we could connect the live points for one more move). The remaining dead spots are called Pharisees (look it up for the etymology!). We count the number of Pharisees P as the number of spots (n+m), minus the number of live spots (3n-m), minus the number of dead neighbors 2(3n-m). So P=4m-8n, and m = 2n + P/4. So the number of moves must be at least 2n, and the number of Pharisees will be a multiple of 4. > I also am having trouble obtaining information in books, > Please Help! If there are any pointers that you may give me that > would be great! Thank you so much, I love the game! Besides Winning Ways and the Martin Gardner articles, you might be able to get something out of Applegate, D., G. Jacobsen, and D. Sleator. Computer analysis of sprouts. Carnegie Mellon U Comp Sci Tech Report No. CMU-CS-91-144, May 1991. Unfortunately, http://www.cs.cmu.edu/People/sleator/readme.html seems to have a broken link. The paper is excerpted in _The Mathemagician and Pied Puzzler, A Collection in Tribute to Martin Gardner_, edited by Elwyn Berlekamp and Tom Rodgers (AKPeters, 1999). Dan Hoey Hoey@AIC.NRL.Navy.Mil lakhtl...@yahoo.com --- Newsgroups: geometry.research From: haoyuep@aol.com (Dan Hoey) Date: 25 Nov 2000 01:20:22 -0500 Subject: Re: Existence of starshaped sets F. A. Toranzos wrote: > PROBLEM 1. Given two convex sets K' and K" included in this order, > is there a starshaped set S such that K' is it kernel and K" it > hull? I really doubt it. In fact, I suspect that any convex kernel must be the intersection of countably many half-planes with the set of which it is the kernel. For instance, if part of the boundary of K' is a circular arc that is not part of the boundary of K", I expect you are out of luck. > In the affirmative answer, is that set unique? In general, there is a great deal of freedom in choosing a set with a given kernel, since we may omit any region R of the set that is not in the kernel if we also remove the umbra of R (as illuminated from the kernel). There is even more deal of freedom in choosing a set with a given hull, since we may omit any part not on the hull, as well as all or part of the interior of a line segment of the hull. With this guidance, finding counterexamples is easy. > PROBLEM 2. Since I feel that the answer of previous problem is > negative, let us rephrase it in the following way: Characterize the > pairs (K';K") of convex sets with K' included into K" such that > there exists at least one starshaped set S whose kernel is K' and > whose hull is K". Sounds like an interesting research topic, though a literature search might net some prior work, or even an answer. Dan Hoey haoyuep@aol.com --- Newsgroups: geometry.research From: haoyuep@aol.com (Dan Hoey) Date: 2000/11/29 Subject: Re: Another Proof Danny Purvis writes: A really neat argument, which impressed me a great deal, until I tried to extend it to prove the "Fundamental Theorem of Zero- Order Moribundity." The problem with the proof is: > ... (3) Each live point at game's end (survivor) must access 2 > regions, neither of which can be accessed by another survivor. This is contradicted by the "scorpion" endgame, which I draw below. The zeroes refer to original points; other digits are points added during play. 0-------1------0------4-------0 |\ | | /| | \ | | / | | 3----2 5----6 | \ / \ / \___/ \___/ Note that the central 0 does _not_ access two regions. While this breaks the proof, I suspect there is something of value left in the argument. Some combinatorics involving number of regions, number of connected components, number of survivors accessing 1 vs 2 regions, and some other factor I have not yet considered might lead to the result. By the way, I think I've found the paper on Computer Analysis of Sprouts that I mentoned a couple of days ago. It's on the web at http://reports-archive.adm.cs.cmu.edu/anon/1991/CMU-CS-91-144.ps, but you'll need a Postscript viewer to read it. Cheers, Dan --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Nov 30, 2000 12:17 PM Subject: Re: Why mirror invert right and left and not top and bottom? John Savard writes: >Or consider a mirror on the north wall of a room. You look north and >face it. >The guy in the mirror: his head is still *up*, like yours. >The guy in the mirror: his right hand is on his *east* side, like >yours. >But _he faces south_ and _you face north_. [...] >Left and right are _relative_ directions, constructed from the >(absolute) "up" and the (relative) "front" direction of a person, >so since "front" was changed from north to south, the mirror man's >unchanged _east_ hand is now his left hand - left and right are >reversed. That last paragraph is the most succinct and convincing explanation of the situation that I have heard. But I notice that when you were still talking in absolute terms, you said, "His right hand is on his *east* side, like yours." Certainly his eastern hand is an image of your right hand, but I don't know that we can call it "his right hand". For one thing, it is on the left in the frame of reference defined by his relative up and front. And also, it is a _left hand_, in the sense of having a direct correspondence to everyone else's left hand, as opposed to an opposite (or "mirror" correspondence. Take a picture of it and go shopping for a glove. The mention of ceiling mirrors reminds me of when my one-person office became a two-person office. I had to move all my stuff to one half like a Heisenberg demon, so I drew a map of my office and its contents in a computer drawing system, and moved the contents around to fit them in. It really helped that my ceiling was covered by one-by-two foot tiles, which made rough measurement easy. After I drew the planned arrangement, I took it to the officemate for her approval, and she looked at it, and looked at it, and said, "Where is... Let's see, the door is over here, ... Oh, you've got it swapped left to right!" But of course she was wrong--I had it swapped up to down. I had drawn a map of the ceiling! Dan Hoey posted and e-mailed. haoyuep@aol.com --- Math Forum From: haoyuep@aol.com (Dan Hoey) Subject: Sprouts notation Date: Dec 27, 2000 9:27 PM Here are the elements of Sprouts notation I have developed in response to the discussion earlier this month under the "Game of Sprouts" topic in geometry-research. Element 0: Terminology The number of lines entering a spot is called the spot's "degree". Degree zero, one, and two spots are called "live" spots; the degree three spots are "dead". The lines entering a spot divide the spot into "sites". A spot of degree zero or one forms a single site. Degree two spots have two sites and degree three spots have three sites. A degree two spot is called an "eye spot" if its sites are in separate regions. If both its sites are in the same region, it is called a "pier spot". The sites in a region that are connected to each other form a "boundary." We list the sites of a boundary in "left-hand order," the order in which a miniature robot within the region would encounter them walking forward along the boundary with its left hand on the boundary. If the boundary surrounds the region, this is clockwise order. If the region surrounds the boundary, left-hand order is counterclockwise. Element 1: Basic position notation In an N-spot Sprouts game, the initial N spots are numbered 1,2,...,N and the spots added in the course of the game are numbered starting at N+1. Each boundary is written as a list of the spot numbers of its sites in left-hand order, starting at an arbitrary site and separated by commas. Each region is represented as a list of its boundaries separated by semicolons. Finally, the region representations are listed separated by slashes. 1--6---5 Example: This position can be written | 9 1,6,8,7,4,7,3,9,3,7,8,6,5,6;2/3,9. 8 / \ 2 | \ / Element 2 describes how to abbreviate 4--7------3 this as 1,8,4,9t,8,5;2. Element 2: Abbreviating position notation The position notation may be abbreviated by omitting dead spots. If a degree one spot has all other spots on its boundary deleted it must be marked with an "o" to distinguish it from a degree zero spot. Any region with fewer than two live spots may be omitted, but eye spots listed in only one region must be marked with a "t" to distinguish them from degree one spots. If the two sites of a pier spot become adjacent, the pier spot may be listed once, marked with a "t". An example of the abbreviation appears in the previous example. It is possible to specify a move in Sprouts by providing the full position after the move--in fact, the full position notation provides a complete history of a game. You can see this by using the position notation to draw the game in pencil, then inking it in one move at a time. However, it is helpful to be able to specify a move more concisely, and I describe how to do so below. Element 3: Basic move notation A move that connects spot A to spot B, creating spot C in the middle, is written A-C-B, perhaps with additional notations. By convention, the lower-numbered endpoint is listed first. The direction of the move, from A to B, determines one site of C as a "left" and the other as "right". When listing sites in left-hand order, A is listed after the left site of C and B is listed after the right site of C. When A and B are the same spot, this determination is ambiguous, the left site is taken to be the one accessible to other sites on A's boundary, if any. ______ Example: The position 1,3,2,4,2,3/2,4 is (l) / \ created by the moves 1-3-2; 2-4-2. The 1--3--2 (r) 4 (l) first 3 refers to the right site of spot 3, (r) \______/ and the second 3 refers to the left site. Element 4: Specifying sites for pier spots When an endpoint of a move is a pier spot, it is necessary to specify which site is being connected. This is done by suffixing ".N", where N is the number of the first live spot appearing after the site in left-hand order. Just as A is written on the left and B on the right in the move move A-C-B, the left site is C.A and the right site is C.B, unless A or B becomes dead after the move. (We avoid using dead spots to specify sites because they would not appear in the abbreviated position). (5.1) Example: After 1-5-2; 3-6-4, there are four ways of 1---5---2 connecting spots 5 and 6, leading to the following (5.2) four abbreviated positions: Move 5.1-7-6.3 yields position 1,2,7,3,4,7. (6.3) Move 5.1-7-6.4 yields position 1,2,7,4,3,7. 3---6---4 Move 5.2-7-6.3 yields position 1,7,3,4,7,2. (6.4) Move 5.2-7-6.4 yields position 1,7,4,3,7,2. Element 5: Specifying boundary separations When a move connects two sites on the same boundary, the region containing the boundary is split. All other boundaries in the original region will appear either in the region accessible from the left site of the new spot or the region accessible from the right site. This separation is specified by listing the lowest numbered live spot from each of the boundaries to go into one of the regions. A list of boundaries accessible to the left site is preceded with "<", while a list accessible to the right site is preceded with ">". If there are no other boundaries to separate, the separation is written "=". 8 7 Example: After 1-6-2; 3-7-4; 1-8-2>; 3-9-4>1 / \ / \ the position is 1 2 3 5 4 \ / \ / 1-6-2-8;3-9-4-7/1-8-2-6/3-7-4-9;5. 6 9 Element 6: Specifying the region for double-eye-spot moves. When two eye spots share the same two regions, a move connecting them must specify in which region the connection is made. Since such eye spots appear on the same boundary in each region, they separate the region as in element 5. The separation is also used to determine which region is used, in one of the following ways: 6a. If the separation normally lists at least one boundary, the listed boundary is sufficient to specify the region. 6b. If the separation is between at least one boundary on one side and zero boundaries on the other side, the separation must specify the side with at least one boundary. 6c. If there are no live boundaries being separated, but there is at least one other live spot on the boundary being connected, then the lowest numbered live spot is listed as being separated, as if it were on a separate boundary, along with which side the separation is on. 6d. If there are no live spots in the region being separated, then the separation is written "=". _ Examples: After 1-3-1> the position is 1,3;2/1,3. / \ 2 A move between eye spots 1 and 3 must be written 1---3 1-4-3>2 or 1-4-3= as in elements 6b and 6d, respectively. 3 In the game 1-4-2; 2-5-3; 1-6-5.2 the position is | 1,4,2,3,6/1,6,2,4. A move between eye spots 4 and 6 6---5 is written 4-7-6>1 for connection in the region / | containing 3, or 4-7-6<1 for the smaller region, as 1--4--2 in element 6c. Element 7: Equivalent representations for a position A position representation can be changed in three ways with no effect on the position represented: 7a: Changing which site is used as the start of a boundary or boundaries, 7b: Changing the order in which boundaries are listed in a region or regions, and 7c: Changing the order in which the regions are listed. There are two other changes that can be made, provided that we do not need to interpret the notation of moves made in the position: 7d: Permuting the numbers used to denote the spots, and 7e: Reversing the order of all boundaries in a region or regions. If a position is changed in these ways, any further moves must be translated by performing a corresponding permutation to the spot numbers and exchanging ">" with "<" in the reversed regions (except where a move connects a point to itself, as in element 3. I believe these elements are a complete description of a notation system for Sprouts, but it is quite possible I have overlooked something. I welcome comments and questions. Dan Hoey haoyuep@aol.com --- Newsgroups: geometry.research From: haoyuep@aol.com (Dan Hoey) Date: 27 Dec 2000 23:47:09 -0500 Subject: Sprouts notation I regret that it's taken me a so long to respond to questions on Sprouts notation raised by Laurie Mersereau and Danny Purvis. I needed time to look over all the earlier discussion about this, to make sure that the changes I saw as necessary were not addressed in earlier messages. As it turns out, my concerns are new. Most of the concerns boil down to identifying connections to spots that appear twice in the same region, and to keeping track of handedness between boundaries in a given region. The issue of spots that appear twice is illustrated by the following example. Suppose in three-spot Sprouts we start by forming a five spot chain: 1---4---2---5---3 If we are then to connect spots 4 and 5, we must specify whether we connect them on the upper side or the lower side. For instance, if the connections are both on the same side, then we can continue the game by connecting spots 1 and 3. But if we connect the upper side of 4 to the lower side of 5, then spots 1 and 3 will be inaccessible to each other. The handedness issue comes when we create two objects in the same region. Suppose a four spot game begins by creating two circles. If the circles look like this: 1---5 2---6 | | | | 7---3 8---4 then the game might continue by connecting 1 to 6, 5 to 2, and 3 to 8. But if the circles look like this: 1---5 2---8 | | | | 7---3 6---4 then connecting 1 to 6 and 5 to 2 will separate spots 3 and 8. So at the time of creating the two circles, we need to specify which configuration has been created so we can know what continuations are possible. I have come up with a notation system for Sprouts that addresses these issues and a couple of other minor problems. I follow existing work as much as possible, but I've had to add some new concepts to explain the improved notation. As I've worked on it, I've run into a couple of new problems, and worked them out. The result is a fairly extensive description, which I will put in a new geometry-research topic entitled "Sprouts notation." Dan Hoey haoyuep@aol.com ---