Equation that always has a single solution, obtainable only by numerical methods.

Question

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.

Answer 1

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:

Answer 2

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).

Answer 3

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.