Newsgroups: geometry.research From: haoyuep@aol.com (Dan Hoey) Date: Wed, 16 Jan 2002 20:16:09 +0000 (UTC) Subject: Re: curiosity John Steinberger wrote: > Consider the following problem: you have two (countable, locally > finite, discrete) sets of points in the plane that have the same > density (d), call them the red points and the blue points.... > THE QUESTION: can you always match up the red > points with the blue points one-to-one such that there is an upper > bound M on the distances of red/blue pairs? It's not so surprising that the Euclidean answer is no. In one dimension, take the red points to be the even integers and the blue points to be the odd integers minus some infinite set of density zero. The deficit will add up inexorably. For more dimensions, take the Cartesian product with Z^(n-1). I'm afraid I haven't any good ideas about the non-Euclidean cases. Dan Hoey haoyuep@aol.com --- Newsgroups: geometry.puzzles From: haoyuep@aol.com (Dan Hoey) Date: Mon, 18 Feb 2002 19:27:52 +0000 (UTC) Subject: Re: Cutting a hexagon into 6 congruent pieces > Can someone PLEASE help me with this? Here's the question > (as written on the assignment page): No, thank you. Assigners of problems should either provide help or forbid it. And if they do neither, they should at least direct requests for assistance not to include "puzzles" groups, which suffer from the contrasting aims of our intellectual interest, your education, and other assignees' recognition of their accomplishment. That's my view, and it may or may not be popular, but I decline to debate it; I'm just not that interested. I want to address the mathematical point implicit in the misstatement of your problem. > It's my birthday and I pride myself in being original, but I > need your help figuring out how to divide [up] my birthday cake. > The cake is a HEXAGON and the pieces need to be congruent, > so that nobody complains. The setter (or transcriber) seems to have forgotten that not all hexagons are regular. I expect that many hexagons cannot be divided into six congruent pieces, but I don't have an example-- anyone care to give one (with proof)? An extended question is to characterize the hexagons that can be so divided. We might even extend this to six-segment closed paths that may be permitted to intersect themselves, so that "divisions" like I've drawn below might occur (where I hope you can figure out what happens at the (#) marks, which are too hard to draw in ASCII). _______ \ : / \ : / \:/ X /:\ # : # / `*' \ ______/#######\______ \ .-/ \-. / \' / \ `/ \/ \/ Enjoy! Dan Hoey haoyuep@aol.com --- Math Forum From: haoyuep@aol.com (Dan Hoey) Date: Mar 7, 2002 8:47 AM Subject: Re: generalized integer puzzle The question of finding n for which a_1 + a_2 + ... + a_n = a_1 . a_2 . ... . a_n has exactly one solution in positive integers is addressed in R. K. Guy, _Unsolved Problems in Number Theory, 2d ed_ under the heading "Sum Equals Product." I think it's item D28. If I recall correctly, all such n under 50,000 or so are known (There are fewer than ten. Either 114 or 144 is one of them, and the other has been published as a typo.) but it is not known whether there are more. I haven't looked to see if it seems likely there would be more, but I tend to doubt it. Dan --- Newsgroups: geometry.puzzles From: haoyuep@aol.com (Dan Hoey) Date: Sun, 31 Mar 2002 17:18:42 +0000 (UTC) Subject: Re: Show your workings ....... pleeeeeeeeeease! mak wrote: > Consider a triangle ABC below, we draw a line from B to AC > meet at E, such that angle EBC is 30 deg and angle EBA is > 15 deg. And we draw a line from C to AB meet at F, such > that angle FCB is 25 deg and angle FCA is 10 deg, (all > angle figures as shown) can anybody find the angle BEF?? > /\A > / \ > / \ > / \E > / . \ > / . \ > F/. . \ > / . . \ > / . . \ > /15. . 10\ > / . . \ > /. 30 25 . \ > B ---------------------- C which I suppose could be trig homework, or some sort of exam or contest question. I don't need your workings, but maybe you could list your sources. If you came up with the puzzle on your own, I'd think you'd want to claim the credit. Ely wrote: > BEF is 25 degrees. which is not correct. Guess? Troll? Shill? Homework trap? Hard to tell. Baz wants to know: > Can the answer of 25 degrees be obtained by construction > and the application of geometretical principles or is the > only way of getting the answer to draw the triangle and > measure it (in which case it isn't really a problem but a > draftsman's exercise).... Well, isn't a draftsman's exercise a problem? But it would take a pretty bad draftsman to get 25 degrees--I was able to come up with a diagram showing the answer between 30 and 32 degrees, and that's without a protractor. I got a highly accurate answer by using the law of sines (twice) and the law of cosines. I don't know if you call them geometrical principles. I somewhat doubt there's a closed-form solution not using inverse trig functions or the like. Mary Krimmel wrote: > Pleeeeease tell us what the problem is! > I have no idea what you're asking for! Well, Mary, if you're really trying to find out what geometry-puzzles posts are referring to, you might learn to use http://www.mathforum.com/discussions/, since some posts there don't show up on search engines nor your server. If you just want to scold people for not including enough context in their followups, I don't find posting repeated complaints in the newsgroup to be all that netiquettually correct either. Dan Hoey haoyuep@aol.com --- Math Forum From: haoyuep@aol.com (Dan Hoey) Date: Jun 10, 2002 2:39 PM Subject: Re: 64 bit permuation trick? by Phil Carmody Phil Carmody wrote: > David Kastrup wrote: > > uint64 rotate90(uint64 a) > > { > > a = (a&0xf0f0f0f000000000)>>32 > > |(a<<4&0xf0f0f0f000000000) > > |(a>>4&0x000000000f0f0f0f) > > |(a&0x000000000f0f0f0f)<<32; > > a = (a&0xcccc0000cccc0000)>>16 > > |(a<<2&0xcccc0000cccc0000) > > |(a>>2&0x0000333300003333) > > |(a&0x0000333300003333)<<16; > > a = (a&0xaa00aa00aa00aa00)>>8 > > |(a<<1&0xaa00aa00aa00aa00) > > |(a>>1&0x0055005500550055) > > |(a&0x0055005500550055)<<8; > > return a; > > } > Worthwhile optimisation. Still far short of the LUT though. Would you be interested in trying: uint64 rotate90(uint64 a) { uint64 m; m = (a^(a>>32)) & 0x00000000ffffffff; a ^= (m|(m<<32)); m = (a^(a>>28)) & 0x00000000f0f0f0f0; a ^= (m|(m<<28)); m = (a^(a>>16)) & 0x0000ffff0000ffff; a ^= (m|(m<<16)); m = (a^(a>>14)) & 0x0000cccc0000cccc; a ^= (m|(m<<14)); m = (a^(a>>8)) & 0x00ff00ff00ff00ff; a ^= (m|(m<<8)); m = (a^(a>>7)) & 0x00aa00aa00aa00aa; a ^= (m|(m<<7)); return a; } Dan Hoey haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 15 Jun 2002 17:33:38 GMT Subject: Re: Quickly find when it gives a Square Mike writes: > Many thanks to all those that replied.. but factoring would cost me > more than I would save. I don't think so. Finding a solution to your problem _is_ factoring, in its essence. You can factor by trial division (as you have done), or you can factor by trial division with some modular constraints (as in Oscar Lanzi's suggestion) or you can use other methods for factoring. But you might as well realize you are factoring, so you can use some of the extensive information available about how to factor your number in the best way you can, and--conceivably if not likely-- apply the insights of your problem to get new results in some important mathematics. Your problem is to find, given integers a and b , a solution in integers to y^2 = x^2 + ax + b . Modify this to a^2 - 4b = 4x^2 + 4ax + a^2 - 4y^2 = (2x+a)^2 - (2y)^2 = (2x+a+2y) (2x+a-2y) . So (2x+a+2y)(2x+a-2y) must be a factorization of a^2-4b. We can write a^2-4b = m(m+n), so 2x+a+2y = m+n 2x+a-2y = m , which yields x = (2m+n-2a)/4 y = n/4 . This shows us that we need a factorization where n == 0 (mod 4) and m == a (mod 2) . For instance, when a=200, b=-147, we must factor 40588 as the product of two numbers, both even, differing by a multiple of four. The positive possibilities are factorization m n x y 2 . 20294 2 20292 4974 5073 146 . 278 146 132 6 33 Note that from x and y we can immediately recover the factors m and m+n. So any method of solving your problem is effectively a method of factoring a^2-4b. Dan Hoey haoyuep@aol.com --- Math Forum From: haoyuep@aol.com (Dan Hoey) Date: Jul 4, 2002 9:41 PM Subject: Re: complexity of pentominoe-like tiling problems David Bernier asks: > How complex is the decision problem for tiling-problems using a > finite (irregularly-shaped) set or collection of pieces cut-out > from a square-grid along horizontal and vertical grid lines? and proposes an answer based on the SET PARTITION problem (a close relative to KNAPSACK). The problem is that these problems are not NP-hard in the "strong sense". That is, the problem is solvable in time polynomial in the sum of the numbers involved (rather than the sum of their logarithms, in which the time is exponential). But tiling problems are typically represented in size proportional to the number of squares to be tiled, since instances are not restricted to the simple shapes that can be represented logarithmically. So in the usual sense, the example given is solvable in polynomial time. For a better construction, see "Hard Tiling Problems with Simple Tiles" by Cristopher Moore and John Michael Robson, at http://arxiv.org/abs/math.CO/0003039 . The abstract begins: It is well-known that the question of whether a given finite region can be tiled with a given set of tiles is NP-complete. We show that the same is true for the right tromino and square tetromino on the square lattice, or for the right tromino alone.... but even if you didn't know the result well in the first place, their construction will be enlightening. Dan Hoey haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 11 Jul 2002 04:20:06 GMT Subject: Re: Rationals with Only 1's and 2's in Continued Fraction pha...@ghs.org (Paul D. Hanna) wrote: > Here is another sequence of rationals I cooked up (see sequence > below). These are the rationals >= 1 whose continued fractions > consist of only 1's and 2's. Yes, that's the _set_, but it took me a while to figure out what the _sequence_ was--i.e, what order was being imposed on the set. From examination, it seems: q(F(n)+m) = 2 + 1/q(F(n-2)+m) for 0 <= m < F(n-3), and q(F(n)+m) = 1 + 1/q(F(n-2)+m) for F(n-3) <= m < F(n-1). The first rule consists of prepending "2" to the terms of the continued fraction, and the second consists of prepending "1". This sequence has the property that the term-sums of the continued fractions are nondecreasing. I'm not taking any stand on whether or not this is the most natural ordering of the set. But: > Can anyone derive solutions to the following related questions? > (1)What is the GEOMETRIC MEAN of this sequence of rationals? > (2)What is the ARITHMETIC MEAN of this sequence of rationals? It's easy to see that the arithmetic mean does not exist. For note that q(F(n)+m) = 1 + q(F(n)-F(n-3)+m) for 0 <= m <= F(n-3) (*). Thus a tail of the sequence consists of terms one greater than in the previous tail. Since this tail is about 1/(phi^3) of the terms, it will cause a repeated drift in the mean that does not approach zero. To be precise, let us define the finite sums s(n) = q(0)+q(1)+q(2)+...+q(n-1). The difference (*) implies that s(F(n)) - s(F(n-1)+F(n-4)) = s(F(n)+F(n-3)) - s(F(n)) + F(n-3) If the limits s(F(n))/F(n) -> a, s(F(n)+F(n-3))/(F(n)+F(n-3)) -> b, exist as n->oo, then this implies a.F(n) - b.(F(n-1)+F(n-4)) = b.(F(n)+F(n-3)) - a.F(n) + F(n-3) 2.F(n).(a-b) = F(n-3) a-b = F(n-3)/(2 F(n)) -> 2 phi^-3 = 4 phi - 6 ~~ 0.472. So if these limits exist, they are different. The limits would have to exist and be equal for the mean to exist. For the geometric mean, we can do something similar with logarithms. I'm interested in what the lim sup and lim inf of the means might be. Dan Hoey Posted and e-mailed --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 13 Jul 2002 13:04:28 GMT Subject: Re: Rationals with Only 1's and 2's in Continued Fraction pha...@ghs.org (Paul D. Hanna) wrote: > ... the sequence of fractions > is bounded, each element always falling within the interval > (Phi,1+sqrt(2)) = (1.61803398875, 2.41421356237). > and later clarified > The terms of the sequence of fractions are instead bounded > by the interval: [1,3) > yet the terms do approach (Phi, 1+sqrt(2)) as the limit, > which is what I meant above. Now I've figured out what you are doing. You have assumed that the minimum and maximum irrational continued fractions with terms of 1 or 2 are [1,1,1,...] = phi and [2,2,2,...] = 1+sqrt(2). This would be the case if a continued fraction were a monotone increasing function of its terms. But continued fractions are monotone increasing in their first, third, fifth, etc. terms and monotone _decreasing_ in their second, fourth, sixth, etc. terms. So the minimum is [1,2,1,2,1,2,...] = (sqrt(3)-1)/2 ~~ 1.366 and the maximum is [2,1,2,1,2,1,...] = sqrt(3)+1 ~~ 2.732. In the latter quote you use the word "term" for what I believe are commonly referred to as the "partial quotients." The terms are all 1 or 2. The partial quotients are the rational numbers represented by these continued fractions. > At any rate, the fact that the terms are bounded, even with the > discontinuous limiting attractors that are found in this sequence, > insures that an 'average' exists. That much is true. No. For the average (arithmetic mean) to exist, the limit of Sum[0<=ioo. For many bounded sequences, the average will fluctuate with an amplitude that does not approach zero, but with ever-decreasing frequency. Consider sin(log(n)) for instance. Or 0,1,0,0,1,1,0,0,0,0,1,1,1,1,...., the second most significant bit of 2,3,4,.... These sequences do not have arithmetic means. The second one has lim inf 1/4 and lim sup 1/2. > WHAT IS THE MOST NATURAL ORDERING? > I do not know if this sequence is the "most natural ordering" of > the set of fractions whose continued fractions consist only of > 1's and 2's, but I feel that it is. I'm not going to take a stand on the "most natural ordering"--I honestly don't have a candidate. I only raised the issue because the existence of an arithmetic mean and its value depends on the ordering you take. By re-ordering the sequence, the [lim sup,lim inf] interval can be made to be any subinterval of [(sqrt(3)-1)/2,sqrt(3)+1]. Dan Hoey haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 15 Jul 2002 22:40:37 GMT Subject: Re: Rationals with Only 1's and 2's in Continued Fraction pha...@ghs.org (Paul D. Hanna) wrote: > I still maintain that the limit exists: > limit_{n->oo} (1/F(n-1)) sum_{k=F(n)}^{F(n+1)-1} q(k) > which is the limit of the average of the F(n-1) number of terms of the > sequence that are found between the F(n)-th term and the (F(n+1)-1)-th > term of the sequence. I don't have any reason to doubt that the limit you give exists, but the arithmetic mean would be limit_{n->oo} (1/n) sum_{k=0}^{n-1} q(k) which does not converge. I outlined a proof of the mean's divergence in my first message, but let's try again. An easy induction shows that all the continued fractions with at least three terms lie in the interval [4/3, 11/4]. This implies that all the continued fractions with at least four terms lie either in [19/14,23/13] (if they are of the form 1+1/x) or [33/14,36/13] (if they are of the form 2+1/x). In your ordering of the sequence, the terms from q(F(n)) to q(F(n)+F(n-3)-1) lie in the second interval, and are at least 33/14. The terms from q(F(n)+F(n-3)) to q(F(n+1)-1) lie in the first interval, and are at most 23/13. The problem here is that sequence elements lie in two disjoint intervals, and the arithmetic mean cannot be in both of them. Whichever interval does not contain a proposed arithmetic mean can interfere with the convergence to that mean, if the runs of sequence elements in that interval are too long. I'll make explicit just what is too long. In general, suppose we have a sequence s(n) that has an arithmetic mean A = limit_{n->oo} (1/n) sum_{k=0}^{n-1} s(k). I will prove that for any e > 0, there exists integer M such that: If m > M, then there exists k with m <= k < (1+e)m and s(k) M. Then by assumption there is some m > M with s(m), s(m+1), ..., s([(1+e)m]) all greater than A+e. sum_{k=0}^{m-1} s(k) > m(A-e^2), sum_{k=m}^{(1+e)m-1} s(k) > em(A+e), so sum_{k=0}^{(1+e)m-1} s(k) > m(A+e^2), which violates | A - (1/m) sum_{k=0}^{m-1} s(k) | < e^2, QED. A similar argument shows that we can take M such that also If m > M, then there exists k with m <= k < (1+e)m and s(k)>A-e. Now if the sequence q has an arithmetic mean A, take e < min( max(A-23/13, 33/14-A) , phi^-3 ) . Either A < 33/14, A > 23/13, or both. if A < 33/14, take M large enough that F(n)+F(n-3) > (1+e) F(n) for F(n)>M. Then there is an integer k with F(n) <= k < F(n)+F(n-3) and q(k) < A+e <= 33/14. This contradicts the observation that all such k should have q(k) in [33/14,36/13]. A similar contradiction is found if A > 23/13. I hope I haven't messed up the argument here. I'm sure of its essential correctness, but if there is anything that doesn't make sense let me know. Dan Hoey haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 20 Jul 2002 05:07:12 GMT Subject: Re: Fun With 3-SAT "Russell Easterly" writes: > Fun With 3-SAT > I would appreciate any comments on the worst case > complexity of the following algorithm. Russell, You've given us a dozen or so algorithms for NP-hard problems over the last several years. Isn't it about time you learned to analyze their correctness and complexity? They've all been incorrect, or have used exponential time, or both. Even the ones that you only claim "significantly reduce the difficulty of solving some cases" don't seem terribly good for the hard cases, compared to the well-known algorithms. > I haven't studied the 3-SAT problem much but it seems to be > equivalent to converting an expression in CNF to DNF. Read a book! Converting an expression from CNF to DNF can produce exponentially long output, so of course there can't be a polynomial time algorithm for it. Deciding CNF satisfiability is equivalent to deciding whether or not the DNF version has any clauses at all. Each disjunct in a DNF formula is a complete satisfying assignment of all pertinent variables. Your later idea: > But I choose from the clauses that have the fewest number > of variables. If the clauses I am choosing from have only one > variable left that can be assigned, then a wrong choice > doesn't cause exponential growth because there are no > other choices to consider. is very well known, and you will run across it over and over if you (free clue --->) read some papers on the subject (<--- free clue). Yes, any variable that appears alone in a clause can and should be eliminated immediately. Ditto any variable that never appears negated. Ditto unnegated. Everyone does this--at least everyone who knows what they are doing. If you could make it happen often enough, you would win. But you don't have any idea how often you can make it happen. Should that make you optimistic? It's an open problem--nobody knows how fast they could eliminate variables with the best method. But every time they analyze a particular method, it's exponential. You've got an un-analyzed method. What do you expect? If you could improve on, say, the O(1.35^c) algorithm of Beigel and Eppstein (arXiv.org:cs.DS/0006046) you might have something. Even if you can't take existing work as a starting point, _understanding_ the previous work could help you evaluate your own approach. > What I would like to figure out is how often I can expect > the "shortest" clauses to have two or fewer assignablef variables. I can tell you that. You can expect at least one clause with two or fewer variables almost every time you make an assignment. The exception is when you have managed to isolate some subset of variables by satisfying all the 3-clauses that connect them to the rest of the problem. But when you separate the variables that way it would be better to solve the parts separately anyway. And next time, when you have reassigned the early variables, those formerly satisfied clauses will turn into 2-clauses attached to the fragment. Your algorithm as stated is going to make its first assignment, yielding some 2-clauses, and then you are going to grind away assigning values to variables mostly based on their appearance in the 2-clauses. You probably aren't going to run out of 3-clauses very fast, so you won't quickly get into a 2-SAT problem (at which point which you should _not_ use your algorithm. Use a polynomial time 2-SAT algorithm). After all of that, when you get down to a small problem that has no satisfying assignment, look at how many assignments you made to get to the 2-SAT problem. Raise 1/2 to that power, and that is an (overoptimistic) estimate of how much of the task you have accomplished so far. If it's some fixed fraction--say, 1/10 of the variables--you still have an exponential algorithm. Why don't you look at what your algorithm is like on a 2-SAT problem that has been augmented with a few 3-clauses. If you can figure out why your algorithm loses on 2-SAT, and why a few 3-clauses make a 2-SAT problem hard, you may start realizing where you stand. > I have tried to come up with a worst case > scenario, but so far, I haven't found any bad ones. > Of course, I am still just looking at problems with > a small number of variables. But unless you start understanding what constitutes progress in a general scenario, you have no way of estimating how good your approach is. So you can create some 2-clauses--what does that buy you? You make progress, you lop off big pieces of the solution space, you drop some variables, but until you can show how much time you take to drop more than O(1) variables, and how many subproblems you might have to solve, you haven't figured whether your approach is any good. And you know how what your guesses are worth. I'm not saying you shouldn't play around with ideas for solving NP-hard problems. But you have repeatedly mistaken your inability to measure your progress for evidence that it is immeasurable. Isn't it time to learn something about measuring, so you can tell a good idea from a bogus one on your own? It's like someone looking for gold in a cave, who has fallen into a hole a dozen times. Get out of the cave and go find a flashlight! It's not as exciting as looking for gold, and you won't get rich and famous for finding a flashlight, but it could make the difference between being a prospector and being a fool in a cave. Even prospectors fall into holes, but they learn, and fall less and less as time goes on. Some of them even get rich and famous. Cave fools never learn, and eventually they make a name for themselves--as better left in their hole, because any effort spent pulling them out is wasted. Have you ever seen cave fools on sci.math, sprinting into that cave down well-worn passageways, diving into their hole over and over again, gloating over the gold that is sure to be just out of reach? Is that what you want to be? You're not a cave fool yet, but it's the direction you're heading. You have the ability to do better work, you just need to stop giving up the hard parts and declaring success. That trick doesn't work. Dan Hoey haoyuep.aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 20 Jul 2002 05:14:34 GMT Subject: Re: denumerability of the rationals Robin Chapman wrote: > Dave Seaman wrote: > > One method that has been discussed in sci.math a few times is > > described in "Recounting the Rationals" by N. Calkin and > > H. S. Wilf, _American Mathematical Monthly_, Vol. 107, No. 4 > > (April, 2000), p. 360. Their sequence begins > > 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ... > Herb Wilf recently informed me that Moshe Newman had noticed > that this sequence obeys an extremely simple recurrence: > a_{n+1} = 1/(1 + 2[a_n] - a_n). Also noticed by John Conway, who mentioned that the recurrence extends backward to cover Q U {oo}, with a_{-1-n} = -1/a_n . Also, if you write a nonnegative rational as a continued fraction with an odd number of terms, a_n = d + 1/(e + 1/(f + 1/(g + ... 1/z))), then the binary notation for n is (1^z)...(0^g)(1^f)(0^e)(1^d), where ^ denotes repetition. Dan Hoey haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: 21 Jul 2002 01:28:26 GMT Subject: Re: Rationals with Only 1's and 2's in Continued Fraction Monday night I, haoyuep@aol.com (Dan Hoey) wrote: >I hope I haven't messed up the argument here.... But of course I had. Here's a correct proof of the lemma I used in my proof that Paul Hanna's ordering of these numbers doesn't have an arithmetic mean. Lemma: Let {s_0, s_1, s_2, ...} be a sequence with an arithmetic mean A = limit_{n->oo} (1/n) sum_{k=0}^{n-1} s_k. Then for any e > 0, there exists integer N such that for all n > N, A+e > min_{n <= k < (1+e)n} s_k. There's probably a neater way of stating the lemma with lim sup, but I'll settle for this. Proof: First, note that the result holds for the sequence {s_0, s_1, s_2, ...} exactly when the result holds for the sequence {s_0-A, s_1-A, s_2-A, ...}, whose arithmetic mean is zero. So without loss of generality, let A=0. Second, it suffices to prove this for e<2 , since that implies the result for larger e. So given 2>e>0, let q=e^2/(4-2e) and take N such that for all n>N, q < | (1/n) sum_{k=0}^{n-1} s_k | . Increase N if necessary so that N>2/e as well. For n > N let m=[(1+e)n] and t=min_{n<=k (1+e)n-1 = (1+e/2)n + (e/2)n - 1 > (1+e/2)n, since ne>Ne>2. Since the minimum can't exceed the mean, t <= (1/(m-n)) sum_{k=n}^{m-1} s_k. Furthermore, sum_{k=n}^{m-1} s_k = (sum_{k=0}^{n-1} s_k) - (sum_{k=0}^{m-1} s_k) < nq + mq, as guaranteed by m,n > N. Combining these two equalities yields t < (m+n)q/(m-n) < ((1-e)n + n)q / ((1-e/2)n - n) = (2-e)q / (e/2) = e, because q=e^2/(4-2e) . So t < e, QED. Dan Hoey haoyuep@aol.com --- Math Forum From: Dan Hoey Date: Sep 21, 2002 9:38 PM Subject: Re: Covering number of hypergraph On 21 Aug 2002, ali saman tosun wrote: > Can a 24-uniform 146-regular hypergraph with 576 vertices have a > covering number <= 48 ? Minimum Vertex Cover of hypergraphs is > NP-complete and approximation algorithm tells me covering numver > >=24. I need answer to above question. 24-uniform means all > hyperedges have 24 vertices on them. 146 regular means each vertex > has 146 edges adjacent to it. Covering number is the minimum number > of vertices such that all edges have one of the vertices on them. Yes, but it's easier to show one with covering number exactly 24. Take the vertex set AuB where |A|=24, |B|=552. Construct a 23-uniform 146-regular hgraph (B,E). This easy to do by partitioning B into 24 blocks of 23 elements, then creating 145 variants of that partition, taking care not to duplicate any blocks. Now take the hgraph E' = {{A_e} u e : e in E}, where vertices A_e are taken from A, using each element 146 times. The hgraph {AuB,E'} is of the required form, and A is a cover. The NP-completeness result is not very relevant for finding a hgraph of a particular type, but rather for finding the cover given a hgraph that has been designed to make the cover hard to find. Of course, any 24-u 146-r 576-v hgraph with covering number 24 must be an instance of the construction I've outlined. But in most cases you should be able to find the cover fairly easily by looking for pairs of vertices that never appear in a hedge. Elements of the cover appear in at least 23 such pairs, while other elements usually appear in few or none. Dan Hoey haoyuep@aol.com --- Newsgroups: sci.math From: haoyuep@aol.com (Dan Hoey) Date: Wed, 2 Oct 2002 13:30:46 +0000 (UTC) Subject: Re: Group pairing problem On 01 Oct 2002, karin wrote: >Maybe you can tell a little more about your "group". Is it an >actual group with multiplication? I don't know what you mean by >"symmetry-nonequivalent" and "using the symmetry". It might be >possible to give an answer if you provide some details. Hauke describes his group as the permutations on [Aa][Bb][C] together with swaps of Aa and of Bb. This is more easily recognized if we replace [C] with a pair [Cc] that is swapped in some way determined by the rest of the permutation. If we consider the pairs to be three orthogonal axes and the swaps to be reflections that invert the sense of those axes, then we get a 24-element subgroup of the group of symmetries of a cube. There are three possibilities: C, the group of direct symmetries of the cube, A, the group of symmetries that induce an even permutation of the faces, and H, the symmetric difference of A and C. I'll mention that C and A are isomorphic to S_4, the group of all permutations on four letters. I'm sure H has a well-known isomorph, too, but I forget what it is. In general, we consider a pairing A={{a1,b1},{a2,b2}, ..., {ak,bk}} to be "symmetry-equivalent" to all pairings {{r(a1),r(b1)}, {r(a2),r(b2)}, ..., {r(ak),r(bk)} for r in some group G of permutations {a1,a2,...,ak,b1,b2,...,bk}. Presumably the symmetry group G is intended to be the same as original group whose elements are being permuted. Dan Hoey haoyuep@aol.com --- Math Forum From: Dan Hoey Date: Nov 5, 2002 7:41 PM Subject: Re: # Adjacent Pairs In Permutations Both Odd... Leroy Quet wrote: >> >Consider all of the m! permutations of {1,2,3,4,...,m}. [snip] >> >the TOTAL number of occurrences of adjacent elements both >> > being odd in all of the permutations is: [snip] >> >Therefore, IF true, the number of opposite-parity pairs >> >grows much faster than the number of same-parity pairs. [snip partial retraction] I haven't followed all the equation-crunching (and I certainly sympathize with the problem of the fiddly little errors, but I can give you a short answer based on group theory. First, I must say that "adjacent elements both being odd" in a permutation is something that should be defined. If a permutation is a function, then under the usual definitions it is a set of ordered pairs that have no canonical structure of adjacency or parity. I think you mean to count the number of pairs (p,i) where p is a permutation from S_m, i is an integer from {1,2,...,m-1}, and p(i) and p(i+1) are both odd (resp. both even, of the same or opposite parity). If that's true, we can answer the problem by saying that the number of odd adjacent pairs is exactly what we would not find surprising. The way to do this is to define K(i,j,k) = { p in S_m : p(i)=j, p(i+1)=k } . Group theory tells us that the permutations in K(i,i,i+1) form the subgroup PF(S_m,{i,i+1}) of S_m, consisting of those permutations that fix the set {i,i+1} pointwise. Furthermore, for every pair of unequal elements j,k in {1,2,...,m}, K(i,j,k) is a coset of the subgroup K(i,i,i+1). Thus every K(i,j,k) has exactly the same size, m!/binomial(m,2). Summing over all pairs of distinct odd (resp. even) j,k and all appropriate i, we conclude that the ratio of odd to even adjacent pairs in permutations is the same as the ratio of odd to even among the pairs of same-parity distinct integers in {1,2,..,m}. Dan Hoey haoyuep@aol.com --- Date: Wed, 13 Nov 2002 14:39:51 -0500 (EST) To: Richard Guy , James Propp Cc: math-fun@mailman.xmission.com From: Dan Hoey Subject: Re: [math-fun] seven James Propp writes: > Does the group of order 168 shed any light on the curious fact that > the map > (x,y) |-> (y,(y+1)/x) > (from C(x,y) to itself) is of order 7? > (Another way of stating this fact is that the sequence x,y,(y+1)/x, > ((y+1)/x)+1)/y,... satisfying a(n+1) = (a(n)+1)/a(n-1) is periodic > with period 7. This sequence is usually attributed to someone named > Lyness, but I don't know why Lyness studied it.) > Jim Propp Are you sure? I get x, y, (y+1)/x, (x+y+1)/(xy), (x+1)/y, x, y, ... with period 5. Cute, the way it follows the same rule forwards as backwards. But of course the rule a(n)+1 = a(n+1)a(n-1) is symmetric. Dan --- Date: Wed, 13 Nov 2002 15:46:55 -0500 (EST) From: hoey+l@aic.nrl.navy.mil To: math-fun@mailman.xmission.com Subject: [math-fun] Re: seven Jim Propp wrote: > My mistake; as Dan Asimov pointed out, the sequence has period 5. That was Dan Hoey, not that it matters. > Here are the true facts I should have asked about (neither of which > involves the number seven): > 1) The map (x,y) |-> (y,(y+1)/x) is of order 5; > 2) The map (x,y,z) |-> (y,z,(y+z+1)/x) is of order 8. Also the map (x,y) |-> (y,y/x) is of order 6. Is there any c other than 0 or 1 for which (x,y) |-> (y,(y+c)/x) has finite order? Dan Hoey@AIC.NRL.Navy.Mil --- Date: Wed, 20 Nov 2002 15:50:17 -0500 (EST) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: Re: [math-fun] Steven Krantz's review of A New Kind of Science I'm amused by Krantz's report that Wolfram tells us that he has entered one hundred million keystrokes on his computer in the past ten years by way of creating the scientific work that we now read[1]. and the footnote [1] If you send twenty brief e-mail messages per day, you will find that you enter over thirty-five million keystrokes in ten years. If you do things like write books or articles, edit journals, conduct professional correspondence, write reviews, you may find that you actually break Wolfram's keystroke record. Since computer programming and research are also keyboard- intensive activities, I can't help musing on how many keystrokes were entered by the researchers whose results Wolfram has reported. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Date: Thu, 21 Nov 2002 08:54:51 -0500 (EST) From: Dan Hoey To: Richard Guy , math-fun@mailman.xmission.com Subject: Re: [math-fun] 20/11/02 Richard Guy wrote: > So is 02-11-20, and more logical, and consistent > with an agreement signed by almost every country > in the world a little over a quarter of a century > ago, even including the US at that time.... Indeed, it is self-consistent in the sense advocated by Danhy Cohen in IEN137, "On Holy Wars and a Plea for Peace". While I notice that the note is dated 1 April 1980 [sic], I believe the case he makes for endian consistency is sincere. Also, I note that 02-11-20 refers to the same date whether we use the standard form (year=02, month=11, day=20) or the self-consistent little-endian notation (day=02[le], month=11[le], year=20[le]). Of course, the year is more properly written "2002" (or "2002[le]") so the really neat dates start almost eight years from now. Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Date: Thu, 21 Nov 2002 19:16:32 -0500 (EST) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: [math-fun] Multiply-gendered humanitarians Thanks to Ed Pegg for reminding me of the somewhat more difficult questions about BINGO. The game of BINGO comes in various flavors. In the one I know, each player is supplied with a 5x5 board. The first column is filled with five different numbers drawn at random from {1,2,...,15}, the second column from {16,...,30}, and so forth, except that the center square is marked out. A random number generator supplies numbers from 1 to 75, and when a number appears on a board, the player marks out that square. The first player to get five marks in a row vertically, horizontally, or diagonally wins. We assume that each board is equally likely, though that can't be true--with over 552 septillion possible boards, only a small fraction of them have ever been printed! Also I don't know whether the bingo-printing industry prints new boards all the time. It's possible they have a relatively small set of boards they print over and over. Do any funsters know? A second question: After N numbers have been drawn, what's the probability you have five in a row? I don't have an easy answer, but somehow I suspect that in the intersection of math funsters and generating funcsters there should be one. And a question that Ed passed on from Paul Stephens: Suppose we have a side bet on which of the 12 lines will be filled by on the winning board (and in a small number of cases, whether the winner has multiple lines). What are the odds on this bet? How does it vary as a function of the number of players? There are at most five equivalence classes of lines: center horizontal(1), off-center horizontal(4), center vertical(1), off-center vertical(4), and diagonal(2). Is the distribution for diagonals the same as for the center horizontal? I'm almost sure of that, but somehow not satisfied. Is the board symmetry group of order 32, or larger? Does this interact in any interesting way with S_75? Dan Hoey@AIC.NRL.Navy.Mil --- Date: Fri, 22 Nov 2002 10:17:15 -0500 (EST) From: Dan Hoey Subject: Re: [math-fun] Multiply-gendered humanitarians To: math-fun@mailman.xmission.com About Bingo, I wrote: > << > There are at most five equivalence classes of lines: center horizontal(1), > off-center horizontal(4), center vertical(1), off-center vertical(4), and > diagonal(2). Is the distribution for diagonals the same as for the center > horizontal? > >> And Dan A. responded: > ... If the only question is Find the probability P(X;n) that line X > is filled after n draws, then there are only 2 relevant categories > for X: those that need 5 matching draws, and those that need only 4. I was a little fuzzy on the question last night. Try this: I want to find P_1(X;n), the probability that line X is filled on draw n _and_ that no line was filled after n-1 draws. The other question I'm asking is P_k(X;n), the probablity that line X is filled on one of k boards on draw n, and that no line was filled on any of the boards before that. Now what are the equivalence classes for X? Dan Hoey Hoey@AIC.NRL.Navy.Mil --- Date: Tue, 3 Dec 2002 12:00:32 -0500 (EST) From: Dan Hoey To: Math-fun@mailman.xmission.com Subject: Re: [math-fun] Square (& other) chains and necklaces. Dan Asimov wrote: > Nice example! Now suppose every vertex is required to have finite > valence. Then I think this slight modification of Mike's example > will still serve as a graph where every {1,...,n} has a Hamiltonian > path, but not {1,2,3,...}. (This is a slight modification of Dan's graph.) 4--3--5--7--9---11--- | /| /| /| / | / ... |/ |/ |/ | / | / 1--2--6--8--10---12-- Now suppose we require Hamiltonian cycles for every {1,...,n}. Is there then a Hamiltonian path for N (there can't be a cycle). Suppose we require Hamiltonian cycles for every {a, ..., b} for a,b in Z? Can we then find a Hamiltonian path through Z? Dan (not that Dan, this Dan) Hoey@AIC.NRL.Navy.Mil --- Date: Tue, 3 Dec 2002 14:05:06 -0500 (EST) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: Re: [math-fun] infinite paths & cycles Marc LeBrun wrote: > Only if we insist that everything be FINITELY connected are these > infinite hairpins a problem. But then it kind of begs the question > whether the infinite graph itself is "connected" in the first place. The only kind of graph connectedness I know of is finite. If you take the adjacency graph of (-1/2)^n, n=0,1,..., then you get two infinite paths with a limit point of zero, but I can't see any graphlike property that can make them connect. Thus any infinite path is either isomorphic to the adjacency graph of N or the adjacency graph of Z, and infinite cycles don't exist. Dan Asimove got what I meant. In general, I'm trying to figure out if we can make conditions on finite subgraphs of an infinite graph that will enforce a Hamiltonian path of either sort on the whole. Dan --- Date: Tue, 3 Dec 2002 18:14:15 -0500 (EST) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: Re: [math-fun] infinite paths & cycles When I said, "The only kind of graph connectedness I know of is finite," I meant that a path with two endpoints has to have finite length. So the distance between any two points is finite if it exists. Dan --- Date: Fri, 6 Dec 2002 11:47:01 -0500 (EST) From: Dan Hoey To: math-fun@mailman.xmission.com Subject: Re: [math-fun] Re: Number of ones in the binary expansion of 3^n Don Reble wrote: > More likely, a(n)/n should tend to log_2(3)/2 = 0.79248+, > since a bit is equally likely to be 0 or 1. (Well, the > first and last bits are ones; I meant the other bits.) The fours bit is always zero. Other bits (at least up to the 2^29s position) are exactly balanced. Dan --- Date: Mon, 9 Dec 2002 17:43:07 -0500 (EST) From: Dan Hoey To: Subject: Re: [math-fun] Thought up while drawing polygons ... "Steve Gray" asks: > In the unit square pick 4 points A,B,C,D at random (x,y each > uniformly distributed). Draw lines AB, BC, CD, DA. What is the > probability that two of these lines will cross (that is, we get a > reflexive quadrilateral)? It's easy to see that the answer is two thirds of the probability that the convex hull of {A,B,C,D} has four sides. That holds for any i.i.d. selection of the points (consider the points drawn from a circle). > With 5 points there are several possible topologies: no > crossings, one, two, three, or five. Is 4 crossings possible? No, but I forget the good proof, and hesitate to give you a tedious one. For N points, just characterizing the topologies gets interesting. Do we even have a closed form for the maximum number of self-intersections of the tour {p1, p2, ..., pn, p1}? Dan Hoey@AIC.NRL.Navy.Mil --- Date: Mon, 9 Dec 2002 18:33:40 -0500 (EST) From: Dan Hoey To: "Shel Kaphan" Cc: math-fun@mailman.xmission.com Subject: Re: [math-fun] solid angle from three wedges "Shel Kaphan" asks: > A long time ago JHC gave (on math-fun) a nice way to see that > the central angle of the icosahedron is atan(2) > but I can't find or reproduce it :-( > Does anyone still have that by any chance? I don't know if this is it, but I think it's nice. Trim three index cards to the golden ratio (or let 3x5 be close enough) and cut a centered slit as long as the short edge parallel to the long edge of each. Then you can place one card through the slit of another, at right angles, so that their centers coincide. If you similarly place the third card through the slit of the second, and arrange the first to pierce the third ouroborromeanly, then the vertices of the cards will be the vertices of a regular icosahedron. /\ / \ ____________ \ \ \ \ \ \_________ \ /\ \ / / \ / \ \ / / \/ \_____\ / Istimirant stella! / / / / / / / / /_____\ /________/ \ \ / \ \ /________\ \ / \ / \/ Then show that the tangents of the central angles of a golden rectangle are 2 and -2. Dan Hoey@AIC.NRL.Navy.Mil --- Date: Mon, 9 Dec 2002 19:03:55 -0500 (EST) From: Dan Hoey To: Subject: [math-fun] Clarification and correction Dan Asimov noted that I was somewhat unclear when I said > << > It's easy to see that the answer is two thirds of the probability that > the convex hull of {A,B,C,D} has four sides. That holds for any > i.i.d. selection of the points (consider the points drawn from a > circle). > >> I meant something like "drawn independently from any nonsingular probability distribution on a circle." And I chose a circle (not a disc) just to make the probability of the hull having four sides be 1, so that the probability of forming a reflexive quadrilateral would be 2/3. It's a symmetry argument--the three configurations A---B A---D A C | | \ / |\ /| | | X | X | | | / \ |/ \| D---C C---B D B are equally likely. Also, in my other recent message, I forgot and misquoted the Bayeux Tapestry. The correct phrase is "Isti mirant stella" ("They wondered at a star.") Dan ---