October 13th, 2007
Post solution related stuff on this page, as usual.
Pages: 1 2
This entry was posted
on Saturday, October 13th, 2007 at 10:45 pm and is filed under Math, Riddles.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
October 15th, 2007 at 12:31 am
The following solution is not pretty, but it works.
Let us call any member of the set Z^4 (indicating starting position and velocity) a ship, and denote the set itself Ships. There are countably many ships, therefore there is a bijection f:N↔Ships. If we know the details of our ship, then we know its location on every turn. Thus, at any turn t, we assume that our ship is the ship f(t), and try to bomb it based on that assumption. We might hit the ship by luck with the wrong assumption, but the right assumption will definitely cause a hit, and will be made for any ship S at turn f^-1(s). This strategy has some similarity to a certain riddle about people with hats.
I don’t like this solution that much. One reason is that each guess would hit more than one ship – it would hit a Z^2-grid of ships. You might improve the strategy by “skipping” turns when the ship f(t) would already have been bombed before, but then again, that is probably no improvement at all. The second reason is that the bijection f between N and Z^4, which determines the strategy, is too arbitrary. There might be a more canonical solution (pun not intended), which I would like to see.
October 15th, 2007 at 12:55 am
Just to sharpen a minor point: The riddle about people with hats that I mentioned appears here, under the name of Guess my Number. The similarities between the strategies are the following (Note: Contains most of the solution to Guess my Number):
1) I need to know something. (My own number / The ship’s current location)
2) If I knew something else, which is static*, I would also know the thing that I need to know. (The sum of all numbers mod N / The ship’s parameters)
3) Because it is static, I can guess that second thing, and I am given just enough guesses to make sure that one of them is right. (There are N possible remainders, and each of the N men can guess one number / There are countably many parameters for the ship, I am given countably many tries)
* By static I mean that it does not depend on the guess itself, that is, all guesses are equivalent. “My own number” depends on who is guessing, so it is not static; The sum of all numbers does not depend on the guesser, so it is static. Similarly, the ship’s location changes with time, so it is not static, but its parameters are constant in time, so they are static.
October 15th, 2007 at 4:07 am
First of all, great solution. I do not really understand what you don’t like about it (or rather, I do not think there is a canonical improvement [did like the pun though!]).
Note also that the solution extends easily to a grid of QxQ (and a velocity in QxQ).
This brings up an interesting question. Say that the starting parameters are in R^4 (no longer countable) but the ship has a positive size (e.g. it is some sort of rectangle). Will the solution for QxQ still work? Now, since the ship has a positive size you could suggest to simply use the solution of the parameters in Q^4 (a small error is acceptable). The problem is that any small error in the initial parameters might lead to greater errors as the enumeration continues, thus never hitting the ship. As Nadav pointed out, it seems to me (I did not give this too much thought – I might be wrong) that no solution exists for this case.
Anyone cares to differ?
October 15th, 2007 at 2:56 pm
oh, Dan – you beat me to it
i thought it was a very nice riddle and likewise the solution.
first, i understood the riddle somewhat differently. I understood “pirate’s strategy” as an algorithm, or in other words a computable function f:N->Z^4. this obviously doesn’t matter in the problem as it was introduced, since Z^4 is computable.
This extends to any computable family of boat routes (e.g functions in N->Z^4) – for example all polynomial routes. but this is not tight.
take for example an uncomputable (or even uncountable!) family of routes, and concatenate to them the point (1,1). the pirate of course could succeed.
October 15th, 2007 at 6:00 pm
The real variant is interesting. I believe (that is, have proven and believe that my proof is valid) that there is a working strategy for the one dimensional case (or rather – as long as the velocity space is one dimensional), and that there is no strategy for greater dimensions. This is because the sum of n^-d, over natural n, converges for d=1 and is unbounded for d > 1.
In one dimension: Let us assume that the boat is a closed interval, and that we know its length L. We may then recalibrate our unit (let us call it the meter) so that the boat is of any size we want, let us say 1 meter. Let us also assume that we are given that the boat’s center’s original position was an integer, that is the starting properties of the boat are from the set ZxR. At turn t (that is, after the boat has moved t times; for simplicity we assume turns start from 1), we can cover with our bomb a subset of parameters {k}xI (in fact, a lot more than that, but that is not important), where k is an integer of our choice and I is a closed interval of length L/t, by bombing the place where the center of the boat would be now if the starting parameters were (k, (midpoint of I)). It is possible to cover the set ZxR with the intervals of length 1/n (I leave it unproven, as it is quite tedious to write it out), so that is a working strategy.
Now, instead of assuming the boat is 1 meter long, let’s assume that is 2 meters long. Any such boat with properties RxR would contain in itself a boat with length 1 meter and center with integer coordinate. The algorithm presented above would then surely hit the contained boat, so it will also hit the real boat.
For dimensions d > 1: Again, assume we start after the boat has moved. Let us also assume that we know the position of where the boat started is 0 (this doesn’t help us at all). Let us also assume that the boat is a cube with side of 1 (It’s easy to see that if we can’t hit a cube, we can’t hit any other shape, and if we can hit a cube, we can hit any other shape; shapes are assumed to be with positive volume, and all terms are meant to be non dimension-specific). The set of starting parameters is R^d, of the velocities. At a turn t, if we shoot a bomb at point P, then we will hit any boat with parameters in a the cube of side 1/t and center P/t. The volume of this cube is t^-d, and so the total volume of points covered will be Sum(t^-d : t from 1 to infinity) < infinity, so necessarily not all of the space will be covered, thus no strategy would be foolproof.