Wikipedia:Reference desk archive/Mathematics/2006 July 26

From Wikipedia, the free encyclopedia

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.

< July 25 Mathematics desk archive July 27 >

Contents 1 A Quick question 2 Interesting Question 3 (a/(a+b)-(c/(c+d)=x 4 Fair dice 5 Prime Finder

[edit] A Quick question

I had a test on functions in one of my maths classes and the following question came up.I couldnt solve it so could anyone please tell me the answer alongwith the method of how to solve it?

(x^2)-4+(3/x)<0

I dont know the proper method of approaching the question so could someone please answer it?

This may well be homework, so I won't answer it, but I will give you a clue about one method of solving it. Try expressing the whole thing as one fraction (with denominator x) and then factorise the numerator. You should end up with something like , and then look for intervals where each bracket is positive or negative. Lets us know how far you get with this approach. Madmath789 10:33, 26 July 2006 (UTC)

... and you can double-check your solution by considering what happens when |x| is large, in which case the x² term dominates, and when |x| is small, in which case the 3/x term dominates. Gandalf61 10:51, 26 July 2006 (UTC)

Thank you so much madmath.I am getting the inequation, (x^3)-4x+3<0 which can be further simplified into (x-1)*(x^2+x-3)<0 which gives us x<1 or x^2+x-3<0 so now how do I solve the above quadratic inequation? please reply soon

one more thing is if an equation is less than 0 that is x^2+2x+1<0 then will the discriminant that is b^2-4ac be less than 0? If so ccould you tell me how?

You are on the right track. I recommend you draw a sketch graph for each of your expressions, to get a qualitative feel for how they behave at different values of x. One thing to note is that when you multiply the expression on the left hand side of your original inequality by x, you must remember that x may be negative, in which case the inequality is reversed - for example, starting from 1 > 0, you cannot conclude that 1/x > 0 for all x. The simplest approach is to split your argument into two cases - x greater than 0 and x less than 0 (the original expression is undefined when x=0). And the sign of the discrimant of a quadratic tells you whether the quadratic has real roots, and so whether its value has the same sign for all x, or whether it can change sign. If the discriminant is strictly positive then the quadratic has two distinct real roots a and b, so its value changes sign depending on whether x is within or outside of the interval [a,b]. Gandalf61 12:32, 26 July 2006 (UTC)

To be more specific, observe that we can transform

into

as you must have; but then we have three distinct cases.

1. x = 0
2. x > 0
3. x < 0

The first case must be excluded or else the original problem statement doesn't work. The second case is implicitly assumed in deriving

But the third case gives the alternative

The factorization

is correct, but leads to different conclusions in the two cases.

Note that we have a variety of possible sign combinations for the factors. For example, we must consider whether we might have x positive, x−1 negative, and the quadratic positive. Or we might have x negative, so necessarily x−1 is negative, and thus the quadratic must also be negative.

Looking specifically at the quadratic portion, we see that no matter whether x goes to positive or negative infinity, the polynomial value goes to positive infinity. (The x² term overcomes the others.) Therefore any dip below zero, if it exists at all, must happen between the zeros. We can use the quadratic formula to find the zero crossings. The discriminant is one way to determine if we have none, one, or two zeros. For a quadratic, the discriminant is an unavoidable part of computing the quadratic formula (it's the quantity inside the square root), so we needn't go to any extra trouble to discover that here we have two zero crossings. --KSmrq^T 17:26, 26 July 2006 (UTC)

This sort of problem is usually done by marking a number line with with all the zeros (and "infinities") of the left-hand side of the inequality and then testing each region. We can do this because we know the sign of the expression will not change unless x-1, x²+x-3, or x change sign. Each of these expressions can only change sign at a zero crossing. Use the quadratic formula to find the zeros of x²+x-3. You can solve it just with algebraic manipulations, but you run into problems like your disappearing x term in the denominator providing a zero crossing of sorts at x=0. Also, if there are two zero crossings at one point, then the sign doesn't change and if an expressions just touches zero, but doesn't cross (like x²), then there is also no sign-change. —Bradley 16:24, 26 July 2006 (UTC)

Thank You very much

[edit] Interesting Question

This is not homework; actually, I thought of it while I was in the shower.

What if you have an array of boxes like this:

_________
|  |  |  |
|__|__|__|
|  |  |  |
|__|__|__|
|  |  |  |
|__|__|__|

Each box can either contain 1 dot or no dots. How many different (not counting symmetries) patterns of dots can be made if each row of boxes must contain at least 1 dot and each column of boxes must contain at least 1 dot? I've tried just listing them all out. It gets tedious after a while. There must be a better way to do it.--Anakata 14:48, 26 July 2006 (UTC)

• Do mirror symmetries and rotational symmetries count? - Mgm|^(talk) 15:03, 26 July 2006 (UTC)

Here is a simple brute-force way to do it. There are 2⁹ ways to put dots in boxes. If you choose one row or column to leave empty, there are 2⁶ ways to put dots in the remaining boxes. If you choose two rows or two columns to be empty, there are 2³ ways to fill in the remaining boxes. If you choose one row and one column to be empty, there are 2⁴ ways to fill in the remaining boxes. So a first order approximation, correcting for some but not all of the overcounting, is

However, this still overcounts. It doesn't properly deal with configurations in which there are exactly two dots in one column or row and the rest of the board is empty (i.e. two columns and one row empty or two rows and one column), configurations in which there is exactly one dot (two columns and two rows empty), and configurations in which the entire board is empty. Here they are:

• two dots in same row/column is counted 1-3+1+2=1 times
• one dot is counted 1-4+2+4=3 times
• zero dots is counted 1-6+6+9=10 times

so the solution is

I guess that works, but it doesn't generalize nicely to larger boards.. –Joke 15:39, 26 July 2006 (UTC)

Set aside reduction by symmetries and consider placing dots as described. (This might be called a rook pattern, considerably simpler than the eight queens puzzle.) The position of the dot in the first row is column 1, 2, or 3. The position of the dot in the second row is one of the two remaining columns. The position of the dot in the third row is forced. (Read the article on permutations.) Since there are so few possibilities for your 3×3 example, it's probably simplest to write them all down and eliminate "duplicates" based on however you wish to define symmetry. For larger arrays, symmetry becomes more important. --KSmrq^T 17:50, 26 July 2006 (UTC)

But each row and column must contain at least one dot. They may contain two or three. –Joke 18:15, 26 July 2006 (UTC)

My mistake; thanks for catching it. The correction does make the counting more tedious!

Counting in a completely different way (by number of dots), I get 6+45+90+78+36+9+1, confirming 265 total. Most of the cases are easy. --KSmrq^T 00:38, 27 July 2006 (UTC)

Generalizing to n by n boxes, you get, for n=0,1,2,3,etc, the values 1, 1, 7, 265, 41503, 24997921, 57366997447, 505874809287625, 17343602252913832063, 2334958727565749108488321, 1243237913592275536716800402887, 2630119877024657776969635243647463625, ... (sequence A048291 in OEIS). So the answer is 265. The OEIS entry also gives a formula. --Lambiam^Talk 20:45, 26 July 2006 (UTC)

I disagree with those results. Looking at the case of 2x2 boxes, I only get 3 possibilities, once all rotational and mirror symmetries are removed (I used X's instead of dots):

OX   OX   XX
XO   XX   XX

For the 3x3 case, I get 38 possibilities:

3X cases:

OOX OOX 
OXO XOO
XOO OXO

4X cases:

XOX OXX  XOX OXX OOX OOX 
OXO OXO  XOO XOO XXO XOO
XOO XOO  OXO OXO OXO XXO

5X cases:

XXX XOX XOX  OXX OXX OXX 
OXO OXX OXO  XXO OXX OXO
XOO XOO XOX  XOO XOO XXO

6X cases:

XXX XXX XXX XXX OXX OXX  XXX XXX XXX XXX OXX OXX 
XXO OXX OXO OXO XXX XXO  XXO XOX XOO XOO XXX XXO
XOO XOO XXO XOX XOO XOX  OXO OXO XXO OXX OXO OXX

7X cases:

OOX OXO OXX OXX OXX XOX XOX XOX
XXX XXX XOX XXO XXX OXX XOX XXX
XXX XXX XXX XXX XXO XXX XXX XOX

8X cases:

OXX XOX XXX 
XXX XXX XOX
XXX XXX XXX

9X cases:

XXX
XXX
XXX

I probably made a few mistakes, but this shows the general scale of the answer. Please list examples of cases I've missed. StuRat 05:13, 27 July 2006 (UTC)

I think it wasn't clear which symmetrical answers we were including and which we were excluding, so we ignored symmetry entirely. The problem is symmetrical under rotations and reflection, and you appear to have excluded answers that could be produced from yours under these symmetries. But the problem is also symmetrical under arbitrary permutations of the rows and columns, which you have not considered. –Joke 14:32, 27 July 2006 (UTC)

Including the permutation symmetry, I think you get 1+1+2+3+2+1+1=11 solutions, although I didn't count very carefully. –Joke 14:40, 27 July 2006 (UTC)

I don't understand "symmetrical under arbitrary permutations of the rows and columns", can you please provide a pair of my solutions which are symmetrical in this way ? StuRat 19:54, 28 July 2006 (UTC)

If I may: Under 4 dot cases, these two

	●	●
	●
●

●		●
●
	●

differ only by a swap of the first two columns. --KSmrq^T 20:28, 28 July 2006 (UTC)

I see. Those case aren't what I, or most people, would call "symmetrical", however, so I doubt if they meant to filter those cases out (unless they explicitly said to do so). StuRat 04:49, 29 July 2006 (UTC)

Wow, I don't feel so bad for not finding the general formula. I am quite pleased that I can count, though. –Joke 20:53, 26 July 2006 (UTC)

[edit] (a/(a+b)-(c/(c+d)=x

This is not a homework question, but something developed from a question above about correlation for 2x2 tables.

In the formula (a/(a+b)-(c/(c+d)=x

with the constraint that all of a b c and d must be greater than or equal to zero.

what are the maximum and minimum possible values for x?

Thanks. --81.104.12.34 18:42, 26 July 2006 (UTC)

Just for visuals: —Mets501 (talk) 20:27, 26 July 2006 (UTC)

The maximum x value is 1 (when b and c are 0). The minimum is −1 (when a and d are zero). This is because for both fractions, both have a maximum of 1 and a minimum of zero. —Mets501 (talk) 20:33, 26 July 2006 (UTC)

[edit] Fair dice

A fair die is one that, when rolled, is equally likely to land on any given face. Clearly, the platonic solids make for fair dice, and the bipyramidal solids are also fair. Are there any other polyhedrons that can be fair dice? --Serie 22:02, 26 July 2006 (UTC)

Yes, the rhombic dodecahedron and other Catalan solids, as well as the trapezohedra. I'm not fully sure these are the only others, but I suspect so. --Lambiam^Talk 23:17, 26 July 2006 (UTC)

It would seem to me that you could take any regular polygon, use it as the base for a right prism, and adjust the height of the prism to make a fair die. The faces would not all be congruent, but it could be fair. If the height of the prism is very small in comparison with the bases, then you basically have a coin, and the probability is very high that the "die" will land on a base. On the other hand, if the height is very large, then you have a rod-like object^[1], and the probability is very high that the die will land on a side. There must be a certain height somewhere between these extremes for which it is equally likely that the die will land on any given face, but I'm not exactly sure how to calculate it. —Bkell (talk) 04:59, 27 July 2006 (UTC)

[1] I would rather say pencil-like object. :) Agree with the rest. CiaPan 05:40, 27 July 2006 (UTC)

To actually find the height (length) making this fair requires either a tremendous amount of experimentation, or a large dosis of unpleasantly difficult mathematics using some set of simplified laws of physics. --Lambiam^Talk 09:56, 28 July 2006 (UTC)

Dice#Non-cubical dice also mentions others, such as pentagonal trapezohedron. – b_jonas 14:06, 27 July 2006 (UTC)

The pentagonal trapezohedron is included in the class of trapezohedra mentioned above. --Lambiam^Talk 09:56, 28 July 2006 (UTC)

Can't you just take two identical pyramids with regular n-gon bases and stick them base-to-base to get a fair 2n-sided 'die'? Madmath789 10:01, 28 July 2006 (UTC)

Yes. Such a solid is called a bipyramid. Serie mentioned these in his initial post. ;-) —Bkell (talk) 14:44, 28 July 2006 (UTC)

Ah - so he did! :-) Madmath789 14:57, 28 July 2006 (UTC)

[edit] Prime Finder

At the bottom of Formula_for_primes#Prime_formulas_and_polynomial_functions, it shows a polynomial that, for all whole positive input values, will output one of three things: a negative, zero, or a prime. Most of the other number theory books I've read also mention it. There's something I don't get, though. There's been a whole lot of work put into fast optimization algorithms. Why can't one of those be applied to this? It seems like all it would take is a starting point above zero, and any point it moved to after that would be taking it upwards to another prime. Black Carrot 22:29, 26 July 2006 (UTC)

With the goal being what, enumerating primes? The problem is that it's a function of 26 variables, and 26-dimensional space gets very big very quickly. There's no way to know which direction to move to get to the next prime, and it could be far away. —Keenan Pepper 04:46, 27 July 2006 (UTC)

The other thing about this particular polynomial is that it involves a lot of subtraction. In fact, if you expand it out, you get one positive term at the beginning, and then a whole bunch of terms that are subtracted from it. In order to produce a positive number, every one of these subtracted terms must be zero (if I remember correctly), so you end up solving a massive system of equations, the same one shown in Formula for primes#Formula based on a system of Diophantine equations. The two methods are equivalent. If you just plug in values for the variables in the formula at random, you will almost always get a negative number. —Bkell (talk) 05:04, 27 July 2006 (UTC)

Looking at it a little more closely, I remember how it works again: The factor k + 2 at the beginning will give you your prime number, but it's multiplied by . If any of the terms is nonzero, then everything within those square brackets will be less than 1, i.e., zero or negative (since all the variables are integers); this will produce a nonpositive result. Consequently, k + 2 is prime if and only if every term is zero. Now you will notice that each term corresponds exactly to one of the equations given in the next section as . —Bkell (talk) 05:14, 27 July 2006 (UTC)

Consequently, your chances of randomly plugging integers into the formula and getting a prime are equal to your chances of randomly plugging integers into the system of equations and getting a solution, i.e., really, really slim. Also, once you have a solution, you won't be able to easily modify one or two of the variables to get another solution. —Bkell (talk) 05:18, 27 July 2006 (UTC)

Actually, I've been told (but I don't really believe) that there is no known set of values for those 26 unknowns yielding a prime value. But the mere existence of this rumour shows that it must be hard to find such a set.--gwaihir 11:33, 27 July 2006 (UTC)

I somehow must not have made my point clear. Given any solution to it (even a negative one, come to think of it), it should be possible, using a hillclimbing algorithm (in other words, one of those things that finds the direction of highest slope and follows it) to move farther and farther upwards. It may be a complicated polynomial, but it's still differentiable at every point, and therefore, at every point it's possible to calculate the slope in all directions. Even a local maximum (where there is no upward slope) shouldn't stop it for long, since that's one of the main things people working on this have been developing ways to bypass. So, it seems like, given any starting point, this would be guaranteed to move quickly and reliably upwards. As soon as it passed zero, it would be generating only primes, right? So why wouldn't this work? Black Carrot 18:49, 27 July 2006 (UTC)

For one thing, the polynomial is nonpositive almost everywhere (though maybe not in the strict mathematical definition of "almost everywhere") if the variables are nonnegative, so it would probably take a very long time to find any point above zero. Additionally, it's not enough to just find a positive value of the polynomial: you must find a positive value of the polynomial where all of the variables have integral values. As Keenan Pepper noted, you will be working in 26-dimensional space, and that's a lot of dimensions to search. Supposing that you happen to find a positive value of the polynomial where all of the variables are integers, then you have one prime, but that point is almost certainly a local maximum, and to find another positive value of the polynomial will not be trivial. I'm sure you can generate primes by the method you described if you stick with it long enough, but it's probably much faster to just do trial division. ;-) —Bkell (talk) 20:27, 27 July 2006 (UTC)

Perhaps the solution can be found within bosonic string theory? –Joke 20:48, 27 July 2006 (UTC)

How bumpy could this thing really be? I mean, it only has a degree of what, twenty-five? That's practically flat. Actually, it doesn't look to me like it even goes above ten, but let's say it does. Take the graph for one variable (g, maybe) with all the others set. That can't possibly have more than a dozen local maxima. Let another letter vary, and there's maybe 150 maxima, tops, right? And remember, that's an overestimate, since a lot of the bumps should be lost to negative inputs and stuff. I don't see how there could be more than 12²⁶ local maxima. And of course, there would be lots and lots and lots of saddle points. Am I wrong? Now, even a number with 30 digits is pretty tiny compared to the number of primes this has to be able to output, so it seems to follow that there are indeed flat spaces, and that the mountains don't just go straight down in all directions. And to respond to the integer thing, sure, you'll keep landing on real numbers instead of natural numbers, but can you actually believe that the output will suddenly dip to negative if you slide half an inch to the left? Black Carrot 23:00, 27 July 2006 (UTC)

"Can you actually believe that the output will suddenly dip to negative if you slide half an inch to the left?" Yes, because of the factor. Those expressions must all be exactly zero if the value of the polynomial is going to be positive. Therefore, if they are all zero at some point, and you move "half an inch to the left," one or more of them are suddenly not going to be zero anymore, and the value of the polynomial will be negative. —Bkell (talk) 04:16, 28 July 2006 (UTC)

You make a persuasive argument. However, all the variables would be changing at once, so there's really no guarantee they wouldn't all continue to cancel out. And this thing was designed to give useful outputs at the integers, so it seems reasonable to suppose any positives discovered near integers were pointing the way to the actual mountaintop nearby. Sitting on the side of the mountain, if you will. I'm beginning to wonder how this could work in the first place, though. I don't suppose you could point me to a proof of some sort? Black Carrot 17:49, 28 July 2006 (UTC)

After some googling I found this link. Is this the proof you're looking for? — Pt _(T) 00:13, 29 July 2006 (UTC)

Sorry, my computer locks up every time I open a pdf. Could you summarize it? Black Carrot 01:32, 29 July 2006 (UTC)

Keep in mind that this polynomial wasn't designed to be "useful"; it was only designed to explicitly show such a thing (i.e., a polynomial whose positive values are identical with the set of primes).

"However, all the variables would be changing at once, so there's really no guarantee they wouldn't all continue to cancel out." That's true, there's no guarantee, but look at the system of 14 equations at Formula for primes#Formula based on a system of Diophantine equations. You need to find a set of 26 integer values for the variables a through z that satisfy all of those equations simultaneously in order to get a positive value from the polynomial and find a prime. There may be many places on the 26-dimensional surface, between the lattice points, where the value of the polynomial is positive; at such points, plugging the values of a through z into the right-hand sides of each of the 14 equations will yield values in the open interval (−1,+1). But just because you "almost" have a solution to the system of equations doesn't mean that you can move to a nearby lattice point and get a solution.

The proof that this polynomial behaves as claimed involves many deep results in number theory. It would be difficult to give a summary; the paper itself is already very brief in its proofs. Perhaps you can view the PDF on another computer? —Bkell (talk) 03:04, 29 July 2006 (UTC)

I'll see what I can do about the pdf, and thanks for showing it to me. What do you think, however, of my analysis of its bumpiness? I honestly don't see how infinitely many extremely steep mountaintops, so steep that many of them fit in between consecutive integers, could be fit into this formula. It's a polynomial of finite length, which means finite bumpiness. Only stretches of flatness can be infinite, so some of those must occur in the positive area, to account for all the infinite primes. Black Carrot 19:50, 29 July 2006 (UTC)

Yeah, I don't know how to answer that right now. Let me think about it. —Bkell (talk) 06:21, 30 July 2006 (UTC)