Wikipedia:Reference desk/Archives/Mathematics/2009 January 18

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Mathematics desk
< January 17 << Dec | January | Feb >> January 19 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 18[edit]

3 spiders and a fly[edit]

The following question was posed to me, and I failed to solve it and had to be told the answer. As a result, I posed a second question, to which I still don't know the answer.

Original 3 spiders and a fly

  • Imagine an equilateral tetrahedron (four equilateral triangles assembled to make a triangular based pyramid).
  • For reasons inexplicable, 3 spiders and a fly are only able to walk along the edges of the tetrahedron. The spiders have to say where they start and exactly where they are going to walk in advance. The 'invisible' fly is clever and must be told their plans in advance so he can decide his starting point and movement.
  • The fly is ever so slightly slower than the spiders (say 99% of the speed), but being invisible, a spider only knows he has caught the fly by treading on it.
  • Can the spiders catch the fly? If so demonstrate how. Or can the fly forever remain uncaught? If so prove it.

Related One spider and a fly

  • If there was only one spider, how much faster than the fly would he need to be to be able to catch it? If it was a thousand times faster it is easy to catch the fly, unless the fly is considered as a point object (which I don't - lets say the fly has a diameter = 0.001 of a pyramid edge). How about 100 times or 10 times or 3.14159 times faster? Prove your value is the minimum required.

Can anyone solve the related question? -- SGBailey (talk) 00:10, 18 January 2009 (UTC)

This question seems fairly challenging. Part of the reason is that the tetrahedron is a relatively complicated graph to start with—you might want to try some simpler graphs first. For example:
  • On a cycle graph, the spider can catch the fly if and only if the spider is faster.
  • On a claw graph (i.e. the Y or tripod graph), it seems to me that the spider can catch the fly if and only if the spider is more than twice three times as fast, though I'm not sure how to prove this. It shouldn't be too hard to figure out how fast the spider must be on an arbitrary star graph
  • Other basic graphs to look at include bouquets of circles and dipole graphs.
Once you figure out the solutions to some of these, you might be in a better position to solve the problem on the tetrahedron. Jim (talk) 17:44, 18 January 2009 (UTC)
On a tetrahedron, a fast spider basically has to speed around all the edges, checking a small way up each edge from each corner. If the corners are ABCD and we use 'x' to represent (say) travelling from the current corner towards corner 'X' 10% of an edge length, then AbAcAdA means that the fly isn't near corner A. Thus a fast enough spider could do AcAdABdBCdCADcDBDC and guarantee to catch the fly. If the fly was a point source, it could hover near a corner and take infinitesimal steps away from the corner on the branch not being used by the spider at that instant. In the scheme shown, the spider travels 8 edge lengths (6 edges, 1 duplicate edge and 5 10%*2 "out and backs". At 800 times the speed of the fly, the the spider could be sure that the fly can't get from (say) 11% the way along and edge to a corner before the entire tetrahedron is traversed. I expect that minor changes to the route, like double checking corners on a second arival could almost have the necessary speed, since the fly would have to get from 11% on this arm to the corner and then to 11% on that arm to avoid detection. I guess a speed factor in the order of 400 times. It may be that by adjusting the 10% corner sweep distance, maybe to as much as 50%, might help by forcing the fly to have to travel further to and from a corner. But (1) I'm not sure how to optimise the parameters to determine the best speed for this spider algorithm, and (2) it may not be the best algorithm. Any ideas anyone? -- SGBailey (talk) 00:31, 19 January 2009 (UTC)
Three spiders can catch a point fly going a fifth as fast as them. Call them 1, 2, and 3, and call the vertices A, B, C, and D. Start 1 at A and 2 and 3 at B. Move 1 to B. Move 1 to C and 2 and 3 to D. Move 2 to C and 3 to A. Move 1 and 2 to A. Move 1 to B. I think they might be able to catch something a quarter or third as fast as them, but probably not a half as fast. Black Carrot (talk) 22:33, 19 January 2009 (UTC)
They can catch something a third as fast as them. Do the first four moves of the previous thing, replace the last move with "Move 1, 2, and 3 to B", and add one thing: Move 1 to C and 2 to D. Black Carrot (talk) 22:38, 19 January 2009 (UTC)
Let the spiders follow a four-step cycle. Spider 1 will go from A to B, from B to C, from C to D, and from D to A. Spider 2 will go from A to C, will wait at C, will go from C to A, and will wait at A. Spider 3 will wait at B, will go from B to D, will wait at D, and will go from D to B. For a given speed of fly, is there any path it can follow that would survive this indefinitely? Black Carrot (talk) 06:55, 20 January 2009 (UTC)
It is possible for 3 spiders to catch a fly going 99.9% of "spider speed". Although nowhere near optimal, I agree with BC's fifth speed and third speed paragraphs. The last para is equivalent to the answer I was given (that answer had s2 and s3 travelling at 50% s1 speed rather than waiting - it is equivalent). However to make it work the spiders must be in sync. That is s1 and a waiting spider should leave a corner together to prevent the fly doubling back briefly. -- SGBailey (talk) 09:19, 20 January 2009 (UTC)
I think it's impossible for a single spider to catch a fly going more than a third as fast as it. First, to restate the problem. The edges of the tetrahedron will be colored entirely in red and white. A red point is a place the fly could choose to be. A white point is a place the fly could not possibly be. At first, the entire tetrahedron is red except the spider. As the spider moves, it drags a little comet tail of white behind it. Let F(t) be the total amount of red at time t. Assuming all the edges are a unit long, F(0)=6, and the question is whether the spider can follow some path that will make F eventually zero. F is clearly continuous, so it must pass through every value between 6 and 0 to do that. Consider a time t such that F(t)=3. That means that there is a total of 3 units of red scattered over the graph, and 3 units of white. Fiddling with cases seems to make it clear that the function is increasing as time moves forward from this point. The spider can move forward into a red area, decreasing the amount of red at a certain rate. However, there will have to be at least 3 different points where white and red meet other than at the spider, and at each of these points the amount of red is increasing at a rate more than a third the speed of the spider. In other words, there's three spigots pouring into a tank, and only one letting out, and the total rate of change of the volume of water in the tank is positive. So, for any point t where F(t)=3, there is an interval immediately following it in which F>3, and F can never drop below 3, let alone to 0. Black Carrot (talk) 00:37, 21 January 2009 (UTC)
Sounds very plausible. Thanks. -- SGBailey

(talk) 06:42, 22 January 2009 (UTC)

volume of a nonEuclidean tetrahedron[edit]

The title says almost all. I have a tetrahedron defined by its dihedral angles; from these I obtain the normal vectors of a set of bounding planes, and then the coordinates of the vertices. Is this enough information to obtain the tet's volume in a convenient way? —Tamfang (talk) 06:13, 18 January 2009 (UTC)

Not sure what you mean by a "nonEuclidean" tetrahedron. Do you mean it doesn't have flat sides ? Or do you just mean it's not a regular (equal sides) tetrahedron ? In the latter case, see Tetrahedron#Volume_of_any_tetrahedron. StuRat (talk) 11:57, 18 January 2009 (UTC)
I'd have taken it to mean a tetrahedron in a non-Euclidean space, probably a hyperbolic space. Michael Hardy (talk) 00:06, 19 January 2009 (UTC)
But they also mentioned "bounding planes". Do they exist in a hyperbolic space ? StuRat (talk) 00:10, 19 January 2009 (UTC)
You can certainly have surfaces that are locally planar, so you can get a decent approximation as long as the tetrahedron isn't too big. --Tango (talk) 00:17, 19 January 2009 (UTC)
Just as hyperbolic geometry has its own definition of 'line', in three dimensions it has its own definition of 'plane'. In the hyperboloid model (which is the most convenient for analytic geometry), a plane consists of the intersection of the hyperboloid with a hyperplane passing through the origin. —Tamfang (talk) 04:05, 19 January 2009 (UTC)
Yes, I should have said "a tetrahedron in hyperbolic space". (I'd like to know the answer for spherical space, too, but don't have a need for it.) —Tamfang (talk) 04:05, 19 January 2009 (UTC)
See this paper for a usable (though complicated) formula. Jim (talk) 16:39, 19 January 2009 (UTC)
Yow, I was hoping it wouldn't need numerical integration. Perhaps I'll sort my list by inradius instead. But thanks. —Tamfang (talk) 06:26, 21 January 2009 (UTC)
For anyone who doesn't know, the area of a hyperbolic triangle with angles α, β, γ is simply π − α − β − γ. More generally in a plane of constant Gaussian curvature κ the area is κ−1 (α + β + γ − π). This works except in Euclidean space, where it yields ∞ · 0, which happens to be the subject of the thread below this one. I imagine that Tamfang was hoping the three-dimensional case would be equally beautiful. I'm disappointed to learn that it isn't. -- BenRG (talk) 13:11, 21 January 2009 (UTC)

Infinity multiplied by zero[edit]

If infinity is multiplied by zero, would the product be zero, or infinity? Because theoretically, anything multiplied by zero is zero and anything multiplied by infinity is infinity. One would think that infinity multiplied by zero would be zero, because it could be rendered as infinity zero times ( ) or zero infinity times (0+0...), which both end up being zero. But I still choose to ask this question because I want to make sure my logic is correct. Filosojia X Non(Philosophia X Known) 08:13, 18 January 2009 (UTC)

(edit conflict) This is a nice question actually. Consider a line of infinite length having 0 width (or thickness). We would expect its area (i.e the area enclosed by it) to be 0, yes? But its area is 0 * (infinity) so 0 multiplied by infinity is indeed 0. Although you could say I shouldn't do this, how about checking the distributive law? Let's see:
0*(infinity + infinity) = (0*infinity) + (0*infinity)
0*(infinity) = (0*infinity) + (0*infinity)
0 = 0*infinity
To get from the second step to the third, we cancelled (0*infinity) from both sides of the equation. Now in any number system, we would expect the distributive law to hold: this is such an important law. So in the number system: [-infinity, +infinity] (by this I mean all real numbers together with the two infinities), we would expect the distributive law to hold. But if it does hold, we get 0*infinity = 0 so I would say that this is the most natural result. In fact, as I noted in the beginning, many measure theorists (that is people who study generalizations of concepts such as length, area and volume), agree that 0 = 0*infinity. Hope this helps. --PST 08:26, 18 January 2009 (UTC)
The above calculation doesn't really mean much. If you had 0 * infinity = infinity, then you'd have infinity = infinity + infinity in the second step. You can't just "cancel" an infinity from both sides without defining infinity - infinity, which isn't usually done. As a few other people have said, there are other reasons for choosing 0 in other contexts. (talk) 02:28, 19 January 2009 (UTC)
But note that the above calculation follows from the distributivity law (which is natural). It is also well known that infinity + infinity = infinity. It is well known that 2*infinity = infinity (this is the most natural result possible). By the way, see field (mathematics). For [0, +infinity] to form a field, one must be able to have additive inverses of every element so I am allowed to cancel. --PST 18:42, 20 January 2009 (UTC)
Actually, infinity - infinity=0 * infinity!----The Successor of Physics 10:58, 21 January 2009 (UTC)
Well, it depends. In systems such as the extended real numbers and the Riemann sphere, 0·∞ is undefined, and in calculus it is considered an indeterminate form. However in measure theory the value is usually taken to be zero by convention. --Trovatore (talk) 08:18, 18 January 2009 (UTC)
So it depends upon how you look at it.

Filosojia X Non(Philosophia X Known) 08:22, 18 January 2009 (UTC)

PST, if you are going to interject your answer between the question and a previous answer, then kindly indent more than the original answer, not less. I have fixed it for you. --Trovatore (talk) 08:30, 18 January 2009 (UTC)

There was an edit conflict. Since my response was longer, it is quite likely that I was the one to first start posting. That is why I indented less. --PST 08:33, 18 January 2009 (UTC)
You have to think in terms of what can be seen or checked by others rather than of what you think you know. Your starting to edit is not observable. Dmcq (talk) 13:58, 18 January 2009 (UTC)
I don't understand. What do you mean by "Your starting to edit is not observable"? Do you mean that "You are starting to edit in a non-observable manner" or something like that? --PST 17:38, 18 January 2009 (UTC)
Dmcq simply means that nobody except you knows the exact time when you started writing your comment. In the same way, nobody except Trovatore knows the exact time when he started writing his. Therefore, we don't attempt to determine who started editing first and reflect that in the layout. Edit conflicts or not, the comment published first is the comment published first. -- Jao (talk) 17:52, 18 January 2009 (UTC)

0·∞ is an indeterminate form in the sense that one can find two functions such that the first approaches 0 and the second approaches ∞ and their product approaches 42, or you can alter the functions to get any other number besides 42. For the purposes of measure theory, it often makes sense to take 0·∞ to be 0. For example,

Michael Hardy (talk) 00:03, 19 January 2009 (UTC)

the square root of [edit]

If then what would equal ? Filosojia X Non(Philosophia X Known) 08:37, 18 January 2009 (UTC) —Preceding unsigned comment added by Earthan Philosopher (talkcontribs)

Think of complex numbers as points on a plane, then x+iy is the point (x,y). Then represent these points as a distance from the origin and an angle from the positive real numbers. It that scheme, +1 is (1, 0 degrees), +i is (1, 90 degrees), -1 is (1, 180 degrees) and -i is (1, 270 degrees). To find the square root, do the normal positive square root action on the distance from the origin and halve the angle (for the 'positive' square root) - for the other square root, add 360 degrees to the angle before halving it. Thus the four points listed above have all have roots of distance 1 and at angles: +1 -> 0 or 180 degrees (= +1, -1); +i -> 45 or 225 degrees (= 1/root2 + i/root2, -1/root2 - i/root2); -1 -> 90 or 270 degrees (= +i or -i); -i -> 135 or 315 degrees (= -1/root2 + i/root2, +1/root2 - i/root2). -- SGBailey (talk) 09:38, 18 January 2009 (UTC)
It's this, try squaring it to prove it is right;
SpinningSpark 10:50, 18 January 2009 (UTC)

So . Which would then yield . Which states that. Filosojia X Non(Philosophia X Known) 11:14, 18 January 2009 (UTC)

Also note that there is a general pattern if you write such numbers in exponential form:
Which you can check is the square root of i by
GromXXVII (talk) 17:58, 18 January 2009 (UTC)
I made a generalized formula for which is where c is any arbitrary constant.----The Successor of Physics 09:50, 19 January 2009 (UTC)
That would have to be

Filosojia X Non(Philosophia X Known) 22:51, 25 January 2009 (UTC)

I think you missed out a \ in your Tex markup, so you mean . Gandalf61 (talk) 10:07, 19 January 2009 (UTC)
Yes, thats right. Thankyou!----The Successor of Physics 13:42, 19 January 2009 (UTC)
But the c's just cancel... --Tango (talk) 11:41, 19 January 2009 (UTC)
Well, not if they're negative. Superwj5's formula yields, using different non-zero values of c and the common single-valued nonnegative-to-real square root function, both possible square roots of i. Of course, it does so in an unnecessarily complicated way (to put it mildly). -- Jao (talk) 13:53, 19 January 2009 (UTC)

Henge circles[edit]

Apparently, some ancient henges were marked out with a loop of rope held taut against stakes in the ground. If the number of stakes were two, this would, of course, construct an ellipse whose focii were at the stakes, but in the case of the henges more than two stakes have to be assumed to arrive at their actual shape. Is there a name for such figures and do we have an article? SpinningSpark 10:57, 18 January 2009 (UTC)

Only two stakes at a time will be foci. So the curve will consist of elliptical arcs. Bo Jacoby (talk) 12:51, 18 January 2009 (UTC).
I realise that, I was asking if the figure has a name. SpinningSpark 14:58, 18 January 2009 (UTC)

Continued fractions and quadratic irrationals[edit]

Hi there - I've been studying up on finite and infinite continued fractions and I've found a question which aims to prove that the continued fraction representation of a number x is eventually periodic iff the number x is a quadratic irrational. I've managed to prove the easy part, that but for it says "Assuming the result that Pell's equation always has a solution in integers x, y when d is an integer but not a perfect square, show that for any such d, is eventually periodic." I'm not really sure where to start with this at the moment - any pointers would be much appreciated.

Incidentally, I've read through a number of other proofs of this on the internet and understood them fine, so it's not just a matter of proving the implication in the other direction - i'm more interested in how exactly I would go about with this specific method. Many thanks, (talk) 16:06, 18 January 2009 (UTC)B

The proof the other way isn't so straightforward, Lagrange gave a proof which I believe depends on showing that the remainder term at each stage satisfies a quadratic equation with bounded parameters, so there's only a finite number of remainders and the sequence repeats. This can also be used to give a rather large overestimate of the maximum length of the sequence. I've just had another look and here's actually an article Periodic continued fraction which seems to have a reference to a book that probably has a proof. Dmcq (talk) 18:00, 18 January 2009 (UTC)
Check also Pell's equation and Methods of computing square roots. Pell's equation with parameter d is strictly linked with the continued fraction of . The link is given by the simple fact that a pair of integers (x,y) solves Pell's equation if and only if the matrix
is in the special linear group over (integer coefficients and det=1). It is easy to check that the set of the matrices of the above form is an infinite subgroup of the special linear group; this implies that there are infinitely many solutions to Pell's equation (added rmk: as soon as one knows there is at least a non-trivial one: see Algebraist's post below); clearly converges to as . If I remember well, it turns out that are convergents for (you don't get all of them, even if you start from the minimal solution). Additional informations: if you take the matrices with x>0 you get a further subgroup of index 2, isomorphic to , because is totally oredered (and discrete). You can see it as a subgroup of the modular group. Notice that the matrix solves the equation: , whence also , that, read on the coefficients in terms of fundamental recurrence formulas, should give the periodicity. --PMajer (talk) 22:47, 19 January 2009 (UTC)
Is that really easy to check? I agree that it's easy to show it's a torsion-free subgroup, so it's infinite as long as it's nontrivial, but to show it's nontrivial is to show that Pell's equation always has a solution, which I didn't think could be done simply. Algebraist 23:49, 19 January 2009 (UTC)
Yes, that is the nontrivial part, but I understood that it is assumed for given in the question. You probably know better than me how it is shown the existence; I guess checking the convergents for and showing that for some k has to be 1...--PMajer (talk) 00:17, 20 January 2009 (UTC)
The proof I saw years ago in my algebraic number theory class consisted of noticing it's a trivial special case of Dirichlet's unit theorem. I'm sure that's more technology than you actually need, though. Algebraist 00:24, 20 January 2009 (UTC)
Yes, I've the same feelings. What I can add about the OP is that there is a classical result on continuous fractions (it's in Hardy-Wright book, sure) that states that if then is a convergent of ; and this applies nicely here because if (x,y) is a solution of Pell's equations we have
by the mean value theorem. Therefore any solution of the Pell's equation corresponds to a convergent. I remember that after all the direct proof of Lagrange theorem is just an application of pigeon's principle, that need a bit of work but elementary: the same proof probably also allows to say that in the case of not only the coefficients are periodic but for some k (I hope somebody will give some light for I do not have time to make a search nor to think about it...) --PMajer (talk) 11:31, 20 January 2009 (UTC)

One cannot reconstruct a finite group from its character table[edit]

One cannot reconstruct a finite group from its character table, e.g. have the same character table. But one can reconstruct them from their representation category by Tannaka duality. Can someone explain what the additional information contained in the representation category is? Thanks. (I also asked this on talk:Tannaka-Krein duality.) Ringspectrum (talk) 16:42, 18 January 2009 (UTC)

It has lots of extra info. The character table only tells you about 1-dimensional representations (i.e. homomorphisms from your group to ). The representation category encodes all representations (i.e. homomorphisms from your group to ) as well as info about their tensor products (e.g. given two irreducible representations V and W, how do we decompose into irreducible representations). kfgauss (talk) 17:45, 18 January 2009 (UTC)
This is not the usual definition of character table of a finite group. The character table of a finite group lists all isomorphism classes of irreducible representations, not just those of dimension 1. JackSchmidt (talk) 17:48, 18 January 2009 (UTC)
After a quick look at the T-K duality article, I don't see anything obvious. Since the representations are over the complex numbers, there is a 1–1 correspondence between the finite dimensional representations and non-negative integer combinations of the rows of the character table. The tensor product is the point-wise product of the characters, and the dual is the complex conjugate. The dimension of the homomorphism groups is just the scalar product of the characters which can be computed just from the character table. The only thing that might be left out is a more careful bookkeeping of what happens when you compose homomorphisms between representations (we know the Hom groups up to iso from the character table, but vector spaces have lots of isos, so maybe something gets lost here).
The Tannaka result seems a little counter-intuitive to me since the group ring itself does not determine the group up to isomorphism, but perhaps the tensor product is helping to pinpoint the subgroup of the group of units that is the group. The group ring determines the category of finite dimensional modules over the group ring, but the group rings of the quaternion and dihedral groups of order 8 over the complexes are isomorphic. JackSchmidt (talk) 17:48, 18 January 2009 (UTC)
Thanks for the correction. What you say about composing homomorphisms sounds about right. In particular you can do things like the following: for Q and D_4, there are four 1-dimensional reps V_1, V_2, V_3, V_4 and one two-dim rep W. We have . Thus we have a map . For an automorphism , we can ask whether lies in the image of A. (I haven't checked, but it might be the case that this is "enough": i.e. perhaps the set of such is the group Q or D_4, respectively.) This sort of info isn't available in the charater table but is in the category with its dual and tensor structures. kfgauss (talk) 21:41, 18 January 2009 (UTC)