Consider the task of programming a 1D car starting on point $0$. The car drives 1 km / min ( to both left and right).
The task is to find a coin at an unknown integer distance $x$ (in km) from the starting point $0$.
In the most efficient way ofcourse !!
Example
The coin is at 3. The car is programmed to drive to 7 first , then -9.
The car starts going to 7 but stops when he arrives at 3 because the coin is detected.
3 km hence 3 min. Optimal result.
Second example
Coin at - 4.
Car is programmed
Go to 1, -1 , 2 , -2 , 3 , -3 , 4 , -4 , ...
Coin is found at -4 but the result is very poor !!
So the question is
What is the best strategy or way to program the car ??
Is The best way even unique ?
Im talking best on average because depending on the position of the coin luck might help ofcourse.
Going forward all the time is most successful if $x$ is positive ofcourse. But fails 50 % of the time !!
It needs to work all the time !!
This appeared as a simple task to me.
But I started getting doubts.
Should we program like
Go to 1,-2,4,-8,16,... ?? Or more like Fibonacci ?
Or maybe triangular numbers ?
And how to make this mathematically formal ?
Also , what kind of math is this ?? Is this computer science or not ?
Not sure about the tags.