Saturday, September 19, 2009


We have a infinity road and a car whose initial position(at time t=0) is some integer coordinate which you don't know.The car is running at a fixed velocity of some other integer per second which you do not know neither. You even do not know the car is running towards +infinity or -infinity.

What you can only do is at a single integral time point you can make a query like this: Is the car at point x now? (you can choose the integer x).You can do query only once at a time and will be given the answer "yes" or "no" based on the truth.

Design a query strategy such that you can guarantee you will get a "yes"
answer in finite time.

Sol: Hint Cantor Paring Function: