Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 8 Jan 91 15:08:11 GMT Subject: An old Math Magazine problem (was Re: A mysterious shell script.) s...@Lise.Unit.NO (Stig Hemmer) writes: >So it does. The earlier post asked the following question: (paraphrased) >'Given a start number X_0, make the sequence X_1=f(X_0), X_2=f(X_1) etc. > Will two such sequences (from different starting numbers) always merge?' Where f(x) was described as the sum of all the factors of x, including 1 and x. This function is usually called sigma(x). Unfortunately, Stig misparaphrases the previous article, in which amb...@acf5.NYU.EDU ([garbled] Balamurali Ambati) asked >This is an old Mathematics Magazine Problem from ~ 15 years ago. In >a sequence of positive integers, N_{k+1} = N_k + the sum of all the >distinct prime factors of N_k including 1 and N_k, k=0,1,2,... Or, if we standardize the nomenclature, N_k plus the sum of the distinct prime factors of N_k, including N_k if prime, plus the non-prime 1. Unfortunately, Ambati continues >Such a sequence is 1,2,3,4,7,8,11,12,18,24,... The sequence >5,6,12,18,... merges with the first sequence as do all sequences >with N_0 < 91. In which it is clear that N_{k+1} is taken to be N_k plus the sum of the distinct prime factors of N_k, excluding N_k if prime, plus the non-prime 1. I do not know which sequence appeared in the Math Magazine problem. If anyone looks it up, please let me know. Dan Hoey Hoey@Zogwarg.ETL.Army.Mil --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 10 Jan 91 18:23:01 GMT Subject: Re: Numbers from 1 to 1,000,000 (corrected) je...@essex.ac.uk (Reid J) writes: >If p(n) is the number of zeros used in the range 1 - 10^n >then > p(n) = p(n-1) + 9 * 10^(n-2) + 1 for n > 1 and p(1) = 1 >(Note I haven't prooved [sic] this yet....) Wrong, presumably from carelessness rather than misunderstanding, and don't think I'm throwing any stones. In the numbers from 10^(n-1) through 10^n - 1, there are 9 * 10^(n-1) numbers of n digits each, so 9(n-1)10^(n-1) non-leading digits, of which one tenth, or 9(n-1)10^(n-2), are zeroes. When we change the range to 10^(n-1) + 1 through 10^n, we remove 10^(n-1) and put in 10^n, gaining one zero, so p(n) = p(n-1) + 9(n-1)10^(n-2) + 1 with p(1)=1. Solving the recurrence yields the closed form p(n) = n(10^(n-1)+1) - (10^n-1)/9. Dan --- Newsgroups: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 15 Jan 91 17:25:48 GMT Subject: The Dodecahedron and the Bugs wcw07...@uxa.cso.uiuc.edu (some random student) writes: > There is a dodecahedran (sic) with 20 verticies (sic).... > On each vertex is an ant.... Well, this problem showed up on rec.puzzles in November, except that credit was given to OMNI's world's hardest IQ test, the posting wasn't riddled with misspellings, the poster (Derek Bosch) gave his name, and he used flies instead of ants. (If you don't think I should mention these discrepancies, please let me know by email.) The problem was also suggested for the other Platonic solids and one of the Archimedean ones. However, I didn't see any answers back then. cec35...@uxa.cso.uiuc.edu (Chuck Carroll) answers the question based on the related, but not equivalent problem: >... color 20 of the 30 edges on a regular dodecahedron blue so that >there are two blue edges at each vertex. Or, color ten of the edges >red so that exactly one red edge is at each vertex. Chuck solved this by writing a computer program, but it can be done fairly easily by hand, as follows. Since there are twenty blue edges there are forty sides of blue edges, so each face has an average of 40/12=3 1/3 blue sides. Therefore there is at least one face with four or five blue edges. If you draw the graph of a dodecahedron and mark the five sides of one face blue, the rest of the coloring may be found by the procedure: Repeat 1) If a vertex is incident on two blue edges, color its third edge red, and 2) If a vertex is incident on a red edge, color its other edges blue until no more can be done. The dodecahedron will be completely colored, and the blue edges will form three closed loops. On the other hand if you color four sides of one face blue, and the fifth side red, and perform the above procedure, you will end up coloring all but nine edges. You then get to choose the color of one of the edges (any one of the eight with a previously colored neighbor) and that choice determines the rest of the colors by the above procedure. You end up with a single closed loop that divides the dodecahedron into a double helix. (The last choice determined whether the helix has a right- or a left-hand thread!) By counting the colorings congruent to the ones above, we get six of the first kind (corresponding to the six possible choices of a pair of antipodal faces colored blue) and thirty of the second kind (corresponding to the fifteen possible choices of a pair of antipodal edges at the ends of the double helix and the two possible choices of the helix's handedness). This confirms that Chuck's program produced the right answers. This method easily answers the question for the tetrahedron (three single-loop solutions, one up to congruence) and the cube (three double-loop solutions and six single-loop solutions, one each up to congruence). The octahedron is not that complicated, either, though the coloring procedure must be modified to take account of its vertex degree being four instead of three. The octahedron has four double-loop solutions (one up to congruence), four single-loop solutions (o.u.t.c.) found by inverting the double-loop coloring(s), and twelve single-loop double helix solutions (o.u.t.c.). I have not found the solutions for the icosahedron, and it seems much more difficult. As for Archimedean solids, it's anyone's guess. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 24 Jan 91 15:04:35 GMT Subject: Re: An interesting combinatorical question ss...@andrew.cmu.edu (Steven M. Stadnicki) asked: >1) Start with an n-digit number, all 1's. Continue XORing with >random n-digit numbers until you reach zero (0's in all places). >How many steps will this take, on the average? warw...@batserver.cs.uq.oz.au (Warwick Allison) writes: >... every XOR operation will have 1/(2^n) chance of producing all zeroes >(by being equal to the current A value), Correct. >so the solution is that, on average, it will take 2^(n-1) XOR >operations to become all zeroes.... No. The average number of operations will be 2^n. In general, if we take a sequence of independent trials, each with probability p of success, the average number of trials to the first success is 1/p. Also, there is one exception to the solution. When n=0, the average number of operations is zero, because the n-digit number, all ones, is in that case also all zeroes. Dan --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 28 Jan 91 17:14:07 GMT Subject: Re: Perfect numbers iain@minster.york.ac.uk writes: >Can any one supply me with large perfect numbers ? >(By large I mean greater that 8589869056) All known perfect numbers are of the form (2^p - 1) 2^(p-1), where 2^p-1 is prime. Such primes are called Mersenne primes and the list as of mid-1990 is p=2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, and 216091. Any other Mersenne primes must have 150000350000. Any other perfect numbers must be odd, and as of 1989 it is known they must be greater than 10^300. Thanks to Chip Kerchner and Bob Silverman for posting these status reports last year. Dan --- Newsgroups: rec.puzzles Followup-To: alt.flame From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 19 Feb 91 17:23:03 GMT Subject: Re: Correction to which kind gt28...@prism.gatech.EDU (Benjamin H. Cowan) writes: [...solution omitted...] }Gee... for some reason this doesn't look like responding via e-mail. Maybe }it's because it *ain't* responding through e-mail. Read the instructions, }people. And cos...@bbn.com (Bernie Cosell) writes: >Why? Betty doesn't run the newsgroup and for some time now we have >been posting puzzles, solutions, discussions, etc with no particular >problems.... Actually, I take it to be the rule that solutions may usually be posted, but not when the problem's proposer requests response by email. But if we are to determine the rule by observation of current practice, I must modify that rule to exempt inconsiderate, incompetent, or careless respondents. They seem to be exempt from all kinds of rules around here. Dan --- Newsgroups: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 19 Feb 91 20:40:39 GMT Subject: Re: natural mathematics m...@hubcap.clemson.edu (m j saltzman) writes: >One possible way to think about nature "doing" math is the notion of >an analog computer. There are a number of such devices; two examples >come immediately to mind: > 2) Approximating the minimum-length Steiner tree connecting > points in a 2-dim plane using soap film. Place vertical > pins in a board at the chosen points. Dip the board in > soapy water, and the film that forms between the pins will > (with a little luck) be a good approximation to the shortest > network connecting all the points, if addition of new > junction points is permitted (again, in roughly constant time). > Finding the true optimum is NP-hard on a digital computer, > and any heuristic will be at least linear in the number of points. It's important to realize that finding the optimum Steiner tree consists of two parts: Choosing a topology for the tree and minimizing the length of the tree for that topology. The first part is the NP-hard part, in the sense that proofs of the NP-hardness use certain kinds of very regular Steiner trees for which the minimum length is immediate from the topology. The second part can be done quite quickly, perhaps in time linear in the input size. The soap-film computer chooses the topology at random, and quickly finds the optimum Steinter tree for that topology. Thus it is solving only the easy part of the problem, doing it very quickly. But if you use as many CPUs as you have points--essentially putting a CPU in each pin--you might be able to do as well as the soap-film computer. Perhaps a better analogy would be to use a CPU for each soap molecule. The situation is somewhat like the somewhat counterintuitive result that SUBGRAPH ISOMORPHISM is NP-hard, but GRAPH ISOMORPHISM may not be. The situation is explained when you look at the SI proof and notice that the graph for which we are seeking an isomorphic subgraph is a clique, for which the GI problem is trivial. So all of the difficulty in SI is accounted for in choosing the subgraph; the isomorphism part may as well be thrown in for free. Dan --- Newsgroups: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 19 Feb 91 21:01:29 GMT Subject: Re: monotone function problem ha...@ruuinf.cs.ruu.nl (Hans Zantema) writes: >Are there two strictly ascending functions (i.e. m>n => f(m)>f(n)) f and g >from natural numbers to natural numbers for which > f(g(n)) > g(f(f(n))) (*) >for all natural numbers n? pmont...@euphemia.math.ucla.edu (Peter Montgomery) writes: >No. [...] >When k = 0, this reduces to g(n) >= n and follows from the monotonicity >of g. gate...@rice.edu (John Gateley) writes: >This is wrong, g(n) >= n does NOT follow from monotonicity. It does, hoewever, follow from being a monotonic function from natural numbers to natural numbers. >There are two functions: >f(n)=n-1 >g(n)=n-1 >They are monotonic: for all n1>n2, f(n1)=n1-1>n2-1=f(n2). >And, f(g(n))=n-2, g(f(f(n)))=n-3. But they map the least natural number to some number that is not natural, so they do not address this problem. Dan --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 25 Feb 91 15:58:51 GMT Subject: Re: CS problems with names lin...@Eng.sun.com (Peter van der Linden) writes: > When you think about it, there are a *lot* of classical problems in > Computer Science that have been given flippant names.... The most notable is probably the Traveling Salesman problem. In fact, an excellent book on the TSP (whose authors I cannot at the moment recall) has a foreword that mentions how a travelling salesman stopped at a farmhouse and asked for shelter for the night. The farmer said that his spare room was occupied by his daughter, who had come home on vacation from the university, where she studied mathematics. The farmer called his daughter to ask if she would mind sharing the bed, and she answered, ``Get out of here, both of you! This is a serious book of mathematics, and your childish jokes have no place in it!'' Dan --- Newsgroups: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 12 Mar 91 18:51:25 GMT Subject: Re: Palindromic prime question unb...@uncecs.edu (Jay F. Rosenberg) writes: >Is it known whether there are any more palindromic primes with digit >sum = 2 beyond 11 and 101? dt...@unix.cis.pitt.edu (David M Tate) provides the ``partial non-answer'': >If there is such a palindromic prime, it has an odd number of digits. A somewhat less partial non-answer is that the number of digits must be one greater than a power of two. If you can't figure out why (and want to know) send me mail. I've checked up to 10^1024+1 without finding any more primes. Dan --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 22 Mar 91 16:22:02 GMT Subject: Cross-sectional symmetry (was Re: Four ounces) s...@athena.mit.edu (David A. Seal) writes: >Fill each container so that when it is tilted the water will just >cover the bottom completely while just barely spilling over the edge. >This means that each one is exactly half full.... (Assuming, of >course, that the x-sectional area of the containers is constant, i.e. >can-shaped, rectangular-shaped, etc.) Actually, the usual argument requires more than a constant cross- section. The (plane) cross-section must also be symmetric, in that you must be able to find a special kind of line I will call a bisector. A line L is a bisector if, when you take any two lines that are parallel to L and equidistant from L, the intersections of those two lines with the cross-section are equal. You then tilt the container while keeping the bisector of each cross-section horizontal. What shapes are symmetric in this way? Certainly in any shape that has 180-degree rotational symmetry, every line through the center is a bisector. In any mirror-symmetric figure, the axis of symmetry is a bisector, but there may not be bisectors in other directions. Thus if the cross-section is a triangle, and you use a vertex for a spout while keeping its opposite side horizontal, the cup will be only one-third full. It's not hard to see that every triangle has three bisectors. I think most quadrilaterals lack bisectors, but I'd like to know just which do and which don't. A line through two opposite vertices that divides the area in half is a bisector; is there a symmetric quadrilateral that lacks such a line? A characterization of all bisectible polygons would be most welcome. Also, there are cross-sections that work to cut the volume in half without being bisectible in this sense. The criterion is that a pseudo-bisector be found. A pseudo-bisector is a line that is equidistant from two parallel lines of support, and has an additional criterion on that I find difficult to characterize. It may be that a pseudo-bisector divides the polygon into two pieces whose (second?) moments about the respective lines of support be equal. Does anyone have a good definition? Does every well-behaved cross-section have a pseudo-bisector? I think the birthday-cake theorem ensures this, if the theorem I'm thinking of is called the birthday-cake theorem. You know, the one about how you can cut an arbitrarily-shaped cake in half in any direction, and the distance of the knife from the lines of support is a continuous function of the angle, so as you twist the knife through 180 degrees the distances functions must cross each other. I think that should work for whatever moment or whatever is used for the pseudo-bisector. As usual, if I have slipped up somewhere, or if there is some lack of clarity in this note, I'd appreciate a correction by e-mail, so that we can vet the corrections and reduce duplication. Answers to the open questions are also welcome, of course. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 22 Mar 91 19:44:49 GMT Subject: Re: seeing the trees for the forest (correction) This is a corrected version of my previous article. jadah...@acsu.buffalo.edu (jason a dahlin) writes: >Arrange 10 trees so that they form 5 rows of 4. As I noted some years back, this problem is easier to solve than to fail at solving. Spoiler follows... Pick five [not four] lines in the plane. If you were so unlucky as to pick two parallel or three that intersect in a point, you lose. Otherwise put the trees at the intersections. Dan [I am grateful to Robert Ebert for noting the error in the previous version. I am not particularly grateful for his posting of its contents without the spoiler warning or the form-feed. -- DH] --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 9 Apr 91 14:16:26 GMT Subject: Re: Longest minimum path (was word tesselation) warw...@cs.uq.oz.au writes: >Okay, these are easy, but how about finding `the big one': the pair of >words with the LONGEST minimum path in the network of words formed >by having every word a node, with arcs to every word with a single >letter different. Is this another travelling salesman perhaps? :-) Longest minimum path is solvable in polynomial time. In fact, it can be done in O(V(V+E)) time, which is modest as polynomials go, though perhaps painfully slow when V is in the hundreds of thousands. I suspect that it won't be so hard if you partition the graph into connected components first. If anyone takes up this exercise, please let me know. If you ask for the longest non-self-intersecting path, now that's a hard problem. Dan Hoey@AIC.NRL.Navy.Mil --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 9 Apr 91 17:09:43 GMT Subject: Palintuples While following the references in Myron P. Souris's excellent article (``Cache and Ferry'', <1991Apr6.13081...@sldev1.mdcbbs.com>) I noticed another non-solution to an interesting problem on the same page (50) of the March '90 _Mathematical_Gazette_ (Vol 74, #467). We are asked to find numbers that are integer multiples of their reversals--palintuples, if you wish. Of course, all the palindromic numbers are a trivial example, but if we disregard the unit multiples, the field is narrowed considerably. G. H. Hardy (after Rouse Ball) noted that the only four-digit palintuples are 8712=4x2178 and 9801=9x1089. In the _Gazette_ note, Martin Beech notes that direct computer search of all the four-digit numbers is the ``simplest, though not necessarily the most elegant'' way of proving this. He used the same approach to find that the only five-digit palintuples are 87912=4x21978 and 98901=9x1089. The similarity to the four-digit result prompted Beech to suspect that all numbers of the form 879*12 and 989*01 are palintuples. He claims to have ``confirmed'' this result on a hand calculator. Leaving apart my concern about the non-mathematical induction involved in this leap of faith (to a result that virtually proves itself once you formulate it) I was then amused to see him conjecture that such numbers are all the palintuples. If he had bothered to try something beyond a cursory glance at a quick hack, he might have been able to characterize all the palintuples. Can you find all palintuples? I enclose a hint at the end of this message, if you want it. I'll answer this question next week. In the mean time, please don't spoil it for everyone. Dan Hoey Hoey@AIC.NRL.Navy.Mil [ The origins cited for this problem are Rouse Ball, _Mathematical_recreations_and_essays_ as cited by G. H. Hardy, _A_mathematician's_apology.] Hint: Prove that the palintuples do not form a regular language. Then specify the palintuples with a regular expression! --- Newsgroups: news.misc From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 9 Apr 91 17:54:48 GMT Subject: UNIX Today!: Cretins or victims? So is this garbage really from baboons working for UNIX Today!, or is some competitor forging messages to destroy their reputation? Don't bother answering, I wouldn't believe you anyway. This message isn't from me either. Dan --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 15 Apr 91 16:58:42 GMT Subject: Palintuples solution I challenged you to find all the palintuples, numbers that are multiples of their reversals. In case you missed it or forgot, Rouse Ball (_Mathematical_recreations_ _and_essays_) originated the problem, and G. H. Hardy (_A_mathematician's_apology) used the result that 9801 and 8712 are the only four-digit palintuples as an example of a theorem that is not ``serious''. Martin Beech (_The_mathematical_ gazette_, Vol 74, #467, pp 50-51, March '90) observed that 989*01 and 879*12 are palintuples, an observation he ``confirmed'' on a hand calculator. I prefer a different form of confirmation, such as a Proof: First, letting "9*" and "0*" refer an arbitrary string of nines and a string of zeroes of the same length, I note that 989*01 = 989*00 + 1 = (990*00 - 100) + 1 = 990*00 - 99 109*89 = 109*00 + 89 = (110*00 - 100) + 89 = 110*00 - 11 It is then obvious that 989*01 = 9 x 109*89. The same formulation shows that 879*12 = 4 x 219*78. QED. Hand calculator, indeed! Beech conjectured that these palintuples are all that exist. The conjecture is wrong, for we may form palintuples by taking palindromes over the (infinite) alphabet consisting of the palintuples of Beech's conjecture and strings of zeroes. For instance, 8712 000 87912 879999912 879999912 87912 000 8712 = 4 x 2178 000 21978 219999978 219999978 21978 000 2178 (where I have inserted spaces to enhance readability) is a palintuple. The reason these do not form a regular language is that the palintuples on the left must be the same palintuples (in reverse order) as those on the right: 8712 8712 87999912 = 4 x 2178 2178 21999978 is not a palintuple! You may use the pumping lemma just as in the well-known proof that palindromes are not a regular language. Now to characterize all the palintuples, let N be a palintuple, N=CxR(N), where R(.) signifies reversal, and C is an integer. (I use "x" for multiplication, to avoid confusion with the Kleene star "*" to signify the concatenated closure.) If D is a digit of N, let D' refer to the corresponding digit of R(N). Since N=CxR(N), D+10T = CxD'+S, where S is the carry in to the position occupied by D' when R(N) is multiplied by C, and T is the carry out of that position. Similarly, D'+10T'=CxD+S', where S', T' are carries in and out of the position occupied by D when R(N) is multiplied by C. Since D and D' are so closely related, I invent the symbol D/D' to refer to a digit D, with the digit D' to follow the number expressed to the right. So 989901 may be written as 9/1 8/0 9/9 and 87912 may be written as 8/2 7/1 9. I will sketch a proof that the set of palintuples is the language specified by the regular expression: (8/2 7/1 9/9* 1/7 2/8 0/0*)* (0/0* + 0 + 8/2 7/1 ( 9/9* + 9/9* 9)) + (9/1 8/0 9/9* 0/8 1/9 0/0*)* (0/0* + 0 + 9/1 8/0 ( 9/9* + 9/9* 9)). (1) For each D/D', there are a very limited--and often empty--set of quadruples S,T,S',T' that satisfy the equations D +10T =CxD'+S D'+10T'=CxD +S', (2) yet such a quadruple must exist for "D/D'" to appear in a palintuple with multiplier C. Furthermore, the S and T' of one D/D' must be T and S', respectively, of the next pair of digits that appear. This enables us to construct a finite state machine to recognize those palintuples. The states [X/Y] refer to a pair of carries in D and D', and we allow a transition from state [T/S'] to state [S/T'] on input symbol D/D' exactly when equations (2) are satisfied. Special transitions for a single-digit input symbol (the central digit of odd-length palintuples) and the criteria for the initial and the accepting states are left as exercises. The finite state machines thus formed are State Input New Input New Input New Accept? State State State --> [0/0] Y 8/2 [0/3] 0/0 [0/0] 0 [A] [0/3] N 7/1 [3/3] [3/3] Y 1/7 [3/0] 9/9 [3/3] 9 [A] [3/0] N 2/8 [0/0] [A] Y for constant C=4, and State Input New Input New Input New Accept? State State State --> [0/0] Y 1/9 [0/8] 0/0 [0/0] 0 [A] [0/8] N 8/0 [8/8] [8/8] Y 0/8 [8/0] 9/9 [8/8] 9 [A] [8/0] N 9/1 [0/0] [A] Y for constant C=9, and the finite state machines for other constants accept only strings of zeroes. It is not hard to verify that the proposed regular expression represents the union of the languages accepted by these machines. I have written a computer program that constructs finite state machines for recognizing palintuples for various bases and constants. I found that base 10 is actually an unusually boring base for this problem. For instance, the machine for base 8, constant C=5 is State Input New Input New Input New Accept? State State State --> [0/0] Y 0/0 [0/0] 5/1 [0/3] 0 [A] [0/3] N 1/0 [1/1] 6/1 [1/4] [1/1] Y 0/1 [3/0] 5/2 [3/3] [3/0] N 1/5 [0/0] 6/6 [0/3] 6 [A] [3/3] Y 2/5 [1/1] 7/6 [1/4] [1/4] N 1/1 [4/1] 6/2 [4/4] 1 [A] [4/4] Y 2/6 [4/1] 7/7 [4/4] 7 [A] [4/1] N 1/6 [3/0] 6/7 [3/3] [A] Y for which I invite masochists to write the regular expression. If anyone wants more, I should remark that the base 29 machine for constant C=18 has 71 states! By the way, I did not find any way of predicting the size or form of the machines for the various bases, except that the machines for C=B-1 all seem to be isomorphic to each other. If anyone is interested in investigating this problem more fully, let me know. In closing, I should note that the conclusion of Beech's article assumes a most sublime ridiculousness in the presence of this analysis. Beech speaks of his investigations as demonstrating ``the computer acting as the mathematician's eyes in a complex field.'' While I believe that the computer can so act in many cases, his example demonstrates that the computer, by acting as a guide dog, may occasionally lead mathematicians to walk around with their eyes closed. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 15 Apr 91 17:18:38 GMT Subject: NPR Sunday Puzzler As you may remember, a discussion on NPR's Weekend Edition Sunday Puzzle (24 March) led me to investigate the combinatorical aspects of folding maps, and I found some results that seem to contradict Will Shortz's conclusions. I sent him a letter with my results on 2 April, but I have not heard back from him. The NPR Sunday puzzle, however, continues to air. I heard the broadcast on 1 April, in which he asked several seasonal questions, such as how to rearrange the letters of ``Maria's Failing'' to form a familiar sign. I listened on 8 April, and I did not hear a puzzle, though there was a segment of ``Car Talk''. I assumed they just skipped the puzzle that week, but on 15 April Will Schortz referred to his previous week's show. That week's problem was something about finding hyphenated words with four N's or with four T's. I don't know if Washington, DC's WETA-FM just dropped the puzzle segment last week, or if I somehow fell asleep through it. However, there's the possibility he mentioned something about map folding and I missed it. If so, I'd appreciate a note by email. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 16 Apr 91 19:07:03 GMT Subject: Re: Magic square questions torb...@diku.dk (Torben [gidius Mogensen) writes: >In the thread of discussion of how to construct magic squares, I would >like to add a few observations: 1) Odd-sided magic squares are easy (De la Louberes method). >2) If you have magic squares of sides N and M, you can easily >construct a square of side N*M.... >3) The 4 sided magic square is classical: > 1 14 15 4 > 10 8 5 11 > 7 9 12 6 > 16 3 2 13 >4) There is no 2x2 magic square. >This gives us a simple procedure for constructing magic squares except >those whose side lengths are equal to 2 modulo 4 (like 6, 10, 14 etc). Actually, this also fails to produce magic squares of side 8 modulo 16, 32 modulo 64, ..., 2^(2n-1) modulo 2^(2n), .... If a magic square of side 8 exists, that will suffice to complete the claimed result. Unfortunately, I don't have one to hand at the moment, but I seem to recall they exist. Dan Hoey@AIC.NRL.Navy.Mil --- Newsgroups: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 18 Apr 91 18:25:24 GMT Subject: Re: Self-ref clue puzzles david.lloyd-jo...@rose.uucp (DAVID LLOYD-JONES) writes: >It seems to me there's a class of puzzles in which the fact that the >puzzle is soluble constitutes one of the clues necessary for solving >the puzzle. Having said that, I can't for the life of my think of one. The well-known puzzle of Monty and the three doors may be written as Monty Hall plays a game with the contestants on his show. He shows the contestant three doors, behind one of which is a prize. He lets the contestant pick one of the doors, then--using his knowledge of where the prize is--he opens one of the unchosen doors that has no prize behind it. (He can always do this because only one door conceals a prize). The contestant can then choose whether to have what is behind the first door picked or what is behind the other closed door. Which is the better choice? for which the answer is well known; send me mail if you haven't seen enough about this problem. (Trying to solve it by network discussion has been shown to yield a large number of messages, most of them wrong in one subtle way or another. I think it is more productive to read about this in the rec.puzzles FAQ list.) My point is that this problem is usually posed in a shorter form, such as: Monty Hall has put a prize behind one of three doors. He lets you pick one, then he opens one you didn't pick and offers to let you switch. Should you? In this second formulation we have the possibility that you are dealing with a character I call ``Monty's Evil Twin'', who only offers to let you switch when you picked the prize door first. If you pick a door without a prize, Monty's Evil Twin sends you home empty-handed. There's also ``Saint Monty'', who doesn't offer a switch unless switching lets you win. It's pretty clear that you should switch if Saint Monty lets you, but not when the Evil Twin offers. This relates to the question of self-referential puzzles in that, without some knowledge of the a priori distribution of Saints and Evil Twins, you can't deduce the payoff from switching vs. staying. Bernie Cosell has reasoned that by assuming we are given enough information to solve the problem, we can rule out the possibility of any but the single-strategy Monty of the first problem statement. (I think his reasoning is unjustified, but Bernie says I'm being picky. Let's call the whole thing off.) Back in December, Phil Servita used a statistical approach. He noted that if the a priori likelihood of Saint Monty is the same as that of the Evil Twin, then your observation of being given a choice makes the Saint twice as likely as the Twin, so they cancel out. I would be interested in seeing this analysis carried out on the entire space of mixed-strategy Monties. I think the ``default'' a priori probability depends on how you parameterize the space, but I'm not really sure. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 18 Apr 91 20:41:01 GMT Subject: Re: Alternate Foundations w...@wang.com (William Ricker) writes: >If you're looking for an alternative foundation of mathematics.... >The (in)famous John Horton Conway has spoken on, and I believe >published in a collection, a delightful alternate foundation based on >Game Theory, of all things.... Yes, but we should be careful to understand we are talking about combinatorial games of perfect information. The topic ``game theory'' often refers to probabilistic games such as poker. >Given time, I can probably unearth the reference from wherever I >scribbled it. It's been published as a wonderful little book, _On_Numbers_and_ _Games_ (Academic Press, 1977). I hope it's still available. Despite the larger and more recent _Winning_Ways_ (by Berlekamp, Conway, and Guy, Academic Press, 1982) there's a lot of good stuff you'll only find in ONAG. Dan --- Newsgroups: comp.lang.lisp From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 26 Apr 91 15:35:50 GMT Subject: GET / GETF warning. The fact that GET/GETF use EQ instead of EQL needs to be emphasized more. Such as a remark that it is an error to use a number as an indicator in the property list. It's all the worse that for many implementations EQL fixnums are EQ, so you don't see the bug until your problem gets into bignums. This might be a useful thing to put in the FAQ list, too. Dan --- Newsgroups: sci.math Followup-To: alt.flame From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 26 Apr 91 15:47:33 GMT Subject: Abuse (was Re: Political Economy of) david.lloyd-jo...@rose.uucp (DAVID LLOYD-JONES) writes: >Rather than abusing Han de Bruijn directly you [Allan Adler] post an anonymous >bit of nastiness which you attribute to "someone who studies these subjects." It's a pity, because de Bruijn richly deserves all the abuse we can give him on this news group. He, after all, abuses sci.math by posting articles that consistently have nothing to do with mathematics. He seems preoccupied with some bit of inane philosophy, yet he doesn't sends his little Richards to the philosophy groups, because the readers of those groups insult him too much. Clearly the restraint here is acting to our disadvantage. Dan Hoey Hoey@ETL.Army.Mil --- Newsgroups: news.admin Followup-To: alt.flame From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 7 May 91 14:53:33 GMT Subject: Re: Really old news being resent Smileys are subtitles for dolts. People who write them have too much sympathy and too little taste. stan...@phoenix.com (John Stanley) writes: >When the posting is in news.admin, and is supposed to be discussing >the source of a problem, the most logical assumption is that the >poster is posting facts. The most logical assumption is that you shouldn't go shooting your mouth off about the imminent demise of the net until you know what you're talking about. Unfortunately, no one seems to follow this advice but me. Dan --- Newsgroups: comp.lang.lisp From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 8 May 91 15:44:21 GMT Subject: Re: How does one quote an atom in Sun CL (correction) char...@ai-cyclops.jpl.nasa.gov writes: >The following works as a general purpose quoting function for any LISP datum: >(defun kwote (thing) > (if (constantp thing) > thing > `(quote ,thing))) No. The CONSTANTP test is incorrect for constants that do not evaluate to themselves. For instance (KWOTE 'PI) -> PI fails the expected (EQL 'PI (EVAL (KWOTE 'PI))). The traditional way of defining KWOTE is (defun kwote (thing) `',thing) although the alternate definition (defun kwote (thing) (if (and (constantp thing) (eql thing (eval thing))) thing `',thing)) is functionally acceptable and arguably preferable. If you're about to lose your connection, you can try (DEFUN KWOTE (-\))`',-\)) --- Newsgroups: rec.puzzles, sci.math Followup-To: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 8 May 91 18:20:09 GMT Subject: Re: Name this property ma...@cs.fsu.edu (Bill Mayne) writes: >A few years ago in an amateur (very amateur) number theory discussion >group on a bulletin board Walter Nissen proposed the following >challenge: > Find all natural numbers which have a binary representation > that ends in a string of digits identical to the decimal > representation. E.g., the binary representation of 101 is > 1100101, which ends 101. Nice problem. >In the first place it is obvious that there are an infinite number of >such numbers, so finding them all is out of the question. You can certainly describe the infinite set in instructive ways. For instance, ``The tens and hundreds digits are arbitrary (1 or 0) for numbers up to five digits, must be equal for six or seven digits, and must be zero for more digits.'' This might lead to an algebraic structure, or at least good bounds on how many such numbers there are below 10^n. >...there is a very efficient algorithm for enumerating all the >examples up to a given size. Does your algorithm generalize to other bases? Base 5 should be easy. Base 4 is probably tricky. Base 3 may get real tough. >(Up to 32 digits, the limit of integer size with most C compilers on >PCs, ...) Ick. You need some bignums. Or maybe just vectors of digits. But something, because the interesting things don't start happening until about 10^14. >As far as I know this was just something Mr. Nissen dreamed up. My >question is: Is there a name for this property? I suggest ``polyradicism''. >Is there any area of theory which resembles this type of thing? I don't know. Let me know what you find out. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Date: Mon, 13 May 91 14:46:06 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Very silly ways of building very large cubes (was Re: 5by cubes) Andy Latto wrote: You can't make an order 21 cube, or any cube of order 7 or higher. When you turn the top layer of such a cube by 45 degrees, the corner cubie will not touch the other layers at all, so there's no way to keep it attached, and it will fall off. Then "Dale I. Newfield" responded: There is no law that says that the cubes have to be the same size. and showed that by making the outer layers thicker, we can increase the size of the cube. There is another way around Andy Latto's con- cern, and that is that we can--at least in theory--design a physical cube that lets pieces overhang, such as corners that touch only two surfaces, and yet still holds the pieces so they cannot be removed. This idea (which came up in talks with Jim Saxe about a decade ago) is to slice up the cube with a fresnel saw. A fresnel saw is used to cut a piece of glass into two fresnel lenses out of pieces of glass, and you find them in the same stores that sell plaid paint and jelly- doughnut cookie cutters. (In case you don't know what a fresnel lens (pronounced freh-NEL) is, for this note it's sufficient to think of it as a surface with small concentric circular grooves in it. Kind of like those old vinyl recordings people used to listen to, except that the grooves are circular instead of spiral, and the grooves don't wiggle back and forth.) Now if you have two surfaces with mating grooves--each one has a ridge that fits in each of the other's grooves--when you put them together you can twist one with respect to the other, but you can't slide one across the other, because the grooves are locked together. There is one thing you can do that we don't want: you can lift one slab away from the other. The solution now is to get a *very* *sharp* fresnel saw, that cuts hooked grooves that interlock with each other. You get surfaces with cross sections that look somewhat like hook-in surface _________ _______________________ _________ \ / \ / . \ / \ / | | | | | | | | | | | __ | | __ . __ | | __ | | | | \ | | \ | / | | / | | \ \___/| \ \___/| . |\___/ / |\___/ / \ | \ | | | / | / \_____/ \_____/ . \_____/ \_____/ _____ _____________________ _____ / \ / | \ / \ | ___ \ | ___ . ___ | / ___ | |/ \ \ |/ \ | / \| / / \| \__ | | \__ | axis | __/ | | __/ | | | of | | | | | | rotation | | | ___________/ \_________/ \_________/ \_____ hook-out surface except that the surfaces are closer, so the hooked grooves are engaged with each other. (Now we see why we need a fresnel saw, so that we can cut the two mating surfaces in one cut, and avoid the problem of trying to assemble two separated pieces (though we could get around that difficulty messily with glue)). So we may cut up a 2n+1 x 2n+1 x 2n+1 cube with a fresnel saw, to make a large Rubik's cube. The only really touchy point is the need to make the ``direction'' of each cut match the direction of the other cuts at that ``depth.'' Here, direction refers to whether the hook-in surface faces toward the nearest parallel side or away from that side, and ``depth'' refers to the distance from the nearest parallel side. This ensures that when we permute cubies around the directions of the groove hooks will not change, so the grooves will always mate. If n is large, then pieces of one slab will overhang at each turn, so you can see the grooves on a whole surface of a corner, or on two surfaces of an edge piece. But you can't pull the piece off, because it won't move straight with respect to the rest of the cube, only in curved trajectories. We have to keep the fresnelling small with respect to the size of the cubies, and the tolerances are pretty tight, but that's the regime we theoretical engineers are working in. (I'd like to mention that cubes made with this method also have the nice feature that there's a 2n-1 x 2n-1 x 2n-1 Rubik's cube on the inside, so you can play with the theoretical invisible group while you're at it.) Now what about cubes of even side? The fresnel saw cuts two surfaces that mate to each other but not to themselves. How can we get a surface that mates to itself? I think the answer is that we can't. But this doesn't mean we are out of luck, as there are several ways of fixing up the center cuts of these cubes. Perhaps easiest way is to embed a 2x2x2 cube in the center of the original solid cube, and use it to hold the octants together. Unfortunately, this method requires an appeal to the existence of even-sided cubes, rather than teaching us how to build them. The other ways of finessing the center cut involve the thin-center- slab approach. You know you can simulate a 2x2x2 pocket cube with the corners of a regular 3x3x3 Rubik's cube, and similarly you can simulate any even cube with a larger odd cube. Also, we can make that center slab very thin, so it becomes part of the supporting structure rather than a significant part of the cube. We also remove the cor- ners from the center slab, so it does not protrude from the cube. We may even make covers for the cubies slabs adjacent to the center, to cover up the crack where the center slab lives. We are ready to cube! Or are we? The thin-center-slab suffers from the partial-twist problem. We can see this in the simulation of the 2x2x2 by a 3x3x3. If you try to simply ignore the center slabs, you can end up with the corners being aligned with each other but with a center slab twisted by 45 degrees. This makes it impossible to turn the corners except in the plane parallel to the oblique slab. If we shrink the center slab enough that it becomes unnoticeable, we will still be unable to twist the cube except in one direction except by breaking the center slab. The first solution to the partial-twist-problem is to select one of the eight near-central cubies, a cubie that abuts the center slabs on three sides. We then glue the adjacent parts of the center slabs to that cubie. Then when we turn along the center slice(s), the glued part of the thin center slab will follow the selected cubie, and will push the rest of the thin center slab along. This is a modification of the solution that is taken inside Rubik's Revenge, as I described to this group in my Invisible Revenge article of 9 August 1982. I like this solution except for one thing. It destroys the symmetry of the cube, by selecting one specialized octant that the center slab must follow. There is one more solution, though, that keeps the cube symmetric, which is *even* *sillier* than the thin center slab itself. Let us now visualize the center slab. It has the corners removed, so it is in the shape of a disc. The disc is cut in a grid pattern by the cuts from perpendicular planes. Now suppose we cut each slab in a second grid pattern, with the grid at a 45 degree offset from the original. With such a center slab, the cube can be twisted if each slab grid is in the correct position, or if some are at a 45 degree offset from the correct position. And how shall we prevent turns of less than a 45 degrees? Gears! Embed tiny gears in each fragment of the center slab, that contact tiny toothed tracks in the adjacent slabs on both sides. This will force the center slab to turn at exactly half the angular rate of one half of the cube with respect to the other. Thus when the off-center slabs of the cube are aligned, the center slab will be at one of the positions that allows twisting. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 14 May 91 21:59:27 GMT Subject: Re: Optimal change and related trivia farrell@cs.uq.oz.au writes: >There is an old problem about the most efficient way to give change in a cash >transaction, i.e. requiring the least coins. And se...@Morgan.COM (Seth Breidbart) notes: >The problem is NP-complete; it is trivial to reduce the knapsack >problem to it. (Throw in a lot of stamps of very tiny denomination, >you lose iff you have to use some of them.) Therefore, it's quite >unlikely that anyone will find an efficient algorithm. Knapsack is only weakly NP-complete, so there are algorithms that operate in time polynomial in the amount to be changed. For instance, you can use dynamic programming: recursively find the optimum change for each value less than the amount, then find the minimum, over values one coin less than the amount, of the number of coins needed to make change. The best change uses one coin more than that minimum. Dan --- Newsgroups: rec.arts.sf-lovers Date: 15 May 91 15:14:44 GMT From: hoey@zogwarg.etl.army.mil (Dan Hoey) To: SF-LOVERS Subject: Re: Awards WFJ101@psuvm.psu.edu (Bill Johnston) writes: >The only awards I know about are the Hugo (awarded by Worldcon members) >and the Nebula (awarded by the Science Fiction Writers of America)... >When I was at Balticon this year, they gave out the [Compton Crook] award >for what I assumed was 'best first novel'. The Compton Crook award is given by the Baltimore Science Fiction Society for the best first novel in the field of Science Ficiton, Fantasy, or Horror. Previous non-genre novels do not disqualify an author. The John W. Campbell award is given by Worldcon members for the best new SF writer. Writers are eligible for the first two years after their first publication. The Sei-Un award is given by a Japanese SF organization for the best SF work (novel? story?) translated to Japanese. Murcans tend to get this mixed up with the Cy Young award. The L. Ron Hubbard Writers of the Future awards is given by some Hubbard-related organization for several SF-related works; I don't have details. The administrator, Algis Budrys, says they have gone to some effort to distance it from the church of Scientology; how well they manage depends on who you ask. The Gryphon award is given by Andre Norton to an unpublished female writer. Widely criticised for its sexual exclusivity, it was first presented at NorEascon 3, probably more out of consideration for their Guest of Honor (Ms. Norton) than for it being a Good Idea. I think the Philip K. Dick award is given for a horror novel, but I'm not sure. And there's an Ellery Queen award given for mystery novels. I think that may be the one Sharyn McCrumb won for _Bimbos_of_the_Death_Sun_. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 16 May 91 19:15:16 GMT Subject: Re: Optimal change and related trivia hoey@zogwarg.etl.army.mil (I) wrote: >Knapsack is only weakly NP-complete, so there are algorithms that >operate in time polynomial in the amount to be changed. se...@Morgan.COM (Seth Breidbart) writes: >But the amount to be changed is exponential in the length of the >problem (I can specify the number n using log2 n bits), so this >algorithm has exponential running time, as a function of the length >of the input. It all makes sense except the word ``but''. That is exactly what I meant. The term ``weakly NP-complete'' means that if you measure the size of numbers by their magnitude rather than their logarithm, there's a polynomial-time algorithm. When making change, you have to handle a number of tokens proportional to the amount to be changed, so I think that's an appropriate measure for this problem. i...@prg.ox.ac.uk (Ian Collier) makes the dynamic programming algorithm more explicit, and concludes >This algorithm is O(n2). Actually, if there are C coins and we want to change an amount N, the algorithm takes O(C N logN) time, if we charge logN for addition and comparison of logN-bit numbers. In the uniform model, where arithmetic is a constant-time operation, it takes only O(CN) time. Dan Hoey Hoey@ETL.Army.Mil --- Newsgroups: sci.crypt From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 10 Jul 91 03:19:21 GMT Subject: Re: PGP10, Primality questions, legal questions, lots more! mira...@gpu.utcs.utoronto.ca (Robert Ames) writes: >In any event, I feel that public keys should be printable, and the best >system of doing that is the RPEM-style hexadeciimal number. PGP uses >binary keys - a flaw in an otherwise generally good program. Sure, having them readable is useful, but hexadecimal is bloated. If you print them in base 64 they are only half as long. I'd use [0-9A-Za-z./] as the digit set. Dan --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 10 Jul 91 20:23:34 GMT Subject: Re: GAMES magazine cos...@bbn.com (Bernie Cosell) writes: > *NO* Games magazine does *NOT* still exist. Its publishing company > went bankrupt and with it went Games. Period. > As it happens, a new investor/publisher has come along and hired > many of the old Games staff members and has started a brand new > magazine whose *very*first* issue came out just a month or so ago. > The new magazine is VERY similar to the old one [and, indeed, is > called 'Games'], but it is a wholly separate venture... octogard!graham (Graham Mainwaring) writes: > Games Magazine went under and exists no more. In my opinion, it > was a bad business decision for the new venturists to call their > enterprise "Games Magazine," because of all the fools who can't > distinguish between Joe Smith Jr. and Joe Smith Sr. I think these statements go beyond legal fictions into legal fantasy. After all, the new magazine trades on the technical reputation and image of the old one. They even published the answers to the puzzles posed in the final few issues of the old magazine. Still, it's hard to see how the editorial people should be held morally accountable for business decisions made by the managing company. If the published statements are accurate, the closest anyone on the new magazine got to the business end of the old magazine was to cash (or be unable to cash) their paychecks. You always risk this sort of thing when subscribing to magazines. But you also get a big discount for subscribing. My experience is that you end up saving money on average, even counting the magazines that go out of business. But suit yourself, there are still newsstands. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: sci.math, rec.puzzles Followup-To: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 10 Jul 91 22:00:30 GMT Subject: Boxes with same volume and area The pool puzzle I answered a few months back led me to consider the problem of boxes (rectangular prisms) with integer sides and the same volume and surface area. There are a lot of them, such as the 3x8x8 and the 4x4x12 with common volume 192 and area 224. There are even triples, such as the 144x14x12, 112x24x9, and 63x48x8 with volume 24192 and area 7824. Is there a set of four or more such boxes? Are there bounds on the ratios of the sides? On the ratio of area^3 to volume^2? Can you give a formula to generate the solutions? Is there anything published on this problem? Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 11 Jul 91 17:26:52 GMT Subject: Re: Help on a Boolean logic problem mo...@thunder.mcrcim.mcgill.edu (der Mouse) writes: >e...@hpsciz.sc.hp.com (Evan Whitney) writes: >> ... by using a recursive technique, you can invert N digital >> signals with only 2 inverters.... >It initially looks as though you can, but you can't. The resulting >circuit contains feedback loops and in practice will oscillate; I >recall reading an article by someone who actually tried building the >thing. Does anyone have a citation to this article, or other info on the problem? Has it been proven impossible for any inverter-building scheme, or just the one someone tried? Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: sci.math Followup-To: poster From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 12 Jul 91 14:14:40 GMT Subject: 0^0, was Re: Definitions, was: *Re: Mathematical Induction?* hay...@buster.cps.msu.edu (Thomas P Hayes) writes: >I have even seen it (wrongly [sic]) > 0 >asserted that 0 = 1, despite the fact that by appropriate choice of >function, this indeterminate form may take on any value whatsoever. People who have been reading sci.math for a while know that it isn't 0 x 0 that's the indeterminate form, it's lim lim -, and if you are x->0 y->0 y foolish enough to define the former in terms of the latter you will be tempted to decide to leave 0^0 undefined. But as you will see in _Concrete_Mathematics_, there are too many good reasons for defining 0^0=1 (without the spurious recourse to the indeterminate form) to let it be undefined. See the sci.math FAQ list or send mail if you are unclear on the subject. >Who knows how many other functions such as factorial have been >extended to include 0 despite the fact that this makes them more >difficult to explain? Mathematicians don't define things to be easy to explain, they define things to be easy to use. But in the case of 0^0, the simplest definition of exponentiation over the integers--the one set theorists use--happens to give 1 as the result. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 15 Jul 91 21:36:50 GMT Subject: Stamps spoiler: (was Chris? & Balls & Balances) tho...@guardian.wpi.edu (Richard John Yanco) writes: > .. "Dad wants one-cent, two-cent, three-cent, five-cent, and >ten-cent," she replied. "He said to get four each of two sorts and >three each of the others, but I've forgotten which." > [the exact money is] "Just these dimes." > [J.A.H. Hunter] Neat. The easy way to solve this is to sell her three each, for 3x(1+2+3+5+10) = 42 cents. Two more stamps must be bought, and they must make eight cents (since 18 is too much), so the fourth stamps are a three and a five. OBnews: Will Shortz has finally given us a combinatorial puzzle again on NPR! Put letters in a square grid. As in the game of Boggle, you can read words out in a (possibly self-intersecting) path of horizontal, vertical, and diagonal steps. Find the smallest number of letters from which the names of the nine planets can be read: mercury, venus, earth, mars, jupiter, saturn, uranus, neptune, and pluto. Since seventeen letters are used, that's a lower bound, but you can't achieve it. Please don't post answers before 28 July, when this puzzle ends. Dan --- Newsgroups: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 16 Jul 91 00:24:31 GMT Subject: Re: Magic (Was: A value of Pi to 10000 places) st...@fritz.sri.com.UUCP (John Stach x6191) writes: > AER5...@TECHNION.BITNET (Meir Feder) writes: >> There are some well known rational approximations for Pi such as 22/3 >> (very poor approximation) ^^^^ Right. That is an impressively poor approximation. >>Some years ago I found in the Journal of Recreational Mathematics the >>following non-rational approximation which can be easily calculated using >>a simple calculator (accurate up to 10 decimal digits): >>\|(\| 2143/22) I get 3.141592652582646..., only accurate to 8 digits after the decimal. Maybe this means including the digit 3 before the decimal, and including the digit 2*10^-9 that is fairly close to 3*10^-9. >My thinking cap is loose today. What does \| stand for? square root. Dan --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 16 Jul 91 13:46:27 GMT Subject: Re: NPR puzzle m...@suna3.cs.uiuc.edu (Tom Magliery) writes: >hoey@zogwarg.etl.army.mil (Dan Hoey) writes: >>OBnews: Will Shortz has finally given us a combinatorial puzzle again >>on NPR! Put letters in a square grid. As in the game of Boggle, you >>can read words out in a (possibly self-intersecting) path of >>horizontal, vertical, and diagonal steps. Find the smallest number of >>letters from which the names of the nine planets can be read: mercury, >>venus, earth, mars, jupiter, saturn, uranus, neptune, and pluto. >>Since seventeen letters are used, that's a lower bound, but you can't >>achieve it. >>Please don't post answers before 28 July, when this puzzle ends. >so we're looking for the number of letters used, and not the area of >the enclosing grid? (i think minimizing that could be an interesting >puzzle as well.) I'm certain he said to minimize the number of letters. When he had described the rules for admissible solutions, I knew he was going to minimize one or the other, so I listened for it especially. Also, he gave the lower bound as 17. >a clarification of the rules for those who don't know boggle: words >can be self-intersecting, but only if the path you are following is >diagonal at the intersection point. you can't re-use a letter in a >word unless it appears in the grid twice. ... >however, i didn't hear weekend edition, so maybe shortz intended for >self-intersection to be allowed in this puzzle. dan? I'm not sure here. He did mention that it was ``as in Boggle'', so perhaps he meant the rules you state. But I came away believing the rules as I gave them. Still, I may have missed a word or two when he was explaining intersection. If anyone is sure what he said, please speak up. It's kind of a pity, too, because I think the rules where repeated letters are permitted makes a much harder problem, especially for obsessivists (like me) who want to prove optimality. >as to the lower bound: considering the repeated letters in mercury, >neptune, and uranus, and assuming boggle rules as i stated above, 21 >is tighter (but seems VERY unrealistic...). This is a place that militates for the ``allowing repeated letters'' understanding. He mentioned the 17 lower bound, but not the 21. But maybe he thought it would be too hard to explain, or didn't think of how easy it is to get the intersection rule wrong and that the lower bound makes it clear. Dan Hoey Hoey@ETL.Army.Mil P.S. Yes, I have seen the arithmetic error in my solution to the stamp problem. Fixing it is an exercise for the reader. --D --- Newsgroups: sci.physics Followup-To: poster From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 16 Jul 91 17:43:42 GMT Subject: Re: Hidden messages d...@netcom.COM (Doug Merritt) writes: >"Can God fiddle with the digits of pi?" No, he can't, regardless of >your religion. He could fiddle with *us* so that we couldn't figure >out that there was such a thing as pi, but that's about it. Actually, it's pretty easy. He just hacks into our computers and puts whatever secret messages He likes. The hard part is hacking this into everyone's computers the same way. I understand He's not above buying a little extra time with a lightning bolt, head crash, locusts or other bugs, etc. Who's the great deceiver now? Dan --- Newsgroups: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 16 Jul 91 19:28:58 GMT Subject: Re: How about this Travelling Salesman? dt...@unix.cis.pitt.edu (David M Tate) writes: >Recognition version: >Given an arbitrary graph G, does G contain a Hamiltonian cycle? No, that's Hamiltonian cycle. The recognition version of TSP is: Given a graph G with positive integer edge weights and a positive integer K, does G contain a Hamiltonian cycle of weight at most K? Dan Hoey hoey@ETL.Army.Mil --- Newsgroups: sci.math From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 19 Jul 91 15:52:02 GMT Subject: Re: A Diophantine Equation (with a rot13 spoiler) amb...@acf5.nyu.edu (Balamurali K. Ambati) writes: >Prove (or disprove) that there are exactly 4 pairs of integers (x,y) >that satisfy: > y x > x = (x+y) Disprove, certainly. I know of six pairs, only one of which is controversial. If anyone wants to prove that's all of them, be my guest. Sbe k sebz zvahf gjb gb guerr gur inyhrf bs l ner zvahf fvk, gjb, gjb mrebrf, naq gjb fvkrf. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 22 Jul 91 21:45:44 GMT Subject: Re: Placing tiles in a grid (was: Covering a grid with tiles) a...@hadar.cs.Buffalo.EDU (Ajay Shekhawat) writes: >Given an NxN grid, and "t" identical tiles of size MxM each. In how many >ways can we place these t tiles on this grid, so that > - There is no overlap > - The edges of the tiles are parallel to the boundaries of the grid > - The endpoints of the tiles are on the gridpoints. > t = 1 >There are (N-M)^2 ways of placing one tile. You are mistaken. There are (N-M+1)^2 ways of placing one tile. > t = 2 >... (this is where it becomes real tough)... Pretty easy, actually. First you count the number of ways of putting the two tiles down, permitting overlaps. Then you subtract out the number of ways of putting the tiles down so they overlap. The overlap will always be a rectangle. It isn't that hard to count, for every 0I heard this from an associate who isn't on the net. I'm not sure if >this is old or not, but I thought it was funny. Sure it's old. I saw it in a plan file on the net at least seven years ago. > Which one of the following group does NOT belong? > 1) Herpes > 2) Measles > 3) AIDS > 4) A Condo. in Nashua, NH >The correct answer is Measles. You can get rid of Measles. Good grief, get the joke right. Use "Gonorrhea" or "Syphilis". "Measles" is just dumb. Dan Hoey Hoey@ETL.Army.Mil --- Newsgroups: rec.puzzles, sci.math Followup-To: rec.puzzles From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 24 Jul 91 14:00:25 GMT Subject: Re: A Puzzling Catalyst (Spoiler, but the puzzle continues) cos...@bbn.com (Bernie Cosell) writes: >dcasa...@magnus.acs.ohio-state.edu (Donald J Casadonte) writes: >}The will al[l]otted specific portions of the cattle the sheik had >}owned to go to each son. To the oldest, 1/2 of the cattle were to >}be given. To the next oldest, 1/3 were to be given, and to the >}youngest, 1/9 were to be given. >}"Look, suppose I give you one of my cattle to put in with your >}own... [divide them up] and then I will take my cattle back..." >What is happening, of course, is that the will ... only allocated >17/18ths of the flock. By having the denominator have interesting >factors you can hide the omission pretty well. So let's pick another >good-multiplier at random: say 24. So we need to add up to 23/24ths, >and so we can do it with 12, 8, 3. ... > his flock was five, and he bequeathed 1/2 to one son and 1/3 to the > other.... Or even, suppose he bequeathed half of his only cow to his only son! I wonder if we should count the case where he had neither cattle nor sons? >his flock was 23 and to his five sons he bequeathed 1/3, 1/4, 1/6, >1/8 and 1/12 of his flock. The unstated criterion here is that the will uses Egyptian fractions (the numerators are all one). So the question here is for which numbers N are there factors of N adding to N-1? It certainly works for any power of 2, by taking all the proper factors. In fact 2^K is the smallest K-son number. Bernie noted N=6; this is the largest two-son number. What is the largest three-son number? (In case you need a hint, V pbhyq gryy lbh ohg gung jbhyq tvir gur nafjre njnl.) Note that twelve is a three-son number in two different ways: a sheik with eleven cattle could bequeath 1/2, 1/4, and 1/6 or 1/2, 1/3, and 1/12. What is the smallest three-way number? What is the smallest K-way K-son number (and what is the smallest K? They need not be the same solution, as far as I know. But then I'm not sure any exist). The big question is, is there an ODD K-son number (other than one)? I don't expect anyone knows, but this is not quite a famous unsolved problem. Is there any literature on this one? Dan Hoey Hoey@ETL.Army.Mil --- Newsgroups: rec.humor.d Followup-To: sci.med From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 24 Jul 91 21:17:36 GMT Subject: Re: Which one doesn't belong? c...@vaxb.acs.unt.edu (christopher williams) writes: >you have a cure for syphilis? maybe you should tell the rest of the world, eh? I tried, but Sir Alexander Fleming got there first. Dan --- Newsgroups: comp.lang.lisp, sci.math.num-analysis Followup-To: sci.math.num-analysis From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 29 Jul 91 22:32:44 GMT Subject: Re: random selection w/o replacement The key point here is to manage the non-replacement by exchanging the selected elements with elements at one end of the sequence. That way the unselected elements form a contiguous subsequence, which you can index into with (random number-remaining). That way, if your sequence is a vector, you take time linear in the number selected. If you have to do this a lot of times, you can use the vector over and over again. It just gets more and more randomized. And of course if you select all the elements, you've got a shuffle. (defun select-without-replacement (n eseq &aux (len (length eseq))) (dotimes (used n (subseq eseq (- len n))) (rotatef (elt eseq (random (- len used))) (elt eseq (- len used 1))))) >if the number of items you're selecting is << than the length of the >sequence, then the following is simple and probably okay: >(defun randum[sic]-elements (n eseq) > (do ((len (length eseq)) > (result nil)) > ((= n (length result)) result) > (pushnew (elt eseq (random len)) result))) The I'th element into result will take Theta(I + I^2/LEN) time on average, so the total time will be Theta(N^2 + N^3/LEN). Provided, of course, that ESEQ is a vector. >... This can be improved by doing the member test explic[i]tly, >thereby avoiding taking the length of result on each iteration.... Pretty minimal speedup, since pushnew (or member) has to look at the whole list anyway. >A better algorithm is to copy the sequence into an array (fast, no >garbage), randomize the array (slow?, no garbage), and then take the >first N values out of the array (fast, no garbage). As I've shown, you only need to randomize the part of the array you are going to use. >I tend to swap the 0th element with a random element a large number >of times.... Now that is just wrong. Worse, that is a common beginner's mistake for shuffling a deck of cards, and you should get over it before you start giving advice on the subject. Your method will randomize the first element of the array, but you will never randomize the rest of the array (unless LEN<=2). It's easy to see you can't get a random shuffle, because the the probability of each outcome is a terminating fraction in base LEN arithmetic. The way to shuffle a deck of card is to--guess what--select without replacement (until you reach the end then stop). The above function will do it. In some languages it's easier to collect the selected items at the beginning of the array, and that's a reader's exercise. But remember: if you keep calling random with the same argument, you should start thinking about how that has got to lose. Followups belong in an algorithms group: this is not language-specific. I guess sci.math.num-analysis is about it. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: comp.arch, comp.windows.x Followup-To: comp.arch From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 30 Jul 91 17:38:15 GMT Subject: Re: but EMACS was very efficient under ITS, MULTICS and even VMS g...@buitc.bu.edu (George J. Carrette) wrote: > The classic EMACS implementations made use of a concept called dynamic > echo negotiation, using system calls such as the VMS SYS$QIO with an > input buffer and a character-termination mask. g...@pdx007.intel.com (Andy Glew) replied: >In general, the tty driver might download an EMACS style keymap - as >in don't return to the user if just X is in the buffer, but do return >to the user if ESC X is in the buffer. How much state do you want? >Otherwise, you would unduly restrict keybinding actions - only certain >characters would terminate input. I would be really happy with a list of functions that promised to do self-insert and no other displayed operation. Then on each change of keymap emacs could send the tty driver a mask of the characters bound to those functions, with a maximum (so the end-of-line could be dealt with properly). That ought to deal with 90% of the problem. (Dvorakites and electric-shift-lock devotees fit into 10% of the other 10%. Actually, the former probably need to deal with the driver anyway). Dan Hoey --- Newsgroups: news.admin, news.groups Followup-To: news.admin From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 11 Sep 91 22:19:00 GMT Subject: Re: 101 Things to do at the start of an academic year ap...@soda.Berkeley.EDU (Shannon D. Appel) writes: >> Mental thought Physical action >> space is low, blow away rec.arts... cd ~news >> (ok, I'm in ~news/rec/arts) find . -type f -exec rm -f {} \; > SOunds like yet another argument for rec.sf.* rather than rec.arts.sf.*. Sounds like an awfully thin argument to me. Do you really expect the renaming to keep someone from deleting files in his sleep? Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: comp.lang.misc From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 17 Sep 91 21:35:49 GMT Subject: Re: References to Weak Pointers in Garbage Collection Systems? kel...@kickapoo.cs.iastate.edu (Kelvin Don Nilsen) writes: >A weak pointer is characterized by the following: > 1. if only weak pointers reference a heap-allocated object, the > object is garbage and should be reclaimed. > 2. if at least one strong (traditional) pointer references a > heap-allocated object, the object is not garbage. > 3. if both weak and strong pointers reference an object, > the object is not garbage. if garbage collection > relocates the object, both weak and strong pointers need > to be updated. It seems to me that this definition is missing the essential recursivity of garbage collection. For instance, if the strong pointers that reference an object are in that object itself, then that object ought to be garbage. Two objects that reference each other with strong pointers, yet are otherwise referenced only with weak pointers, ought also to be collected. I think we are looking at a system that recognizes garbage based on strong pointers, but also relocates the weak pointers that do not refer to garbage. Or is there really an example that benefits from the first behavior? Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Date: Mon, 11 Nov 91 17:45:36 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Rubik's Cube question Jeff Baggett (baggett@mssun7.msi.cornell.edu) asks on the sci.math newsgroup: 1. I am seeking a description of the group of symmetries associated with Rubiks cube. I have some ideas but they aren't particularly elegant. Can someone suggest a paper? Jeff, I have looked into this somewhat. As far as I know, the symmetries of the 3^3 cube are just the symmetries of the cube, but in larger sizes we can do better. The best way of looking at this is to imagine that there is a (N-2)^3 cube sitting inside your N^3 cube, and smaller cubes within, and you are trying to solve them all together. Suppose we address each cubelet of the N^3 cube using cartesian coordinates (x,y,z), where (0,0,0) is the center of the cube (for N odd) and no cubelets have any coordinate zero if N is even. The maximum absolute value of the coordinates is [N/2]. Then for 1<=I<=[N/2], there is a symmetry F[I]:(x,y,z)->(f(x),f(y),f(z)), where f(I)=-I, f(-I)=I, and f(x)=x otherwise. Then for 1<=I(e(x),e(y),e(z)), where e(I)=J, e(J)=I, e(-I)=-J, e(-J)=-I, and e(x)=x otherwise. These are symmetries of the cube group, and they map elementary moves to elementary moves (provided we take an elementary move to be a rotation of the slab of N^2 cubelets that have a particular nonzero value of a particular coordinate). Symmetries of the cube group that preserve elementary moves are useful in the study of local minima in the cube group. It turns out that if you only want to consider the outside of the cube (ignoring the (N-2)^3 cube inside) all of these symmetries are still present except F[[N/2]] and E[I,[N/2]]. I mentioned these symmetries in a note to the Cube-Lovers mailing list in 1983. I called E[I,J] evisceration, F[1] inflection, and F[[N/2]] exflection in that note (where I was dealing explicitly with only the 4^3). The discussion of the relation to local minima took place in 1980. Let me know if you'd like a copy of these messages. I ran into these symmetries earlier, though. They are symmetries of the N^3 tic-tac-toe board! I would not be surprised if they arise in some other connection in mathematics, but I have never run into them. They generalize into larger dimensions, as well. I've also taken the liberty of Cc'ing the Cube-Lovers list with this note. If you'd like to be on that list, you may ask of "Cube-Lovers-Request@AI.AI.MIT.Edu". Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Newsgroups: sci.med, misc.emerg-services, sci.chem Followup-To: misc.emerg-services From: hoey@zogwarg.etl.army.mil (Dan Hoey) Date: 12 Nov 91 16:06:52 GMT Subject: Re: Bad advice on Usenet (was Bad Science on McGyver?) lc...@andrew.cmu.edu (Lawrence Curcio) writes: >What is all this nonsense about only qualified persons administering >antidotes? If someone ingests CN, you use the people and materials at >hand. Those people should have elementary knowledge of procedures, but >waiting for a damned health professional to monitor hemoglobin is >idiocy. It depends on how toxic the antidote is. If you kill the patient with the antidote, when the patient might have survived a less risky treatment--or no treatment at all--that is the true idiocy. >In such a deadly situation, there is little to lose. Posting >advice to the contrary can only cost lives. Get real. If you get your medical training from Usenet, you are arguably brain dead to begin with. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Date: Thu, 12 Dec 91 10:29:04 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Rubik's cube dice tops ronnie@cisco.com (Ronnie Kon) writes: An original Sam Loyd puzzle involving the Rubik's cube has come into my hands; somewhat surprising, in that Sam Loyd died in the early years of this century, but no more so than the truly astounding circumstances by which the puzzle came to me, which I would detail if I believe that anyone were interested. Hmm. A likely story. We are challenged to find ``tops'', ... dice which are misspotted, by having only three different numbers on them, each appearing opposite to itself ... spotted 1-2-3, ... from a standard cube in 14 moves. Where he counts a half turn, a slice, and and a half-slices as one move each. I have found how this can be done in 13 such moves. I have some suspicion that it can be done in 12; I'll let you know. We are then challenged to convert this ... into 2-3-4 tops ... in only 3 moves. The second part can be solved by any person who achieves mastery of the cube. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Date: Fri, 13 Dec 91 14:50:03 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Big groovy cubes, revisited Tee Luns writes: ... one of the last posts in cube-mail-7 triggered something in me head. The suggestion was to use a fresnel saw to cut all the cubelets out of a single chunk of material.... Well, I'm glad that my silly ideas triggered something. Sometimes I wonder if they are as amusing to read as they were to write. ... why not a simple dovetail? Certainly a dovetail would do it. I guess when I got to sharpening the fresnel saw I didn't know when to quit. ... have the dovetail/cubelet pair separate, ... screw the dovetails (which are already in their grooves) onto the last couple of cubelets. Surprisingly enough, this is just how Rubik's Revenge is put together. One of the center cubelets (perhaps always on the blue side) has a screw that joins the outside of the cubelet to its dovetail. You can usually find locate it by the dimple in the colored sticker. If the dovetails go right to the surface, one has to be *VERY* careful.... The solution is to make the dovetail taper off at its ends.... This will lead to holes at the surface though, so the cube won't be too pretty. In the 7^3 and larger, they have to go through the surface, and even if they were squared-off dovetails they wouldn't match the color of the adjacent square except in the solved position. Unless of course we make the outer layers thicker, as Dale Newfield mentioned when we were discussing this back in May. A novelty with this approach though is that no centre is required. We could build a hollow 3x3x3 cube with face centres hollow, and see right through the cube.... But, if we had the smaller odd-sized cubes trapped inside, not only would they help hold the outer layers together, if we made the cubelets mostly transparent, we'd be able to see what we've had to imagine in the past. Now that'd be one heck of a puzzle. Wow, I want one! But I don't think the material really needs to be transparent, as long as the face center pieces are hollow. It would help let light in, though. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Date: Tue, 17 Dec 91 16:18:16 -0500 (EST) From: Dan Hoey To: Cube Lovers Subject: Re: Rubik's cube dice tops (Spoiler) Last week ronnie@cisco.com (Ronnie Kon) challenged us to find Rubik's cube patterns with dice pips for 1, 2, and 3 on the three pairs of opposite sides. He claimed it could be done in fourteen HST, where one HST is a turn of a face or center slice by 90 or 180 degrees. I responded that it could be done in thirteen HST. Here is how. I will use this opportunity to practice the enhanced Varga Rubiksong I described (unfortunately with many typos) on 22 Feb 90. The (only such) pattern is the composition of Four-Spot and Laughter. We have long known the processes ris-fos tis-fos, or (RL)^2 FB' (TD)^2 FB', for Four-Spot and fon-ron fon-ron fon-ron, or (FBRL)^3, for Laughter. When we compose them, the F and B moves combine and cancel to produce ris-fos tis-fi ron-fon ron-fon ron, or (RL)^2 FB' (TD)^2 F^2 (RLFB)^2 RL. This 14 HST process is presumably something like what Ronnie had in mind. But since this pattern commutes with ris, or (RL)^2, we can get the same pattern with the conjugate process fos tis-fi ron-fon ron-fon ran, or FB' (TD)^2 F^2 (RLFB)^2 R'L'. This uses only 13 HST. This is also the shortest process I know of in the normal metric: 18 QT, which is not so bad for the combination of two 12 QT processes. I suggested that perhaps 12 HST would be sufficient, but I have not found such an improvement. Nor do I know whether 13 HST is the best that can be done: it seems that proving 13 HST optimal would require examining about 160 million positions, almost as many as the 200 million it would take to prove 18 QT optimal. Dan Hoey Hoey@AIC.NRL.Navy.Mil ---