Я правильно понял, что речь именно о целых (а не натуральных) числах?

Правильно. Именно о целых.

На самом деле всё равно, целые или натуральные.

Пусть x -- начальная координата, v -- скорость.

Для каждого начального условия (x,v) мы можем определить положение лодки в текущий момент t: x(t)=x+vt. А множество (x,v) явно счётно, поэтому просто перебираем их любым способом (например, по классической квадратной спирали), тратя на проверку каждого варианта ровно по одному выстрелу (стреляем в точку x+vt). Таким образом, мы гарантированно поразим субмарину, находившуюся изначально в точке (x,v) за не более чем (2*max(x,v)+1)^2 (это размер квадрата, в котором точно лежит точка (x,v)) выстрелов.

Классическая квадратная спираль -- это один из способов пересчитать все целые точки на плоскости. Начинаем в нуле (0,0). Потом шагаем, например, направо (1,0), вниз (1,-1), влево (0,-1), влево (-1,-1), и т.д. разворачиваем спираль вокруг центра: (-1,0)-(-1,1)-(0,1)-(1,1)-(2,1)-(2,0)-(2,-1) и т.д.

Так мы пересчитываем все целые точки (х,у), перенумеровываем их, т.е., научным языком, выстраиваем взаимнооднозначное соответствие между целочисленными точками плоскости (х,у) и натуральным рядом.

?
Что-то я потерялся. По-моему, в _движущуюся_ субмарину, не зная её скорости так просто гарантированно не попадёшь :)

eruditor
Извините, конечно, математик я, наверное, никакой, но это не решение.
Поясняю:
Большой Бессмертный Вечносытый Заяц(ББВС)прыгает всегда на 2 метра. Маленький Бессмертный Вечносытый Заяц(МБВС) на 1 метр. ББВС стоит на метр впереди МБВЗ. Они одновременно начинают прыгать. Далее...
1) МБВЗ пройдет по всем точкам, на которых был ББВЗ? Ответ:Да!
2) Зайцы когда-нибудь окажутся в одной точке? Ответ:Нет!