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.

[quote author=Yoni link=topic=17079.msg173475#msg173475 date=1191377288]
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.
[/quote]

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

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

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.

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

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

[quote author=Yoni link=topic=17079.msg173530#msg173530 date=1191516745]
I know it seems impossible, but it can be done. I'll post the answer on the weekend unless someone solves it.
[/quote]

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

This "plane" has no boundaries correct?

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

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

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

[quote author=Yoni link=topic=17079.msg173547#msg173547 date=1191543899]
Rule, you can do it. (Encouragement rather than hint)
Falcon, correct.
K, how?
[/quote]
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.

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

[quote author=K link=topic=17079.msg173553#msg173553 date=1191548879]
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.
[/quote]

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.

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 ;)

Cool riddle! May I post it on a forum I visit? (Not x86 of course, as most people there have already seen it :P) I will cite your friend as the inventor, as well as you and this thread of course.

EDIT: I don't see how the current algorithm does not already yield (a,b,c,d). If you know the value of n when you hit the boat, and the rule by which you order the boats, then you can just look for the nth quadruple on your indexed list.

Yeah, you may post it. Go ahead.

As for your attempt of solving the bonus, there is a problem with your solution, but I won't say what it is.

[quote author=Ender link=topic=17079.msg173672#msg173672 date=1191744049]
Cool riddle! May I post it on a forum I visit? (Not x86 of course, as most people there have already seen it :P) I will cite your friend as the inventor, as well as you and this thread of course.

EDIT: I don't see how the current algorithm does not already yield (a,b,c,d). If you know the value of n when you hit the boat, and the rule by which you order the boats, then you can just look for the nth quadruple on your indexed list.
[/quote]

If you bomb (x,y) at time t, you know the magnitude of the x and y components of the velocity but not the sign... the boat could have started at four different positions, depending on the sign of both components of the velocity.

here c,d represent the velocity...)
[code]

(+c,-d)
\        / (-c, -d)
  \    /
    \/
    /\
  /    \
/        \ (-c, +d)
(+c,+d)
[/code]

Good point, K.

[s]The boat sinks in one hit for the bonus problem as well as for the original question, right? If the boat were to be "invincible" and keep going after getting hit, then I believe the bonus problem would be much more tractable, and the algorithm 100% accurate.

But suppose the boat does sink in one hit. Is this algorithm supposed to be successful 100% of the time? [/s]

[s]Nevermind, I think I've thought of a way to do it. Will post later if I can turn the idea into a solution.[/s]

lol, I'm insanely busy so nevermind that.

It's easy.  A bomb wouldn't halt all momentum (unless it entirely obliterated the ship), so you can just look at where it goes after you hit it.

K is wrong.

Unrelatedly: A single bomb doesn't destroy the ship.

Oh, okay. Maybe this works.

Solution:

Let S be the set of all boats and let ~ be a relation on S. Each boat can be represented as B = (a, b, c, d) where (a,b) is the starting point and (c,d) is the velocity vector. Let |B| = (x, y) = (a + cn, b + dn). Define B_i ~ B_j iff |B_i| = |B_j|.

Let B1 be the real boat. We know the set of all boats to be Z^4 and thus countable, so on some nth try we will hit B1. Once we hit B1, construct the ~-equivalence class for B1, we'll call it C. Every boat in C must have a different velocity vector, or else they would have originated at the same point, in which case they would be the same boat. Thus no boat in C will ever meet again. And since the equivalence class C is a subset of Z^4, it will also be countable.

Thus we can "narrow in" on the equivalence class C and only target boats in C. Index every boat in C as 1, 2, 3, ... Every boat we hit in C that's not the real boat will be a miss, since no two boats in C can ever coincide again. Since C is countable, we will eventually hit the real boat on the kth try, and thus the coordinates of the real boat will be the boat in C indexed k.

Very nice and well-worded attempt. Seems to be correct, although I'm not sure you've proven it correctly.
(You can show it easily using linear algebra; if a boat in subset C is hit, the parameters describing the boat satisfy 4 linear equations in 4 parameters, and this system has a single solution which is the parameters of the real boat.)

Anyway, I know a simpler solution (and I hope Ender's solution hints at it).
I'll post it sometime this week unless you can find it.

The solution to the bonus:

Order the ships as in the non-bonus question. Once you hit a boat, try to hit it a second time.
If you succeed twice in a row, that's the exact boat and you can extract its parameters.
If you succeed and then fail, that's not the exact boat and you may keep trying the next boats.

(I'll leave the exact proof of the solution to you.)

I'd understand that if I knew what "cardinality" was