A nice riddle, invented by a friend of mine

[Yoni]

Requires some math knowledge.

There's a boat, that has an initial starting point on the plane and a constant velocity vector.
The starting point and the velocity vector are integers; i.e., the starting point is (a,b) and the boat's position is advanced by (c,d) every second, and a,b,c,d are integers.
You have no knowledge of the boat's position or velocity, but you are allowed, once per second, to bomb a point of your choice in the plane. (After each bombing attempt you know only whether you failed or succeeded.)

Give an algorithm to find and bomb the boat.

[Invert]

Requires some math knowledge.

There's a boat, that has an initial starting point on the plane and a constant velocity vector.
The starting point and the velocity vector are integers; i.e., the starting point is (a,b) and the boat's position is advanced by (c,d) every second, and a,b,c,d are integers.
You have no knowledge of the boat's position or velocity, but you are allowed, once per second, to bomb a point of your choice in the plane. (After each bombing attempt you know only whether you failed or succeeded.)

Give an algorithm to find and bomb the boat.

Blah! I'll try.
Is the boat going in a straight line? Then (c,d) is the slope?

[Barabajagal]

For clarity, this boat would be sunk after one bombing, correct? It's not a battleship type thing?

[Yoni]

Invert: The boat is going in a straight line, starting with (x,y) = (a,b), and each second, x += c and y += d.
Andy: Yes, one hit gets it.

[rabbit]

Clearly the answer is to hack into the boat's GPS system.

[Yoni]

I know it seems impossible, but it can be done. I'll post the answer on the weekend unless someone solves it.

[Rule]

I know it seems impossible, but it can be done. I'll post the answer on the weekend unless someone solves it.

I don't have much time, but a hint would make it seem more possible.

[Falcon[anti-yL]]

This "plane" has no boundaries correct?

[K]

I can see how it would be easy given the initial position, but without that, I got nothin.

[Barabajagal]

Bomb one location repeatedly and hope it upsets godzilla who then destroys the boat for you.

[Yoni]

Rule, you can do it. (Encouragement rather than hint)
Falcon, correct.
K, how?

[K]

Rule, you can do it. (Encouragement rather than hint)
Falcon, correct.
K, how?

We'll assume that the boat gets one turn to move from it's initial position before we can bomb, so that we can't simply bomb the position (a,b) at t=0.
We'll also assume that there is an upper bound on the magnitude of the velocity, which I hope is not cheating.  If the boat is traveling at an infinite rate we're in trouble.

(a,b) is the position at t=0
(c,d) is the velocity

Every turn, the location of the boat is represented by:
x = a + t*c
y = b + t*d

All that remains is to plug each possible value of (c,d) into the equation, incrementing t each turn until we guess the velocity and thus the position correctly.

Edit:  if you were to graph what I'm talking about, it would look like a spiral starting at (a,b)  expanding outward.

[Imperceptus]

this is like battleship, lol. I lack the capacity to figure this one out.

[Yoni]

We'll also assume that there is an upper bound on the magnitude of the velocity, which I hope is not cheating.  If the boat is traveling at an infinite rate we're in trouble.

Many people I have told the riddle to have a difficulty with the distinction between "infinite" and "finite, but unbounded".

There is no upper bound on the velocity. But, it is finite.
That is, the velocity being (c,d), c and d are finite integers. But there is no upper bound on either one of them.

Get it?

I'll post the full solution later this evening.

[Yoni]

I HAS TEH SOLUTION

[Spoiler alert! Solution below.]







The solution in 1 sentence:
The cardinality of the set of all possible boats is Aleph-0, so order them, and on the n'th second, hit boat n in the position it would be in after n seconds.



Longer explanation:

How many possible boats are there? Each boat is identified by its initial position (a,b) and constant velocity vector (c,d), which are 4 integers. Therefore, the set of boats corresponds to the set of quadruples of integers (Z^4).
The cardinality of Z^4 is Aleph-0, the same as the cardinality of N. This is proven in courses on set theory, and I will not explain the full proof here (there are several proofs, given by giving an example of a one-to-one and onto function between the two sets).

K's partial solution already assumes that Z^2 has cardinality Aleph-0, when he says:
"All that remains is to plug each possible value of (c,d) into the equation"
Convince yourself that Z^2 has cardinality Aleph-0. Then you'll see that Z^4 also has cardinality Aleph-0, since (a,b,c,d) <--> ((a,b), (c,d)) <--> (e,f) <--> g. Get it?

Now that you agree that Z^4 has cardinality Aleph-0, we can order the boats and give all of them index numbers 1,2,3,... (this is because there are countably infinite boats). Each boat has an index number; no boat is missing from the list, and in particular, the actual boat is on the list. It doesn't matter how we order them.

This numbering is enough to start attacking: On the n'th second, try to attack the n'th boat - consider that n seconds have already passed, so attack the position it would be in after n seconds (as K has explained). Eventually, n will equal the actual boat's index, and the attack will succeed.




For bonus points: Improve the algorithm so that it also finds the starting point and velocity