# 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?

• Every way i tried I was using probability. I can't seem to wrap my head around it without using it. I'm going to work with what you showed me and report back. Thanks! Nov 26 '13 at 18:24

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.