You are not logged in.
#1 2006-09-07 23:37:10
- Dross
- Power Member
Offline
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]
#2 2006-09-08 01:10:08
- mathsyperson
- Moderator
Offline
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.
#3 2006-09-08 02:56:04
- Dross
- Power Member
Offline
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 
Bad speling makes me [sic]
#4 2006-09-08 22:38:49
- Ninja 101
- Power Member
Offline
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.
#5 2006-09-09 00:56:49
- Ricky
- Moderator
Offline
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..."
#6 2006-09-09 01:49:58
- Dross
- Power Member
Offline
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]
#7 2006-09-10 03:36:47
- tt
- Member
Offline
Re: Battleship on the number line
I think it's impossible too unless two ends of the line joins each other straightly .
#8 2006-09-10 11:00:16
- Ricky
- Moderator
Offline
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..."
#9 2006-09-10 11:14:00
- tt
- Member
Offline
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-10 11:17:03)
#10 2006-09-10 13:35:23
- tt
- Member
Offline
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.
#11 2006-09-10 14:02:19
- Ricky
- Moderator
Offline
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..."
#13 2006-09-11 22:31:15
- Ninja 101
- Power Member
Offline
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.
#14 2006-09-11 23:29:34
- mathsyperson
- Moderator
Offline
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.
#15 2006-09-12 02:29:19
- Dross
- Power Member
Offline
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]
#16 2006-09-12 09:37:29
- Dross
- Power Member
Offline
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]
#17 2006-09-12 10:20:49
- mathsyperson
- Moderator
Offline
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. 
Why did the vector cross the road?
It wanted to be normal.
#18 2006-09-12 22:23:21
- Ninja 101
- Power Member
Offline
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.
#19 2006-09-12 22:47:53
- Dross
- Power Member
Offline
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
Bad speling makes me [sic]
#20 2006-09-13 22:19:32
- Ninja 101
- Power Member
Offline
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.
#21 2006-09-14 10:52:38
- Ricky
- Moderator
Offline
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..."
#22 2006-09-15 05:35:21
- Dross
- Power Member
Offline
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-15 08:47:26)
Bad speling makes me [sic]
#23 2006-09-16 05:46:12
- mathsyperson
- Moderator
Offline
Re: Battleship on the number line
But surely...
Why did the vector cross the road?
It wanted to be normal.
#24 2006-09-16 10:14:25
- Ricky
- Moderator
Offline
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..."
#25 2006-09-16 10:20:24
- Ricky
- Moderator
Offline
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..."