Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking for a parametrized equation (i.e. a class of equations), which has the following properties:

  • It has the form of $f(x) = 0$, where $f(x)$ is an increasing or decreasing (i.e. monotone) function
  • It has a solution
  • It has a single solution
  • Boundaries for the solution can be easily calculated from the parameters
  • The solution can be obtained easily only by numericalal methods, in particular, binary search.

I need it to set up a problem for a programming contest for first-year students, in which they must find the solution for an equation, given its parameters. The first three requirements make things simpler. The requirement about the boundaries will enable them to set up the boundaries for their binary search (they don't know any more sophisticated numerical methods yet). The last requirement is to ensure that they cannot analytically find a solution, so they will have to use binary search.

If, in addition, the equation makes physical sense, that would be perfect (I could invent a background story for the problem). Hope the question is on topic.

share|improve this question
    
+1 VIVA Armenia. –  Babak S. May 3 '13 at 10:00
    
@BabakS. Wow, that was... unexpected :) –  Armen Tsirunyan May 3 '13 at 10:02

3 Answers 3

up vote 2 down vote accepted

Here is another idea. Use the $\Gamma$ function to pose the problem instead:

$$f\left(t;\theta\right)=\Gamma\left(\theta t+2\right)-1.5$$

$\theta$ is the parameter you requested. A sufficient condition for a root to exist on $t\in\left(0,1\right)$ are $\theta\geq 1$, which gives you a very large range of parameters to use.

I doubt they will find a direct way to compute the inverse of $\Gamma$.

You can allow them to use one of $\Gamma$'s well-known approximations. One of the Lanczos approximations featured on that page (at the time of writing) is:

$$\Gamma\left(x\right) \approx x^{x-\frac{1}{2}}e^{-x}\sqrt{2\pi}\left(1+\frac{1}{12x}+\frac{1}{288x^2}-\frac{139}{51840x^3}-\frac{571}{2488320x^4}\right)$$

for all $x\in\mathbb{R}$.

For $\theta=1$, the answer is approximately $0.6628$. Here is a plot using the approximation to the Gamma function:

enter image description here

share|improve this answer

If you mix polynomials and exponentials, you can find functions that cannot be solved analytically, but are amenable to numerical methods. Something like $x^2+e^x-50$ over $[0,100]$ seems to meet your needs. Polynomials plus trig functions are another candidate. So $(x-1)^5+\sin x-100$ over $[0,100]$ is another one.

share|improve this answer

It seems like what you want them to program is the bisection method. Your requirements are equivalent to $f\left(a\right) f\left(b\right)<0$ (i.e. the boundary points have different signs) and that the root be unique on $\left[a,b\right]$. The second requirement is equivalently stated as $$\exists x_0\in\left[a,b\right]\colon \forall x\in \left[a,b\right]\colon f\left(x\right)=0\implies x=x_0$$

The set $\mathcal{S}$ of functions that satisfy this requirement is large (e.g. the set of all monotonically increasing functions on $\left[a,b\right]$ with $f\left(a\right)\leq 0$ is a subset of $\mathcal{S}$).

Here's an example question:

A car is travelling along a straight road with velocity $f\left(t\right)=\sin\left(\frac{\pi}{2}t\right)-\frac{1}{2}$ (feel free to scale the units so that they make sense). Time $t=0$ corresponds to the starting time, while $t=1$ corresponds to the ending time. At what time does the car stop moving? You are not allowed to use trigonometric functions to evaluate $f\left(t\right)$. Instead, use the fact that

$$\sin\left(x\right)=x-\frac{x^3}{6}+\frac{x^5}{120} + O\left(x^6\right)$$

to get an approximate solution (i.e. use the approximation

$$\sin\left(x\right) \approx x-\frac{x^3}{6}+\frac{x^5}{120}$$

in your algorithm).

share|improve this answer
    
Thank you, but this doesn't seem very suitable because I cannot tell them what to use and what not - that's the rules of programming contests. The equation you suggested can be solved analytically. Additionally, It is not parametrized, therefore there is no possibility for test cases, i.e. the input is the parameter, the output is the solution for the equation. –  Armen Tsirunyan May 3 '13 at 10:39
    
Parameterizing the equation is simple: just scale it by a constant. As for the other problem, no matter the function (in this case it is $\sin^-1$), it is usually feasible to find software that has methods to evaluate the function, or tables that are interpolated for particular values of it. So, the question really boils down to replacing $\sin$ with something more obscure. –  par May 5 '13 at 1:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.