From Wikipedia, the free encyclopedia

Mathematics desk
< March 29	<< Mar | March | Apr >>	March 31 >

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.

Contents 1 March 30 1.1 Maths Puzzle 1.2 Similar to upper triangular matrices 1.3 Probability in Mexican Train Dominoes 1.4 Limit of Detection Question 1.5 Integration 1.6 line plots 1.7 mathematics - mile/kilometer fractional relationship 1.8 The Mathematics of Warping

[edit] March 30

[edit] Maths Puzzle

Hey guys, I'm only in high school and I would like to get some help for this little maths puzzle: When Phil was 13 years old, Jill was five times as old as Bill. When Phil was twice as old as Bill, Jill was 19. Their three ages combined is now 100 years. How old is each now?

Thanks in advance for your reply :)... 60.241.227.234 09:04, 30 March 2007 (UTC)

p = Phil, j = Jill, b = Bill

Jill is the oldest, and Bill is the youngest.

When Jill was 19, that means that Phil's age was an even number (in that it could be halved to get Bill's age). So Jill and Phil's ages are of opposite parity. So add one year to get Jill at 20 years old, and Phil is 13, and Bill is 4. 20 + 13 + 4 = 37. 100-37 = 63. Can you do the rest?--Ķĩřβȳ♥♥♥ŤįɱéØ 09:05, 30 March 2007 (UTC)

I don't understand the reasoning, and, if I understand the hint, the answer should be p = 34, j = 41, b = 25. However, that is not a solution.

My approach is as follows. The variables p, b and j are as above. I use t to denote a number of years that has passed. The first given tells us:

p − t = 13  ↔  j − t = 5(b − t) (for all t).

This can be simplified by substituting t := p − 13 in the rhs, giving:

(1)  4p − 5b + j = 52.

The second given is:

p − t = 2(b − t)  ↔  j − t = 19 (for all t).

Substituting t := j − 19 in the lhs gives us:

(2)  p − 2b + j = 19.

Finally, it is given that:

(3)  p + b + j = 100.

From here this should be routine.  --Lambiam^Talk 12:01, 30 March 2007 (UTC)

I was able to solve it. The only thing I did differently was using "X" for the number of years ago for the first given and "Y" for the number of years ago for the second given. I don't think it's a good idea to use the same variable, "t", for what may be (and, in fact, is) two different values. StuRat 20:39, 30 March 2007 (UTC)

How can all t and all t be different values? Do you object to the reuse of "x" in "0+x = x+0 for all x and 1·x = x·1 for all x"?  --Lambiam^Talk 22:45, 30 March 2007 (UTC)

I don't quite understand your use of the phrase "for all t". That seems to be saying that Phil is twice as old as Bill at all times, which is not true, Phil is only twice as old as Bill at one specific time, and this is a different specific time than when Jill is five times as old as Bill. StuRat 07:39, 31 March 2007 (UTC)

Note the use of the symbol ↔, which denotes the logical connective of equivalence, often expressed in words as "if and only if". Using the usual symbolic way of expressing "for all" , the statement is:

For t = 17, for example, we have p − 17 = 2(b − 17) ↔ j − 17 = 19, and t = 16 gives p − 16 = 2(b − 16) ↔ j − 16 = 19. Using the values in the solution for p, b and j, the first becomes false ↔ false, which is true, and the second true ↔ true, which is also true. In all cases, whatever the value of t, both operands of the logical connective assume the same truth values, and so the whole formula is true.  --Lambiam^Talk 09:16, 31 March 2007 (UTC)

Yeah, I would also think your approach is systematic and probably easier to understand (provided of course one knows little bit of algebra). Except that the "(for all t)"s seem unnecessary... Hirak 99

If you say "for some t", the simplifications are invalid. We don't know how long ago it was when Jill was 19, but, calling that "t", whatever the value of t is, the two equations p − t = 2(b − t) and j − t = 19 have the same truth values. Another way of expressing "whatever the value of t is" is "for all t". In a sense I smuggled, because the formulation in natural language only gives you an implication, not an equivalence, but it is not hard to see that it can be strengthened to an equivalence. Without that, you need a slightly more complicated substitution t := 2b − p for the second given, obtained by solving the lhs for t.  --Lambiam^Talk 22:45, 30 March 2007 (UTC)

Kirbytime, you stated "Jill at 20 years old, and Phil is 13, and Bill is 4". But the original problem states that Phil was twice as old as Bill, when Jill was 19. So taking a year off, the quoted information would be "Jill at 19 years old, and Phil is 12, and Bill is 3" which doesn't match the problem. --LarryMac 18:49, 30 March 2007 (UTC)

I think I was drunk while I wrote that. I have no idea what that was about. Sorry.--Ķĩřβȳ♥♥♥ŤįɱéØ 20:42, 30 March 2007 (UTC)

(*Cough*) I'm thinking that if this student could juggle the abstractions presented as hints, the hints would not be necessary.

Especially, some interesting and important conceptual steps are omitted. We are talking about Phil, Bill, and Jill, or more specifically, their ages P, B, and J. These ages are functions of time, t. We are told about three different times, call them t₁, t₂, and t_now. Formally,

and

To make further progress, we must incorporate our knowledge of how ages depend on time. In the process, we should also try to eliminate any visible dependence on t_now. This leads to a key conceptual transformation.

1. Arbitrarily set t_now to zero, since its actual value shouldn't matter.
2. Replace absolute times t₁ and t₂ by time differences, δ₁ and δ₂.
3. Let p, b, and j be the ages now. (These we want to know.)
4. Instead of P(t₁), write p−δ₁; and so on. (This is how ages depend on time differences.)

We seem to have two extra unknowns, the deltas, but they do no harm. Now consider the equation we have restated as

with a little algebraic manipulation we can put all the unknowns on the left-hand side:

Proceeding in this way, we can obtain five equations in five unknowns.

Why do this? Well, this is a step where mathematical experience is invaluable. For our more experienced readers, the problem is now as good as solved. Why? Because we have a systematic procedure, called Gaussian elimination, that we can use once we have this form. But a high school student (like our poster) might never have seen such an advanced idea. Still, I think this is a good place to stop, to leave something yet to do. --KSmrq^T 06:11, 31 March 2007 (UTC)

[edit] Similar to upper triangular matrices

To the best of my memory, there was a SIMPLE procedure for the following purpose. Given a complex square matrix A, find a matrix P such that P^-1AP is an upper triangular matrix (nothing more, need not be a Jordan form). Because I do not expect anything more than upper triangular matrices, the procedure is expected to be short and simple (no vector subspaces are required). I did look up a number of standard textbooks from our local library, they all restrict themselves to diagonable matrices only, i.e. the eigen values are all distinct. Be grateful if somebody could offer me a pointer of this topic. Thank you in advance. Twma 07:43, 30 March 2007 (UTC)

Schur decomposition? --Spoon! 08:59, 30 March 2007 (UTC)

Jordan decomposition? (the Jordan normal form is upper triangular) (see also [1]) --Spoon! 10:55, 30 March 2007 (UTC)

I need a relatively simple procedure or algorithm for my purpose i.e. upper triangular but need not be a Jordan form. The general method to reduce a square matrix to Jordan form is too long. It is NOT acceptable for my special circumstance. I am still looking forward to have better answer. Thank you in advance. Twma 09:22, 1 April 2007 (UTC)

Are you sure you remember correctly? I ask because the usual simple procedures for converting a matrix to upper triangular form do not involve similarity transforms, P⁻¹AP. One option is the LU decomposition, but perhaps you are thinking of the QR decomposition. We do use similarity transforms to convert a matrix to upper Hessenberg form, but that includes a subdiagonal so it doesn't quite fit your description. Nor is there any likelyhood that a "simple" procedure can exist as you request, for the following reason. Suppose A is symmetric; then for any invertible P, necessarily P⁻¹AP is again symmetric. But that means that achieving "upper triangular" form is actually producing diagonal form; and this is the eigenvalue problem, which is not so simple as you seem to expect. --KSmrq^T 02:41, 2 April 2007 (UTC)

As indicated by the title, I do need P^-1AP for similarity of matrices. As pointed out by Spoon! above, Schur decomposition provides an algorithm based on the order of the matrix A. It is good but it is still very long. I wonder whether we can work with each eigen value b of A. The homogeneous system A-bI=0 of linear equations gives some linearly independent eigenvectors. When the geometric multipicity is not the same as the algebraic multiplicity, is there any SIMPLE EASY way to extend these independent eigenvectors? I cannot find what I want from our LOCAL library. Perhaps, somebody at the GLOBAL LEVEL may be able to help. Thank you in advance. Twma 06:44, 2 April 2007 (UTC)

How do I say this so it gets through? There is no simple way to find eigenvalues, even when the matrix is real and symmetric and thus guaranteed to be diagonalizable. We must iterate towards convergence; otherwise, we would have a closed-form way to find roots of a polynomial of arbitrary order, which is impossible. A similarity transform of a symmetric matrix produces a symmetric matrix; if the elements below the diagonal are zero, then so are the elements above the diagonal. The diagonal elements are the eigenvalues. Any method that can handle every complex square matrix A must be able to handle this special case as well. So if this fantasy SIMPLE method existed, it would contradict established theorems. In fact, the Schur decomposition does exactly what I suggest (see Golub and Van Loan, ISBN 978-0-8018-5414-9), yet you complain that it is not simple enough.

Let's try something completely different. Give us a bigger picture; what are you trying to accomplish? This fantasy task is your idea of a step towards solving an original problem. Maybe there is a way to solve that. --KSmrq^T 16:55, 2 April 2007 (UTC)

It comes to a point that I should admit that my memory (the first sentence of this track) was wrong. Schur decomposition is the best possible solution. Thank you all. Twma 03:25, 3 April 2007 (UTC)

[edit] Probability in Mexican Train Dominoes

Hello all.

Maybe you are familiar with the game Mexican Train Dominoes, if not, hopefully you are familiar with the physical form of dominoes in general. In Mexican Train dominoes, a player has an opportunity to play, in a single turn, as many dominoes as he can, matching values end to end in a line. Here are the what I believe are the significant points. Forgive me if I exclude an obvious necessities, for I am an idiot.

• ) There are 91 dominoes to draw from.

• ) Each domino has two "ends" and each end has a value. For example, a single domino may display 3 and 9, or 8 and 12, or 0 and 5.

• ) Values range from 0 to 12.

• ) Each possible combination of values in the set is exhibited but not repeated. For example, 3 and 9 on a domino is the same as 9 and 3.

• ) The object is to lay down dominoes consecutively while matching end values. For example, a player could place domino 3 and 9, and then 9 and 6, and then 6 and 8, and then 8 and 12. This end to end matching forms a line of dominoes called a train.

• ) For this case, three players draw 15 dominoes

• ) One player (the player in question), on his opening turn, plays a "double", or tile with matching values on its ends (he is compelled by the rules to begin with a double). For example, a 12 and 12.

Question: What is the probability that a player has a double to begin the train, and with his remaining 14 tiles the player would have dominoes that, properly played, use the remaining 14, beginning his matching on the double domino.

Background: I play this game with a pair of friends. We have once had a player lay out 14 dominoes including their beginning double. I call that near miraculous, and the chance of laying out all 15, well, darn unlikely.

I look forward to your thoughts. Bad carpet 07:55, 30 March 2007 (UTC)

My immediate thought is to consider a simpler case to see if what transpires can be extended. For n different digits, 0 to n-1, the number of dominoes is n(n+1)/2. I think however that if a sequence of a given length is possible, it can't be achieved by playing just any feasible domino at any stage (e.g. holding 00, 01, 11, and 12, all 4 can be laid out in that order, but playing 00, 01, 12 will have to stop there). Thus simulation is maybe the best option to estimate the probability for the 91,15 case described.86.132.235.7 10:12, 30 March 2007 (UTC)

A simulation with 1,095,000 runs gave 24,162 successes, or about 2.2%. The question whether a given set can be laid out as a train can be reduced to the question whether there is a Hamiltonian path in a graph obtained by a simple procedure from the set of dominoes. I general, figuring out whether a graph is "traceable" by a Hamiltonian path is difficult (NP-complete), and I see no simplification for the graphs we have here. In an actual game you might therefore well overlook a way of using up all your dominoes at once.  --Lambiam^Talk 13:36, 30 March 2007 (UTC)

You mention the Hamiltonian path, but this problem can be phrased in terms of the simpler Eulerian paths. Consider each number to be a vertex, and a domino to connect its two numbers; the total set of dominoes is then the complete (undirected) graph on those vertices plus one self-loop for each vertex. One person's "hand" is then a random draw of (here, 15) edges from that graph, and the question is whether that subgraph has an Eulerian path (noting that vertices with 0 degree are irrelevant to such paths). That question is answered by the "0 or 2 odd degrees" test with the proviso that the graph must be connected; we must also check for having the double.

As a trivial example that need not do either real test, for n values and a draw of m = 2 dominoes, we stipulate that first a double must be drawn (n choices) and then that the other tile (for m > 2, this is tiles, some of which could also be doubles) must be an edge incident on the chosen vertex (which has a "reduced degree" of n − 1). We then have a probability of : for n=2, 3, 4, 5 this is 2/3, 2/5, 4/15, 4/21. I don't know exactly how to generalize the selection procedure, but I feel like there's a beautiful solution somewhere nearby. --Tardis 21:16, 2 April 2007 (UTC)

[edit] Limit of Detection Question

I have plenty of experience determining the limit of detection for analytical chemistry methods. I've used several statistical methods for arriving at an LOD from given sets of data. I'm currently helping someone design a method evaluation though that is giving me some difficulty. It is a PCR assay where we are looking for trace contaminants of foreign DNA. If the contaminating DNA is above a certain level, the PCR procedure will amplify and it is detectable as a band on a gel, which is considered a "positive". Lack of a band would be a "negative". There is no aspect of the band that correlates to the concentration of the contaminant. Due to the nature of the PCR test, we can only consider these two result states. We expect there to be a range of concentrations that give either a positive or a negative due to the variability of the assay. I wish to know how to statistically determine at what level we can assign the LOD.

The LOD is defined as the level at which the assay gives a response (positive)likely to be distinguishable from a blank analysis (which should always be negative). I know perfectly well how to do this when both the blank and samples return numerical results, using tools such as signal/noise ratios, SD ranges, etc... How would one determine an LOD for binary results? We will be testing different concentrations of contaminants with multiple replicates; do we just call the lowest level with more than 50% positives the LOD? Whatever level we define will have to withstand regulatory scrutiny, so I have to be fairly sure that whatever method we select is statistically defensible. Also, We have to decide on the method to determine the LOD before the study is run.

Here is an example of the data we are expecting to receive:

p=positive, n=negative

concentrations from low to high

Dilution Level	Results
Blank	nnnnn
Level 1	nnnnn
Level 2	pnnnn
Level 3	ppnnn
Level 4	ppppn
Level 5	ppppn
Level 6	ppppp
Level 7	ppppn
Level 8	ppppp

We expect to see some aberrations in the data, such as the false negative at level 7. Would I call level 4 the LOD, since it is the first with more than 50% positive? That seems too easy... I would prefer a method that gave a degree of statistical certainty. For numerical assays I can choose α, etc. Any help or thoughts would be much appreciated.

--Mabris 12:19, 30 March 2007 (UTC)

In the table you give, how is "Level X" defined?  --Lambiam^Talk 12:54, 30 March 2007 (UTC)

Also, in actual testing, will you get 5 (independent) results p or n, as above, or just a single p or n, or something else?  --Lambiam^Talk 13:19, 30 March 2007 (UTC)

"Level X" would be any concentration of the impurity under analysis. For example, Level 1 could be 1ng/mL, level 2 5ng/mL, level 3 25 ng/mL. The point is just that we would be testing an increasing set of impurity concentrations and we wish to statistically define the lowest limit we can reliably detect. Each level would be tested x times, each test would be independent of each other. In the example, each level would be tested 5 times. If statistical power required it, we could test more replicates than that. I was hoping to get a general explanation on how to determine LOD in such an instance, since I will have to describe how it will be determined BEFORE we collect any real data.--Mabris 15:11, 30 March 2007 (UTC)

Lambian, I realize I didn't fully answer your second question. Each independent test would give a single n or p.--Mabris 16:01, 30 March 2007 (UTC)

Let me start by saying that what little knowledge and understanding I have of limits of detection comes from our article Detection limit. As I understand it, it is the level at which you can have a detection test that has a probability of false negatives that is at most a given threshold, usually 1%. This corresponds to what is called lower level of detection (LLD) in the article. Let me denote the threshold by the Greek letter θ, where θ = 0.01 corresponds to 1%.

Let pp(x) stand for the probability that a single test on a sample in which the concentration of the contaminant equals x returns a positive result. Assuming that pp(0) = 0, all negatives are false negatives. So the probability of a false negative equals 1 − pp(x).

I further assume that lim_x→∞ pp(x) = 1, and that the function is smooth, strictly monotonic and increasing at all values x of its domain with 0 < pp(x) < 1. This implies that the inverse pp⁻¹(y) is defined for all y between 0 and 1. Under all these assumptions, the LLD is simply pp⁻¹(1 − θ).

The question is now: can we determine that value with sufficient precision from the test data at various concentration levels? If θ is as low as 1%, this may be difficult or impossible. The basic idea would be this. Plot the data points in a graph, with the fraction of positives on the ordinate. Then draw a smoothly increasing curve that gives a good approximation of the data points and that runs from (0, 0) to (X, 1) for sufficiently high X. This curve allows you to read off an estimate of pp, and by using the intercept with a horizontal line at height y, an estimate of pp⁻¹(y). Do this for y := 1 − θ, and you have the LLD for the required confidence.

The problem now lies in "sufficient precision". Because the fraction of positives is subject to random fluctuations and can only assume values that are multiples of 1/n, where n is the number of tests for a given level, there is an error in the data points. We also need confidence that the estimated pp(x) at the spot x where we will pick LLD is at least equal to 1 − θ.

Let n_pos denote the observed number of positives at concentration x on a total of n tests. What can we say about y = pp(x); in particular, can we quantify the uncertainty? I can't think of any essentially better approach than taking the Bayesian posterior distribution starting from a uniform prior. Before normalization, this means a density at y of

(see binomial distribution), which gives us the beta distribution Β(n_pos+1, n−n_pos+1) for y. If f is the probability density function of this distribution, then the probability of a false negative is now

This can be simplified to (n−n_pos+1)/(n+2). If n_pos and n are large enough, this value will be at most θ. But let us look at the best possible case, n_pos = n. Then we can simplify further to 1/(n+2). In order not to exceed θ = 0.01, n would have to be a whopping 98!

If we estimate pp(x) by n_pos/n, we have n_pos = n·pp(x), and the stringent requirement (n−n_pos+1)/(n+2) ≤ θ is equivalent to (n(1−pp(x))+1)/(n+2) ≤ θ. But if pp(x) is estimated by reading it off from the smooth curve mentioned in the beginning, it is almost certainly a better estimate than n_pos/n. Depending on the data, it is probably fair to say that 3 to 5 times n observations contributed to the estimate. So perhaps the requirement can be relaxed to, say, (5n(1−pp(x))+1)/(5n+2) ≤ θ . To reduce the number of relatively uninformative tests you could try to use some initial portion of the data to guess whereabouts the LLD is likely to be, and then focus on sampling around that initial estimate. The value n = 5 from the example still seems way too low, unless you are willing to settle for θ = 0.04 or worse.

If the later actual testing of real samples can be composed from the outcomes of two or more independent tests, all this becomes much easier. For two tests pp(x) only needs to be at least 1 − θ^1/2, since the probability of two independent false negatives is only (1 − pp(x))²; for θ = 0.01 this means pp(x) ≥ 0.9, which replaces the earlier n ≥ 98 by n ≥ 8.

I hope I made no obvious bloopers, or, worse, non-obvious ones.  --Lambiam^Talk 21:55, 30 March 2007 (UTC)

[edit] Integration

Hi. Could anyone show me how to calculate this integral? I've looked around on the calculus articles but can't seem to find anything useful. Thanks

Scipio africanus 16:04, 30 March 2007 (UTC)

For a hint, see Integration by substitution. Baccyak4H (Yak!) 16:11, 30 March 2007 (UTC)

I think trigonometric substitution is more helpful, especially since he has an term.--Ķĩřβȳ♥♥♥ŤįɱéØ 20:34, 30 March 2007 (UTC)

Really the easiest is to look at List of integrals of irrational functions, third section, second case.  --Lambiam^Talk 22:06, 30 March 2007 (UTC)

Thanks guys, got it using Lambiam's link. Scipio africanus 11:04, 31 March 2007 (UTC)

[edit] line plots

Does anybody know what a line plot is? I keep hearing about it. I don't have a clue what it is. Thanks for the help.

It is simply a straight line plotted in a graph or scatterplot of other data. Usually it is the line that represents the best fit according to some criterion. For an example, see the second image in Wikipedia:Modelling Wikipedia's growth.  --Lambiam^Talk 17:31, 30 March 2007 (UTC)

[edit] mathematics - mile/kilometer fractional relationship

What is the fractional equivalent kilometer to mile?63.215.26.149 18:40, 30 March 2007 (UTC)

For rough approximation, I usually use 1 KM = 5/8 of a mile. To be more precise you can use the calculator feature of Google. Just enter "1 KM in miles" in the search bar and it returns 1 km = 0.621371192 miles. --LarryMac 18:45, 30 March 2007 (UTC)

1 mile is approximately equal to kilometers, according to Knuth. (Just follow the links.) – b_jonas 18:50, 30 March 2007 (UTC)

That doesn't appear to be any closer than 8/5. StuRat 20:28, 30 March 2007 (UTC)

I use 1 mile = 1.6km (and that's only if I don't have my trusty TI-84 with me).--Ķĩřβȳ♥♥♥ŤįɱéØ 20:36, 30 March 2007 (UTC)

I just use google. --Wirbelwindヴィルヴェルヴィント (talk) 00:16, 31 March 2007 (UTC)

1 kilometre is exactly mile. 220.239.107.54 22:16, 31 March 2007 (UTC)

[edit] The Mathematics of Warping

I was using Adobe Photoshop today and I discovered the warp tool. Its a pretty cool little tool, you can move the "warper" around and kinda stir the image around a bit. I was wondering what are some key mathematics terms I might want to look up if I wanted to discover how this works mathematically. BTW, I found one (that you might even say works a little better) online. Warp Bin Laden Root⁴(one) 20:59, 30 March 2007 (UTC)

To answer my own question, I think I figured out one way to do it.

You have the original image, and then you have the warp map. The warp map is an array (matrix) the same size of the image, but its elements consist of tuples giving info to what the color of the pixel should be under the warp. To calculate the color of a pixel under the warp, you consult the warp map and get its value (x,y) . Then could be some function of the set of values

where designates pixels of the original image at

and also possibly factoring in the distance between each of the the four coordinates (implicitly given for the four select pixels of the original map) and the point (x + i,y + j) in case you wanted to do a weighted average of the four pixels. The more I think about it, the more I'm certain that's the concept being used. (wait, there's probably aliasing issues as well, it may need to factor in more than just those pixels! But if so, when, and how?) The other question would be, how exactly would I perform the warping?

BTW, opinions still welcome. Root⁴(one) 03:22, 31 March 2007 (UTC)

You know, this "warp map" concept is pretty cool, you can create use the concept to "beam" portions of images to other places (I.E. copy or position flipflop). Or (with the as yet not known solution to the aliasing problem) you could copy an image, place it to the right (resized) a little bit, place another one a little bit smaller and further to the right, (one further still, one more .... ad infinitum (or rather until you cant draw any more)). I'm certainly having fun playing with it mentally. Woot! Root⁴(one) (Rooting for myself, go figure, and that really wasn't what I meant when I created my nickname, hah!) Root⁴(one) 03:54, 31 March 2007 (UTC)

Pardon me for interrupting your inner dialog, but you did ask for some mathematics. Image warping has been done for decades, and in a variety of ways. A key paper revealing methods is Thad Beier's "Feature-Based Image Metamorphosis". Typical mathematics involves splines and Bernstein polynomials. They're pretty cool. --KSmrq^T 17:03, 31 March 2007 (UTC)

Thank you sir! Root⁴(one) 02:16, 1 April 2007 (UTC)