Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

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

Battleship on the number line

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

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

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

Re: Battleship on the number line

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

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

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

Re: Battleship on the number line

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 tongue


Bad speling makes me [sic]

Offline

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

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

Re: Battleship on the number line

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

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

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

Re: Battleship on the number line

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

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

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

Re: Battleship on the number line

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

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

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

Re: Battleship on the number line

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

Offline

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

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

Re: Battleship on the number line

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


"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

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

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

Re: Battleship on the number line

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

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

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

Re: Battleship on the number line

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

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

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

Re: Battleship on the number line

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


"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

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

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

Re: Battleship on the number line

My bad.

Offline

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

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

Re: Battleship on the number line

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

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

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

Re: Battleship on the number line

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

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

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

Re: Battleship on the number line

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

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

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

Re: Battleship on the number line

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

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

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

Re: Battleship on the number line

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


Why did the vector cross the road?
It wanted to be normal.

Offline

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

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

Re: Battleship on the number line

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

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

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

Re: Battleship on the number line

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 tongue


Bad speling makes me [sic]

Offline

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

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

Re: Battleship on the number line

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


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

Offline

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

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

Re: Battleship on the number line

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


"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

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

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

Re: Battleship on the number line

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

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

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

Re: Battleship on the number line

But surely...


Why did the vector cross the road?
It wanted to be normal.

Offline

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

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

Re: Battleship on the number line


"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

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

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

Re: Battleship on the number line

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.


"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

Board footer

Powered by FluxBB