From: Chip Eastham Subject: Re: Rubik's tour. Date: Wed, 26 Jan 2000 23:34:37 GMT Newsgroups: rec.puzzles,alt.math,sci.math,alt.math.recreational Summary: [missing] In article <86bb96$6ae$1@nnrp1.deja.com>, rhoads470@my-deja.com wrote: > In article , > "Androcles" wrote: > [snip] > > Suppose we have Rubik's cube, and suggest a tour such that all > > possible outcomes of the various configurations are presented. We > > begin with the identity. > > Question three, analogous to the knight's tour. > > How many configurations are there each to be visited once and once > > only? > > (8! * 3^8 * 12! * 2^12) / 12 > > > Question four. > > Is this possible? > > Question five: > > How many moves does it take to return to the identity? > > Hmmn. It seems like a tour should be possible due to the regularity > of the configuration graph (a vertex for each configuration and > two vertices are connected if you can move from one configuration > to the other by turning some face 1/4 of a turn). > In graph theory the technical name for a "tour" in which each vertex is visited exactly once is a Hamiltonian path, or if a return to the start is envisioned with one additional final step, a Hamiltonian circuit. A graph is "regular" if the number of edges of a vertex ("degree") is the same for all vertices. Determining if an arbitrary graph has a Hamiltonian circuit (we say the graph is Hamiltonian, for economy) is known to be a Hard Problem (i.e., NP-complete). There are some existence theorems. For example, the jist of the one below is that if there are a lot of edges at every vertex (compared with the number of vertices), then the graph is Hamiltonian. In the configuration graph of the Rubik's cube, every vertex (configuration) has 12 edges. The tinyness of this "degree" in comparison to the number of vertices suggests to me that the graph is unlikely to be Hamiltonian. This is just a guess, based on probabilities. A regular graph can have degree two and arbitrarily many vertices and be Hamiltonian, but there is effectively only one such graph (polygon) for the given number of vertices. Thm. (Dirac, 1952) If G is a graph with n vertices and each vertex has more than n/2 edges, then G is Hamiltonian. Regards, Chip Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik) Subject: Re: defining Dirac's delta, or rather, "mathematical rigor" Date: 30 Jun 2000 23:10:04 -0400 Newsgroups: sci.math In article , Dik T. Winter wrote: :In article <8jje53$6dq$1@news.surfnet.nl> "Raoul :Grasman" writes: : > The other one however, seems : > perfectly plausible and precise enough to me....: this one defines : > @(t) to be the limit, as \epsilon approaches 0, of : > $u(t) =1/\epsilon$ for $0 < t < \epsilon$ and $u(t) = 0$ : > elsewhere. This latter definition provides, in my opinion, some : > insight to the behaviour of this ..ehm.. object. : :Hrm, yes, object indeed. The problem is that for a mathematician that :limit does not exist, the thing diverges, and mathematicians have nothing :more to tell about it. So, while it might provide insight, it is not :mathematical insight. As far as mathematics is concerned Dirac's delta :does not even exist, as there is no proper definition. :-- Doch, as the Germans say (to oppose a negative statement). Dirac's delta is a function, but not acting on numbers. It acts on certain functions, and I'll try to show what functions and how. (The "sharp" view): A function, as we were taught, takes a single point as input and returns a number as output. The input point is thought of as perfectly distinguishable from other such points, so that for x different from y, the task of evaluating f(x) is separate from the task of evaluating f(y). (The outcome may or may not be the same, of course.) Now, the "blurred" view (taking off my eyeglasses): There is no such thing in the world of distance measurement as a precise position of a point. The best we can get is a blob, thicker at the centre and thinning out at the distance. To prepare for the introduction of the delta, let's assume that the blob is given by a continuously, and indeed smoothly, changing density whose total mass is 1 (counting one point), and this density also vanishes beyond a certain radius from the centre. If you prefer probabilistic view, the blob is defined by a "compactly supported" probability density of hitting a random point. How does an ordinary function "act" on such a blob? Say the density is r(x) at point x, and a given function f would evaluate as f(x) if... ... if x were known exactly. What is f(blob)? Physicists and probabilists alike would recommend f(blob) = integral[-inf to +inf] f(x) * r(x) dx calling it either the average of f on the blob, or expected value of f with respect to the probability density r. And here comes the abstract step: There may be "functions on blobs" which do not arise as the previous averages. We liberate our minds from insisting that such a "function on exact points" must exist. All we need from the "function on blobs" is that it acts like a linear function. Oops, the densities do not behave like members from a vector space yet! To remove this defect, we allow r(x) to be of any size, and positive or negative or of changing sign, as long as r is smooth and vanishes outside it interval. (Think of localized, idealized electrical charges.) Now the "integration against f(x)" is linear on the blobs: integral(f(x) * (p*r(x) + q*s(x))) dx = p * integral(f(x)*r(x)) dx + q * integral*f(x)*s(x)) dx An accepted notation is that of an inner product: meaning integral*f(x)*s(x)) dx Then = p* + q* is the symbolic expression of linearity of the action of f on r, resulting in . If you had the patience to follow up to here, you can see the definition (no less than that) of the action of delta on r: = r(0) Just like that. Linearity is checked right away: = p*r(0) + q*s(0) = p* + q* The mystifying step back in so many "presentations" consists of insisting that it the action written as an integral, as if delta were a function on exact points, which it isn't, as you so emphatically admitted. Delta is a (linear) function on the (huge) vector space of those "blobs", defined by its action as above. There is also another technical provision (continuity) to make sure that many useful limits involving the delta function (now we can shamelessly say "function", knowing what its "playground" (domain) is). This development, not as talkative as in above reply, but more involved, goes back to a French mathematician Laurent Schwartz, and many other authors of the 20th century, sort of "cleaning up" after Dirac who found the utility of the formalism in physical theories. Oh, the "blobs" have a technical name "test functions", and the "functions on blobs" are called (Schwartz) "distributions." Under this name, they are discussed in the better textbooks of Real Analysis and/or Functional Analysis (Royden etc.) Calculus with distributions is also possible and well-defined ("rigorous?"). Cheers, ZVK(Slavek)