Wikipedia:Reference desk/Archives/Mathematics/2009 June 15

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.

June 15

Predicting Score in a T20 match

Hi! I am trying to build a mathematical model to predict the number of runs that would be scored by a team if we know the number of runs and the wickets fallen after a few overs. I have made an initial empirical formula:

Let n_x be number of runs scored in x overs and let the number of wickets fallen be w, if x ≥ 10 then

n₂₀ ≈ n_x ( 1 + 2 log (x/w²)) + (10 – (x/2)) log(n_x x/w(20-x))

Can you help me in improving this model? shanu 04:30, 15 June 2009 (UTC) —Preceding unsigned comment added by Rohit..god does not exist‎ (talk • contribs) I fixed the wiki-formatting of the original post. Abecedare (talk) 05:24, 15 June 2009 (UTC)

It would be best to start by plotting n₂₀ versus x, n_x and w, using the database of all previous match scores. That way one can have a general idea of the shape of the curves (surfaces) and also compare the performance of various proposed formulae.

For those who have no idea of what is being discussed: See Twenty20, which is a form of cricket. Abecedare (talk) 05:17, 15 June 2009 (UTC)

In case you don't know this already, be aware that the Duckworth-Lewis method is the canonical way of doing this. Algebraist 07:56, 15 June 2009 (UTC)

Olympiad question

In my wanderings, I came upon a paper for the 1981 International Mathematics Olympiad. It contained quite an interesting question:

Suppose that f(x,y) satisfies:

$(1)\qquad f(0,y)=y+1$

$(2)\qquad f(x+1,0)=f(x,1)$

$(3)\qquad f(x+1,y+1)=f(x,f(x+1,y))$

Hence determine f(4,1981)

I've tried to solve it. The direction I choose has the potential for success, but would take many hours to complete. I figured that, beginning with

$f(4,1981)=f(3,f(4,1980))\,\!$

and continuing thus to find

$f(4,1980)=f(3,f(4,1979))\,\!$

and then

$f(4,1979)=f(3,f(4,1978))\,\!$

would result in a sequence ending with f(4,0). I therefore concluded that f(4,0) was critical, and determined that it produced 7 13. But that doesn't help much, because we then need to plug in 7 13 for

$f(4,1)=f(3,f(4,0))=f(3,13)\,\!$,

and then complete resultant plug ins for y in f(4,y) all the way from 1 through 1981. Obviously, this would take an unfeasible period without mechanised assistance: the Olympiad participants were given 4 hrs 30mins for 6 such problems. I concluded that my approach was "the long way round" and that a more elegant solution probably expending half or a single page is to be found here. Can anyone provide some insight? Cheers, —Anonymous Dissident^Talk 08:03, 15 June 2009 (UTC)

This is actually the Ackermann Function and so there should be something on that link that should provide some help. It is very odd for them to ask a question about such a well-known function and the more recent Olympiads would be very unlikely to contain such a question. --Anthonymorris (talk) 08:12, 15 June 2009 (UTC)

Indeed - the solution is in Ackermann function. But if you want to tackle the problem from first principles, I would start out by finding a recurrence relation for f(m, n) for small fixed values of m. So:

$f(1,n+1)=f(0,f(1,n))=f(1,n)+1{\text{ for }}n\geq 0$

$f(1,0)=f(0,1)=2$

$\Rightarrow f(1,n)=n+2$

then we can proceed to f(2,n):

$f(2,n+1)=f(1,f(2,n))=f(2,n)+2{\text{ for }}n\geq 0$

$f(2,0)=f(1,1)=3$

$\Rightarrow f(2,n)=2n+3$

and so on. Two more steps and you can find an explicit expression for f(4,n) (incidentally, I think your value for f(4,0) is incorrect - it should be 13). Then you can determine an explicit expression for f(4,1981) - you won't be able to write out all of its digits, but it is close to a (very large) power of 2. Gandalf61 (talk) 08:46, 15 June 2009 (UTC)

I agree, doing it again. I'll try your method now. —Anonymous Dissident^Talk 09:19, 15 June 2009 (UTC)

The problem is that those in the competition were not permitted a calculator. How could they have computed the output without one? —Anonymous Dissident^Talk 09:28, 15 June 2009 (UTC)

A calculator really wouldn't help because f(4,1981) is so large. However, it is close to a large power of 2 which can be expressed concisely as a power tower or using tetration notation. Gandalf61 (talk) 09:28, 16 June 2009 (UTC)

Actually, it is not so odd for them to ask a question on a well-known concept. For instance, on a recent Tournament of the towns paper, a question was asked on the concept of combinations. In fact, this question was relatively simple if the solver knew some basic identities related to the concept. Furthermore, this question was one of the "tougher questions" given more points than some of the other questions on the paper. On the other hand, the international mathematics olympiad is much more reputable, and it does strike as surprising that a question on such a well-known concept should be asked. --PST 09:11, 15 June 2009 (UTC)

Conic section-Simultaneity in relativity

This is a question about conic section related to simultaneity in special relativity. If the tilt of the plane is determined, can the conic sections always parallel-shifted in the same direction to match another conic section of the same cone but and a plane which is parallel to, and has the same distance to the apex of the cone as, the first plane? Like sushi (talk) 12:49, 15 June 2009 (UTC)

I can't understand your question. Could you maybe describe the physical situation that led you to ask it? -- BenRG (talk) 10:18, 16 June 2009 (UTC)

The cone is the light cone, the planes are the colloection of paths of observers starting from some distance behind and forward of the origin of the light cone, of every y value (the distance perpendicular to the motion of the observer). The section should represent the place and time at which those observers observe the light (in the reference frame of the source). As the time of the observation of light should be the same time in the referance frame of the observers, moving relatively inertially and were at the same distance away in the reference frame of themselves at the time of emission, in the direction of x (the direction of the motion of the observers), the difference of two obsevation time v.s of distances should be at a fixed rate (if simultaneity is shared in one inertial frame). (If the distances in the direction of x is the same in the reference frame of the source, and the point is compared only within the-same-y-plane, as the time at which the event (emission) occurs is 0 for both, the distances in the reference frame of the observers are supposed to be the same.)

I want to confirm that all such two points are in lines of the same tilt.If all such points are in lines of the same tilt, then the sections also can be always parallel-shifted to match the other.

Like sushi (talk) 06:57, 17 June 2009 (UTC)

Does each plane correspond to one observer? The set of its possible world-lines is the interior of a light-cone. Do you mean something else by 'paths'? —Tamfang (talk) 15:40, 26 June 2009 (UTC)

I divide every value in a table with the smallest value in the same table. What have I done.

Hi all.

Here comes a table with 2 columns and 3 rows.

200 400

600 800

500 700

Now I divide every value in this table with the smallest value, which happens to be 200.

1 2

3 4

2.5 3.5

Here comes my question: What is this operation called? Does it even have a specific name?

I was thinking that perhaps I have "normalized every value in the table to the smallest value", but I'm not sure. Is normalize the correct answer?

Thx. Contributions/194.237.142.21 (talk) 14:15, 15 June 2009 (UTC)

Yes, "normalize" is the first word that comes to mind. Contributions/67.122.209.126 (talk) 15:40, 15 June 2009 (UTC)

Differential equation

Is it possible to find a general solution for $a{\ddot {y}}y+b{\dot {y}}^{2}+cy^{2}+d=0$? Contributions/76.67.79.151 (talk) 19:15, 15 June 2009 (UTC)

Here is a first information; do you have a particular request? Assuming a≠0, you can normalize and fix a=1. For all ξ, y₀≠0, y₁ the Cauchy problem with initial data y(ξ)=y₀ and y'(ξ)=y₁ has a unique local solution, which has a power series expansion at ξ, tha is $\scriptstyle \;y(x)=\sum _{k=0}^{\infty }y_{k}(x-\xi )^{k}$, where the coefficients (y_k) depend on y₀ and y₁ (not on ξ). You can determine the power series equating the coefficients in the differential equation. You will get a recursion formula for the y_k, possibly too complicated to put in a closed form. Of course, if y₀=0 then also y₁ is fixed by the equation for you have by₁²+ d=0. Notice also the transformation z:=y^b+1, (with a=1 as before) that puts your equation in the form z"=R(y).--pma (talk) 20:54, 15 June 2009 (UTC)

Intro to nonlinear differential and integral equations by Harold Davis (ch8 especially) might be a good read for the OP, this equation is of type 12 in the 1st appendix Silverfish70 (talk) 21:11, 15 June 2009 (UTC)

Thank you. 76.67.77.126 (talk) 03:42, 16 June 2009 (UTC)

Formula for Sine based on just angle

If I'm using a circle with radius 1, what is the formula to get the sine from just the angle? Not anything like sin x=oppositie/hypotenuse. I'm looking for the way it is done like with just the angle. --Melab±1 ☎ 20:15, 15 June 2009 (UTC)

this? Trigonometric functions#Series definitions --pma (talk) 21:00, 15 June 2009 (UTC)

See also:

• Exact trigonometric constants for how sin x can be calculated for some angles using trigonometric identities
• Generating trigonometric tables for various numerical approaches to computing sin x for any angle.

Note tat some of the formulas and results are given for angles expressed in radians rather than degrees. Abecedare (talk) 21:12, 15 June 2009 (UTC)

Growth rate of functions

Is there an increasing function (of one real number, obviously) that grows faster than any polynomial, but slower than any exponential? Is there a proof that there is no such function? deranged bulbasaur 20:38, 15 June 2009 (UTC)

Subexponential growth for example $e^{\sqrt {x}}$ (also see Sub-exponential time) (Igny (talk) 20:44, 15 June 2009 (UTC))

Thanks. Actually, that answer was pretty obvious. I guess I should have thought about it more. On a related note, why are these growth rates not really talked about? One frequently hears talk in computer science that would seem to indicate that either a polynomial algorithm can be found, or one is stuck with an exponential worst-case. Is it simply that sub-exponential solutions are rare? Also, shouldn't these time complexities generate their own complexity classes with their own complete problems and such? My trite error was caused by the fact that apparently this is just never mentioned, at least in the relatively introductory materials I have read on the topic. deranged bulbasaur 23:21, 15 June 2009 (UTC)

Integer factorization is a well studied problem where the current best algorithm is subexponential. Taemyr (talk) 00:06, 16 June 2009 (UTC)

Except that "exponential" and "subexponential" are ambiguous terms in this context, many authors will label growth rates $2^{x^{\epsilon }}$ for any fixed $\epsilon >0$ (such as the $2^{\sqrt {x}}$ function above) as "exponential". The choice of terminology here is usually pure PR—people who do upper bounds will advertise their $2^{\sqrt {n}}$-time algorithm as "subexponential", while people who do lower bounds will advertise their $2^{\sqrt {n}}$ lower bound as "exponential". Integer factorization is not known or expected to be subexponential in the latter sense (i.e., $2^{x^{o(1)}}$). — Emil J. 10:48, 16 June 2009 (UTC)

What is interesting however, is that there is a function which is faster than $x^{\alpha }$ for any $\alpha >0$, but slower than $e^{x^{\beta }}$ for any $\beta >0$. Can you construct one? (Igny (talk) 02:37, 16 June 2009 (UTC))

Sure, $x^{\log x}$ for example. Or even $x^{\log \,\log \,\log \,\log x}$, etc. I think your confusion about CS classes is you may have heard that NP-hard problems like SAT probably take exponential time. That is a stronger statement than P!=NP, which says there is no polynomial-time solution (but there might be a subexponential one). That there is a subexponential algorithm for factoring is taken as evidence that factoring is not NP-hard (though this is not known). For an ultra slow-growing function, read about the running time of the optimal union-find algorithm. 67.122.209.126 (talk) 09:42, 16 June 2009 (UTC)

The non-NP-hardness of factoring has nothing to do whatsoever with the so-called "subexponential" algorithm for factoring. The running time of that algorithm is $2^{n^{\epsilon }}$ for some $\epsilon >0$, and there are even EXP-complete (thus definitely NP-hard) problems solvable by algorithms using the same running time. The reason is that substitution of a polynomial (which is a blowup of the input performable by a poly-time (or log-space if you wish) reduction) into $2^{n^{\epsilon }}$ may give you $2^{n^{c}}$ for arbitrary large c > 0. For the same reason, running times of this form are often called "exponential", not "subexponential", as already mentioned above.

The reason why integer factoring (or more precisely, a decision version of factoring; integer factoring itself is a function problem rather than a decision problem, hence its comparison with classes of decision problems like NP is meaningless) is considered not to be NP-hard is that it is in ${\rm {NP}}\cap {\rm {coNP}}$, hence if it were NP-hard then the polynomial hierarchy collapses to PH = NP = co-NP. — Emil J. 10:48, 16 June 2009 (UTC)

Going back to growth of funcions, a nice exercise is this: prove that for any see the forgotten assumption below function f:R→R there exists a real entire function g such that g(x)>f(x) for all x. --pma (talk) 10:57, 16 June 2009 (UTC)

That's impossible, some assumption must be missing here. There are only 2^ω entire (or just continuous) functions g: R → R. Enumerate them as {g_x: x ∈ R}, and diagonalize: define f(x) = g_x(x) + 1. Then f is not majorized by any entire function. — Emil J. 12:21, 16 June 2009 (UTC)

A simpler argument, if I understand the question correctly: define f(x) = 1/x whenever x is not 0, and, say, 0 when x is 0 (it doesn't really matter). This is a function that maps reals to reals; it may not look pretty at 0, but there was no such requirement. And, of course, the function is unbounded around 0, so any function g satisfying g(x)>f(x) for all x would have to have a singularity at 0. --COVIZAPIBETEFOKY (talk) 12:31, 16 June 2009 (UTC)

Yes, that's much simpler, thanks. Generalizing it a bit, a necessary condition for f to be majorized by an entire (or just continuous) function is that f is bounded above on every finite interval. My impression is that this condition is also sufficient. — Emil J. 13:16, 16 June 2009 (UTC)

Ops, I beg your pardon, I forgot to write it; of course, f has to be bounded on bounded intervals, that's for sure. Or we can assume "f even and increasing on positive x", or "f continuous" if you prefer. The condition is indeed sufficient; that was the exercise. --pma (talk) 14:23, 16 June 2009 (UTC)