finding a an object with constant velocity on an infinite grid in discrete time steps Assume you have an object moving at a constant velocity(up, down, left, right) in a grid. You have unlimited resources (memory, time). At any given time step in the grid, you can "guess" the location of the object, and you win if it is currently at that position. Without relying on probability techniques, what would be the best way to approach catching this object?
Hint: "Guess" the starting point and the velocity, and use diagonalization. (I.e. make a list $\langle p_i, v_i \rangle$ of pairs of starting points and velocities, and at time $t$ test $p_i + tv_i$.) I'll let you figure out why it works.