Date: Thu, 2 Jan 2003 20:04:43 -0500 (EST) From: Dan Hoey To: math-fun@mailman.xmission.com, wolfe@gustavus.edu Subject: [math-fun] More Games of No Chance I finally got MGONC last month, after the usual delay between announced and actual publication date. I haven't read much of it yet, but I thought it might be a good time to tell funsters (especially those who were at CGT2) about a minor improvement that David Wolfe was kind enough to sneak into the Calistrate, Paulhus, Wolfe paper (also on http://www.gustavus.edu/~wolfe/dayn/mgonc.pdf). If you look at the Hasse diagram of the lattice of games on day 2 (MGONC p. 28), you'll see that the game * now appears between 0 and *2 . This allows the diagram to be overlaid on a table of day 2 games in a grid indexed by left and right option sets. Such tables appear in R K Guy 1996 (GONC, p. 6) and Fraser, Hirschberg, Wolfe 2003 (http://www.gustavus.edu/~wolfe/dayn/structure.pdf, p. 6). I've put a drawing of the resulting overlaid figure at the end of this message. I suspect that a similar table of day 3 games doesn't exist, because the 98 independent sets of day 2 games aren't totally ordered as the day 1 independent sets are. (There are actually two different orders of the day 1 independent sets, depending on whose options they might be). Still, a 98 by 98 grid of the day 2 independent sets might be start toward developing a picture of the day 3 lattice. Dan Hoey@AIC.NRL.Navy.Mil ==================================================================== Day 2 games by options and a Hasse diagram of their partial order : Right Options : Left : : Options : -1 : 0,* : 0 : * : 1 : {} : ......:...........:...............:.......:.......:.......:.......: : HOT/FUZZY/NEXT. . . . .POS/RT : : . . . . . : : . . 1|0 <----------< 1* <---< 2 : : . . L V . .L V . V : 1 : . ./ | . / | . | : : . / | . /. | . | : : . L. | . L . | . | : : +-1 <--------< 1|0,* <----+-----< 1|* . | . | : : V . V . | . V . | . | : ...: . . . . . | . . . . . . . | . . . | . . . | . . . | . . . | . : : | . | . | . | . | . | : : | . | . V . | . V . V : : | . | . up* <-----+----< 1/2 <--< 1 : : | . | . L V . | .L . : 0,* : | . | ./ | . | / . : : | . | / | . | /. . : : V . V L. | . V L . . : : 0,*|-1 <----------< *2 <----+-----< up . . : : L V . L V . | . V . . : ...: . . . / . | . . . . . / . | . . . | . . | . . : : / | . / | . | . | . . : : L | . L | . V . | . . : 0 : 0|-1 <----+----< dn* <----+-----< * . | . . : : V | . V | . . | . . : ...: . | . . . | . . . | . . . | . . . . . . . | . . . . . . . . . : : | | . | | . | : : | V . | V . V : * : | *|-1 <----+----< dn <-----------< 0 : : | L . | L . : ...: . | . / . . . . . | . / . . . . . . . . : : | / . | / . : : V L . V L . : -1 : -1* <-----------< -1/2 . : : V . V . : ...: . | . . . . . . . | . . . . . . . . . . : : | . | . : : V . V . : {} : -2 <------------< -1 . : : NEGATIVE/LEFT . . COLD/ZERO/PREVIOUS : ...:...............................................................: --- Date: Mon, 6 Jan 2003 08:41:23 -0500 (EST) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: Re: [math-fun] Fibonacci power triangle Richard Schroeppel wrote: > The next diagonals turn out to be products of three adjacent > Fibs divided by 2: 260 = 5*8*13/2. > The right way to look at this seems to be 5*8*13/(1*1*2), a > kind of binomial coefficent with the regular integers replaced > by Fibonacci numbers. The next diagonals will be products of > four adjacent Fibs divided by 1*1*2*3, and so on. Neat! Would you like to call them Fibonomial coefficients, or is that too cute? I wonder if there's an analogue of the role of binomial coefficients in the expansion of (a+b)^n? Dan --- Date: Thu, 16 Jan 2003 13:37:09 -0500 (EST) From: Dan Hoey Subject: Re: [math-fun] Copyright extension To: math-fun@mailman.xmission.com Every person has an opinion about what copyright law is, and what it should be. Most of the opinions differ. Most of the former are erroneous, and most of the latter are wrong-headed. What makes any of us think anyone subscribed to math-fun to hear our erroneous, wrong-headed opinions on a subject we know so little about? Dan --- Date: Thu, 16 Jan 2003 17:09:43 -0500 (EST) From: Dan Hoey To: asimovd@aol.com Cc: math-fun@mailman.xmission.com Subject: Re: [math-fun] Copyright extension > Dan, > There seems to be a considerable interest in this topic. If it leaves you > cold, why not just delete the posts with subject line as above? > Regards, > Dan I'm sick and tired of mailing lists, newsgroups, and any other discussion forum turning into outlets for misinformation, posturing, poseuring, and vapid speculation on this topic. I did not subscribe to math-fun to listen to yet another copyright spew. It's not math, it's just something that EVERYONE has an opinion on, not just mathematicians. You don't think math-fun is the first place it's happened, do you? Copyright arguments EAT discussion groups. If you're so interested in getting misinformation on copyright, why aren't you reading misc.news.intellectual-property, or whatever it's called, on Usenet? You can get much greater quantities of opinions, with the same level of unreliability. And people there won't be asking "where's the math?" because those people are reading a newsgroup devoted to copyright opinionizing, not one they are reading for the math. Dan --- Date: Thu, 16 Jan 2003 19:26:05 -0500 (EST) From: Dan Hoey To: Joshua Singer CC: math-fun@mailman.xmission.com Subject: [math-fun] Re: Manners Joshua Singer thinks my tone is uncalled for. Well, my tone expresses my discomfiture at having to endure this topic, argue against this topic, or both. Someone here might have the mistaken impression that I enjoy arguing against copyright discussions as much as I dislike the discussions themselves. No, I hate and abhor having to remind people that I'm here for the mathematics and not for extended discussions of other topics. I will not enter into any further remonstrations with people who misuse math-fun with discussions of what copyright law is and should be. If it continues beyond my tolerance, I will just unsubscribe. I like reading about math. I am not willing to subscribe to a copyright discussion group to do so. And if anyone tells me "just hit delete" again, I suggest you subscribe to sneh-lovers and see how many times you can hit delete before you've had enough. But I find it difficult to respect anyone's argument for the continuation of this discussion on math-fun. It's not like there aren't places where you can get copyright discussions, all copyright discussions all the time, and the people there are there for the copyright discussions. It's not like the you're going to find anyone posting to math-fun with any special expertise in the subject, or with any great potential for changing the status quo. In fact, the choice of math-fun as a venue for copyright discussion practically ensures that you are going to get half-baked opinions from people who don't know much about copyright, haven't thought through what they do know, and don't have a better outlet for their witless maunderings than gassing in e-mail. Forgive me if anyone who posted here actually _is_ a copyright lawyer, or legislator, or treaty negotiator, or pressure group runner. It certainly sounded like gas to me. And as for it being a popular topic, how about great sex? Everyone's interested in great sex. Let's have a discussion about our sexual experiences, fantasies, aspirations, and phobias, and by all means let's do it in the road on math-fun. And does anyone want to discuss the war on drugs on math-fun? I understand war is hell, but maybe it's more enjoyable on drugs, and I'm sure someone on math-fun has an opinion. How about Nu-Skin--I understand you can make more money with it than Amway, and if your friends turn against you, at least their skin is soft. What does math-fun think about international funds transfer, penis enlargement, collecting pop-tops for kidney transplants, the source of the phrase "rule of thumb", Joe Boxer, Joe Millionaire, Joe Camel, and Joe Pye Weed? Have you ever tried looking in the yellow pages, deleting ninety-eight or ninety-nine of every hundred words, and trying to make a theorem out of what is left? Would you like to try that with math-fun? I wouldn't. You know, I was just now working on the mathematics of Bingo, and here I have to leave for the weekend. Well, have a good one, and I'll see you all in some mathematical venue. Dan --- Date: Tue, 4 Feb 2003 13:33:24 -0500 (EST) From: Dan Hoey To: Scott Huddleston , math-fun@mailman.xmission.com Subject: Re: [math-fun] Hungarian prisoner switch puzzle Scott Huddleston writes: > The Cartalk Puzzler this week looks interesting. Puzzle and URL: > The puzzle previously appeared in the IBM Research "Ponder This" puzzle section. See under July 2002. Dan Hoey@AIC.NRL.Navy.Mil --- Date: Fri, 7 Feb 2003 18:40:44 -0500 (EST) From: Dan Hoey To: "T Campbell" <[redacted]@hotmail.com>, Keith Lynch Subject: Re: Question for a book Dear T Campbell and Keith, I haven't heard back from you about my early sighting of e-mail spam from Steve Kirsch of Infoseek. I should mention that he was not the first e-mail spammer I ran into. Earlier that year, Dave Wagner started spamming Usenet addresses with offers to receive a newsletter advertising his products. If you check the Google usenet archives for "dave@nis.+com" you'll see it. You may even notice a spirited defense of the practice by Kovisoft , who said, "... but people like me [sic] Dave [sic] newsletter is extremly [sic] helpful to me [sic] so get off his back." Then look around and find the ads listing Dave Wagner as the e-mail contact for Kovisoft, Inc. I was not one of the first wave of recipients, but I sent him e-mail telling him to cut it out. He said I had been "mislead" and to check the responses in the newsgroup. I pointed out that I was objecting to what he had done and not denied. Later I got a copy of his e-mail spam, and complained to Netcom, who said that since he had sent me the spam "by accident" it was no problem and had already been "dealt with". So Dave Wagner is another person who doesn't seem to have received the stark fist of removal he earned. Dan ================================================================ >From hoey Wed Mar 9 14:11:43 1994 To: Dave@Delta.NIS.Com,nis@netcom.com (National Information Systems) Subject: Re: Watch out for nis.com. Count me as one person who doesn't think posting on Usenet should result in junk mail from random hucksters. Sending information on something you can provide is useful if the poster asks for your product. But sending your marketing questions to people who don't ask is a reprehensible practice that damages the free exchange of information on the network. Stop it. Dan Heoy Hoey@AIC.NRL.Navy.Mil ================================================================ Date: Wed, 9 Mar 1994 12:37:01 -0800 (PST) From: DAVE@DELTA.nis.com To: hoey@AIC.NRL.Navy.Mil Subject: Re: Watch out for nis.com. >From: hoey@AIC.NRL.Navy.Mil >Date: Wed, 9 Mar 94 14:11:48 EST >To: Dave@delta.nis.com, nis@netcom.netcom.com (National Information Systems) >Subject: Re: Watch out for nis.com. > >Count me as one person who doesn't think posting on Usenet should >result in junk mail from random hucksters. Sending information on >something you can provide is useful if the poster asks for your >product. But sending your marketing questions to people who don't ask >is a reprehensible practice that damages the free exchange of >information on the network. Stop it. > >Dan Heoy >Hoey@AIC.NRL.Navy.Mil Dan, Thanks for your message. Unfortunately, you've been mislead by the poster to news.admin.misc. Please see my response. Regards, Dave Wagner (dave@nis.com) ================================================================ >From hoey Wed Mar 9 16:30:01 1994 To: DAVE@nis.com Subject: Re: Watch out for nis.com. You write: > Thanks for your message. Unfortunately, you've been mislead > by the poster to news.admin.misc. Please see my response. According to the poster, you sent mail about your company's products to him after he posted somewhere on some other topic, not solicting such information. Your posting does not dispute that. Count me as one person who doesn't think posting on Usenet should result in junk email from random hucksters. Sending information on something you can provide is useful if the poster asks for your product. But sending your mailing list information to people who don't ask is a reprehensible practice that damages the free exchange of information on the network. Stop it. Dan Hoey Hoey@AIC.NRL.Navy.Mil ================================================================ Date: Wed, 9 Mar 1994 14:25:41 -0800 (PST) From: DAVE@DELTA.nis.com To: hoey@AIC.NRL.Navy.Mil >You write: > >> Thanks for your message. Unfortunately, you've been mislead >> by the poster to news.admin.misc. Please see my response. > >According to the poster, you sent mail about your company's products >to him after he posted somewhere on some other topic, not solicting >such information. Your posting does not dispute that. > >Count me as one person who doesn't think posting on Usenet should >result in junk email from random hucksters. Sending information on >something you can provide is useful if the poster asks for your >product. But sending your mailing list information to people who >don't ask is a reprehensible practice that damages the free exchange >of information on the network. Stop it. > >Dan Hoey >Hoey@AIC.NRL.Navy.Mil Dan, Thank you for your opinion. It may interest you to know that most people don't agree with you. Regardless, I don't take your message as the harassment that the poster intended it to be -- I really am interested in what people think. Regards, Dave Wagner (dave@nis.com) ================================================================ Date: Mon, 25 Apr 1994 8:19:24 -0700 (PDT) From: DAVE@DELTA.nis.com To: hoey@AIC.NRL.Navy.Mil Subject: FREE UNIX Newsletter -- Would you like to subscribe? Hello! I saw your name in a USENET posting and thought that you may be interested in new UNIX software technologies. My company publishes UNIX-based software for project management, sharing X Window Applications as Groupware and OPEN LOOK to Motif conversion tools, etc. We sponsor a free, monthly electronic newsletter called ACCENTServer which features useful information of general interest to the UNIX community. Sometimes we mention one of our products to help justify the cost of publishing. Receiving it is the only cost to you. If you are interested in joining the ACCENTServer list, please reply with your surface mailing address and your telephone, fax, etc. if you wouldn't mind. For your trouble we'll e-mail you the latest copy of a list of internet services, a very useful document. (This document is also available in news.answers on USENET if you only want the list.) If you are NOT interested, you don't have to reply. I will only add you to the list if I hear from you -- it is NOT my intention to invade your privacy. Thank you for your time. Would you like to join? Best regards, Dave Wagner (dave@nis.com) ---------------------------------------------------------------------- _/ _/ _/_/_/ _/_/_/ National Information Systems, Inc. _/_/ _/ _/ _/ 4040 Moorpark Avenue, Suite 200 _/ _/ _/ _/ _/_/_/ San Jose, California 95117 USA _/ _/_/ _/ _/ 408-985-7100 FAX: 408-246-3127 _/ _/ _/_/_/ _/_/_/ Email: info@nis.com ACCENT GraphicVUE Project Management for UNIX Workstations ACCENT STP Xview, OLIT and Devguide to Motif Conversion Tool ACCENT ToolKit Motif and OPEN LOOK Graphical Interface ToolKit ACCENT RDM User Application Developer and Report Writer ACCENT R SQL 4th Generation Language and DBMS ACCENT X/TeleScreen Sharing X Window System Applications ---------------------------------------------------------------------- ================================================================ >From hoey Wed Apr 27 15:44:31 1994 To: support@netcom.com Subject: Mail abuse by DAVE@DELTA.nis.com Dear Netcom, I'm sure you're aware of the mail solicitation being carried out by Dave@NIS.COM. When this was first reported to Usenet in March, I dropped him a line noting that I considered it abusive. On Monday, I received one of his solicitations. Please stop supporting that network nuisance with MX service. Dan Hoey Hoey@AIC.NRL.Navy.Mil ================================================================ From: support@netcom.com (Netcom Support) Subject: Re: Mail abuse by DAVE@DELTA.nis.com To: hoey@AIC.NRL.Navy.Mil Date: Fri, 29 Apr 1994 12:50:33 -0700 (PDT) In-Reply-To: <9404271944.AA14385@sun13.aic.nrl.navy.mil> from "hoey@AIC.NRL.Navy.Mil" at Apr 27, 94 03:44:33 pm hoey@AIC.NRL.Navy.Mil writes: > From hoey@AIC.NRL.Navy.Mil Wed Apr 27 12:46:26 1994 > From: hoey@AIC.NRL.Navy.Mil > Date: Wed, 27 Apr 94 15:44:33 EDT > To: support@netcom.com > Subject: Mail abuse by DAVE@DELTA.nis.com > > Dear Netcom, > > I'm sure you're aware of the mail solicitation being carried out by > Dave@NIS.COM. When this was first reported to Usenet in March, I > dropped him a line noting that I considered it abusive. > > On Monday, I received one of his solicitations. > > Please stop supporting that network nuisance with MX service. It's already been dealt with. Somehow your name was placed on their list twice instead of being deleted as you requested; they have since corrected this problem. ___________________________________________________________________________ Support support@netcom.com Technical Support Staff NETCOM On-line Communication Services ================================================================ --- Date: Mon, 10 Feb 2003 18:07:27 -0500 (EST) From: Dan Hoey To: "David Wilson" Cc: "Math Fun" , klaus-brockhaus@t-online.de (Klaus Brockhaus) Subject: Re: [math-fun] Ulam(1,2) "David Wilson" wrote: > I took a look at Ulam(1,2), the Ulam sequence starting with (1, 2) and > including every subsequent number which is a unique sum of distinct > earlier terms. This is Sloane's A002858. > ... Can anyone confirm my data? Did you intend to use zero-based indexing? If u(0)=1, u(1)=2, I concur that u(1000)=12336, u(1999)=25511. Otherwise one of us has a bug. I also get u(10000)=132790, u(50000)=676043, u(74084)=1000002. But there's a pretty definite bug in the histogram. My histogram of f(n)=(u(n) mod 21.6)/21.6 agrees with yours in its general trend, but differs in particulars. For f(1000...1999) in 20 buckets I get 113 101 119 98 87 70 58 40 31 8 5 0 0 2 4 14 22 64 66 98 rather than your 110 101 120 97 90 67 58 40 31 9 4 0 0 2 7 11 22 64 66 1 01. As a test, I find that the five numbers in the [.5,.55) bucket arise from u(1091)=13533 (f=0.527771) u(1210)=14894 (f=0.53704834) u(1730)=21870 (f=0.5) u(1748)=22151 (f=0.50927734) u(1947)=24851 (f=0.50927734). What four numbers do you have? I agree exactly with Klaus Brockhaus's data for f(1000...1259), so I think I'm slightly likelier to be correct, but only slightly, and I'm pretty suspicious about the zero-based indexing. My data suggests that 21.6 should be about 21.60157 . Dan --- Date: Mon, 10 Feb 2003 18:36:10 -0500 (EST) From: Dan Hoey To: "David Wilson" Cc: "Math Fun" , klaus-brockhaus@t-online.de (Klaus Brockhaus) Subject: Re: [math-fun] Ulam(1,2) By the way, I get a period of about 10.1968 with Ulam(1,3). But the density waveform is bimodal: 0 40 96 105 112 95 48 0 0 0 0 0 0 29 89 104 111 102 65 4 Dan --- Date: Tue, 11 Feb 2003 14:39:52 -0500 (EST) From: Dan Hoey To: "David Wilson" Cc: "Math Fun" , Subject: Re: [math-fun] Ulam(1,2) "David Wilson" wrote: > There are three differences between my computations and yours. > (1) I use Perl (2) I index from zero and (3) I wrote the algorithm > myself. If you index from zero, i.e. u(0)=1, u(1)=2, then that is the same thing I did. My program is written in Common Lisp. I wrote it with enough complexity that I could easily have an error. > Any of these may account for discrepancies between our > results, and since you and Brockhaus agree, I will let you be right, > it isn't worth it to me to find my error. Well, it's worth it to me if you can find it, because I want to know if I made an error. I wonder if you might have the correct sequence but some problem with the histogram, say with the boundaries of the bins or something. For that reason, I would really like to know what you calculate as the contents of bin [.5,.55). But this wish is not critical--don't bother if it's really a big problem. For my part, I'm going to rewrite my code (a) simply and slowly, just to test up to u(1999), and (b) with a slightly different method of optimization, to see if I can carry it out further. > All I was interested in was whether the observed bunching > phenomenon was real, or whether I was totally off the wall. > It appears that both you and Brockhaus have confirmed the > bunching with period about 21.6. Well, I wouldn't call what I confirmed "bunching", but a periodic predominance. Maybe that's just a difference of vocabulary, and maybe there's something else here we haven't really tested for. > Do you think this is a constant? In carrying it out to u(70000) it seemed to be a constant, but the value is more like 21.60157 as I said. Definitely between 21.6015 and 21.6016. > If so, what would cause this regular bunching? Here's a phenomenon that might explain it. It is similar to a phenomenon seen in "Take or Break" games such as Grundy's Game. Suppose that the real numbers mod K are divided into a sparse space S and a common coset C such that for all s1,s2 in S, c1,c2 in C, we have s1+s2 and c1+c2 in S and s1+c2 in C. Suppose further that the sequence values are in C with finitely many exceptions X, a subset of S. Then we might see a situation where - almost all values in S are be prohibited because they appear as c1+c2 for more than one pair c1,c2 in the sequence, and - for any sequence value c1 in C and x1 in X, the value c1+x1 is in C and will be represented at least once as a sum of sequence values. So as long as there is no c2+x2=c1+x1, the value c1+x1 will be in the sequence. There seems to be something more going on here, because the density within C is not uniform. But possibly that's just because the buckets are too big to show the exact structure of C. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Date: Tue, 11 Feb 2003 15:24:05 -0500 (EST) From: Dan Hoey To: Jud McCranie Cc: math-fun@mailman.xmission.com Subject: Re: [math-fun] Ulam(1,2) Jud McCranie > I'm getting in on this in the middle, so I don't know what you're > discussing, but maybe I could see what I get with my program. Thanks for the offer. There are two things I want verified. First, is it true that: u(1000)=12336 u(1091)=13533 u(1210)=14894 u(1730)=21870 u(1748)=22151 u(1947)=24851 u(1999)=25511 ? This is with zero-based indexing (u(0)=1, u(1)=2, u(2)=3, ...), so maybe you need to add 1 to the indices. Second, letting f(n) = (u(n)/21.6) - floor(u(n)/21.6, for what n in 1000...1999 is .5 <= f(n) < .55? Thanks. Dan Hoey --- Date: Tue, 11 Feb 2003 15:30:47 -0500 (EST) From: Dan Hoey To: Jud McCranie Cc: math-fun@mailman.xmission.com Subject: Re: [math-fun] Ulam(1,2) Sorry, the second query should be: Second, letting f(n) = (u(n)/21.6) - floor(u(n)/21.6, for what n in 1000...1999 is 10.3 <= f(n) < 11.33? Thanks. Dan Hoey --- Date: Tue, 11 Feb 2003 15:36:11 -0500 (EST) From: Dan Hoey To: Jud McCranie Cc: math-fun@mailman.xmission.com Subject: Re: [math-fun] Ulam(1,2) Oops, let's stick with: Second, letting f(n) = (u(n)/21.6) - floor(u(n)/21.6), for what n in 1000...1999 is .5 <= f(n) < .55? There should only be four or five answers. Dan Hoey --- Date: Tue, 11 Feb 2003 18:50:39 -0500 (EST) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: Re: [math-fun] Ulam(1,2) Thanks to corroboration from Jud McCranie, Klaus Brockhaus, and my own new code, and partial corroboration from Edwin Clark, I'm satisfied I had the right answers (though occasionally the wrong question, due to confusion between f(n) mod 21.6 and f(n)/21.6 mod 1 . Oh, and occasionally dividing 21.6 by 2 and getting 10.3 instead of 10.8, in case you were wondering. It's amazing any of my code works the way I'm dropping bits. I'm still working on the faster version of the code. The idea is to code the "lookahead numbers" from u(n)+1 to 2u(n) in order as k when k is not representable as u(i)+u(j) and [m,n] when all numbers m <= k <= n are representable as u(i)+u(j) in just one way. The numbers representable in two or more ways are not mentioned. This is based on the observation that about 1/3 of the lookahead numbers are in the first case, and 2/3 in the third case. Almost all of the first case are singletons, while the run length in the second case averages about 2. The second case accounts for a vanishing fraction of the numbers, but they appear in larger and larger runs. For instance, at u(53584)=724384, the 724384 lookahead numbers are representable in 0 ways, 1 way, more than 1 way 246539 4059 473786 times, in 245835 266 249533 runs. Dan --- Date: Tue, 11 Feb 2003 22:13:56 -0500 (EST) From: Dan Hoey To: "Math Fun" Subject: Re: [math-fun] Ulam(1,2) "David Wilson" writes: > Here's another idea to consider: > Each Ulam number u(n), n >= 2 (zero index) is a unique sum a(n) + > b(n) of distinct earlier Ulam numbers a(n) < b(n). Tabulate a(n) > for 2 <= n <= 2000. There are only 47 distinct values of a(n). It > seems like certain Ulams, starting with 2, 3, 47, 69, etc, are much > more likely to be involved in the sums for subsequent Ulams. Presumably the ones that appear often are the ones in the "sparse space". But something's off with the definition, since your observation would imply that 1, 2, and 3 were all in S, and so the whole sequence would be in S. So I suspect that one of {2,3} will die out as a common addend, and the other will be in the sparse space. Or maybe I need to rejigger the sparse space analysis. If a sparse space can be found that has only finitely many elements of the sequence in it, the sequence can be generated in linear time instead of quadratic. Dan --- Date: Tue, 11 Feb 2003 22:45:34 -0500 (EST) From: Dan Hoey To: "Math Fun" Subject: Re: [math-fun] Ulam(1,2) Oops, from Jud McCranie's small gaps data, I my guess about 2 or 3 dying out is wrong. Something more than a sparse space is at work here. Dan --- Date: Wed, 12 Feb 2003 17:26:30 -0500 (EST) From: Dan Hoey To: Subject: Re: [math-fun] Ulam(1,2) With the first 5 million elements of Ulam(1,2) I've added a new significant figure: The Ulam(1,2) density period is P=21.6015845, plus or minus a few e-7s. It's too far away to be 2765/128, and I don't see anything very attractive in the ISC. Here's a plot of u(n) versus u(n-1), mod P. I took out the bucket elements less than 100, and coded 100-999 and 1000-9999 as 1-9 and a-j. I've noted the common gaps in parentheses, though I may have made some errors with that. Note that the density is blank for residues between 9.0 and -8.0 (or between 0.37 and 0.58 if you prefer normalized mods). \ u(n-1) (mod P) u(n) \-8.0 -4.0 0.0 4.0 8.0 (mod P)\ + + + + + -8.0 + + + + + + + + + + + +(56,34,12) + + + + + + + + (61,39,17) + \\\ + (29,7)+ + + \\\ + \ 3 + \\+ + + \21 + \ 6 + 11 +(44,22) + 133 + 119 + 11 + \\ + 154 + 11b+ +1 + \1 +(83) 266 + 11b + + \2 + \ 287+ 12b + + \4 + 1 2b9 13b + + 2 \6 + 1 3bb +13b + -4.0 + + 47+ + \8+ + + + + 3bb + + + + 13b + + + + + + 9b 1b +3bb 1 + 113b + + bb 2b 2 + 2bb 23+ 113b + + bb +2b 16 + 3bb 55 13b + + bb 1+ 3b 39 + 2bb 66 13b + + 1bb 5 3b 3b+ 3bb +66 39+ (7,27,5) 2bb1b 2b 5b 3bb + 55 36 + \\\ 3cb1c 1b 5b 3b8+ 65 13 + \11 4cb1d 1b +7b 296 55 +11 + \11 5cb1e 7 + 8b 164 55 + 0.0 ++++++++\11++6cb+f+++5+++7b+++++142+++55++++++ + \ \+16bb g 2 7c + 21 54 + + \11 16bb h + 7b + 53+ + \11 17bb h + 7b + 33 + \32 17bb h+ 7b + 21 + 1 +\32 17b8 i 6b+ +11 + 2 + 142 27b7+i 7b + \\ + 2 + 31 27b6 h 6b (37,15) + 13 + 12 16b5 h +5b + + 24+ 1 15b4 h + 59 + 4.0 + + + + + +25 + + + + \594 g+ + + +48 + + + + + + 25 +\473 g + 26 + + +34 + \473 g + 25 + + + 35 + \462 f + 14 + + + 24 + \352 e+ 13 + + + 23 + \341 e \2+ + + 11 + \22 d \1 + + \\ + \1 d \\ + + (30,8)+ \ d (20,42) + + + \ c + 8.0 + + + + + + + + + + + + + + + + \ c+ + + + + \ b \ 5 \\\\ \ (69,47,25,3,2) There definitely seems to be more going on than just a density attractor near 0 mod P--why are the the dense areas not centered in the basin? I'm considering a try of this with u(n) versus u(a(n)), where u(n) = u(a(n)) + u(b(n)) is the canonical decomposition. (I suppose a(n) < b(n), but I wonder if sometimes the other choice would be better.) By the way, I'll warn anyone who wants to work with this period to be numerically careful. Calculating u(n) mod 21.6015845 in floating point gets significantly imprecise when u(n) goes above a few million (Allegro CL on an Ultra). I was about ready to report some curious granularity effects modulo P/256 but fortunately I checked with rational arithmetic first. Things got smooth. Dan --- Date: Wed, 26 Feb 2003 16:17:03 -0500 (EST) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: Re: [math-fun] Prime question Don Reble writes: > > Let p be a good prime if it has only one digit or else a single > > digit can be deleted leaving a prime. Note that this definition was later amended. More below. > Sounds good to me. Indeed, a big prime may have a number of "shortened > primes"; I wonder how many to expect. > Roughly, a number N has a 1/log(N) chance of being prime. That is, > if a number has D digits, the odds are about log(10)/D = 2.302585/D. > If a number is prime, it's coprime to 10, at least, and so ends with > 1, 3, 7, or 9. And "almost all" of the shortenings are also coprime > to 10. The odds of being prime increase by a factor of almost 2.5. So that's the product of 1 = probability of staying prime to 2 2 = relative density of primes in {1} mod 2 1 = probability of staying prime to 5 5/4 = relative density of primes in {1,2,3,4} mod 5 so 5/2 log(10)/D = 5.756463/D. In general, consider that we delete the k'th digit, b, from a D-digit prime P=a + b*10^k + (c*10^(k+1)), producing N = a + c*10^k = P - (b + 9*c)*10^k. For any a prime q, N==0 (mod q) iff P==(b+9c)10^k (mod q). I get Prob(N==0) (mod q) = 0 when q=2 or q=5, 3/10 when q=3, 1/q when q>5. So the probability that N is prime will be (Log(10)/D) Product (1 - Prob(q|N))/(1-1/q) (q prime) = (Log(10)/D) * (1/(1/2)) * ((7/10)/(2/3)) * (1/(4/5)) * ((1-1/q)/(1-1/q)) ^ whatever = (21/8) (Log(10)/D) = 6.044286/D . > Anyway, although the odds might not scale by 2.5, it comes awfully > close: maybe 2.4971498... :-) So the primality-probability of a > shortened prime is about 5.7499001/D. > Now, a (D+1)-digit prime has D+1 shortenings to D-digit > numbers. You'd expect about 5.7499001*(D+1)/D primes among them. For > large D, that approaches just 5.7499001. > One might imagine the distribution of prime shortenings to be Poisson. > Therefore the probability that a big prime is _bad_ comes to > exp(-5.7499001). I think this should be 10^(-21/8) = .00237137. But the important thing is it's a constant. This is the probability that there is no way to remove a single digit and get a prime. But the intended definition was the probability we could remove a single digit and get a _good_ prime. If the probability of being able to remove a digit a second time were independent of the number of ways of removing the first digit, this would give a probability of .99762863^D that a prime would be good, and this would approach zero. In fact, we would expect a finite number of good primes. But to me it seems more likely that B(D), the probability of a D-digit prime being bad, might be (B(D-1))^((21/8) (Log(10)) = B(c) ^ (((21/8) Log(10))^(D-c)) which would make almost all large primes good. Dan --- Date: Thu, 27 Feb 2003 11:38:16 -0500 (EST) From: Dan Hoey To: Math Fun Subject: Re: [math-fun] googol = ? David Wilson asked: > What would be the proper name for a googol? The biggest zillion I > know is 10^63 = 1 vigintillion = 1 20-zillion, this means that a > googol is 10 32-zillion, but I don't know what a 32-zillion is > properly called, if it has a name. The "Book of Numbers" naming system gives this as "ten duotrigintillion" US or "ten thousand sedecillion" British. I don't know why the answer from "Dr Math" is different. Dan Hoey --- Date: Thu, 27 Feb 2003 12:39:25 -0500 (EST) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: Re: [math-fun] Prime Question: Whoops Michael Kleber writes: > No no no, these probabilistic arguments are going the > wrong direction. I figured out one reason last night, see below. > > Let a prime be a good prime if a digit can be deleted leaving either > > the empty string or a good prime. > > Are there infinitely many good primes? > > Let's be very naive and say that all we know is the prime > number theorem, Pr(n is prime) =~ 1/ln(n). > > Then E(# n-digit good primes) / E(# (n-1)-digit good primes) =~ > (# ways to add a digit) * (Pr(an n-digit number is prime), which > is around (10n) * (1/(n ln 10)) = 10/ln 10 =~ 4.34. So the number > of good primes should grow exponentially. That assumes that various n-1-digit primes you get have independent likelihood of being deletable. But that's not at all true, since if you have one n-1-digit delprime, then there is at least one n-2-digit delprime, and so the n-1-digit number you get from deleting the second digit first can be tranformed into the n-2-digit delprime by deleting a single digit. So the probabilities of getting delprimes by deleting different digits have a positive correlation. Looking at the sequence of deletions, I see that the case of divisibility by 3 is much different from what I had been thinking. The digits {1,4,7} and {2,5,8} must be deleted in alternation (possibly with intervening {0,3,6,9}s) or you will hit a number divisible by 3. In particular, the number of 1mod3 digits must differ from the number of 2mod3 digits by exactly 1. Dan Hoey@AIC.NRL.Navy.Mil --- Date: Thu, 27 Feb 2003 14:15:23 -0500 (EST) From: Dan Hoey To: Subject: Re: [math-fun] Re: HTML in math-fun, seqfan posts > I will never again take up the subjects of race, religion, politics or > HTML in math-fun or seqfan. I will not again post, or answer replies, > on this subject. :-) Thank you. Dan --- Math Forum From: haoyuep@aol.com (Dan Hoey) Date: Mar 19, 2003 10:37 AM Subject: Re: CO-NP SAT Confusion On 18 Mar 2003, Ken Payson wrote: >Please help me to understand why an algorithm which can decide SAT >in polynomial time on an NTM can't also be used to decide UNSAT. >Let Q(x) be an algorithm running in polynomial time on a >non-deterministic turing machine >1) Q(x) = True --> x in SAT >2) Q(x) = False -->x not in SAT >3) Q(x) = True --> x not in UNSAT >4) Q(x) = False --> x in UNSAT >1) and 2) are true if Q is a correct algorithm which it is by assumption. >Q(x) = True --> x is statisfiable ---> > not x is unsatisfiable --> x not in UNSAT so 3) follows from 1) ^^^^^^^^^^^^^^^^^^^^^^ That should be "x is not unsatisfiable". >Q(x) = False --> x is not statisfiable ---> x is unsatisfiable >--> x is in UNSAT so 4) follows from 2) >But I'm told that 3) and 4) don't follow from 1) and 2). If so, you're told wrong. 3) and 4) are exactly equivalent to 1) and 2). > What am I not understanding. I think you are not understanding that Q(x) still returns "False" for x in UNSAT and "True" for x not in UNSAT. To demonstrate UNSAT in NP, you would need an algorithm in NP that returns "True" for x in UNSAT and "False" for x not in UNSAT. We are used to thinking that we can simply change all the "return(x)" statements in a program to "return(not x)", and get a program that returns the opposite answer. This is not, however, true of nondeterministic algorithms. Remember that a nondeterministic algorithm returns "True" when at least one branch returns "True" (if you are using the "branch" formulation). Changing the results returned by each branch does not change the "at least one" to "every", which is what you would need to construct the desired predicate in the straightforward way you suggest. Dan Hoey haoyuep@aol.com --- Newsgroups: geometry.puzzles From: haoyuep@aol.com (Dan Hoey) Date: Wed, 19 Mar 2003 17:46:44 +0000 (UTC) Subject: Re: point outside an equi-triangle Yes, both answers 9sqrt(3)+sqrt(19) and 9sqrt(3)-sqrt(19) are solutions to the original problem. The stricture that the point be outside the triangle is satisfied in both cases. Dan Hoey haoyuep@aol.com --- Newsgroups: rec.puzzles From: haoyuep@aol.com (Dan Hoey) Date: 22 Mar 2003 17:05:47 GMT Subject: Re: Hot Dogs and coin flips Bob Harris wrote: > You flip the fair coin several times, until you get two heads in > a row. Each time the coin comes up *tails*, you get to eat > one hot dog for each flip you've made so far. > Example: > T H T T T H T H H > 1 3 4 5 7 -----> you eat 20 hot dogs > Question: > How many hot dogs do you expect to eat? > While this is an easy puzzle to simulate, I think it is a > tougher problem to crack analytically. Well, let's first try a simpler game, where you eat just one hot dog each time the coin comes up tails. This is a simple extinction game: You have a 0.75 probability (T or HT) of getting to eat a hot dog and play again, and 0.25 probability (HH) that the game is over. If you expect y dogs, then y = 0.75(1+y), so y=3. We can model the increased payoff in your game due to having already flipped N coins as playing my game N alongside yours. So in your game we have a 0.5 prob- ability (T) of eating one dog, playing my game once, and playing your game again, a 0.25 probability (HT) of eating two dogs, playing my game twice, and playing your game again, and a 0.25 probability (HH) of going away. If x is the expected number of dogs in your game, then x = 0.5(1+y+x) + 0.25(2+2y+x) = 4 + 0.75x, so x=16. I guess that analytic solution isn't quite trivial, but not too bad. Dan Hoey haoyuep@aol.com --- Newsgroups: rec.arts.sf.fandom From: haoyuep@aol.com (Dan Hoey) Date: 04 Apr 2003 00:27:01 GMT Subject: Re: More on David Brin and Jo Walton at Boskone Kevin J. Maroney wrote: > Elisabeth Riba wrote: > >I'd never heard the Charles Platt story, nor any other > >tales about Harlan resorting to violence. Can somebody > >sum it up or point me to an account of what happened? > In 1984, Larry Shaw was dying of cancer. Ellison and > Robert Silverberg presented a tribute to Shaw during the > Hugo Awards ceremony. Platt wrote a nasty piece about it > in Science Fiction Chronicle (in his "Gabby Snitch" gossip > column). Ellison travelled to the 1985 Nebula Banquet > with the express purpose of punching Platt in the nose, > which he did. (The late Robert Shea, who was one of the > nicest human beings to have ever walked the planet, said, > "Hell, I would have done it myself.") I have heard various criticisms of the "Gabby Snitch" column, and some people have said it was "ugly" or "nasty". Ellison justified his assault on Platt on the basis that the article was insulting to the memory of Larry Shaw. But the only part of the article I have seen was this excerpt, which appears in the _Gauntlet_ article (URL below): | "Silverberg and Ellison did an 'Obituary Preview' for the | unlucky Shaw. E & S method acted a speech (mainly written | by Ellison) with so much MELODRAMATIC HYPERBOLE some | people thought it was a joke -- till Ellison grimaced and | wiped his forehead to signify the emotional trauma. Then | poor Mr. Shaw accepted his BRASS PLAQUE and croaked, 'I | bought this fella's first story, and I hope to be around | to buy his last!' Too late, Larry -- as I understand it, | Harlan wrote his last story sometime during 1981." I don't think Larry Shaw comes off as the villain of that excerpt, but of course it's out of context. As I was checking through my files for this reply, I found an earlier article from you. Eight years ago, in rec.arts.sf.written, you asked Charles Platt: : Do you happen to have to hand the two sentences you wrote : about the event? A number of people, including those who are : not inclined to think ill of you or well of Ellison thought that : your statements were in exceptionally atrocious taste and : embarrassing. and Platt's reply was that a) he agreed that the criticism of him might be justified, b) he didn't have the article, and c) he thought that a few sentences would be misleading out of the context of a considerably longer article. So have you gotten any more information about the context in the intervening years? This year, Kevin continues: > ... Many more details, if you're really interested, can be found > here: That article by Richard Cusick was fascinating. There is certainly a great deal of exposition about several feuds involving Harlan Ellison. Mixed into it was a running commentary about the evil motives of Ellison's opponents and the justifications and rationalizations that show how he is victimized by his enemies. It seemed to me that Cusick intended that the factual reporting would support the editorial analysis, but I thought the latter tended to call the former into question. The factual material certainly does not stand on its merits as a piece of journalism. Aside from having the editorialism mixed in with it, there are serious logical problems. In one place, Cusick uses a false dichotomy in an attempt to impugn the consistency of Platt's statements. Several disputed incidents are described as fact and without any assertion of their provenance, and they seem to be directly from Ellison. I cannot accuse Cusick of a lack of journalistic integrity, since he may just be sloppy. But I cannot accuse him of a lack of journalistic competence, since he may have cooked the argument on purpose. But for all the questionable exposition, what I found most amazing were the opinions that 1. A publisher does not have the right to use the news and editorial functions of his publication to settle old scores and private matters, and 2. A person who becomes enraged at mean-spirited criticism, and who hires a lawyer to send a letter threatening a lawsuit if the criticism is published, cannot be accused of attempting to suppress free speech. Cusick flims a lot of flam around these points, but they are still patent nonsense. The latter point may seem like a non-issue--using legalities to suppress free speech is not illegal, after all--except that we usually don't give such people awards for defending free speech, as I understand PEN did. Dan Hoey haoyuep@aol.com --- Date: Tue, 8 Apr 2003 12:42:18 -0400 (EDT) From: Dan Hoey To: Roland Silver , math-fun Subject: Re: [math-fun] tic tac toe variants Roland Silver writes: > ... I published a paper on the automorphisms the board (permutations > of the cells which preserve 4-in-a-row) some years ago (Amer. Math. > Monthly; Vol. 74, No. 3 (March 1967), pp. 247-254). Aside from the > obvious subgroup of 48 rotations and reflections, there are two > other independent automorphisms. One scrambles the board by > interchanging each of the 3 parallel pairs of inner planes, while > the other inverts the board by interchanging each of the 3 pairs > consisting of an inner plane and its parallel outer neighbor. > The whole group has 192 elements. I enjoyed that paper quite a bit. I especially appreciated the work you did to show that there were no _other_ symmetries. Later on, I was working with "Rubik's Revenge", the 4^3 Rubik's cube. I think it was David Singmaster who noticed that it had some extra symmetries, and I realized with amazement that they were the same as the extra symmetries of 4^3 tic-tac-toe. (These symmetries only work if you consider the puzzle to consist of an array of cubes all the way through, where the inner cubes have to be solved as well as the outer ones.) These symmetries--inverting some layers and permuting the noncentral layers--extend to larger sizes and dimensions of Rubik's cubes and tic-tac-toe boards. I suspect these are all there are, no matter how big you get, but I haven't a proof. I wonder if these groups have any other applications? Dan Hoey@AIC.NRL.Navy.Mil --- Date: Thu, 24 Apr 2003 09:34:20 -0400 (EDT) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: Re: [math-fun] brick tilings reid@math.arizona.edu (michael reid) wrote: > check out "tiling a polygon with rectangles" by claire and richard > kenyon, proceedings of the 33rd foundations of computer science (FOCS), > 1992, pp. 610-619. theorem 3 of that paper asserts that, given a simply > connected polyomino region tiled by m x 1 (vertical) polyominoes > and 1 x n (horizontal) polyominoes, then any two such tilings can > be obtained from one another by steps of the form > replace an m x n subrectangle tiled by horizontal > tiles by one tiled by vertical tiles > or the inverse operation. Neat! And the restriction to simply connected regions is necessary: _______ _______ | |_____| |_____| | | | | | | | | | |_|___| | | |___|_| |_____|_| |_|_____| Dan --- Date: Thu, 1 May 2003 21:00:20 -0400 (EDT) From: Dan Hoey To: wpthurston@mac.com Subject: Re: [math-fun] hex on manifolds cc: math-fun Bill Thurston writes: > Does anyone have some thoughts about generalizations of hex to > various manifolds? > ... For CP^2, a good rule seems to be to declare the winner to be > anyone such that H^2(their colors) is non-zero. Forgive me if this is exactly what you said, but I suggested playing hex on the projective plane a few years ago. Bill Taylor pointed out the natural winning configuration: a path that is not contractible to a point. (If that isn't what you said, what's CP^2?) You can play on a "Y" board, which is graph-isomorphic to a hemi-icosahedron with the sides triangulated. Edge moves are made by playing two antipodal stones. On the commercial board (available from Kadon), you play on the vertices of the triangulation. If you prefer ASCII art, I wrote a program that produces drawings where you play in the spaces. Here are three sizes of board. For the smallest, there's only one starting move, only one response, and then two of the four third moves are winners. The next size up has two openers--are they both winners? ____ ____ / \__ ____/ \ / __/ \__ __/ \__ \ \__/ \ \__ __/ __/ \__/ / \ \____/ \ __/ \____/ / \ \ \__/ \ \ __/ / \__ \ \ ____ / / \____/ / __/ \____/ __/ \__/ / / \____ \__/ / \__/ / / \__/ / \ \ / __/ \__ / \__/ __/ __/ __/ __/ \ \ \__/ \__/ \__ \____ \ \__/ / \__/ \__/ \ \____/ / \ / \ \____/ \__ \____/ / / / \__/ \__/ / / / __/ \__ \____ \ \__ \__ / \____/ \ \ \ \__/ \__ \____/ \__ \__/ \__/ \__/ / \ \__/ / / \ \____/ \__ \__ \ \ \__/ / / \ \__/ / __/ \__ \____/ \__ \__ \____/ \__ \__/ / / \ \__/ \__ \____/ \ \__ \__/ \ \__/ \ \ / / / \ \____/ \ \____/ \__ \__ \____/ / / \ \__/ / __/ \ \____/ \ \ \__/ \__ \__/ / / \ \__/ \__ \____/ \ \__ \__ \__ \__/ \ \__/ / / \ \__/ \ \____/ \__/ \__ \____/ / / \ \__/ / / \ \____/ \ \ \ \____/ / / / \ \____/ \____/ \ \__ \__ \__ \ \__/ \__/ \____/ \ \____/ \__/ \__/ \__ / / \ / \ / \ \____/ \ \ \ \ \__/ \__/ \__/ \____/ \__ \__ \__ \__ \__ / \ / \ / \ / \ / \__/ \__/ \__/ \__/ \ \ \__/ \__/ \____/ \__/ \ \ \ \ \ / / \ / \ / \ / \ __/ __/ __/ __/ / \__/ \__/ \__/ \____/ \__/ \__/ \__/ \__/ \__/ / \ / \ / \ / \____/ / / / / \ \__/ \__/ \____/ / \____/ __/ __/ __/ / / \ / \____/ \____/ / \__/ \__/ \__/ \ \ \__/ / \ / \____/ / / / \__/ / \ \ \__/ / \____/ __/ __/ / \ \ \__/ __/ \____/ / \__/ \__/ \ \__/ / \__/ / \____/ / / / / \ \ \____/ / \____/ __/ \ \ \__/ __/ \____/ / \__/ \__/ / \__/ __/ \____/ __/ / \ \ \____/ __/ \__/ \ \__/ __/ \____/ __/ / / \__/ __/ \____/ \ \ \____/ __/ \__/ __/ \____/ / \__/ __/ \ \____/ \____/ By the way, did anyone figure out toral 4x4 tic-tac-toe? Dan Hoey@AIC.NRL.Navy.Mil --- Newsgroups: sci.math.research From: haoyuep@aol.com (Dan Hoey) Date: 04 May 2003 05:02:50 GMT Subject: Re: Graph isomorphism with "don't care" colours bdm@cs.anu.edu.au (Brendan McKay) asks the computational complexity of: Given two undirected graphs G, H where each vertex is given a color, or a special "dont care" color, is there an isomorphism between the graphs that respects colors, _except_ that the "don't care" color can be mapped to any color, or vice versa. As he suspects, the problem is NP-complete. I have a transformation from CLIQUE. Given a graph G=(V,E) and an integer k, we will determine whether G has a clique of size k. Let K(V)=(V,E') be the complete graph on V. Now construct A, the incidence graph of K(V): A = (V union E', { {v,{v,w}} : v,w in V } ). Select a subset V_k of V of size k and let K(V_k)=(V_k,E_k) be the complete graph on V_k. Define the following two colorings of A: A_G : for v in V, v is colored 0; for e in E, e is colored 1; for e in E' \ E, e is colored 2. A_k : for v in V, v is colored 0; for e in E_k, e is colored 1; for e in E' \ E_k, e is colored "don't care". Consider a color isomorphism M: A_k -> A_G. Constrained by the color 0, M must map V to V, and so by cardinality must also map E' to E'. Furthermore, for any v,w in V_k, the only vertex in A adjacent to both v and w is {v,w}, which is colored 1 in A_k, so M({v,w}) must be colored 1 in A_G, so M({v,w}) must be an edge in E. So M maps V_k to the vertices of a clique in G. Clearly any such M is a color isomorphism from A_k to A_G. So A_k and A_G are color isomorphic exactly when G has a clique of size k, QED. In case it matters, I note that only one of the graphs need have "don't care" vertices for the problem to be NP-complete. Dan Hoey haoyuep@aol.com --- Date: Tue, 6 May 2003 21:57:18 -0400 (EDT) From: Dan Hoey To: "math-fun" Subject: Re: [math-fun] A proposed new chess rule Of course pinned pieces can check just like any others; I can't imagine players of real chess wanting it different. Still, a variant chess without check-pins might be fun. But then can a pinned piece pin another piece? If A pins B pins C pins D pins A, then I guess any one piece could move, but its ally would then be "really" pinned. I seem to recall a problem where there is a mate in N moves after 2N+2 checks, all by pinned pieces. Or maybe it was 2N+3 checks. Dan --- Date: Mon, 12 May 2003 10:15:24 -0400 (EDT) From: Dan Hoey To: math-fun Subject: Re: [math-fun] Home Schooling Eugene Salamin writes: > The one most important thing we can do for the educational system is > to encourage "vouchers" .... I abhor the practice of waging political campaigns on math-fun. Unfortunately, some people are encouraged by their ability to mistake irrelevance for irrefutability. I often hear these people arguing on busses. Dan Hoey --- Date: Mon, 9 Jun 2003 13:33:16 -0400 (EDT) From: Dan Hoey To: Michael Kleber Subject: Re: [math-fun] Car talk puzzler cc: math-fun@mailman.xmission.com Michael Kleber writes: > Last week's Car Talk puzzler might have some interesting math. > (Tom and Ray said this has been floating around, but I haven't > heard it before; am I behind the curve here?)... There are a lot of crossing problems, but this one is quite familiar. It has been kicking around rec.puzzles since 1996, when it was said to be a Microsoft interview puzzle: http://groups.google.com/groups?selm=01bbc5b7%242146dd80%247b839bce%40redpwq.acc ucomm.net Somewhere along the line it was dressed up as being the four members of the band "U2" who had to get across to make their concert on time. (Do bands start on time now? It's been a long time since I was at a rock concert.) > 1) If you have 2n people, how many different undominated strategies > are there, and what structure does this set have? I don't see why you want the number of people to be even. For N people, the minimum number of crossings is 2N-3, but that may not be optimal in all cases. I know that for N=6 we can force 11 crossings, but I don't know if there's an optimal 9-crossing solution for N=5. Dan Hoey@AIC.NRL.Navy.Mil --- Date: Mon, 9 Jun 2003 15:43:34 -0400 (EDT) From: Dan Hoey To: Michael Kleber Subject: Re: [math-fun] Car talk puzzler cc: math-fun@mailman.xmission.com Michael Kleber writes: > Dan Hoey wrote: > > There are a lot of crossing problems, but this one is quite > > familiar. It has been kicking around rec.puzzles since 1996[...] > Over lunch, I mentioned it to Dimitry Kleinbock, who said he saw it > in a Quantum Magazine even before that (and culled it for a Math > Circle type thing he was doing in NJ, and he might be able to dig up > a citation). Neat. I didn't think it was likely to be a Microsoft original. I wonder if I saw that Quantum. I remember thinking the puzzle looked familiar when I saw it in rec.puzzles. > But any reference for >4 crossers? I don't know of any. I wonder if anything useful comes of bridges that hold three people? Or flashlights that require two people to carry? When I wrote: > > I know that for N=6 we can force 11 crossings.... I was wrong. Somehow I thought the case with 1,2 small and 3,4,5,6 large would require that, but your strategy > 12, 1, 34, 2, 12, 1, 56, 2, 12 is clearly the solution. I haven't got a proof, but I suspect 2N-3 crossings is always best. > Which of the three N=6 strategies is preferable depends on how 2 a2 > compares to a1+a3 and a1+a5. I don't know if it would help to consider the first differences of the parameters (since if the number of crossings is constant, they are all that matter). Then the criteria would be d1:d2 and d1:d2+d3+d4. Dan --- Date: Tue, 10 Jun 2003 17:18:56 -0400 (EDT) From: Dan Hoey To: Michael Kleber Subject: Re: [math-fun] Car talk puzzler cc: math-fun@mailman.xmission.com I wrote: > I haven't got a proof, but I suspect 2N-3 crossings is always best. I still haven't proved anything, but I wrote a brute-force program, and I'm beginning to suspect there's less here than meets the eye! Namely, that for N>1 there are essentially floor((N-2)/2) strategies, depending on how many of a_(n-1), a_(n-3), ..., a_(3 or 4) are greater than 2a_2 - a_1. Then you do 1 and 2 across, 1 back, two largest across, 2 back, that many times, and 1 and largest across, 1 back for the rest, plus a final 1 and 2 across. I've been trying to figure out a way of making this nontrivial, but it starts getting baroque. You have N guys and a (J,K) litter--a litter that holds J guys and needs K other guys to carry it, traveling at the speed of the slowest bearer.... Dan --- Newsgroups: rec.puzzles From: haoyuep@aol.com (Dan Hoey) Date: 18 Jun 2003 02:54:47 GMT Subject: Re: random tic-tac-toe Sterten@aol.com proposes a puzzle from Juha_Saukkola@hotmail.com: > suppose a one-player tic-tac-toe on a 3*3-board. He gets an > X with probability p and an O with probability q=1-p on each move. > He wins as soon as he has 3X in a row/column/diagonal and > loses on 3O in a row/col/dia . Else it's drawn after 9 moves. > What's his best strategy and his winning-expectation > (won=1,lost=0,drawn=0.5) using that strategy for p=0.5 ? Jon Haugsand wrote: > I cannot possible see any strategy here. As he is bound to > place something on each of the nine squares and the only > choice he has, if I understand you correctly, is when each > square gets its marking. Thus, the strategy of pointing to > each square in sequence is as good as any ... As Risto Lankinen pointed out, the decision of when the squares get marked is important, since if both X and O will eventually get three in a row, the winner is the first to get their three. Jon Haugsand wrote: > The probability of getting three Xs on a row with randomly > getting an X or an O with prob 1/2 is, as far as I can calculate > 239/512. I get 282/512 -- 198/512 probability of three Xs in a row and no three Os in a row, and 84/512 probability of both X and O getting three in a row. The probability of a tie (no three in a row) is 32/512. A program I wrote produced this table of all the outcomes: ...................... : Number of OOO rows : : | .................:................ : | : Number of XXX rows : : v : 0 1 2 3 4 5 6 8 : : :................................: : 0 : 32 74 66 34 13 6 4 1 : 1 : 74 72 6 : 2 : 66 6 : 3 : 34 : 4 : 13 : 5 : 6 : 6 : 4 : 8 : 1 :...: Where each outcome has probability 1/512. Danny Kodicek wrote: > The way I read the question, he discovers which symbol he is > using and *then* places it on the board.... As Guenter later clarified, this is not the intended reading. I have not investigated it. John Haugsand's analysis does help, since it tells us that there is no benefit to any sequence _unless_ both X and O will have three in a row after nine moves. If both have three in a row, neither has a diagonal row, so the diagonals do not affect the strategy. Analysis of the game in which diagonals do not win may be easier, since the automorphism group has order 72 instead of 8. However, a brute force program does not need this simplificition. It might be interesting to consider three-dimensional tic-tac-toe, in which diagonal wins do not prevent multiple wins, so that diagonals have strategic importance. My program finds that the following strategy is optimal, winning with probability 281/512: 1. If there is one X and no Os on the board, make the next play on one of the horizontal or vertical lines containing the X. 2. If there is one O and no Xs on the board, make the next play somewhere other than on the horizontal and vertical lines containing the O. 3. Otherwise, if there is a vacant square that is not on a line containing two Os, make the next play on any such square. 4. Otherwise, make any possible move. Together with the 32 tied games, this yields an expected 297/512 points per game. Note that this 1/512 less than the number of positions in which X has three in a row. Apparently this is due to the situation X | X | ? ---+---+--- X |any| O ---+---+--- ? | O | O in which there is a 1/4 probability that the first square tried will be O, while the second would be X. Dan Hoey haoyuep@aol.com --- Newsgroups: rec.puzzles From: haoyuep@aol.com (Dan Hoey) Date: 29 Jun 2003 03:10:22 GMT Subject: Re: four bottles Duncan Booth writes: > Not a proof that this is the shortest, but my > reasoning why I believe that five is the shortest: > ... Out of curiosity, I decided to find the shortest solution by exhaustive search. Call the possible nonfinal bottle positions (up to rotation) 1: D D D U 3: D D U U 5: D U D U 7: D U U U . The state of the player's knowledge is what subset of the four positions is still possible. My program finds that from the initial state (1357), the first two moves must reduce the possibilities to (1) or (7) with two probes. The use of one opposite and one adjacent probe has already been seen. Another way is to use two opposite probes, e.g.: 1. Turn both opposite bottles up. 2. If both opposite bottles are up, turn them both down. Otherwise turn both up. This ensures that only one bottle is up, because otherwise the game would be over. The next three moves must be an opposite probe yielding (3), an adjacent probe yielding (5), and an opposite probe yielding (). It might be interesting to see what strategy minimizes the expected length of the game. Dan Hoey haoyuep@aol.com --- Date: Wed, 2 Jul 2003 12:08:58 -0400 (EDT) From: Dan Hoey To: Henry Baker Subject: Re: [math-fun] Re: Z*(SqrtN) cc: math-fun Marc LeBrun wrote: > >> Regarding Z*(SqrtD) = {x + y SqrtD; integer x, y, D>=0}... > >> 2. What's best to call the whole algebraic structure? I'd say Z*(SqrtD) = {x + y SqrtD; integer x, y>=0}, for integer D>=0, just to keep the scope straight. I take it "Z*" is the nonnegative integers. Henry Baker wrote: > "algebraic natural numbers" or "natural algebraic numbers" ?? Cute name, but I'd rather use that for the positive elements of Z(SqrtD) (or the nonnegative ones, in France and set theory). Then the elements of Z(SqrtD) with both components positive could be called "supernatural", and those with at least one component positive could be called "subnatural". Dan Hoey@AIC.NRL.Navy.Mil --- Date: Wed, 2 Jul 2003 14:09:04 -0400 (EDT) From: Dan Hoey To: Marc LeBrun Subject: Re: [math-fun] Re: Z*(SqrtN) cc: math-fun Marc LeBrun wrote > > I take it "Z*" is the nonnegative integers. > Yes. I've never much liked that notation either. Is there a better > one? I've also considered using Z0, N0 and even U (for unsigned) but Z* > seems pretty prevalent, despite its opacity. I like Z^(>=) (i.e. Z superscript greater-than-or-equal). Then you can use things like Z^(>1) for {2,3,...}. Let a countable number of flowers bloom! > >>=Henry Baker > >> "algebraic natural numbers" or "natural algebraic numbers" ?? > > Cute name, but I'd rather use that for the positive elements of > > Z(SqrtD) (or the nonnegative ones, in France and set theory). > The "non-negative algebraic integers" might be construed to include > the undesired Sqrt2-1, which is positive but has a negative > component. Yes, that's what I meant. I mostly like this definition of natural because it leaves useful definitions for "supernatural" and "subnatural". Of course, it's mostly because I get a kick out of naming "supernatural numbers". I imagine Knuth got a similar kick out of naming Conway's "surreal numbers". > > Then the elements of Z(SqrtD) with both components positive could > > be called "supernatural", and those with at least one component > > positive could be called "subnatural". > Isn't "natural" supposed to connote a strictly positive integer? In Germany and algebra, yes. In France and number theory, zero is natural. That's of course a gross (and possibly geographically incorrect) simplification of the zerophilia question, but basically you can't count on a particular meaning of "natural" unless you define it. For most natural purposes, it doesn't really matter--you can get a peano with or without the "Z" key, and you just have to transpose music written for the other kind. > I would think "natural algebraic numbers" would refer to only those > numbers with all components positive integers. I guess if you like N = Z^(>), that's a good way of thinking. In that case, I'd call Z^(>=) the "znatural numbers". Just be careful saying it, because people start slapping for mosquitos. > Assuming that, I guess it'd make (some kind of) sense to call the > superset got by adjoining the ("unnatural"?<;-) elements with zero > components the "supernatural algebraic numbers". I still like "super-" = both components, "sub-" = either component definition. Then if you want both components znatural, you're talking about the superznatural part of Z(sqrt2). Dan Hoey@AIC.NRL.Navy.Mil --- Date: Thu, 3 Jul 2003 10:53:16 -0400 (EDT) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: Re: [math-fun] misc / astronomical gravitational simulations Richard Schroeppel writes: > The finite speed of gravitational attraction should be an issue > for galactic simulations, even if other relativistic effects do > not arise. E.g., suppose that some configuration several light > years away suddenly flies apart. The observer (viewer _or_ body > effected by the gravitational change) wouldn't notice it for > quite a while. That always made me wonder. After all, if the configuration is far enough away to notice the delay, it ought to gravitate the observer much like a point mass. If the configuration flies apart, conservation of momentum keeps the center of mass fixed (or on the same inertial path), and conservation of mass keeps the magnitude the same. Now some of the mass needs to become energy to make the body fly apart, but I think the energy has the same gravitational effect, no? This is all very confusing to me, but I suppose we could turn all the mass into photons, half toward the observer and half away. The attraction will approach infinity when the photons arrive. But with lightspeed propagation of gravity, the gravity does not change until the photons arrive, so it essentially jumps to infinity rather than increasing gradually. Is that a sensible scenario for testing the difference, or is there something I've missed? Dan Hoey@AIC.NRL.Navy.Mil --- Date: Thu, 3 Jul 2003 18:22:15 -0400 (EDT) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: Re: [math-fun] NY State math exam flapment Henry Baker > From what I can tell, these tests are already doing what they are > intended to do: determine who can function in our society. In that case, the "Math A Regents exam" is not a mathematics test, so your remark is misdirected. This is a list about mathematics, not cultural integration tests. Not that your departure from the topic is comparable to the reek of gas about "flaming liberals" we got from the flaming ... whatever ... earlier today. That one belongs on a bus--they take any kind of rant you like there. Meanwhile, I'm intrigued by the straw problem. So far, the best I've done is to express the length as sqrt(tt+uu+vv) where (t,u,v) satisfy equations (x-t)^2 (tt+uu+vv) = 4 r^2 (uu+vv) (y-u)^2 (tt+uu+vv) = 4 r^2 (tt+vv) (z-v)^2 (tt+uu+vv) = 4 r^2 (tt+uu) in the box dimensions (x,y,z) and the straw radius r. Adding them up, I'm startled (possibly not for the first time) that any way you lean a disc of radius r on the floor against two walls, the center will be sqrt(2)r from the corner. Is there an easy geometrical proof? But I'm pretty much flummoxed about solving the whole system. Maybe I should have gone to high school in New York. Dan Hoey@AIC.NRL.Navy.Mil --- Date: Mon, 7 Jul 2003 04:14:06 -0400 (EDT) From: Dan Hoey To: Henry Baker Subject: Re: [math-fun] circular discs in corners cc: math-fun@mailman.xmission.com About my remark that > > any way you lean a disc of radius r on the floor against two > > walls, the center will be sqrt(2)r from the corner. Henry Baker says: > You are absolutely right! I checked this using a symbolic algebra > package on the plane to Boston today. From one of my previous > forays, I already had a good method for finding the incenter of a > circle in 3D, so I found the incenter of the triangle (x,0,0), > (0,y,0), (0,0,z). I then found the distance^2 to the origin. I then > divided by the radius^2 of the incircle, and voila'! The ratio is > exactly _2_ ! Taking the square root, we get a ratio of sqrt(2) for > the ratio of the distance to the radius, as you point out. Well, that is even more startling, because it's a solution to a different problem! Your calculation is of a disc supported by three perpendicular lines; mine is of a disc supported by three perpendicular planes. Does this mean what I suspect it means--that if you support the disc on three perpendicular planes, the lines from the points of tangency to the origin must be mutually perpendicular? I'm becoming motivated to make sure I get this solved, just to verify that conjecture. > A man in the street could understand this -- nail one end of a > string into a corner of a room. Take a large circular table with a > small hole in the center, and put the string through the center. > Now push the table into the corner, and pull the string taut. You > can move the table around -- up to and including flat against one > wall, and you won't break the string, and the string won't become > slack either! I thought of a gadget something like that, only with a rigid strut holding the disc center to the corner. Then you don't have to watch it to know it doesn't go loose. Of course, neither of these tethers lets you turn the disc over, as you can in theory. (If the above plane-support=line=support conjecture is true, then you could also mount a tripod of perpendicular struts from the corner so that they meet the disc at the points of tangency.) I wonder if this linkage has any useful qualities as a somewhat universal joint? Say one that provides heavy-duty support (from the disc resting on the planes) and light-duty tension (from the strut). The strut can be connected with ball-and-socket joints on both ends, since it isn't subjected to great force. I don't know if there's a better way to support the disc than with sliding edges. If the planes are backed off, a carriage could be inserted that slides on the plane and accepts the disc in a groove. Optionally, a hole through the carriage could maintain alignment with the tripod leg, if that conjecture works out. This would be interesting just to watch. Meanwhile, I'm still trying to solve the original problem (which is the key to all the other stuff.) I looked at the two-dimensional problem to see if I could get anywhere. I think I've seen rectangles inscribed in rectangles before, but I'm not sure where, so I worked on it from scratch. Anyway, for an a x b rectangle is inscribed in a c x d rectangle, I get 0 = (a^2 - b^2)^2 - (ad - be)^2 - (ae - bd)^2 which means solving a quartic (unless I've overlooked some simplication.) (I find it interesting that this equation can also be written 0 = (a^2 - b^2)^2 - (a^2 + b^2) (d^2 + e^2) + 4 abde which is only quadratic in the reparameterization of the rectangles from (width,length) to (hypotenuse squared,area). And then the two kinds of parameters are nicely segregated from each other, though the a^2b^2 term is of ambiguous kind.) I still haven't worked out a way of using this to solve the three-dimensional problem. Dan Hoey@AIC.NRL.Navy.Mil --- Date: Mon, 7 Jul 2003 10:14:03 -0400 (EDT) From: Dan Hoey To: Henry Baker Subject: Re: [math-fun] circular discs in corners cc: math-fun@mailman.xmission.com Henry Baker wrote: > I think that the right way to think about this is to keep the > straw stationary, and wiggle a right-angled corner around on > the end of it. The corner itself traces out the surface of a > hemisphere of radius r sqrt2 around the center of the end of the > straw. Okay, but how to wiggle it so that the point at (X/2,Y/2,Z/2) (in the coordinates of the corner) lies on the axis of the straw? I haven't even figured out how to map from the (three-parameter) position and orientation of the corner to the vertices of the triangle. > But I disagree that you think that these are two different problems. > The plane determined by the end of the straw intersects the corner > in a triangle, and I contend that the end of the straw is the incircle > of that triangle. You are correct, of course. I misread your earlier statement, "I found the incenter of the triangle (x,0,0), (0,y,0), (0,0,z)...," as referring to the center of the circle through those three points (the circumcenter of the triangle), rather than the center of the circle inscribed in the triangle. Now that I see it, I admire your transformation very much! Tangent planes to tangent lines, axes to vertices. > Question: Does the base of the hemisphere (described above) traced > out by the corner form the circumcircle of the triangle? That > doesn't seem right, since the circumcircle isn't always concentric > with the incircle. No, and, "Indeed, it couldn't be right." > So what _is_ the geometric significance of a circle sqrt(2) bigger > than the incircle? (and concentric with the given incircle). Answer: The circumcircle of a square with that incircle. For when the corner is in the plane of the incircle, the triangle has a right angle at the corner (and you get to pick any hypotenuse tangent to the other side of the incircle). Dan Hoey@AIC.NRL.Navy.Mil --- Math Forum Date: Jul 12, 2003 5:00 PM From: haoyuep@aol.com (Dan Hoey) Subject: Re: Problem: a/b + b/c + c/a = n On 10 Jul 2003, Marcus wrote: > I'm stuck on this problem that was posed on another message board. > The problem is to find which positive integers n can be the result > of a/b + b/c + c/a, where a, b, and c are positive integers. > Marcus I don't know why this question hasn't shown up on Usenet or Google, but that may be why you've gotten so few answers. I think the problem is well-known (though not to me). Anyway, an approach is to assume gcd(a,b,c)=1, though a, b, and c may not be pairwise relatively prime. Then it turns out that we can find integers t,u,v that are pairwise relatively prime, and for which a=t^2 u, b=u^2 v, c=v^2 t. The same (t,u,v) also yields a triple a=t^2 v, b=v^2 u, c=u^2 t, which is different if the t,u,v are different (which can only occur with (1,1,1) and (1,1,2)). Anyway, n=(t^3+u^3+v^3)/(tuv). My program tries u=1,2,...,50 (though it could easily go further on a better Lisp). For each u it tries all 1 <= t <= u with gcd(t,u)=1. For each t and u it tries all divisors v|t^3+u^3 with v >= u. The result (sorted by n) is: n t u v 3 1 1 1 5 1 1 2 6 1 2 3 9 2 3 7 10 5 7 18 13 9 13 38 14 2 7 13 17 5 18 37 18 13 42 95 19 1 5 9 21 2 13 21 26 9 38 91 29 27 43 182 30 2 21 31 41 2 31 43 41 1 5 14 41 1 2 9 51 9 13 77 53 2 7 27 54 2 43 57 66 1 3 14 83 5 9 61 106 1 35 54 149 1 14 45 154 2 13 63 161 11 38 259 174 5 7 78 178 2 27 97 195 7 15 143 250 2 9 67 261 3 7 74 269 1 14 61 323 9 49 377 326 5 14 151 451 23 31 567 478 13 23 378 633 3 14 163 978 33 43 1178 978 2 7 117 1011 7 11 279 1410 3 22 305 1658 19 26 905 1718 9 19 542 1769 2 5 133 1875 15 19 731 1893 3 43 494 1914 31 45 1634 2163 1 49 325 2309 2 13 245 2369 1 9 146 2681 1 49 362 4018 14 45 1591 5246 13 31 1454 5430 19 25 1606 6638 26 37 2527 7061 2 35 703 8346 31 37 3094 10995 3 23 871 12105 7 18 1235 13971 3 11 679 14803 1 9 365 15722 7 38 2045 17859 37 45 5453 18014 1 35 794 20778 2 13 735 21529 1 14 549 24761 7 31 2318 31130 14 43 4329 33081 3 31 1754 39290 7 45 3518 59802 1 14 915 82949 5 13 2322 84178 9 19 3794 92454 5 39 4246 112901 5 34 4381 118366 2 31 2709 187001 2 13 2205 191974 9 46 8915 196026 7 26 5973 203654 2 43 4185 941491 1 45 6509 2000041 1 29 24390 Dan --- Date: Mon, 14 Jul 2003 10:13:17 -0400 (EDT) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: Re: [math-fun] Marilyn Vos Savant again ????? Dan Asimov wrote: > The world's smartest human has posted a probability problem, and her > answer to it, on this webpage > . That URL demanded cookies and a zip code, which I am not inclined to supply. BUt it also included a pointer to a "text-only page", , which has a "fascinating new probability problem about a student taking a test" buried in a bunch of ... other material. Dan Hoey@AIC.NRL.Navy.Mil --- Date: Mon, 14 Jul 2003 13:24:18 -0400 (EDT) From: Dan Hoey To: math-fun Subject: Re: [math-fun] Marilyn Vos Savant again ????? "Bernie Cosell" wrote: > Right, and just to summarize here: it seems to be identical with the > Monty Hall problem, EXCEPT: that the instructor informed the > students of a wrong-choice on the exam *without* knowing which > choice the student had made. The question addressed is whether the > instructor's 'revelation' being random, rather than knowingly NOT > selecting the one the player/student chose, affects the odds. Just to be complete, I should say that the instructor informed the students that choice C was wrong. The question was asked from the standpoint of a student who initially answered A. Of course, the students who chose C should change their answer, just as when Monty Hall shows you a goat behind the door you picked, and asks you if you want to switch. In case that's too hard to figure, he could show you the car behind a door you didn't pick and ask you if you want to switch. Of course, MvS is still is ignoring the case where the host doesn't always give the contestant a chance to switch. Dan --- Newsgroups: microsoft.public.windowsupdate From: "Dan Hoey" Date: Sat, 2 Aug 2003 13:03:34 -0700 Subject: Re: Error Message when trying to update windows 98SE "PaulM" wrote: >"Ben" wrote... >> Error message )X800A01AD when checking for windows 98 >> Select Edition upgrades >Check this page > http://v4.windowsupdate.microsoft.com/troubleshoot/ I've got Ben's problem, too, and when I try to visit the troubleshoot page I get a popup: Line: 151 Char: 5 Error: Automation server can't create object Code: 0 URL: http://v4.windowsupdate.microsoft.com/troubleshoot/ and when I OK it there's nothing on the page. I've been trying Symantec's WinDoctor on this system, and there are some missing "ActiveX/COM subkeys" and some references to a missing file C:\Windows\System\MSXML3.DLL. I don't know if that's the problem. Is there a way to reinstall some part of the OS, like the ActiveX subsystem? Any other ideas? Dan Hoey haoyuep@aol.com --- Date: Tue, 12 Aug 2003 09:13:21 -0400 (EDT) From: Dan Hoey To: lkmitch@att.net, math-fun Subject: Re: [math-fun] Words Kerry writes: > There's a 540-word variation on the "A man, a plan, a canal--Panama." > palindrome here: > http://www.jy-muggeridge.freeserve.co.uk/pals_hoey.htm A more complete version of the story is at http://nielsenhayden.com/hoey.html and an interesting newer development at http://www.norvig.com/palindrome.html in case you're interested. Dan --- Date: Mon, 22 Sep 2003 19:00:58 -0400 (EDT) From: Dan Hoey To: John Conway Subject: Re: [math-fun] non-square products of squares? cc: math-fun cc: Marc LeBrun John Conway writes: > Let me ask for the smallest group in which two squares can > multiply to a non-square.... It's nice to see this. I was going to look with Gap, and your analysis helped convince me. > Therefore, the smallest groups in which squares can multiply to > a non-square are A4 and Q12; indeed, they are the only such > groups with order < 16 (and probably the only ones with order < 20, > since I don't believe there will be any of order 16). I found two such groups of order 16, but I haven't figured out what their names are. A presentation for the first is . Its squares are 1, b^2, and (a b)^2, and the product of the last two is not a square. The other group may be presented . Its squares are 1, a^2, b^2, and again the product of the two non-identity squares is not a square. > A much harder and more interesting problem is: what's the > largest probability we can attain? The largest among groups up to order 255 is 5/6, in a 192-element group. Gap calls it SmallGroup([192,1022]), but again I don't know a name for it. The smallest presentation I've found is where [x,y] means x y x^-1 y^-1. This is edged out by probability 27/32, in SmallGroup([384,572]), which I haven't looked at in detail. Dan --- Date: Tue, 23 Sep 2003 16:55:53 -0400 (EDT) From: Dan Hoey To: John Conway Subject: Re: [math-fun] non-square products of squares? cc: math-fun John Conway writes: > Exactly what are these the probabilities of? I was using > the probability that a given triple a,b,ab should be of form > square,square,nonsquare. Are yours the conditional probability > that ab should be a non-square GIVEN that a,b are squares? > [I mention that there is a third natural probability around, > namely the probability that a^2.b^2 should be a nonsquare.] I see! I first calculated the second probability, and saw that it wasn't what you were describing. Also, the denominators aren't as pretty, because they reflect the somewhat flukey number of squares. So I switched to the third, and since it agreed with your number (1/6) for A4 (and since I overlooked the 1/36 you got for Q12) I thought that was what you meant. So the numbers I reported were the probability that aabb is a nonsquare. Looking at the first probability I see it can't exceed min(s^2,1-s) where s is the density of squares--that's at most tau^-2 ~ .382, and it's even less because not every product of squares can be a nonsquare. Up to order 255, the only group that exceeds 1/6 is SmallGroup(48,50), or . It has a probability of 5/24 that a,b,ab are square,square,nonsquare. Dan --- Date: Wed, 24 Sep 2003 10:49:42 -0400 (EDT) From: Dan Hoey To: John Conway Subject: Re: [math-fun] non-square products of squares? cc: math-fun I wrote: > Up to order 255, the only group that exceeds 1/6 is > SmallGroup(48,50), or > = (a b a^-1 c)^2 = 1> . > It has a probability of 5/24 that a,b,ab are square,square,nonsquare. I looked at your classification of groups of order 16 and verified your translation of the smaller anonymous groups I found. In hopes of identifying this group, I found its derived subgroup 2^4 . Of course G/G' is C3. But the direct product C3 x 2^4 is not G. That seems similar to the case for A4: A4/C3 = 2^2 but 2^2x3 is not A4. Somehow I thought that was the way to decompose and reconstitute groups, but I guess I'm mistaken. As for identifying the group, I have checked that its order spectrum [1,15,32,0,...,0] is unique. Its center is 1. Dan --- Date: Wed, 24 Sep 2003 13:52:00 -0400 (EDT) From: Dan Hoey To: John Conway Subject: Re: [math-fun] non-square products of squares? cc: math-fun John Conway wrote: > On Wed, 24 Sep 2003, Dan Hoey wrote: > > I looked at your classification of groups of order 16 and verified > > your translation of the smaller anonymous groups I found. In hopes of > > identifying this group, I found its derived subgroup 2^4 . > This must be a typo for 2^2 ? No. I'm trying to describe the 48-element group with order spectrum [1,15,32,0,...,0]. Gap claims its derived subgroup (which it defines as the subgroup generated by the commutators) is the 16-element group with order spectrum [1,15,0,0]--that's 2^4. Could GAP be mistaken, or am I just spreading confusion? Thanks for explaining this stuff. I'm really in the dark about being able to describe the group I'm talking about. Dan --- Date: Wed, 24 Sep 2003 15:32:59 -0400 (EDT) From: Dan Hoey To: math-fun Subject: Re: [math-fun] distinguishing groups cc: Dylan Thurston Dylan Thurston wrote: > On Tue, Sep 23, 2003 at 11:43:33AM -0700, Richard Schroeppel wrote: > > Similar questions exist for graphs & other math objects. > The graph isomorphism problem is known to be NP-complete, so any sort of > properties that distinguish graphs is likely to be hard to compute. No, it isn't (unless I've missed a very surprising very recent breakthrough). It's a long-standing open problem. Because the graph isomorphism algorithms of unproven polynomiality are so good, it's conjectured that graph isomorphism is strictly easier than NP-complete (by people who are willing to conjecture that NP > P). Some people even conjecture it's P (even without conjecturing NP = P). You may be thinking of subgraph isomorphism, which is NPC, but there the hard part is finding the subgraph, not the isomorphism. (In the usual proof, the test graph is a complete graph, for which isomorphism is easy. > Is there a way of stating a finite-group-isomorphism problem so that it > is decideable? Is it then NP-complete? If you're given the multiplication table, it's certainly decidable. I suspect it's more likely to be polynomially related to graph isomorphism than NP-complete (but I haven't really worked on it). Dan --- Date: Wed, 24 Sep 2003 17:25:37 -0400 (EDT) From: Dan Hoey To: John Conway Subject: Re: [math-fun] distinguishing groups cc: math-fun John Conway wrote: > My feeling is that the methods we used could be converted into > a formal proof that one could distinguish between any two given > candidate groups of orders < N in a time bounded by some power > of log N. [Note that that's weaker than saying "find which group of order > < N you have".] But it's the former problem that Rich is taking N^O(logN) to solve! I suspect you're at least going to have to multiply that log N by the sum of the orders of the generators, in case someone gave you generators of two huge cyclic groups and asked you to test eqality with the black box multiplier. But even doing it in provably O(N^c) would be an advance. I suspect that's going to run into the same sort of problem graph isomorphism has. There are methods that work well on a lot of graphs, and combining them _seems_ to work well on all graphs, but we can't prove there isn't an exception. Dan --- Date: Fri, 26 Sep 2003 05:39:12 -0400 (EDT) From: Dan Hoey To: John Conway Subject: Re: [math-fun] non-square products of squares? cc: math-fun This really is fascinating. I've been trying to follow along with Gap, and I ran into a problem because it takes about five or ten minutes to find all the elements of Aut(2^4). I kept trying to figure out what was wrong, where if I waited I would have had it. So now I can calculate semidirect products 2^4:3[h], where h is a homomorphism from 3 to Aut(2^4), and there are the three you promised: The canonical 2^4:3, the direct product 2^4x3, and... well, one that's halfway in between. I don't know if it's worth giving it a special name. Anyway, I still haven't found any group with a greater proporition of (a,b,ab)=(square,square,nonsquare) than 1/6, except for the 5/24 we get from 2^4:3. In fact, the proportion seems to go down, so perhaps 2^4:3 is unique. I have no idea how one might prove it, though. Here's a poser that came up while I was writing the code to search for nonsquare products. Can it ever happen that (a,b,ab,ba)=(square,square,square,nonsquare)? I can prove it's impossible for finite groups, but what about infinite? Dan --- Date: Fri, 26 Sep 2003 09:52:51 -0400 (EDT) From: Dan Hoey To: math-fun Subject: Re; [math-fun] Kissing number (again). John Conway wrote: > The feeling that I'd expressed too strongly my criticisms of Jud > McCranie's proposed attack on the kissing number problem somehow > convinced me that they were wrong, and led me to apologise.... You know, I had been about to do something like that, too. I think it was all the "wolg'ing that was so irritating. A little "wolg" goes a long way, and after two "wolg"s and an "etc" I was about to "wolg" all over my keyboard. But looking closer, I think there's something correct in Jud's idea, perhaps new or perhaps not. It might even be possible to use it to (correctly) prove bounds on the r-kissing number (how many radius-r balls can kiss a unit ball in k dimensions) for which I'm sure there are plenty of open cases. First, let's try it without using symmetry or requiring any adjacencies of the balls (except, of course, to the central one). Quantitize the space of ball centers into small pieces p1,p2,...,pm. This could be done as coordinate-wise, so that each pi is the intersection of a dimension-k box with the (1+r)-sphere, or perhaps there is a better way of chopping up the space. A pair of pieces (pi,pj) is admissible if they contain respective points (xi,xj) at a distance of at least 2r. If that's too hard to test, admissiblity standards can be loosened. For instance, we could call (pi,pj) admissible if the underlying boxes contain an appropriate pair of points. We then exhaustively search for a set of n pieces that are pairwise admissible. If there is no such set, then the (r,k) kissing number is less than n. Of course, this doesn't prove the converse. But I think that if the kissing number is less than n, then there is a minimum overlap epsilon that will occur in any configuration of n spheres. If we require the pieces (or their boxes, in the loosened regime) to have dimension at most 2 epsilon, then the search for a pairwise adminssible subset will fail. This can be improved for efficiency. If n >= k I think that we can require each ball to kiss k-1 others in addition to the central one. If that's incorrect, we can at least require some adjacencies. This will allow us to require that adjacent balls be mapped to pieces that contain respective points (xi,xj) at a distance of exactly 2r. Other reductions of the search space are possible from symmetry. I imagine this method will be intractible in the interesting cases, but at least it's correct. Dan P.S. Thanks Hartmut and JHC for reminding me that conjugacy induces a homomorphism! --D[o]H --- Date: Fri, 26 Sep 2003 13:24:09 -0400 (EDT) From: Dan Hoey To: Jud McCranie Subject: Re: [math-fun] Kissing number (again). cc: math-fun > My 4-D intuition is certainly no good, so I was wondering if what seems > would work in 3D would carry over to 4D (about whether or not it is > sufficiently general for a ball to touch the maximum number of other > balls). But let me ask this about the "continuum", and I'll use the 3D > analogy. > Suppose you've got a few balls touching the central one and you're > finding the places where you can add another one. The simplest > approach would be to find all of the places where it touches the > central ball and two others, but that isn't sufficiently general. No, it isn't. Your problem is not geometry, it's logic. You can't assume that the new ball will touch more than one of the previously placed balls (and you can't even assume _that_ just by saying so, you have to prove it--see below). > Consider the new ball touching the center ball and is in contact > with ball A. You can't assume that. It might be in touch with just one of the previously-placed balls, and you can't even guarantee which one. > Swing it one way (staying in contact with ball A and the central > ball) until it touches ball B. But your "swinging" it is not general, because it might interfere with the further placement of other balls. If you interfere with future placements, your solution is not general, even in two dimensions. The way you can guarantee that each ball touches at least two others, one of them previously placed, is this way: Hypothesize a complete kissing arrangement of N>2 spheres. I will prove there is a connected kissing arrangement in which every ball touches at least two others, by modifying the given arrangement: 1. If the arrangement is not connected, you can move one connected component as a unit until it touches another ball. 2. If ball A touches only ball B, then ball B must touch some ball C (otherwise case 1 would hold). You can swing ball A around B until A hits some other ball-- perhaps not C, but some ball. This modification increases the number of adjacencies by 1, so if you repeat it as long as there is a ball touching fewer than two others, it will terminate in at most (n-1)(n-2)/2 + 2 steps, because with that many adjacencies every ball must touch at least two others, QED. This _allows_ you to search for arrangements by placing each new ball so it touches one previous ball somewhere. If you further restrict your choice. you invalidate the entire effort, since you might not find an arrangement even if one exists. I looked at trying to modify this for four dimensions, and I find that you can prove that every ball must touch at least two others. Same in K dimensions: every ball must touch at least two others. You might have all N balls in a loop, so you have to guess each ball but the first, second, and last with K-1 degrees of freedom. You can't do better with "geometric intuition". John was right, of course. Dan --- Date: Fri, 26 Sep 2003 13:59:05 -0400 (EDT) From: Dan Hoey To: Jud McCranie Subject: Re: [math-fun] Kissing number (again). cc: math-fun Oops! I wrote: > Jud McCranie wrote: > > Consider the new ball touching the center ball and is in contact > > with ball A. > You can't assume that. It might be in touch with just one of the > previously-placed balls, and you can't even guarantee which one. I'm sorry, I misread "center ball" as one of the ones you placed. You can indeed choose the new ball so it is touching the kissed ball and one previously placed ball A. But to do even that, you have to prove at least part of the theorem from my last message. > > Swing it one way (staying in contact with ball A and the central > > ball) until it touches ball B. Swing it the other way until it > > touches ball C. Now would it be the case that only certain areas > > in that swing need to be considered? Would it be that, say, any > > position from 0 to 0.1x is essentially the same because it makes > > no essential difference in how the rest of the balls are placed, > > and 0.1x to 0.36x are essentially the same, etc? If so, that > > would be how it can be reduced to a finite number of cases. You really do have to consider the whole arc. There is a way to make the number of cases finite, and that is to say, "The new ball G is at some unspecified place on this epsilon-arc." You can't say that it makes "no essential difference" where it is, but you can say the difference it makes is no greater than the diameter of the set of places it could be. In the future, when you're "swinging a newer ball around G," you will have to take account of not really knowing where you placed G, so the space of possible tangencies to G has positive area, and you have to say "some unspecified place in this epsilon-patch" instead of "along this epsilon-arc". And at the end, you won't usually have a packing, because you have to overpack to take account of the uncertainties. All you can say is that, if you end up with a sufficiently great amount of overpacking, that there couldn't have been a packing of that many balls in the first place. Dan --- Date: Fri, 26 Sep 2003 18:32:31 -0400 (EDT) From: Dan Hoey To: John Conway Subject: [math-fun] Re: [math-fun] non-square products of squares? cc: math-fun John Conway writes: > Since the two best examples are A(4) = 2^2 : 3 and 2^4 : 3 > it would seem that 2^6 : 3 deserves examination. Let me try > to do that now (despite the fact that I have to lecture in a few > minutes). > ... I presume 7/32 beats 5/24, but don't have time to check. Well, of course it does. It seems that 2^6:3 is SmallGroup(192,1541), and yes, it has a s.s=n density of 5/32. I haven't got a way of forming the semidirect product os something that large yet. And pretty much by luck, scanning the 1090235 groups of order 768 from the highest numbered down, the first one that had a derived subgroup of 2^8 was SmallGroup(768,1085321), and it's got a s.s=n density of 85/384 . Assuming that group is 2^8:3, we've got density of 2(1-2^-k)/9 in 2^k:3 for 0(?),2,4,6,8 . I didn't find anything over 1/6 in groups of size 80 or 448. I couldn't check 320. Dan --- Date: Mon, 29 Sep 2003 11:24:25 -0400 (EDT) From: Dan Hoey To: math-fun Subject: Re: [math-fun] More on sphere packing "Allan C. Wechsler" wrote (of Jud McCranie's conceptual program in four dimensions): > The central problem is the size of the configuration space that must > be explored: 24 or 25 spheres jostling around, each contributing 3 > degrees of freedom to the configuration space. JM proposed, if I > read him right, to prune this space by considering only > configurations of a certain special kind, in which the configuration > may be built by adding each new sphere in the 'socket' formed by > three previously-placed spheres. (This is hard to visualize, but in > four-space, you need three other spheres to form a well-defined > socket with no degrees of freedom.) Enumerating such configurations > would be much easier than searching an enormous 75-dimensional > configuration space. It may be that Jud made such a proposal, but I am sure he no longer believes it to be proved correct. In fact, I suspect he may have proposed a somewhat less dubious proposal that was misunderstood. The problem arises from confusion over whether we are counting the original unit 3-sphere (in which case we would say four hyperspheres are required to form a socket in R^4) and over whether we are talking about packing in R^3 (using ordinary 2-spheres) or in R^4 (with 3-spheres). (In addition, I think there is some confusion about this nomenclature--I understand the surface of a ball in R^4 to be called a "3-sphere", but Allan calls them 4-spheres, so we can be sure confusion abounds.) I know that some of my respnoses were based on confusion over whether a given description includes the original unit sphere. At any rate, I believe we will do better to pack _points_ on the unit k-1-sphere (in R^k) with a prescribed lower bound r on the distance between points. This translates directly into the packing of kissing k-1-spheres of radius r/(2-r), if I've done my algebra correctly. At any rate, I would like to mention a modification to the approach I outlined on Friday. In this approach we place points in k-cells of side epsilon that intersect the given k-1-sphere. I will assign a point a "nominal location" of the center of its cell. However, since the point may differ from that location by epsilon.sqrt(k)/2, we must enforce a separation of points by r + epsilon.sqrt(k). In addition, since we require that each point be at the minimum distance to at least two neighbors, we count those points within r - epsilon.sqrt(k) of the given point toward the count of required near neighbors. Now, searching for these points with approximately n(k-1)-k(k-1)/2 degrees of freedom may be fairly intractible, but we may get some relief from the minimum and maximum spacings where the packing is tight. I was concerned that this relief might happen too far down the search tree to be helpful, and I would like to share an idea that might help make the relief more generally available. The idea is basically to start with a large epsilon, and to go to epsilon/2 by cutting all the cells in 2^k pieces. Most of the pieces go away (because they no longer intersect the k-1-sphere), and the reduced epsilon should also prune the cases. As epsilon is reduced, the configuration becomes more and more constrained, and we may be able to identify places where the constraints are loose. I imagine the looser spheres might in fact not need to have their cells cut as much after a certain point. This leads to a sort of quad-tree approach to the search space. I'm curious about how this approach might work (or how it may have worked already, since it's a fairly standard approach to geometrical searching). I remark that it not could not only tell us which (n,k,r) are not feasible, but it could provide witnesses for which (n,k,r-epsilon.sqrt(k)) are feasible. Dan --- Date: Mon, 29 Sep 2003 14:29:25 -0400 (EDT) From: Dan Hoey To: John Conway Subject: Re: [math-fun] More on sphere packing cc: math-fun I'm quite sorry that I do seem to have gotten the signs on my epsilons backwards. The relevant paragraph should have read: > At any rate, I would like to mention a modification to the approach I > outlined on Friday. In this approach we place points in k-cells of > side epsilon that intersect the given k-1-sphere. I will assign a > point a "nominal location" of the center of its cell. However, since > the point may differ from that location by epsilon.sqrt(k)/2, we > must enforce a separation of points by r - epsilon.sqrt(k). In > addition, since we require that each point be at the minimum distance > to at least two neighbors, we count those points within > r + epsilon.sqrt(k) of the given point toward the count of required > near neighbors. The output of the program would be: 1. If there is an (n,k,r) configuration, to find (n,k,r-eps.sqrt(k)) configurations for arbitrarily small eps, and 2. I there is no (n,k,r) configuration, to prove it by running out of cases when eps < (r-maxr(n,k))/sqrt(k) . Here maxr(n,k) is the maximum r' for which an (n,k,r') configuration exists. Perhaps case 1 would usually be faster with Gosset, but as I understand it Gosset might fail to find a configuration even when one exists. Dan --- Date: Mon, 29 Sep 2003 16:15:27 -0400 (EDT) From: Dan Hoey To: John Conway Subject: Re: [math-fun] More on sphere packing cc: math-fun@mailman.xmission.com John Conway wrote: > I didn't read the piece I snipped, but presume that it is supposed > to guarantee to find (in particular) a 25-sphere configuration in 4D if > one exists. I can't really see how it can do that, while still being > approximate. Do you think it can? No, of course not. Why would you presume I attempt such a guarantee, when it is patently impossible? I claim that if there are no (25,4,1+2epsilon) configurations, the algorithm would say so. This is important, because if there are no (25,4,1) configurations, there must be an epsilon for which there are no (25,4,1+2epsilon) configurations. I also claim that every (25,4,1) configuration is represented in the output by an approximation that describes the coordinates of the centers to within epsilon. Each of these can be converted to a (25,4,1-2epsilon) configuration. Dan --- Date: Mon, 29 Sep 2003 16:36:14 -0400 (EDT) From: Dan Hoey To: John Conway Subject: Re: [math-fun] More on sphere packing cc: math-fun@mailman.xmission.com I wrote: > Why would you presume I attempt such a guarantee, > when it is patently impossible? Possibly because about half of what I say has errors in it, including my latest attempt. What I meant to say was summed up correctly by Andy Latto. Dan --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 09 Oct 2003 01:05:20 GMT Subject: Re: ab... = (a*b*...)^n ? Dave Rusin wrote: > In Maple: > dp:=proc(i, B) if i < B then i > else (i mod B)*dp((i - (i mod B))/B, B) fi:end: > B:=3:k:=4: # for example > for i from B to B^k-1 do pr:=dp(i,B):if pr>1 then > n:=round(evalf(log(i)/log(pr))):if i=pr^n then lprint(i,pr,n):fi:fi:od: You get a lot further by examining only those numbers whose prime factors are less than B. I did some of this and got a number of examples. Some of the longer ones: Base 5: 212323421441324231_5 = 1761205026816 = 1327104^2 Base 6: 411412_6 = 32768 = 32^3 Base 7: 523251_7 = 90000 = 300^2 Base 11: 118239_11 = 186624 = 432^2 Base 16: b73351_16 = 12006225 = 3465^2 Base 17: 1cce112423bf2_17 = 1019744590233600 = 31933440^2 Base 24: 122n2g_24 = 8667136 = 2944^2 Still nothing in base 10 up to 10^200. But if we allow rational exponents, there are more possibilities. Base 3: 1122221122_3 = 32768 = 64^5/2 Base 5: 224_5 = 64 = 16^3/2 Base 6: 4424_6 = 1024 = 128^10/7 Base 9: 12212_9 = 8192 = 8^13/3 24424_9 = 16384 = 256^7/4 48848_9 = 32768 = 8192^15/13 Base 10: 128_10 = 128 = 16^7/4 Base 12: 1228_12 = 2048 = 32^11/5 Base 14: 288_14 = 512 = 128^9/7 Base 15: 2585_15 = 8000 = 400^3/2 319c9_15 = 157464 = 2916^3/2 Base 18: 777_18 = 2401 = 343^4/3 Base 19: g26c_19 = 110592 = 2304^3/2 Base 22: 16c8_22 = 13824 = 576^3/2 6l1e_22 = 74088 = 1764^3/2 Base 26: 3993_26 = 59049 = 729^5/3 The example in base 3 is instructive--I believe the proposition that every power of 2 greater than 2^15 has zeroes in its base-3 representation is an open conjecture. Dan Hoey haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 11 Oct 2003 04:41:34 GMT Subject: Re: ab... = (a*b*...)^n ? Subj: Re: ab... = (a*b*...)^n ? Date: 10/10/03 1:13:34 PM Eastern Daylight Time From: Hoey@aic.nrl.navy.mil (Dan Hoey) To: haoyuep@aol.com "r.e.s." wrote: > "Dan Hoey" wrote ... > > You get a lot further by examining only those > > numbers whose prime factors are less than B. > > Still nothing in base 10 up to 10^200. > Would you describe further how you did that? ... The basic idea is to generate all numbers whose prime factors are less than B. I initialize a set S={1}. I repeatedly remove the smallest element e from S and for each prime p < B I insert the product e p into S. This is especially fast if S is implemented as a priority queue (see Knuth v3). An optimization to avoid inserting any element twice is to insert only products e p such that p is the smallest prime factor of e p. A further optimization for composite B is to avoid inserting any product e p that is a multiple of B, since that number and its multiples have zeroes in their base-B expansions. > Obviously, you didn't test each number to see > whether its prime factors were less than 10, .... If there are k primes less than B, there are only O(n^k) elements to process below B^n. If B is composite, the second optimization reduces this to O(n^(k-1)). Either of these is vastly smaller than B^n. Dan Hoey haoyuep@aol.com --- Date: Thu, 16 Oct 2003 11:00:53 -0400 (EDT) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: [math-fun] Re: Poincare Conjecture "Jon Perry" writes: > Thanks - I can see the weaknesses in my argument. Very good, if true. > However, is there anything wrong with this; > PC is true because from the 3-sphere, a compact, simply connected > manifold, through only operations which preserve homeomorphicity, we > can attain every other compact, simply-connected 3-manifold. Yes, there's something wrong with that. Any statement of the form "PC is true because " is hogwash. If you were going to prove PC, you would need more than a sentence to express a convincing proof. It might be accurate to say "If I could prove , that would imply PC". That depends on the sentence, of course. If you ever convinced someone that you might have a proof of PC, then it might be appropriate to say something of the form, "I have proved , and that implies PC." But you made the statement in the hogwash form. Moreover, you made that statement in reply to a message that shows that you not only did not present a realistic approach to a proof of PC, but were apparently unclear on the concept of what a proof of PC would be, and that you were beginning to sound like a crank. I hope your statement is not a proof, because it certainly isn't a proof of the Poincare conjecture. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: rec.puzzles From: haoyuep@aol.com (Dan Hoey) Date: 19 Oct 2003 01:48:38 GMT Subject: Re: That's a switch! Carl G. wrote: > Most newsgroup members are acquainted with the classic > puzzle where a farmer needs to transport a goat, a cabbage, > and a wolf across a river. He can only transport two items at a > time, and can't leave the goat alone with the wolf, or the > goat alone with the cabbage. Assume that you lived before the > days of modern electronics and computers, and wanted to make > a device that simulated the classic puzzle. Your design > consists of a box with four toggle switches and a light bulb. > Each toggle switch represents one of the objects in the puzzle > (the farmer, the goat, the cabbage, the wolf). The direction > that the toggle switches are flipped represent which side of > the river the object is on (left or right). The light bulb > should turn on whenever (and only when) there is a "danger" > situation (e.g., the goat is left alone with the wolf). You > have three single-pole double-throw (SPDT) switches and one > double-pole double-throw (DPDT) switch. You also have a > battery (of the right voltage for the light bulb) and some > wire. How would you wire the toggle switches, light bulb, and > battery, together so that your device properly simulates the > puzzle? The wire can only be used to connect together the > other components. I found three circuits (up to certain symmetries), which I write in terms of modules: Series(Equal(Rev(F1),Or(C,W)), Equal(Rev(F2),G), L) Series(Equal(Cascade(Or(C,W),Rev(F1),Rev(F2)),G), L) Series(Equal(Cascade(G,Rev(F1),Rev(F2)),Or(C,W)), L) where F1, F2 are the two poles of the farmer switch, C, G, and W are the cargo switches, and L is the lamp. I define modules as follows: Series(x,y) = Series.1-x.1, x.2-y.1, y.2-Series.2; Equal(x,y) = Equal.1-x.C, x.L-y.L, x.R-y.R, y.C-Equal.2; Rev(x) = Rev.C-x.C, Rev.L-x.R, Rev.R-x.L; Or(x,y) = Or.C-x.C-y.C, Or.L-x.L-y.L, Or.R-x.R-y.R; Cascade(x,y1,y2) = Cascade.C-x.C, x.L-y1.C, x.R-y2.C, y1.L-Cascade.L, y2.R-Cascade.R; Where the terminals of a switch S are labeled S.C, S.L, S.R and the terminals of a circuit T are labeled T.1, T.2. Connections are signified with hyphens. The "Series" module is extended to more than two arguments by associativity. The symmetries that I know can be applied to the problem are: 1. Submodules of a Series can be rearranged. This is also true of Equal, Rev, Or, and the last two submodules of Cascade, but I don't think these actually change anything. 2. Any circuit can be put in Backward ( Backward(x) = Backward.1-x.2, x.1-Backward.2; ). 3. Equal can be rewired as Equal(x,y) = Equal.1-x.L-y.R, x.C-y.C, x.R-y.L-Equal.2; in some or all positions. At first I thought this only worked when no submodule was an Or, but that restriction turns out to be unnecessary. 4. C and W can be interchanged (though I don't think this actually creates any new circuits). 5. F1 and F2 can be swapped. 6. G, F1, F2 can be replaced with Rev(F), Rev(G1), Rev(G2), respectively, where F represents the farmer and G1, G2 are the two poles of the goat switch. 7. All switches can be Reversed, though I don't think there are any new circuits this creates. I'd like to know if any other circuits can solve this problem. I've been tempted to try exhaustive search, but I haven't figured out how to cut the search space down to a reasonable size. Dan Hoey haoyuep@aol.com --- Newsgroups: rec.puzzles From: haoyuep@aol.com (Dan Hoey) Date: 26 Oct 2003 03:34:09 GMT Subject: Re: R = PI ohms "Martin Round" nos...@blueyonder.co.uk wrote: > "Daniel W. Johnson" wrote: > > A requirement to use all the resistors would not > > actually be interesting.[...] > True. I suppose you could say, 'current must flow in each > of the resistors', but that's a bit contrived. Less contrived would be "no resistors can have their ends wired together" (along with the expected "both ends of each resistor must be connected to both terminals through a path not including that resistor"). > Anyway, as expected, 10 resistors can do better than > 9. I'm not sure if what follows is the best solution, > but it's the best one I've found yet. I get 524935/167092, for an error of 1.95e-9. > By the way, what method did you use to work out the exact > resistance, expressed as two integers? I've done it using > simultaneous equations, but is there an easier way? > Matrices perhaps? Presumably you know the formulas for parallel and series circuits. Just one more formula is necessary for the circuits we've seen so far: the "delta-Y" formula. In any circuit in which resistors of value 1/Yab, 1/Ybc, 1/Yca appear between nodes a and b, b and c, and c and a, respectively, we may remove those resistors and replace them with a new node and resistors of value 1/Ya, 1/Yb, 1/Yc between the new node and nodes a, b, and c, respectively, where Ya = (Yab Ybc + Ybc Yca + Yca Yab) / Ybc, etc. This transform can be inverted with the Y-delta transform Yab = Ya Yb / (Ya + Yb + Yc), etc. If you have a circuit without triangles, this won't help you. There is a star-clique transform that will turn any circuit into a nest of resistors, but at this point it might be as well to invoke a theorem of Kirkhoff: Define the conductance of a subgraph to be the product of the conductances (1/resistances) of its edges. Then the resistance of the network between nodes A and B is the quotient of the sum of the conductances of all spanning trees of the network divided by the sum of the conductances of all subgraphs that would become spanning trees if supplemented by an edge AB. I have only seen this theorem quoted without proof, so I can't answer a lot about it. Still, this should be in textbooks if you know where to look. Dan Hoey haoyuep@aol.com --- Date: Mon, 27 Oct 2003 15:56:05 -0500 (EST) From: Dan Hoey To: John Conway Subject: Re: [math-fun] cyclic quadrilaterals cc: math-fun John Conway writes: > ... Alternatively, let AEPF be any circle through A and P, and > then BFPD and CEPD be the circumcircles of BFP and CEP > (which will automatically intersect at a point D on BC). > This is all part of "the Miquel theory" of the triangle. JHC By considering the point at infinity, I understand this to mean that if we have points 01234567 in cocircular quartets 0123, 4567, 0145, 2367, and 0246, then quartet 1357 must also be cocircular. I didn't know that. Are all such patterns known? Say, given a mapping of a hypergraph to the plane, where vertices are mapped to points, and the images of the vertices of each hyperedge are cocircular, can we tell what other subsets of vertices are forced to map to cocircular points? Dan --- Date: Mon, 27 Oct 2003 17:06:29 -0500 (EST) From: Dan Hoey To: Eugene Salamin Subject: Re: [math-fun] RE: Prentice Hall strikes again cc: math-fun Eugene Salamin maunders again: > What is needed to to do away with the obstacles to free choice. What is needed is to do away with that obstacle to the discussion of mathematics. Does he really think repetition of this rant is going to sell anyone on it? Dan --- Newsgroups: rec.puzzles From: haoyuep@aol.com (Dan Hoey) Date: 28 Oct 2003 03:29:33 GMT Subject: Re: R = PI ohms I wrote: > Less contrived would be "no resistors can have their ends > wired together" (along with the expected "both ends of each > resistor must be connected to both terminals through a path > not including that resistor"). and Phil Carmody correctly observes that this still allows us to throw away a pair of resistors wired in parallel to an isolated node. I now believe the right criterion is for the graph of resistances (plus an edge for the source-to-sink circuitry) to be _biconnected_, which means that the removal of any one node will not result in a disconnected graph. This implies all the previous criteria except the bogus one that prohibits a resistor that fails to pass any current due to the values of the resistances rather than the topology of the graph. In addition, I should mention that I've re-derived the star- clique rule, which allows us to remove any internal node of the graph. If internal node x is connected by conductances y_i to nodes n_i, we may remove x and the y_i and replace them with conductances y_ij = y_j y_k / (sum_i y_i) between each pair of nodes n_i, n_j. Proof: Suppose in the original network that nodes n_i are at voltages v_i, and x is at voltage v. By Kirkhoff's law, 0 = sum_i (v - v_i) y_i = (v sum_i y_i) - (sum_i v_i y_i), so v = (sum_i v_i y_i)/(sum_i y_i). The current out of node n_k will be y_k (v_k - v). In the proposed network, if the nodes n_i are at voltages v_i, then the current out of n_k will be sum_j (v_k - v_j) y_jk = sum_j (v_k - v_j) y_j y_k / (sum_i y_i) = y_k (sum_j (v_k - v_j) y_j) / (sum_i y_i) = y_k ( (sum_j v_k y_j)/(sum_i y_i) - (sum_j v_j y_j)/(sum_i y_i) ) = y_k (v_k - v), which is the same as the current out of n_k in the original network. By uniqueness of the solution to any network, this implies that the voltages and currents will be preserved in the resulting network, QED. This allows us to remove the internal nodes one by one, which should be reasonably efficient if we collapse parallel conductances after each removal. The resemblance of this procedure to Gaussian elimination reminds me of that of Persian Monarchs to Blind Hookey. Dan Hoey haoyuep@aol.com --- Date: Tue, 28 Oct 2003 12:28:17 -0500 (EST) From: Dan Hoey To: Richard Guy Subject: Re: [math-fun] The Pythagorean Comma cc: math-fun@mailman.xmission.com Richard Guy writes: > It IS known by some mathematicians. See p.257 > of The Book of Numbers. But, lack-a-day, we > define it as `the difference between 7 fifths > and 4 octaves' whereas it should be `12 and 7'. According to Margo Schulter's believable-sounding Usenet post (citing Boethius's _De Institutione Musica_ as translated by Calvin Bower in _Fundamentals of Music_), 2^8:3^5 is a limma or diesis or Pythagorean minor semitone, 3^7:2^11 is an apotome, 3^12:2^19 is the Pythagorean comma, 3^6:2^9.5 is a schisma, and 2^4:3^2.5 is a diaschisma. Dan Hoey@AIC.NRL.Navy.Mil --- Date: Wed, 29 Oct 2003 17:28:31 -0500 (EST) From: Dan Hoey To: "'math-fun'" Subject: RE: [math-fun] Simple EF > > > This may be completely dumb, but is it always possible to > > > solve x/y = a/b + c/d, where all algebraic quantities are > > > positive integers, for all x and y? How can we make this not completely dumb? Given that x,y are positive and relatively prime, can you give formulas for a,b,c,d that guarantee that all are positive and that (a,b)=(c,d)=1? Hmm, still pretty dumb. Suppose we also require that a,b,c,d are four different positive integers? I've gotten b and d different, but I haven't managed all four. In case that's still dumb, can all of a,b,c,d be made relatively prime in pairs? Dan --- Date: Mon, 10 Nov 2003 16:25:00 -0500 (EST) From: Dan Hoey To: math-fun@mailman.xmission.com, "N. J. A. Sloane" Subject: Re: Subject: [math-fun] 15-puzzle NJAS wrote: > I'm surprised that the 4x4 case hasn't been solved - can anyone help? The fifteen puzzle is quite a bit harder than the Rubik's cube kind of puzzle, because it's not a group. The set of moves from a given position depend on where the blank is. Also, there is only two-fold symmetry to the puzzle, except in the variant where the home position of the blank is the center. There is also a variant in which sliding a row of tiles counts as a single move. I wrote a simple program to find the results for the eight-puzzle in all these variants (fancy search techniques are unnecessary for this size of problem). The answers I get are: Move Blank Maximum Number of maximal-distance positions and slide home distance (position of blank in those positions) tile corner 31 2 (adjacent edge) tile edge 31 2 (adjacent corner) tile center 30 148 (88 corner, 60 center) row corner 24 1 (center) row edge 24 2 (diagonally adjacent edge) row center 24 4 (corner) By the way, 16!/2 milliseconds is "only" about 331.5 years, and I'd guess the time taken to examine a position is probably more like a few dozen microseconds than a millisecond. But it's still cpu-years. Dan --- Date: Mon, 17 Nov 2003 14:38:46 -0500 (EST) From: Dan Hoey To: "wouter meeussen" , "math-fun" Subject: [math-fun] Re: powers of PseudoAntisymmetric (-1,0,1)- Matrices "wouter meeussen" writes: > One counter-example to spoil things a bit: What is this a counterexample of? > for n=7, a small sample of (-1,0,1)-matrices whose powers are > 'same', shows that not all are pseudo-Antisymmetric (= AntiSymmetric > + Diagonal) What about [ 0 1 ] [ 1 0 ] ? Isn't that a non-PA (-1,0,1)-matrix whose powers are PA (-1,0,1)-matrices? But the (powerlength = divisor of 12) remains valid. That's not true of the permutation matrix [ 0 1 0 0 0 ] [ 0 0 1 0 0 ] [ 0 0 0 1 0 ] [ 0 0 0 0 1 ] [ 1 0 0 0 0 ]. Earlier, you wrote > > Consider > > the (-1,0,1)-matrices T with properties : Det[T] not zero > > (invertible), all powers T^k are also invertible (-1,0,1) matrices. > > Properties: > > powerlength of T divides 12, > > Det[t] is 1 or -1, > > T is pseudoAntisymmetric, What are you asserting or conjecturing about those matrices and those properties? By the way, a more standard term for "powerlength" would be "order", or "multiplicative order" if you use the word "order" for some other property. Certainly any matrix of finite multiplicative order must have unit determinant, but I can't see any other likely conjecture. Dan --- Newsgroups: geometry.puzzles From: haoyuep@aol.com (Dan Hoey) Date: Mon, 15 Dec 2003 21:57:31 +0000 (UTC) Subject: Re: Volume of a Tetrahedron Jo Drom writes: > I need to how to find the Volume of a regular tetrahedron. > I have looked into many sites on this and haven't found one > I can understand. I attend seventh grade and have a basic > knowledge of algebra. I can barely grasp sine cosine and > tangent so please leave trigonometric functions at the door > if you can. First, let's consider tetrahedrons as a kind of generalized cone. For any plane figure B and any point P not in the same plane as B, consider the set of all points that are on a line segment from P to some point of B. We call this "the cone with base B and apex P", or C(B,P) for short. Usually when people talk about cones they mean "right circular cones", where B is a circular disc and P is on the perpendicular through the center of B, but it's convenient to think of these other things as cones. What is the volume of a cone? A triangle is a kind of two-dimensional cone, and the area of a triangle is proportional to the length of the base times the altitude. So we might expect that the volume of a cone will be proportional to the area of the base times the altitude, and that is indeed the case. There may be a way for you to show this without calculus, but it may be messy. Granting that, what is the constant of proportionality? Consider a unit cube, let one of the vertices be P, and let B1, B2, and B3 be the faces of the cube that don't touch P. The cube is the union of C(B1,P) U C(B2,P) U C(B3,P), so the constant must be 1/3, and so we have he formula Volume of C(B,P) = 1/3 times Area of B times Altitude of P . Now to get the volume of a regular tetrahedron, you need to know the area of its base (a regular triangle) and the altitude of the apex. You can get the altitude of the triangle from the Pythagorean formula, and that will give you the area of the base triangle. The altitude of the tetrahedron is the distance from the center of the base triangle to the apex. You can also get that from the Pythagorean formula once you know the distance from the center of the base to a vertex of the base. You can find that distance in various ways, but as long as we are dealing with areas and volumes, consider that . A /:\ / : \ / : \ / .O \ / .-':`-. \ B /-'___:___`-\ C F in an equilateral triangle ABC, triangles AOB, BOC, and COA are congruent, so they have have the same area. What does that say about the altitude OF of BOC compared to the altitude AF of ABC? I hope you enjoy this excursion. Dan Hoey haoyuep@aol.com --- Date: Tue, 16 Dec 2003 17:21:49 -0500 (EST) From: Dan Hoey To: Chris Landauer Subject: Re: [math-fun] convex lattice 11-gon of minimum area cc: math-fun@mailman.xmission.com cc: sfinch9@hotmail.com Chris Landauer wrote: [...] > Now the program just uses a simple radius bounded backtracking > search for the points in the polygon, with some special processing > near the end. Once the area of the polygon determined by the current set of points exceeds your bound, you can cut off the search. Perhaps it's obvious that you already do this, since you can run the search at all. How about this: Start by picking the vertex V most distant from the origin. All convex polygons with area A and including {O, V} must lie between the two lines parallel to OV at a distance of 2A/|V|. That will probably be only about 4A points. I'm trying to figure out what to do with SL(2,Z). Suppose all points of the polygon lie within a rectangle M1 <= x <= M2 and 0 <= y <= N <= M2-M1. Under what circumstances will the map (x,y) -> x-y,y) or (x,y) -> (x+y,y) reduce the value of M2-M1? If M2-M1 goes below N, we can transpose and try again. Can this be made to map to a polygon with a small radius bound? What gets me is that Jamie Simpson apparently proved that the minimum must be at least 39/2. Is this something that can be pushed with computation? Dan --- Newsgroups: geometry.puzzles From: haoyuep@aol.com (Dan Hoey) Date: Wed, 17 Dec 2003 22:30:51 +0000 (UTC) Subject: Re: Volume of a Tetrahedron John Conway wrote: > I'm a bit surprised that nobody has yet mentioned the > formula found by Cayley, and later independently by Menger > (and rediscovered by me, as a schoolboy), for the volume of > an arbitrary tetrahedron. It is > | 0 aa bb cc 1 | > |aa 0 CC BB 1 | > det |bb CC 0 AA 1 | / 144 > |cc BB AA 0 1 | > | 1 1 1 1 0 | > where a,b,c are the lengths of the three edges at some > vertex, and A,B,C the lengths of those opposite to them. > I hope I'm remembering this correctly - will someone > please check? It generalizes in a fairly obvious way > to all dimensions. You've got the matrix right, but its determinant is 288 V V, not 144 V. Dan --- Date: Fri, 19 Dec 2003 11:16:07 -0500 (EST) From: Dan Hoey To: math-fun Subject: Re: [math-fun] convex lattice 11-gon of minimum area Here's a better search cutoff than the area bound, though I still don't see how to make the search finite. Theorem: Any convex lattice N-gon that contains K collinear lattice points (x,y), (x+a,y+b), (x+2a,y+2b), ..., (x+(K-1)a,y+(K-1)b) has area at least (K-1)(ceiling(N/2)-1)/2. The proof relies on two lemmas that probably have better proofs than these: Lemma 1: If a and b are relatively prime integers, not both zero, then the lines through lattice points in the direction of the vector (a,b) are at a distance of 1/sqrt(a^2+b^2) from each other. Proof: Take a square WXYZ with no lattice points on its boundary and with WX a translate of the vector (a,b). Every line parallel to WX passing through WXYZ that touches any lattice point must touch exactly one lattice point in WXYZ. There are a^2+b^2 lattice points in WXYZ, so that many lines, with a total separation of sqrt(a^2+b^2), so the separation between any two is 1/sqrt(a^2+b^2) QED. Lemma 2: Suppose a convex plane figure meets parallel lines R,S,T such that the intersection with line R is a line segment of length X, and lines S and T are at a distance of Y from each other. Then the area of the figure is at least XY/2. Proof: Let the intersection with line R be segment AB, and let C,D be points in the figure on S,T respectively. Then by convexity the figure contains triangles ABC and ABD. If R lies between S and T then the triangles are disjoint and have total area XY/2. If R is outside S and T then the larger triangle has total area greater than XY/2 QED. Proof of theorem: Suppose the convex lattice N-gon contains K collinear lattice points on a line parallel to vector (a,b), with a,b relatively prime, not both zero. Consider the lattice lines parallel to vector (a,b) that meet vertices of the N-gon. Since no more than two vertices lie on any line, there are at least ceiling(N/2) such lines. By Lemma 1, two of the lines must be at least (ceiling(N/2)-1)/sqrt(a^2+b^2) apart. Furthermore, the line containing the K collinear lattice points meets the N-gon in a segment at least (K-1)sqrt(a^2+b^2) long. By Lemma 2, the N-gon has an area of at least (K-1)(ceiling(N/2)-1)/2 QED. In searching for an 11-gon of area less than 21.5, we can then rule out any line of 9 collinear lattice points. Furthermore, once we have two vertices X,Y of the polygon, lattice points ruled out by applying the theorem to X will shadow other points from Y, which will be ruled out by convexity, and those points may cast shadows from X, and so on. Furthermore, any P for which the triangle PXY contains a prohibited point will then be prohibited. If we can surround the partial polygon with a ring of points that are angularly close, this will reduce the problem to finitely many cases of choosing vertices from finite sets. Unfortunately, I suspect this not is enough to make the whole problem finite. Using Dylan's observation, it looks like we still have infinitely many points to choose from for the third vertex (though I haven't worked it out in detail). Still, we may be closing in on a final answer to the problem. Dan ---