You are not logged in.

- Topics: Active | Unanswered

**Dross****Member**- Registered: 2006-08-24
- Posts: 325

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.

Bad speling makes me [sic]

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

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.

Why did the vector cross the road?

It wanted to be normal.

Offline

**Dross****Member**- Registered: 2006-08-24
- Posts: 325

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

Bad speling makes me [sic]

Offline

**Ninja 101****Member**- Registered: 2006-02-20
- Posts: 936

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

Chaos is found in greatest abundance wherever order is being saught. It always defeats order, because it is better organized.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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.

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**Dross****Member**- Registered: 2006-08-24
- Posts: 325

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.

Bad speling makes me [sic]

Offline

**tt****Member**- Registered: 2005-07-03
- Posts: 32

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

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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

Offline

**tt****Member**- Registered: 2005-07-03
- Posts: 32

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

Offline

**tt****Member**- Registered: 2005-07-03
- Posts: 32

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.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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

Offline

**tt****Member**- Registered: 2005-07-03
- Posts: 32

My bad.

Offline

**Ninja 101****Member**- Registered: 2006-02-20
- Posts: 936

it is going southwest to the falklands at 100 knots.

Chaos is found in greatest abundance wherever order is being saught. It always defeats order, because it is better organized.

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

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?

Why did the vector cross the road?

It wanted to be normal.

Offline

**Dross****Member**- Registered: 2006-08-24
- Posts: 325

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.

Bad speling makes me [sic]

Offline

**Dross****Member**- Registered: 2006-08-24
- Posts: 325

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.

Bad speling makes me [sic]

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

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.

Why did the vector cross the road?

It wanted to be normal.

Offline

**Ninja 101****Member**- Registered: 2006-02-20
- Posts: 936

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

Chaos is found in greatest abundance wherever order is being saught. It always defeats order, because it is better organized.

Offline

**Dross****Member**- Registered: 2006-08-24
- Posts: 325

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

Bad speling makes me [sic]

Offline

**Ninja 101****Member**- Registered: 2006-02-20
- Posts: 936

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

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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

Offline

**Dross****Member**- Registered: 2006-08-24
- Posts: 325

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

Bad speling makes me [sic]

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

But surely...

Why did the vector cross the road?

It wanted to be normal.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

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.

Offline