A nice riddle, invented by a friend of mine

[Ender]

Cool riddle! May I post it on a forum I visit? (Not x86 of course, as most people there have already seen it ) 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.

[Yoni]

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.

[K]

Cool riddle! May I post it on a forum I visit? (Not x86 of course, as most people there have already seen it ) 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.

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 Select Expand



(+c,-d)
\        / (-c, -d)
  \    /
    \/
    /\
  /    \
/        \ (-c, +d)
(+c,+d)


[Ender]

Good point, K.

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?

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

lol, I'm insanely busy so nevermind that.

[rabbit]

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.

[Yoni]

K is wrong.

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

[Ender]

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.

[Yoni]

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.

[Yoni]

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

[UserLoser]

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