Wikipedia:Reference desk/Archives/Mathematics/2006 September 6

< September 5	Mathematics desk archive	September 7 >

Humanities Science Mathematics Computing/IT Language Miscellaneous 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 at one of the pages linked to above.

< August September October >

September 6

chess questions

Hi, is this a good place for chess questions? If there are any good chess players reading this, please let me know by adding a note here, because then I'll use this site. Mathematicians think of chess problems as mathematical problems, so it should be theoretically correct to put such questions here, but if no one is interested in the subject, I'd better not waste anyone's time. The Mad Echidna 00:37, 6 September 2006 (UTC)

Yes, but remember to check (no pun intended) the articles on chess first before deciding to ask your question here. --Ķĩřβȳ♥ŤįɱéØ 02:03, 6 September 2006 (UTC)

I would say, guardedly, that some chess questions are OK, like the "eight queens" question, or asking for an estimate of the total number of board positions possible. However, just giving us a board arrangement and asking what the next move should be probably isn't the type of question which belongs here. StuRat 02:11, 6 September 2006 (UTC)

It probably isn't too far off to think that people interested in mathematics might also be interested in chess. (Not me though, I'm terrible at the game.) - Rainwarrior 07:30, 6 September 2006 (UTC)

Chess: castling on opposite sides and pawn storms

I've noticed in chess, when players castle on opposite sides, there is some kind of a paradox about the impact of defensive pieces in front of the king. Most writers (eg. Keres and Kotov in The Art of the Middle Game), say that these pieces present targets for the enemy pawn storm. But I have seen many games, especially Sicilians where white castles long, in which one player (usu. white in the Sicilian) uses the defensive pieces and a pawn thrust to actually blockade the pawn storm. Are these blockading possibilities merely special exceptions, or is there a good general rule behind them? The Mad Echidna 04:31, 6 September 2006 (UTC)

This isn't a math-related question about Chess. When answering your previous question, I assumed your chess question was math-related. But this one is better suited to here. --Ķĩřβȳ♥ŤįɱéØ 06:17, 6 September 2006 (UTC)

Decimal system

Hello. My question: If we were fingerless and had to start from scratch (for whatever reason), which numeral system would be best designed to fit our brains? Are there numeral systems that would be more suitable for our minds than the decimal system? Are there numeral systems that would be easier to manage? Or are there other advantages of the decimal system (apart from the fact that we happen to have 10 fingers)? Obviously the binary system isn't very practical for human use, but what about the hexadecimal system? Are there studies or speculations on this? I thank you very much for sharing your thoughts and pointing me to sources. Pat83.77.215.216 09:24, 6 September 2006 (UTC)

It is advantagous to use a base with many factors (this way, more fraction have a terminating digit expansion), so 6, 12, 30 and 60 are good candidates (in fact, bases like 12 and 60 were used in ancient times, and many of the units we use today are relics of that period). Powers of 2 bases also have obvious advantages, so binary (in which there isn't really anything impractical) and hexadecimal are also good candidates. If I had to take a bet, I'd say 12 is what would be adopted. There are probably many studies on this, but I don't know of any specific source. -- Meni Rosenfeld (talk) 09:40, 6 September 2006 (UTC)

The Babylonians used a base-60 system, although you could say it was altenating base 6 and base 10. It's why we still have 60 seconds in a minute, and 60 minutes in an hour or in an arc degree. The duodecimal system, which has base 12, has some non-systematic spontaneous cameo appearances in natural languages, and has also been advocated forcefully last century. Even today there is a society promulgating its adoption. It's hard to say that any of these "fit our brains" better than others, but it should be obvious that 12 is more practical as a base than 13 or 256. --Lambiam^Talk 09:48, 6 September 2006 (UTC)

There's an advantage to using a base somewhere around 4, 5, or 6, as that's the range of objects which can typically be identified without requiring you to count them individually. We still use that system, when using hash marks:

| = one
|| = two
||| = three
|||| = four
|||| = five

StuRat 13:09, 6 September 2006 (UTC)

Thank you, Meni, Lambiam, and Stu. The dozenial system sounds promising. Or maybe it should be 6, since what Stu said makes a lot of sense. You guys helped me. Pat83.77.215.216 13:15, 6 September 2006 (UTC)

You're quite welcome. StuRat 13:25, 6 September 2006 (UTC)

Number Systems of the World cites languages that use bases 6, 12, 15, 20. I believe bases 2 and 5 have been in use; I'll have to go home and look at a book. Base 20 is often combined with 10 or 5 as a subgroup. —Tamfang 19:18, 6 September 2006 (UTC)

Computing Integration vs. Searching Global Optimum Point

Do you think that the problem of computing integration (by any standard methods such as numerical or monte carlo), in high-dimensions, is at least as hard as finding the global optimum points of a function in Euclidean space?

In the integral domain such as [0,1], there is always possible to be a very tiny fraction A in [0,1], say the area $\mu (A)=10^{-100}$ which dominates all the integral, i.e. $f(A)=10^{200}$ while other points in the domain have $f(x)=1$.

So in order to compute integration, it's necessary to search for that tiny fraction which is identical to search for global optimum point. In one dimension, gradient-based methods might work, but what's about in n-dimension?

BTW, since the global optimum points searching is still an important open problem (simulated annealing or genetic algorithms dont guarantee anything), does this mean that the problems of making efficient integration algorithm is also still open? -- 131.111.164.219 12:27, 6 September 2006 (UTC)

Eh? There isn't any gradient in one dimension. Gradient as I understand it means some f(x)/g(y) (generally). What do you mean?

Can you explain what the problem is? (As long as it isn't anything to do with financial maths, of course, as that has me reaching for weapons) :) Rentwa 13:10, 6 September 2006 (UTC)

If the method used for integrating or optimum finding only has access to the function by submitting arguments from a continuum for evaluation, then no method can be guaranteed to do a good job for all functions. So if you need such a guarantee, then both are equally hard, since both are impossible. To get any kind of guarantee you need additional requirements on the function bounding the wildness of its behaviour, for example Lipschitz continuity. --Lambiam^Talk 14:14, 6 September 2006 (UTC)

Er, yes. What Lambiam said. :D Rentwa 14:32, 6 September 2006 (UTC)

Thanks for your attentions. Could you please give me other possible additional requirements on the function, other than Lipschitz continuity? -- 131.111.164.228 13:27, 8 September 2006 (UTC)

For the gradient descent to find its minimum, I think it's enough that the function is convex and its domain is a bounded convex subset of the n dimensional Euclidean space. On the other hand, numeric integration doesn't need such a strong condition. If I remember correctly, numerical integration with the midpoint method using uniformly placed sample points does converge to the integral for any continuous function (on a compact domain, so the function is always bounded and has a Riemann integral) as you place the sampling points closer. This convergence however can be riddiculously slow, so you need addittional properties (like a many-times differentiable function) to guarantee a faster convergence. However, my numerical methods courses were ages ago and I don't remember too much of them, so any of these could be wrong. – b_jonas 20:30, 8 September 2006 (UTC)

hyperbolic perpendiculars

Is there a flaw in this reasoning?

• In the Poincaré disk model of the hyperbolic plane, geodesics are represented by circular arcs which meet the bounding circle at right angles. Each such arc L (unless it is a diameter of the disk, which case I'll ignore for now, handwave limit bla bla) has a center P(L) which I'll call the pole of the geodesic. P(L) is also the intersection of the two tangents to the bounding circle where it meets L.

• The Poincaré disk is conformal. It can be conformally mapped to a hemisphere by stereographic projection, and the hemisphere model is again a conformal map of the hyperbolic plane. In this model the geodesic arcs lie in vertical planes; P(L) lies in the plane of the "equator". L and P(L) define a cone, tangent to the hemisphere all along L. Given a point B in L, draw a line containing B and P(L); this line is tangent to the hemisphere and perpendicular to L, and thus is tangent to a geodesic M which is likewise perpendicular to L. M is contained in a vertical plane which contains the tangent line and thus contains P(L).

• If the hemisphere is reduced to a plane by orthographic projection, we now have the Beltrami-Klein model of the hyperbolic plane, in which geodesics are represented by straight lines. P(L) is in the same place as before, the intersection of two tangents to the bounding circle where it meets L. The plane of M is reduced to a line which contains P(L).

• Conclusion: two geodesics L and M in the hyperbolic plane are perpendicular iff in the Beltrami-Klein map the extension of L contains P(M) and vice versa.

This may be old hat, for all I know, but I haven't found it in my books. —Tamfang 19:11, 6 September 2006 (UTC)

If you are asking only about the conclusion about perpendicular lines in the Cayley-Klein model, then it is known. "A geometria és határterületei" from Reiman István describes the C-K map in chapter 13 and it does indeed give this criterion with poles for perpendicular lines. Your argument to prove this is however new for me. – b_jonas 07:50, 7 September 2006 (UTC)

A proof of this result, with fairly similar reasoning to this, is given in Stillwell's Geometry of Surfaces. Tesseran 22:04, 13 September 2006 (UTC)

norm minimization

Given a unit n-cube C and l-plane Z, l<n-1, find C vertex nearest to Z in eucledian norm. Does anybody know if there is a polynomial time algorithm for this?.

This sounds like a constant time operation. Just check all six vertices against the plane for distance, and when you find the closest one, because it's a unit cube you already know its magnitude and it could be normalized with a single scalar multiplication. - Rainwarrior 19:47, 6 September 2006 (UTC)

That's n-cube, not 3-cube, 2^n vertices...

Does a 3-cube have six vertices then? Please don't snap at the editors, they're only trying to help... Rentwa 21:35, 6 September 2006 (UTC)

A 3-cube has 8 vertices. A 4-cube has 16 vertices. ... See also Measure polytope. --Lambiam^Talk 22:30, 6 September 2006 (UTC)

Whoops. I've been saying n! all this time. Why didn't anyone stop me?? - Rainwarrior 01:28, 9 September 2006 (UTC)

Sorry, I forgot the "n" as I was thinking about it. Anyhow replace 6 with n! and what I said should still hold (except for it being constant time). Find the distance of each vertex to the plane (using the dot product with its normal), take the closest one and then normalize it. I guess this has a complexity of O(n!), so... no, I don't know of a polynomial time algorithm. (I'll think about it though.) - Rainwarrior 02:08, 7 September 2006 (UTC)

Center the cube at the origin and align it with the coordinate axes. Assuming that the plane doesn't pass through the unit n-sphere, it's trivial to find the point on that sphere closest to it. That point resides in some hyperoctant, each one of which contains one vertex, and which one is easy to check. I'm not sure that the hyperoctant's vertex is correct in all cases (even for the exterior-plane problem), but no counterexamples come to mind; perhaps someone can prove or extend this simple idea? --Tardis 23:28, 6 September 2006 (UTC)

Counterexample: Take the 2-cube (square) with sides at |x| = 0.5 and |y| = 0.5, and the 1-plane (line) x+2y = 0.5 (which does not agree with l<n−1, but it is easy enough to use a 3-cube with the same line). It is not clear what the radius of the 2-sphere (circle) is supposed to be, but it is actually irrelevant. The point on the circle closest to the line lies on the ray through its centre and orthogonal to the line, which is parametrically given by λ(1, 2) for non-negative λ. The ray lies in the quadrant (+,+), indicating the vertex (0.5, 0.5). Yet the vertex (-0.5, 0.5) is closer; it even lies on the line. --Lambiam^Talk 00:20, 7 September 2006 (UTC)

I think you didn't read my post carefully enough. You said that I didn't specify a radius; I said that the 2-sphere was supposed to be of unit radius, although now I realize that I meant ${\sqrt {n}}/2$ (the distance from the origin to the hypercube vertices). Also, the plane was supposed to not pass through the sphere, and your example does. In your case, the points on the circle closest to the line are their intersections at $\left(-{\frac {1}{2}},{\frac {1}{2}}\right)$ (of course) and $\left({\frac {7}{10}},-{\frac {1}{10}}\right)$. These are in quadrants $(-,+)$ and $(+,-)$ respectively; one of those is "right" since the line passed through a vertex, but I'm not sure that even one of them would be correct in general. Anyway, do you have a counterexample for the case I claimed to (maybe) solve? --Tardis 04:27, 7 September 2006 (UTC)

I indeed missed the bit about the plane not passing through the sphere. With the ½√n radius that means the plane is also fully outside the cube. I can't immediately think of a counterexample then, but if I had to bet right now I'd bet on this not working already for n=3, l=1. --Lambiam^Talk 04:44, 7 September 2006 (UTC)

I think your solution works... it seems conceptually the same as what I suggested below, except I think it will work so long as the plane doesn't pass through the cube (the sphere covers a bit bigger area, which I don't think is necessary). As for Lambiam's suggestion of n=3, l=1, in this case, the plane is a point, and the cube is just a regular cube, right? Since the octant divides the unit cube on the origin up like a Voronoi diagram, each point in the octant closest to its nearest vertex, if you know the octant of that point, you know which vertex of the cube is closest. - Rainwarrior 20:12, 8 September 2006 (UTC)

Thought of a polynomial time algorithm: take the sign of every component of the plane's normal vector, then use that as your vertex vector. (If the distance of the plane from the origin is negative, flip its normal before you start.) That should be about O(n). It'll fail if the plane intersects the cube though. - Rainwarrior 02:10, 7 September 2006 (UTC)

The normal is in general an (n−l)-dimensional vector space. (The subtrahend is an "ell", not a "one"). --Lambiam^Talk 02:25, 7 September 2006 (UTC)

Argh, sometimes fonts are very confusing. Okay, if you can find a "normal" that is a vector that points in the direction of the nearest point on the l-plane to the origin, I think my suggestion still stands (as long as the plane does not intersect the cube). Finding such a vector should also be and O(n), shouldn't it? - Rainwarrior 19:57, 8 September 2006 (UTC)

(Apply the prefix hyper- as needed...) This problem is (nearly) equivalent to an 0-1 integer programming problem, although since no restriction on the coefficients of the plane is provided, it's not quite one. (Replacing the Euclidean norm with the Manhattan norm and performing optimizations for each half-space separated by the plane makes the objective function linear.) In general, 0-1 integer programming is a classical NP complete problem. Something between linear programming (to always have a vertex as a candidate) and quadratic programming (to use Euclidean distance as the objective function) should work. Although the simplex method isn't guaranteed to be P-TIME, the ellipsoid method applied to the positive definite Euclidean metric is, so this might be workable.-- 66.103.112.140 06:05, 7 September 2006 (UTC)

I am well aware of QP and LP capabilities, thanks though. So far the approach Tardis offered with sphere appears to work for all cases including the one when Z intersects with C - then we just take a disc embedding the n-1 face which is not intersected by Z and do the same thing. Proof appears easy also. Thanks all.

Perhaps the easiest way to see that Tardis's method can't work if Z intersects C is this. The problem is equivalent to: project the 2^n vertices on the perpendicular to Z through the center of C. In general position, these 2^n images will be different. Compute the Voronoi diagram of these points on the perpendicular. Each point will have its own cell, so every vertex is a solution for some translated copy of Z. (I.e. for every vertex, there exists a set of normal translations of Z such that the given vertex is the closest to the plane.) So Tardis's heuristic won't work for most ways Z intersects C. (Of course, if Z only "barely" intersects C, then the plane will still project inside the heuristic's vertex's cell.) More tersely, suppose Z passes through the center of C. Then Tardis's heuristic vertex is the farthest vertex from Z. Works fine on the exterior of C, though. -- Fuzzyeric 02:59, 8 September 2006 (UTC)

I didn't say his method - his approach rather: for l<n-1 one can decompose a polytope C into O(n) faces (facets) which will include every vertex of C such that these facets do not intersect Z. For each facet construct a disc such that all vertices of that facet lie on it's border. Take intersection of Z with the plane of each disc which do not intersect facets themselves. We are back to the external case.

I think this method blows up if Z is normal to a pair of opposite vertices. This is an equatorial case where (a) Z intersects every facet, and (b) a large number of vertices are (roughly) equally close. Subsequent decomposition will cause a O(n!) growth in the number of candidate boundary polytopes, which isn't resolved until Z happens to start missing most of them (which happens when the 'topes are ~n/2-dimensional). A simple example in n=3 is the plane through the center of the cube that is normal to a long diagonal (e.g. {-1,-1,-1},{1,1,1}). This plane intersects every face and all but 6 edges. There's plenty of room to "wiggle" this plane around to be closest to any of the vertices. This example generalizes (successfully) to larger n. -- 66.103.112.140 00:59, 12 September 2006 (UTC)

I don't know how far we'd have to go to call it a proof, but something like:

1. if X is the point on the plane closest to the origin
2. and S is the point on the sphere intersecting the vertices of the unit cube, let s be the distance from S to X (if the plane intersects the sphere, there is no unique point, and the argument may not proceed).
3. let A and B be the nearest vertex of the cube to that point on the sphere, and the second nearest
4. let a and b be the distances from S to A and B respectively, note that a < b
5. the distance from X to A is ${\sqrt {x^{2}+a^{2}}}$, and from X to B is ${\sqrt {x^{2}+b^{2}}}$. The former is lesser because a < b

If the plane intersects the sphere, there will not be a unique point on the sphere that is closest to the plane anymore. For solving those cases, I'd suggest maybe a breadth first search starting with the originally chosen point, and proceeding to neighbouring unsearched vertices? At least this would start with a possible closest, and proceed down until the distance is no longer decreasing (which should be monotonic along neighbours if there is no backtracking). Still, the complexity of this would be O(n!), cause at worst you'll need to search a little more than half of them. - Rainwarrior 20:27, 8 September 2006 (UTC)

How about this for a polynomial time solution: first do what was suggested above, find the nearest point on the plane to the origin, and find its hyper-octant by taking the sign of each vector component. This will give you the closest vertex to the plane as long as it doesn't intersect the cube (as we've already discussed). The next step though, if it does intersect the cube, would be to find a gradient with respect to this normal vector. If you can find the direction (perpendicular to this cube vertex's vector) in which the plane is going away from that vertex (toward the origin, if it were projected on that vector), I think that direction should point toward the vertex which it is closest to (provided it isn't still closer to the original vertex). Anyone have any thoughts on whether this would work or not? - Rainwarrior 02:14, 12 September 2006 (UTC)

Take the {-1,1} 3-cube. Let the plane cut only one corner containing the vertex V. Suppose for concreteness that the distances along the three edges to the intersections with the plane were a, b, and b with a<b. Then the gradient is diagonally across the face opposite the distance a incident on V. We may "wiggle" the plane by rotating it around this gradient vector, thereby making either of the vertices on the edge cut (originally) by the plane at a distance b from V into the nearest vertex. (To ensure this, take 1<a.)

We can then take this plane, pushing it along it's normal vector through the cube and make each vertex be the closest one, sequentially. When this plane gets near the origin, any of the six vertices around the "equator" can be made closest by just "twitching" the plane's normal vector around.

Ultimately, the problem is that (1) the plane can intersect almost every sub-cube in a decomposition of the cube and (2) the closest point doesn't vary continuously across the set of vertices. ("Continuously" meaning from neighbor to neighbor.) To see this, start with the plane coincident with a face. Holding the plane at one vertex, hinge the plane very slightly away from the opposite vertex on the face. Now, translate the plane through the cube. The vertices on the face will be sequentially closest (with ties for vertices not involved in the hinging maneuver) with the "oppostive vertex" being the last one incident on the given face to be closest to the plane. The next point will be the one diagonally opposite to this one (diagonally across all n axes, i.e. across the diameter of the minimal sphere circumscribed about the cube), then all the other vertices on that other face, then (finally) the vertex diagonally opposite to the hinge fulcrum vertex. -- Fuzzyeric 04:06, 12 September 2006 (UTC)

This last suggested solution I made doesn't refer to neighbours at all. You mention that when it gets close to the origin, you can choose a vertex by "twitching" the plane around, and that's exactly what I'm referring to. The direction of the twitch with respect to the plane's normal (defined earlier as the direction of its closest point to the origin) will determine which vertex. If that direction is known, there should be no need to search the other vertices (except the one that lies in the direction of the normal).

As for the "breadth first search" I was thinking of earlier (which I guess your answer was mostly directed to), I think I agree that it wouldn't work, but it was also not a polynomial time algorithm either. - Rainwarrior 16:17, 12 September 2006 (UTC)

Partial Fractions

I just started a differential equations class and I'm a bit rusty from the summer break. I have done the homework on my own, but I'm stuck on a particular problem. I was initially asked to solve the equation

$y'=y(y-2)(y-5)$

I believe I have reduced it to this:

$x=\int {\frac {dy}{y(y-2)(y-5)}}$

The obvious next step is partial fraction decomposition. I attempted to work from this set:

${\frac {1}{y(y-2)(y-5)}}={\frac {a}{y}}+{\frac {B}{y-2}}+{\frac {c}{y-5}}$

but this got me no-where helpful. Based on Partial fraction and http://mathworld.wolfram.com/PartialFractionDecomposition.html I am wondering if the fractions I chose were even right. If not, what should I be starting with? If they are correct, could someone please show me through the next step or two to simplify the integral? Thanks in advance 48v 18:18, 6 September 2006 (UTC)

Everything is good so far. Now you have to multiply by y(y - 2)(y - 5) and expand. By equating the coefficients of the different powers of y, you can find A, B and C. -- Meni Rosenfeld (talk) 18:36, 6 September 2006 (UTC)

Thank you. I'll give that a try! 48v 04:18, 7 September 2006 (UTC)

10 Ways math is used everyday

Could someone please tell me 10 ways math is used everyday. This is for a homework assignment. I have to write 3 sentences on each of the 10 ways I mention. Thanks, Slimezter 19:54, 6 September 2006 (UTC)

You should do your own homework. However, you may find it appropriate to list the tenth reason as "counting to see when I have found enough ways". — Lomn | Talk 20:24, 6 September 2006 (UTC)

Did you look at the article Mathematics for a start? Especially the section entitled "Applied mathematics" gives links to various fields of application. Near the top you find a link to "Portal mathematics" which gives you access to an article on the areas of mathematics, which may give you further ideas. --Lambiam^Talk 21:20, 6 September 2006 (UTC)

converting

how do you convert milimeters into centimeters —Preceding unsigned comment added by 24.244.181.68 (talk • contribs)

Just divide the amount of milimeters by 10. -- TheGreatLlama ^{(speak to the Llama!)} 22:07, 6 September 2006 (UTC)

How Do You Divide? I have learned it, but I forget how to .

Shardsofmetal ^{[ Talk | Contribs ]} 22:53, 6 September 2006 (UTC)

Well, if you divide something by 10, you can just move the decimal place over by one spot. For example, 123.456 divided by 10 is 12.3456. --HappyCamper 23:17, 6 September 2006 (UTC)

So, for example, 123 millimeter is 12.3 centimeter. --Lambiam^Talk 23:58, 6 September 2006 (UTC)

This is a joke right? Or are there people who do not know how to divide by 10? Ohanian 00:36, 7 September 2006 (UTC)

Nope, not a joke. --HappyCamper 00:41, 7 September 2006 (UTC)

I learnt something new :)

I know. Thanks for visiting the reference desk :-) --HappyCamper 22:03, 7 September 2006 (UTC)