Battleship on the number line

Dross · 2006-09-07 01:37:10

There is a battleship on the number line with position x at time t, with x always an integer when t is an integer.

It starts off at an unknown point at t = 0, and travels along the number line at a constant speed in an unknown direction.

For each integer value of t, you get to blow up one bomb at any point on the number line you wish in an attempt to blow up the ship. Bombs are always replaced after being detonated, so you can blow up the same point on the number line as many times as you wish.

Give an algorithm that will garuntee that, after some period of time, you will destroy the ship.

mathsyperson · 2006-09-07 03:10:08

Are we told what the constant speed is that the battleship is travelling at? If we're not, then I don't think it's possible. Maybe it's not even if we are. Or maybe I'm just not thinking hard enough. Maybe I'm saying maybe too much.

Dross · 2006-09-07 04:56:04

We are not told the speed the battleship is traveling at, nor where it starts, nor which direction it is going... but I assure you, there is a way to do it

Ninja 101 · 2006-09-08 00:38:49

what kind of battleship and of which nationality tell me and I will tell you the answer.

Ricky · 2006-09-08 02:56:49

I believe it is impossible.

Let's say you do come up with an algorithm, and that it takes time T to reach some point X. Since the ship's speed is unbounded, it can just move away from you at some speed greater than the "speed" of your algorithm.

Dross · 2006-09-08 03:49:58

Ricky wrote:

Let's say you do come up with an algorithm, and that it takes time T to reach some point X. Since the ship's speed is unbounded, it can just move away from you at some speed greater than the "speed" of your algorithm.

You are quite close to hitting the nail on the head here! I assure you it is entirely possible, I wouldn't want to infuriate anybody by wasting their time... you just have to be a little creative (though I don't mean bending the rules - it's not a word puzzle)

Ninja: It is HMS Dreadnaught, so British.

tt · 2006-09-09 05:36:47

I think it's impossible too unless two ends of the line joins each other straightly .

Ricky · 2006-09-09 13:00:16

Funny, I've never seen the end of the number line. What does it look like?

tt · 2006-09-09 13:14:00

Well, it looks more like a circle around the Earth on which the battleship is moving away from its starting point.

Last edited by tt (2006-09-09 13:17:03)

tt · 2006-09-09 15:35:23

If it has the Earth involved, suppose the Earth is absolutely round and the number line is a straight line, you can ignite the bomb at the point of contact when t=0 before the battleship sailing off into space.

Ricky · 2006-09-09 16:02:19

tt, the problem mentions nothing about the earth. We are on the number line.

tt · 2006-09-09 16:47:53

My bad.

Ninja 101 · 2006-09-11 00:31:15

it is going southwest to the falklands at 100 knots.

mathsyperson · 2006-09-11 01:29:34

Here's my thinking:

The battleship might not be moving at all, which means that the algorithm needs to cover every square on the number line at some point. The simplest way of doing that would be going 0, 1, 2, 3, 4, etc. You could also do 0, 2, 1, 3, 5, 4, 6, 8, 7, 9, or some other fancier way of moving, but as long as you attack every square at some point (which you must, or you might miss it), then you'll always have an average speed or no more than 1.

Therefore, the battleship just needs to move away from you at a speed of more than 1 and it will never get hit. Alternatively, if the battleship is moving quickly, then it could easily sail straight through your algorithm without being hit!

Therefore, I don't believe that it's possible. Can anyone see any flaws with my logic?

Dross · 2006-09-11 04:29:19

mathsyperson wrote:

The battleship might not be moving at all, which means that the algorithm needs to cover every square on the number line at some point. The simplest way of doing that would be going 0, 1, 2, 3, 4, etc. You could also do 0, 2, 1, 3, 5, 4, 6, 8, 7, 9,

Don't forget you'd need to cover all the negative numbers as well.

mathsyperson wrote:

Therefore, the battleship just needs to move away from you at a speed of more than 1 and it will never get hit. Alternatively, if the battleship is moving quickly, then it could easily sail straight through your algorithm without being hit!
Therefore, I don't believe that it's possible. Can anyone see any flaws with my logic?

What I think you're saying is that if your algorighm has a certain fixed speed (or rate of coverage of the integers) then it is possible for the ship to travel faster than this fixed speed, so it can never garuntee hitting the ship.... more on this later, but more than one hint for now would be far too generous.

Dross · 2006-09-11 11:37:29

As an aside, you can make a very minor variation to this algorithm so that it will work for a ship whose starting point and speed are any rational number, but you cannot do it for a ship whose starting point and speed are any real number.

mathsyperson · 2006-09-11 12:20:49

I realised that it would need to cover all the negative numbers, but since 0 to infinity is an infinity of numbers, then if the algorithm works for that range then it must also work for the -infinity to infinity. And 0, 1, 2, 3 is easier to write than -∞, -∞+1, -∞+2 etc.

So I'm just making it simpler to write, but it shouldn't make it any easier to solve than it was before.

Your hint says that I should think of the ship as [being at point x +yt at time t] but I don't really see how that helps. Then again, it is very late. I'll ponder this further and see if I get any insight in my sleep.

Ninja 101 · 2006-09-12 00:23:21

no the ship is my personal clipper and is flying northeast to mars.

Dross · 2006-09-12 00:47:53

Ninja 101 wrote:

no the ship is my personal clipper and is flying northeast to mars.

Now all you have to do is point out where mars is on the number line and you've got your answer

Ninja 101 · 2006-09-13 00:19:32

46427. is where it is on the number line, i win.

Ricky · 2006-09-13 12:52:38

Is anyone still trying to solve this? Or can we ask for the solution?

Dross · 2006-09-14 07:35:21

Well, for anyone still trying to figure it out, here is a really big hint:

And if you just want to know the solution (I told you there was one!) - here it is:

Last edited by Dross (2006-09-14 10:47:26)

mathsyperson · 2006-09-15 07:46:12

But surely...

Ricky · 2006-09-15 12:14:25

Ricky · 2006-09-15 12:20:24

Now, let's make things interesting:

Would such a solution work on the rational line? What about the real line?

Bonus points if you name the property of these numbers which gives the solution.

Math Is Fun Forum

#1 2006-09-07 01:37:10

Battleship on the number line

#2 2006-09-07 03:10:08

Re: Battleship on the number line

#3 2006-09-07 04:56:04

Re: Battleship on the number line

#4 2006-09-08 00:38:49

Re: Battleship on the number line

#5 2006-09-08 02:56:49

Re: Battleship on the number line

#6 2006-09-08 03:49:58

Re: Battleship on the number line

#7 2006-09-09 05:36:47

Re: Battleship on the number line

#8 2006-09-09 13:00:16

Re: Battleship on the number line

#9 2006-09-09 13:14:00

Re: Battleship on the number line

#10 2006-09-09 15:35:23

Re: Battleship on the number line

#11 2006-09-09 16:02:19

Re: Battleship on the number line

#12 2006-09-09 16:47:53

Re: Battleship on the number line

#13 2006-09-11 00:31:15

Re: Battleship on the number line

#14 2006-09-11 01:29:34

Re: Battleship on the number line

#15 2006-09-11 04:29:19

Re: Battleship on the number line

#16 2006-09-11 11:37:29

Re: Battleship on the number line

#17 2006-09-11 12:20:49

Re: Battleship on the number line

#18 2006-09-12 00:23:21

Re: Battleship on the number line

#19 2006-09-12 00:47:53

Re: Battleship on the number line

#20 2006-09-13 00:19:32

Re: Battleship on the number line

#21 2006-09-13 12:52:38

Re: Battleship on the number line

#22 2006-09-14 07:35:21

Re: Battleship on the number line

#23 2006-09-15 07:46:12

Re: Battleship on the number line

#24 2006-09-15 12:14:25

Re: Battleship on the number line

#25 2006-09-15 12:20:24

Re: Battleship on the number line

Board footer