2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ Nov 26 '13 at 18:24
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.