Not Even The Number Line Is Safe
There is an enemy submarine located at an unknown integer somewhere on the number line. The submarine is moving at a constant integer distance per minute (also unknown, and can be positive or negative). Every minute, you can fire a missile at an integer on the number line in an attempt to destroy the submarine.
Is there a strategy to strike the submarine in a finite amount of time?
Assume that you move first and that futuristic medical science allows you to continue firing missiles at the number line for as long you need to.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
What if the submarine is located on at a real (not necessarily integer) point and travels at a constant real (not necessarily integer) speed, but you can fire 1 misslie every real (not necessarily integer) time?
Can you hit it within 1 minute?
Log in to reply
Yes! Use the fact that R^2 and [0, 1] both have the same cardinality as R.
Log in to reply
Cardinality-wise that works, and I can appreciate that aspect of this fun extra question and answer.
However, the question's premise has a problem: there is no such thing as "every real time". The reals (incl. any real interval such as [0, 1]) are uncountably infinite, and thus cannot be enumerated. You cannot possibly have a list of points in time (not even an infinite one) to fire your shots on as time progress.
IMHO, unrealistic hypotheticals unrelated to the core of the question ("medical advancements allow you to keep shooting essentially forever") are a great tool for writing interesting puzzles without making them sound boring or overexplained.
However, logically unsound hypotheticals about the very same general topic that a puzzle is about ("suppose you can shoot at every real time" in a question about cardinalities) may spread confusion or false impressions in the possibly uninitiated target audience.
Good problem. Just one question. Why is my ability to fire missiles determined by medical science instead of military technology?
Log in to reply
Because of the small problem that you might die long before you hit the submarine. I suppose you may also need futuristic military technology which allows you to have as many missiles as you need, but military technology won't help you much if you're dead.
Log in to reply
We might also assume that the medical science is also available to the sub and it's crew along with the ability to remain submerged for long period.
If not, you could extend the parameters to 3 dimensions to include the lifespan of the sub but that would be a wasteful experiment if we continued firing missiles at a dead sub.
How would you know if it was moving positively or negatively? Or does it not matter. I personally thought the answer was no as you couldn't know which way it was going.
Log in to reply
it doesn't matter, since you're covering the negatives as well. consider the submarine being (-1,-1), meaning it started from point -1 then moved -1 every minute. as you can see from the above image, this is the 5th shot, so we assume it moved 5 times, it being at the -6 point, we shoot, we hit, we save the day. and because the spiral above covers every pair of numbers, for initial position and velocity, both positive and negative, while also keeps track of the number of times we shot/it moved, we are able to find the submarine in a finite time.
This is a ludicrous proof of finitude. My 'crazy ivan' will infinitely foil you! Either I outrun your shots as you try to cover every possible start position, or I move slowly towards you and you miss me because of your enlarging firing pattern. -Sitting on Thor's Primes
Log in to reply
It's based on starting position. Since speed is constant, the actual position where the missile is fired won't be the starting position, but rather the starting position plus the speed times the number of minutes passed. So you can't "pass" the missile.
I'm thinking of a natural number. Can you guess it with a finite number of guesses? No. Infinite regardless of cardinality.
Log in to reply
Not true. If your number is n , then I will be able to guess it in n guesses by starting at 1 and then guessing the following natural numbers. It is true that n can be arbitrarily large , but this is not equivalent to saying that n is infinite. No matter what number you choose, it can be guessed in a finite amount of time.
I'm kicking myself for not realising that this was simply a question of cardinality.
Lesson learnt.
Excellent... and by extension, sub can start anywhere in 3 (or more) dimensions with any velocity and be torpedoed in finite time (assuming torpedo size > 0)
But suppose the velocity is 0. Then choose to fire at 0, then 1 then -1 etc. This is a countably infinite set which cannot be completed in finite time. Thus the time to find the sub is infinite.
Log in to reply
It's not so much that there is an infinite set of integers but rather that the location and speed are finite. From that point on, the approach will inevitably find that combination.
If the line is finite then the answer is yes if infinite the answer is no.
There are a few issues with your question. Firstly as a minor point of clarity your question poses, "a line", (one dimension), your solution has two lines (two dimensions). More importantly though there is no clarity as to whether there is a finite distance the sub can travel on the line and if so what happens if the sub reaches the end of that finite distance, does it then return, is the line a circle or does it just stop; as you have not clarified we must assume the line is infinite in both directions.
As an example of why the answer is no. Using a single line; if your integer value changes at the same rate as that of the sub and both are moving down the line in the same direction, you would be running one step behind the sub on every shot and never hit the sub. As you have not said the sub must turn at the end of the line or stop it would seem the line must be infinite therefore the answer is no you and the sub will live forever and an arms dealer will be very rich with an everlasting income!
Log in to reply
The second dimension is used so that two variables (the submarine's starting position and the submarine's velocity) can be considered.
The submarine is moving at a constant integer distance per minute (also unknown, and can be positive or negative).
Therefore, the submarine's current position can be calculated given the starting position, the velocity of the submarine, and the amount of time passed. This solution tries to find the submarine's starting position and velocity, and the missile is actually aimed towards the submarine's current position.
Log in to reply
If the sub has infinite space to move on the line, you will need infinite missiles and time.
Log in to reply
@Sam D – You could give me any starting position and velocity for the submarine, and using Joshua Lowrance's strategy, I could calculate the finite amount of time needed to hit the submarine.
Even though the submarine could be at any integer on the number line moving at any integer velocity, the submarine's actual position and velocity are both finite.
Very nice, I was wrong on this one, reminding me once again that the difference between 'finite' (any number) and 'limited' (under a given bound) is very, very important! Your explanation is great, but I think it would be even clearer if you specified a formula where to aim the missile fired at time t. I guess that would be m+t*n. Assuming the missile always reaches the target position before the submarine moves 😉
I still don't get, how do I catch the submarine if it is going the opposite direction. I mean, if it's beginning position is bigger than my starting point of firing and it's velocity is negative.
Log in to reply
You catch the submarine when you find its starting position and velocity. You don't fire at the starting position; instead, you use these two values and the amount of time elapsed to figure out where the submarine is at this moment. Because the method used here also considers negative velocities (any coordinates below the x-axis have negative velocities), it will hit a submarine moving in any direction.
Yaa same doubt .
What? I don't know that dude. Thanks for your help.
How can we say that submarine will be inside the set of -19 to 11. Submarine may be present outside the range what we are taking.
I disagree. The argument seems to be that every finite number within an infinite set will be found, given an infinite amount of time. The problem with that solution is it ignores the certain possibility of infinite retraction. The location of the submarine may always remain an infinite distance from every shot fired in space/time.
Log in to reply
I can't see an example where such a phenomenon is possible, could you try to give an example?
Ah, I finally get it. The actual location on the number line you would be firing at would be [m + (n * (turn number-1))], with m and n being your assumed values.
Of all things my solution depends on the unique prime factorisation of the integers! Suppose that, when you start firing, the submarine is at position A and moves with velocity V, so that its position at time t is A + V t . All quantities including t are integers.
To simplify things just now suppose A and V are both positive. We will return to think about how to deal with the negative numbers later. Whenever t has a prime factorisation t = 2 α 3 β , aim for the point α + β t . This strategy guarantees that you will hit the submarine after exactly 2 A 3 V minutes. Once you are sure of this consider how ...
...to cope with the negative possibilities. We can use the next prime numbers 5 and 7 to cover negative values for A and V respectively. So
when t factorises as t = 5 α 3 β target − α + β t
when t factorises as t = 2 α 7 β target α − β t
when t factorises as t = 5 α 7 β target − α − β t
This strategy guarantees success in at worst 5 ∣ A ∣ 7 ∣ V ∣ minutes.
Of course we do not know A and V when we start, but we do know that they are finite, and so we have exhibited a strategy which finds the submarine after a finite time.
I like this solution. Not only does it rope in the fundamental theorem of arithmetic, but it also lets you just sit around doing nothing for most of your turns. When t doesn't have one of the four forms you use, there's no need to guess a position at all!
Log in to reply
Thanks for your comment. I wondered about working out an upper bound for the number of rounds of ammunition, given an upper bound on ∣ A ∣ and ∣ V ∣ , but didn't make much progress.
Log in to reply
One upper bound would certainly be 5 ∣ A ∣ 7 ∣ V ∣ (as stated in your solution), would it not?
If you are not obligated to fire every turn, a better (in the sense that it's smaller, not simpler) upper bound would be \substack α ≤ ∣ A ∣ β ≤ ∣ V ∣ ∑ ( ⌊ 2 α 3 β 5 ∣ A ∣ 7 ∣ B ∣ ⌋ + ⌊ 5 α 3 β 5 ∣ A ∣ 7 ∣ B ∣ ⌋ + ⌊ 2 α 7 β 5 ∣ A ∣ 7 ∣ B ∣ ⌋ + ⌊ 5 α 7 β 5 ∣ A ∣ 7 ∣ B ∣ ⌋ − ⌊ 2 α 5 ∣ A ∣ 7 ∣ B ∣ ⌋ − ⌊ 5 α 5 ∣ A ∣ 7 ∣ B ∣ ⌋ − ⌊ 3 β 5 ∣ A ∣ 7 ∣ B ∣ ⌋ − ⌊ 7 β 5 ∣ A ∣ 7 ∣ B ∣ ⌋ )
I don't see an easy closed form there, but there could easily be something I'm missing.
If you're willing to accept a worse upper bound, you could certainly simplify that expression some.
Edit: Ignore that sum... I'm wrong. I'm counting all integers divisible by your special values for t , not all integers with precisely those forms.
Brilliant solution! Is there anything special about the primes you chose. Or are they just random.
Log in to reply
I'm not the author of the solution, but no. The only stipulation is that you need 4 different primes, and you need to arrange them properly -- one prime for positive α , one for negative α , and so on. This ensures that the solution still works if either A or V is zero.
That's a really nice solution!
That a fantastic solution
Still don't know that.😄😄😄😅😅
An easy nonconstructive proof: The submarine has countably many starting positions and countably many starting velocities. Hence the total number of start states is countable. Enumerate then { S 1 , S 2 , S 3 , … } .
At time t , fire at the location the sub would be at time t had it started with state S t . Since the sub actually had starting state S T for some T , you will find the sub at time T .
That's actually a constructive proof. Perhaps the word you're looking for is "exact algorithmic details not determined".
A "nonconstructive proof" would be an existence proof, where you show that something exists, but do not know what it is. E.g. Since there are countably many algebraic numbers and uncountably many reals, hence there must exist a non-algebraic real number. However, I have not constructed one.
Just start at one end of the number line and keep firing progressively in one direction at one step intervals.
Log in to reply
The number line doesn't have an end per se
You can't "start at the end of the number line." Any point you start at, there will be more points on either side of it. If you simply progress in one direction, you'll never hit the submarine if it stays on the other side.
Lol, "start at one end of the number line"
You mean, at infinity? That's not a number and not a position at which you can fire.
That was my solution aswell and I think it's much easier and therefore more elegant than the other ones.
Consider the image above. There is a spiral, starting at ( 0 , 0 ) . Each coordinate value ( m , n ) can be assigned a natural number, a number in the set { 1 , 2 , 3 , ⋯ } . Because each natural number can be assigned coordinate value, we say that the set of natural numbers, and the set of coordinate values have the same cardinality, or they have the same number of elements. Now, for every coordinate value ( m , n ) , we assume that the submarine started at integer value m , and has integer velocity n . So, first assume that the submarine has beginning position 0 , and integer velocity 0 . You go first, and so you fire 0 , where the submarine would be. You miss, and so you know that the submarine cannot have had the beginning position and integer velocity. The submarine moves. Now, you go to the next value on the spiral, ( 0 , 1 ) . The submarine has beginning position 0 , and integer velocity 1 . After 1 turn, the submarine should be on 1 , so you fire there, and miss. The submarine moves. Firing in this manner, you will cover every beginning integer position and integer velocity with a finite number of moves. For example, if the submarine had a beginning position of 3 2 9 5 0 2 3 4 5 1 and an integer velocity of 1 3 4 2 3 9 0 , you will destroy the submarine on the natural number which corresponds to the point ( 3 2 9 5 0 2 3 4 5 1 , 1 3 4 2 3 9 0 ) on the spiral above, which is some large number, but still finite.
Explicitly, this is how we fire our shots:
- First point in the spiral is ( 0 , 0 ) . So at t = 1 , that submarine will be at 0 + 0 × 1 = 0 . We fire at 0.
- Second point in the spiral is ( 1 , 0 ) . So at t = 2 , that submarine will be at 1 + 0 × 2 = 1 . We fire at 1.
- Third point in the spiral is ( 1 , 1 ) . So at t = 3 , that submarine will be at 1 + 1 × 3 = 4 . We fire at 4.
- Fourth point in the spiral is 0 , 1 . So at t = 4 , that submarine will be at 0 + 1 × 4 = 4 . We fire at 4.
- Fifth point in the spiral is − 1 , 1 . So at t = 5 , that submarine will be at − 1 + 1 × 5 = 4 . We fire at 4.
- Sixth point in the spiral is − 1 , 0 . So at t = 6 , that submarine will be at − 1 + 0 × 6 = − 1 . We fire at -1.
So on and so forth. Then, by the time we reach point ( m , n ) on the spiral, we are guaranteed to hit the submarine that started off at m and is traveling at velocity n . Of course, we might be lucky enough to have hit it before hand.