This Submarine Puzzle Seems Impossible

[@IndependentQuark]

For those looking for an extra challenge: Consider now instead that the submarine starts at the origin in a 2D-plane. Its velocity is any vector from the origin to any point in the plane (not just integer points). It starts by moving one step in that direction, then you get to search, it then again moves by the same vector, etc. You now search a 1x1 square with center anywhere in the plane. Can you find the submarine? Does it matter if we chose v from R^2 or Q^2? (plane of reals vs rationals) How about if the velocity vector can only be chosen within a 2x2 square around the origin? How about if we go back to the 1D-case but v is chosen from all of R but you can search a range [x, x+1] in each step?

[@gobleturky6192]

This iterates over the Cartesian product of three countable sets, corresponding to (x, y, v). [x, y is velocity vector]. The Cartesian product of three countable sets is countable, so it should be possible.

[@cooperterrill9095]

​@gobleturky6192 I think the velocity components can be non-integer (I can't really tell by the phrasing of the question). So really it is the product of 3 uncountably infinite sets

[@chartroniumdude5870]

Solution spoilers: . . . . . . . Let t be the number of movements of the submarine. each time you check a 1x1 square, it rules out possible locations of the submarine after t movements. by scaling this square down (with respect to the origin) by 1/t, we get a 1/t side length square representing the possible locations the submarine wasn't at t=1. Since we check one of these squares for each (integer) value of t, we can check a total area consisting of the infinite sum starting from 1 of 1/t^2, which converges to a value around 1.64. Therefore, we can't always find the submarine, even if the velocity vector can only be chosen within a 2x2 square around the origin (area 4).

[@jaywu1951]

It's solvable when it's any finite number of Q dimensions (as it's really the same search space as Integers), but unsolvable even for one R dimension. Restriction to 2x2 does not change anything.

[@1_1bman]

@@jaywu1951 it is solvable for integer P and real number V as long as intervals of range [X, X+1] are searched. here's a simpler problem that can be a stepping stone to finding a solution to that variant: the submarine will now start at P=0, but has a positive real number velocity. you forfeit your initial guess, so the submarine gets to move once before you can do anything. you can search an interval of [X, X+1] every turn. how can you find the submarine?

[@Sjoerd-gk3wr]

It took some time to solve, but this is my solution. SOLUTION SPOILERS... The idea of the proof is to check each possible starting state one-by-one. We define the starting state as a tuple (x, v), where x is the place the submarine started at and v is the velocity of the submarine. We now want to check at time t whether the submarine had starting state (x, v). Thus we want to know what position the submarine would be in at time t, if it had starting state (x, v). Well if the submarine had starting position x and velocity v, then at time t the position would be x + v * t, so we need the check that position. We now want to do this check for every possible starting state, to do this in a countably infinite amount of time we use the following pattern: we first check (0, 0), then we check (1,0), -> (0,1) -> (-1,0) -> (0,-1), after that we check (2,0) -> (1,1) -> (0,2) -> (-1,1) -> (-2,0) -> (-1,-1) -> (0,-2) -> (1,-1), then (3,0) -> (2,1) -> (1,2) -> ... and so on. This path will traverse the entire space of possible starting positions, thus this algorithm will at some point check every possible starting state. So the submarine will at some point be found and be forced to surrender. sidenote: this algorithm can be made a lot faster, but I thought this was the most elegant proof that a possible algorithm does exist.

[@Prakhrr]

is the order of any importance? because if we check for infinite amount of time why does it matter which one we check first, we might as well start from (-infinity, -infinity) to (+infinity, +infinity)

[@Prakhrr]

how can the algorithm be made faster if both values are random(x and v) and it is equally likely to find the ship at any given time

[@chartroniumdude5870]

@Prakhrr you can't really start at (-infinity, -infinity), since once you get to (0,0) an infinite number of checks have already occured, meaning the submarine's position is then undefined. you can also think of it as there not being a "first position" you check. it just breaks everything really. if you check all the finite cases spiralling out to infinity then the submarine's position is always finite too.

[@chartroniumdude5870]

i assume by "made faster" they mean that since many submarine starting states end up at the same place at the same time, you don't have to check all of them. however, since there are infinitely many states regardless it will always take at least a countably infinite number of checks anyway.

[@Prakhrr]

@@chartroniumdude5870 you run out of your infinite checks no matter where you start from, let's suppose for once that you dont run out of checks and use exactly ∞ checks, suppose youc check position B at time T, initial position was X and velocity Y now by checking B at time T, we have checked all the possible tuples(X,Y) which satisfy the equation B = X + T*Y, This equation represents a straight line, all the points on the line are checked, now we want to check all possibel points from (-∞, -∞) to (∞, ∞), this can only be done by an ∞ amount of lines if all the lines are parallel otherwise we will definitely need more than ∞ lines, and because T changes after every check, the slope of the line changes ie. no 2 lines we can make are parallel, therefore we need more that an infinite amounts of check no matter what

[@thinktanium9789]

this was tough, gana have to go with D

[@nickronca1562]

It took me a couple minutes but I got it. You check where the submarine would be at each point in time for every ordered pair (x,v) where x is position and v is velocity as you make your way in a spiral across all (x,v) combinations. Make your way for all ordered pairs in a spiral pattern. So (0,0), (1,0), (1,-1), (0, -1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1), (2,1), (2,0), (2,-1), (2,-2), (1,-2), (0,-2), ... and so on. And then for each ordered pair, whatever timestamp you're at, check where the submarine would be at that timestamp and ordered pair combination.

[@gobleturky6192]

Before watching the video: Let the starting position be x and the speed v. We have two integers x and v, so the position for a fixed times is a function of (x, v). But x and v span Z, the set of integers, which is countable. We are looking at the Cartesian product Z X Z to get the ordered tuples (x, v). By a simple diagonal argument, Cartesian products of countable sets are countable, so it follows that we can hit every (x, v) in finite time. Then just guess the corresponding position, done.

[@1_1bman]

the 1d with velocity in R variant (where you scan an entire interval of length 1) is possible, but i think i've come up with an example of a variant that isn't possible. the submarine still starts at a position on the integers, it starts with a velocity of 0, and it has an _acceleration_ in the real numbers. i reckon this wouldn't have a solution, because the key to the velocity variant is that 1 + 1/2 + 1/3 + ... diverges, but in the acceleration variant, 1 + 1/2^2 + 1/3^2 + ... is a convergent sum.

[@samcertified7178]

The solution in the comment by @Sjoerd-gk3wr works for any function with 2 values that can be changed.

[@benjaminverbeek4232]

Really insightful and creative extension!

[@lox7182]

Can you specify what you mean by the R variant?

[@1_1bman]

@@lox7182 in the pinned comment, there's some extra harder variants

[@boumbh]

Z^2 being countable, take a bijection of N into Z^2 and check for each pair in Z^2 assuming it being the origin and velocity of the submarine.

[@benjaminpedersen9548]

The fact that there is such a search pattern follows from the fact that the integer plane is countable. Any counting function f(t) = (f_x(t), f_v(t)) of the integer plane, e.g. a grid-aligned spiral from (0, 0), generates search pattern g(t) = f_x(t) + t * f_v(t).

[@miracledip5123]

This was my solution! You put it very elegantly!

[@benjaminpedersen9548]

@@miracledip5123 Thanks! Five years of University Mathematics should help with that.

[@ensiehsafary7633]

This is like on dimensional devil's puzzle

[@jareknowak8712]

There is no way to warranty that the sub will be ever found, even when checking every single number form - to + infinity.

[@nickronca1562]

It is, I just commented how

[@angrykirby_yt]

My solution There are 3 variables to take into account the time t which we know, the starting position x and the speed v which we do not know. (x,v) is a pair of integers and the current position is x + vt. So we should check all pairs of integers by applying the current position formula, starting with the one closest to (0,0) in (x,v) space and proceeding in that order to ensure we don't miss the real value of (x,v). I'm not sure but I think we will find the submarine before t = 2^(max(|x|,|v|)+1)

[@1_1bman]

my solution if you can correctly guess the starting position and the starting velocity, you can just extrapolate where the submarine is going to be this turn, so we can turn this into a game of guessing the starting position and starting velocity. you might as well think about it in terms of integer grid points in 2d space. the x axis is starting position, the y axis is velocity. any sequence of grid points which eventually covers any finite grid point will work. you could just start from (0, 0) and then spiral outwards. for the extra challenge, we should be a little more rigorous than "spiral outwards". suppose the starting position is (x, y) and the velocity is (u, v). call the 'distance' of a possible setup to be |x| + |y| + |u| + |v|. first, we pick the only guess of distance 0, (0, 0) at velocity (0, 0). then we go through all the possible setups of distance 1. then all the possible setups of distance 2. so on and so forth. really, as long as there's a way to iterate over all possible numbers in a set, this kind of thinking should extend over there. the rationals are a countably infinite set, so this should work for Q^2, even without the restriction of a 2x2 square. the 1D-case with real numbers, however, gets a little trickier. our 2d plane of integer grid points becomes a 2d plane of infinite rows of real number lines. if we guess a starting position x, we can rule out all of the velocities in an interval of length 1/t, with t being the current turn number. without loss of generality we can assume only positive integer starting positions. for turn number t, if it's odd, we do a guess on starting position 1. if t is even, divide it by 2. if that's odd, we do a guess on starting position 2. if t is still even, divide it by 2 again, and if that's odd, do a guess on starting position 3. basically, if the highest power of 2 we can divide t by is 2^(n-1), we guess starting position n. so when t = k\*2^(n) + 2^(n-1) for an integer k, we guess starting position n, and an interval of length 1/t. famously, 1 + 1/2 + 1/3 + ... is a divergent sum. as well, any sequence 1/u + 1/(u + v) + 1/(u + 2v) + 1/(u + 3v) + ... is also divergent, and this is exactly the kind of sequence we have for the sum of the lengths of the searched intervals. so, yes, we should be able to find the submarine no matter what.

[@TrimutiusToo]

It is possible to find a submarine... Fairly easy, because the number of possible arithmetic progressions is countable...

[@kevinivanderwicaksana7737]

So guys, here is my solution to the submarine on the integer number line problem: Start by searching at 0 once, then let's introduce search sequences and super-sequences. - For the sequences, let s(a,b) where a is an integer (can be negative) and b is a natural number (positive integer) be a sequence of searches a, 2a, 3a, 4a, ..., (10^(b^2))a. - For the super-sequences, let S(m,n) be a sequence of searches which does the sequences s(1,n+1), s(-1,n+2), s(2,n+3), s(-2,n+4), ..., s(m, n+2m-1), s(m, n+2m) in that order. Now after the initial step of searching 0 once, do the super-sequences S(1,0), S(2,2), S(3,6), S(4,12), S(5,20), ... or S(1,0*1), S(2,1*2), S(3,2*3), S(4,3*4), S(5,4*5), ... We will proof that this searching algorithm works for any finite integers (x_0, v) in the original problem. To do that, divide the problem into two cases: case 1: v is positive. Look at all the sequences in the super-sequences s(v+1, (p-1)p+2v+1) where p>=v+1 and p is an integer because the sequence exists for all p>=v+1. Notice that before this sequence is started, 1 + 10^1 + 10^4 + 10^9 +...+10^(((p-1)p+2v)^2) sequences has been done, which means the submarine's position is x_0 + (1 + 10^1 + 10^4 + 10^9 + 10^(((p-1)p + 2v)^2))*v before the sequence is started. You can find an arbitrarily large enough p such that 0 < x_0 + (1 + 10^1 + 10^4 + 10^9 + 10^(((p-1)p + 2v)^2))*v < 10^(((p-1)p+2v+1)^2) and hence, the search sequence will find the submarine because you are chasing it at v+1 speed compared to the submarine's v speed. The lower distance in the positive numbers compared to the total searches in the sequence will result in you catching the submarine. case 2: v is negative. In this case, look at the sequences in the super-sequences s(v-1, (p-1)p-2v+2) where p>= -v+1 and p is an integer. By applying the same logic as the previous case, we find that the submarine's position is x_0 + (1 + 10^1 + 10^4 + 10^9 + 10^(((p-1)p-2v+1)^2))*v befor the sequence is started. You can find an arbitrarily large enough p such that -10^(((p-1)p-2v+2)^2) < x_0 + (1 + 10^1 + 10^4 + 10^9 + 10^(((p-1)p-2v+1)^2))*v < 0 So in this case, you are chasing the submarine at -v-1 speed while the submarine is going at -v speed or v+1 speed and v speed respectively but to the left. This will guarantee you to catch the submarine. case 3: v is 0. This case is pretty simple, take an arbitrarily large enough p such that you can take the super-sequence S(p, (p-1)p) which contain the sequences s(1, (p-1)p+1) and s(-1, (p-1)p+2) which you can use to search for the submarine if it as at the positive and negative whole numbers on the line respectively. And that search for 0 at the beginning was to just avoid the corner case that the (x_0, v) = (0,0). That's the solution... Tell me if there is anything wrong about it. Funny thing: I tried s(a,b) to search a, 2a, 3a, ..., (10^b)*a but that doesn't work for v>10 because (1+10^1+10^2+...+10^k)*v + x_0 is greater than 10^(k+1) if x_0>0 and v>10 for the first and second case (k is in the form of v and p)

[@kricsek]

Check random numbers for ever.

[@featureboxx]

clearly the submarine doesn't move at a constant speed, because the time between two guesses is not constant This fact doesn't change the nature of the puzzle but it is a poor formulation

[@lox7182]

This is like saying that a problem with perfect logicians is bad because noone is a perfect logician

[@milest9754]

Make a grid of the possible values of v and x0. Then check all of them in a spiral pattern starting at (0,0). To check one of the possibilities, you look for the submarine at x0 + vt where t is the number of guesses you’re at.

[@KingJAB_]

Smart, I was wondering if phase space would play a role

[@kingoreo7050]

SOLUTIPN SPOILERS: Any submarine can be described by an ordered pair of integers (x, v) where x its its start value and v is its velocity. To catch the submarine at time t (0 indexed) you need to search x + tv. So the problem just reduced to finding a map between the natural numbers (t) and ordered pairs of integers, that hits every finite integer in finite time. The procedure basically boils down to cantor's diagonlisation argument, which makes alot of sense pictorally, but just to spell it out in text: - First we find a map between pairs of naturals and single naturals (which can be extended to all integers with (0, 1, 2, 3, 4, 5, 6..) -> (0, 1, -1, 2, -2, 3, -3..) - We systematically go through each pair of naturals that add up to a certain number, so all the ones that add up to 0, all the ones that add up to 1, which looks like (0,0), (0,1),(1,0), (0,2),(1,1),(2,0), (0,3),(1,2),(2,1),(3,0), . . . - After replacing each pair of naturals with its corresponding pair of integers (using the map described earlier, when the sequence hits (x,v), search x + vt, and rule out any sub with those starting coords - You will hit every submarine in finite time This was a really fun puzzle btw.

[@nickronca1562]

Don't forget the negative velocities and the negative starting values

[@soggytoast111]

The answer that I came up with is that you search a random space between neg infinity to pos infinity every turn. Given infinite time you must land on the correct point eventually. But I'm not sure if that kind of answer is "allowed" though.

[@yoramgt]

If the distribution with which you sample the set of integers is the same for all your samples then it is untrue that you are guaranteed to hit the target eventually.

[@genericgoat]

Step 1: Make a spreadsheet Step 2: On the X axis, label it the numbers 0, 1, -1, 2, -2 and onto infinity Step 3: Repeat on the y axis Step 4: The x axis represents the starting position of the submarine, and the y axis represents the submarine's velocity Step 5: Label every cell. using the y axis index written as a letter (example: the seventh cell down would be 'H') and the x axis index written as a number Step 6: Make a sequence of labels that includes every label. An example would be A1, B1, A2, C1, B2, A3, D1, C2, B3, A4 and onto infinity Step 7: Index this sequence using integers 0 to infinity. The index of the cell is the number of steps you count. Using the example from above, C1 would have the index 3. This corresponds to a starting point of 0 and a speed of -1. Calculating the position after 3 steps gives -3, so we check -3. This works because every possible starting speed at every possible starting location is checked

[@CodeChrisB]

My Idea is To Always Look at a random Position, one time ill get it

[@IndependentQuark]

How do you know the probability of finding it converges to 1? :)

[@yurenchu]

Ooh, clever and challenging puzzle! I haven't solved it yet, but I'll think about it. I hope I don't miss your follow-up video with the answer. And I hope I will have solved it by the time you post the answer. 😊

[@evyatarbaranga5624]

I have a solution: SPOILERS! Notice that if we can describe the submarine by two values - its starting point x_0 and its speed v. I will those describe a submarine as a pair (x_0, v). Further more notice that if we look at location m_t at time t we rule out all sub marines of the form (m_t - v*t, v) for all v. this is because we could have gotten to m_t if we started at m_t-v*t and moved at speed v, t times. now we want to describe the values of m_t such that we check all possibilities for submarines. meaning we want a mapping from values of t (the natural numbers - N ) to submarine locations (the pairs of whole numbers - Z^2) luckily there are mapping like those, the famous way to count the rational numbers for example. i will not describe a way like this here, but lets assume I have one f:N->Z^2, f(n)=(a_n, b_n). and for each point in Z^2 there is n such that f(n) is that point. now we define m_t = a_t + b_t *t. now if we are guessing m_t, we rule out the possibility of a sub marine at (m_t - b_t*t, b_t)=(a_t, b_t) so now if the ship is at a certain point (a,b) there is a n such that f(n) = (a,b) and then when t=n we will have checked there and would have found the ship. QED

[@Margobra8]

amazing video!! keep them going please 🥺

[@SmoMo_]

Well I guess let T be the current guess number ( starting at 0) Then follow this triangular sequence, N being the current number and R the number of times you’ve previously seen that number already 0 0, 1 0, 1, 2 0, 1, 2, 3 0, 1, 2, 3, 4 … Then search at ( N * T) + R Then also check one minus that. I’m not sure how to generate that triangular sequence from an equation. Looks like you get to the submarine in finite time, as you will first test its span length (S) in (S^2) guesses, and then have to hit it O times ( where O is the initial offset) so S^2 + O clearly being finite if S and O are both finite

[@Sjoerd-gk3wr]

solved it as well it, cant wait to see the video!!

[@tiesrozema2632]

New sub!

[@Rtyui0100]

Love this!! 🤩⛵️

[@awesomegamedev]

Interesting problem. I solved it (without pausing the video) by about ~0:30 mark though (before you explained the full rules, but it was clear where it's going). Solution: SPOILER There are countable possible configurations (initial position + velocity) - each turn we check one of them. Not the best explanation, but I feel lazy writing a proper one. Let the guy do the video:) In shortest code will be something like: t = 0 for (int r = 1; ; r *= 2): for p in range(-r, r+1): for v in range(-r, r+1): { check(p + v*t) t += 1 } (there would be around ~33% avoidable re-checks with this code, but it's short)

[@IndependentQuark]

Interesting approach! There are of course many solution variations possible, look forward to seeing others than my intended & your thoughts on the solution video later. I recommend giving the pinned bonus problem a go :)

[@chlebek605]

how doest this work if you can only see where the submarine is now and only check one number at a time? how do you deal with the case of it jumping over you? what language is the code in?

[@Bob-qz5yj]

This would take infinite time in the worst case though wouldn't it? That's what I'm confused about, doesn't "eventually" mean in finite time/steps?

[@skywardocarina1]

@@Bob-qz5yjyou can complete an infinite amount of steps in finite time in some cases, though this isn’t one of them. If you couldn’t, then a tortoise with a meter head start in a race will always win.

[@mathpuppy314]

@@Bob-qz5yj The concept of infinity (as it's used here) really just means arbitrarily large. Since both the initial position and velocity are finite, the solution must be finite, although it may be very long. It may in fact take an arbitrarily large amount of time, hence the worst case taking "infinite" time. This doesn't actually mean it will never happen, it just means that it will happen after a time that can be arbitrarily large.

[@uxnium]

The only thought I'm getting is to check 0, then 1, then -1, then 2, -2, 3, -3, and so on until (most likely) at infinite turns you find it. Hopefully atleast. Edit since I misspelled ¯⁠\⁠_⁠(⁠ツ⁠)⁠_⁠/⁠¯

[@soggytoast111]

That doesn't work because you'd be searching too slow to ever catch up with the ship as it moves towards negative or positive infinity.

[@uxnium]

@soggytoast111 but both will eventually go to infinity. Let's say the submarine starts at 10 with a speed of -10. The submarine is at 10 then and I'm at 0, the submarine is at 0 I'm at 1, the submarine is at -10 I'm at -1, and so on. At the ∞th round I could be at ∞ while the submarine is at -∞, then after one more round the submarine goes left 10 steps so -∞-10=-∞, and I flip my number and then it's -∞, and I win cuz I found the submarine. To be fair, logically it doesn't make sense, but mathematically it should. Go watch some videos on infinity where they explain that infinies 1+2+3+4... and 2+4+6+8... are equal, or something. Since that's basically this but in a bit different way.

[@soggytoast111]

@@uxnium That's not how infinity works. You can't just treat it as a real number. What actually happens is that on every turn the ship will be at a greater infinity than you are searching on. The ship's movement rate is growing faster than you are searching, so you can never catch up to find the ship.

[@uxnium]

​​​@@soggytoast111 Infinity is infinity, there can't be two infinities different sizes. It probably doesn't make neither logical nor intuitive sense, but that's how it goes (or at least should, idk, I really could be wrong). Let's simplify a bit and say the submarine can only go with a speed of 2, and say it starts at, idk, 2. I search 0 and the submarine moves to 4, I search 1, it goes to 6, and so on. So I go +1 and the submarine +2, repeating those an infinite amount of times we get 0+1×∞ and 2+2×∞, which 1×∞=∞ and 2×∞=∞, and 0+∞ and 2+∞ both equal ∞, we will 100% catch the submarine on the ∞th turn. Even the video is talking about infinities, so how come that the answer wouldn't also include ∞'s? Of course, if we for some reason aren't allowing ∞'s then I have no clue if this is even possible... Edit: I have no clue how to explain stuff properly if you didn't notice ¯⁠\⁠_⁠(⁠ツ⁠)⁠_⁠/⁠¯

[@soggytoast111]

@@uxnium That's not true. Not all infinites are equal. In you example we know that on the ∞ turn: |position of the ship| > |position searched|. If we plot the equation for each one we can see this is true for all real numbers.

[@LATI_A5]

I do not have a solution yet, but I do have a few thoughts. (SPOILERS AHEAD) Maybe it is easier to work backwards using "submarine coordinates", where the submarine starts at x' = 0 and has a velocity of v' = 1, thus its position is given by x'(t) = t. Of course, we don't know the exact transformation rules between our coordinates and the submarine coordinates, but we know it is something along the lines of x'(x) = (x - x_0) / v for unknown x_0 and v. In the submarine's coordinates, our search space would be all rational numbers rather than integers. The above transformation fails if the submarine does not move (v = 0), so that case would need to be handled separately. Since it is impossible to determine which case it falls into (at least nontrivial), we'll think about a strategy down the line. Also, the cases where v < 0 are just mirror images of v > 0, so we should search in both directions from our initial guess equally. Speaking of our initial guess, since x_0 could be any integer it doesn't matter where our initial guess is. So let's start our guess at 0, and move onwards. Our search strategy will have to eventually search every possible position to account for cases in which the submarine is stationary, but must have a component that is faster than any possible submarine. I'm thinking of first looking ahead with a polynomial or exponential growth rate, but also "deploying" searchers that search each immediate region at a much slower pace. The "look ahead" and "local search" components could be run on staggered steps to perform both at the same time. I would love to keep thinking, but I have to go to bed now. I may come back tomorrow if time allows for it.

[@filipo4114]

Probably something like this: def next_x(): yield 0 i=0 x=0 prev_x=0 while True: #one for going from 2^i down and another for going from -2^i up x=2**i prev_x=int(2**(i-1)) while x > prev_x: yield x x-=1 x=-2**i prev_x=-int(2**(i-1)) while x < prev_x: yield x x+=1 i+=1 gen = next_x() for _ in range(49): print(next(gen))

[@nektomike]

When will be answer video？

[@IndependentQuark]

Out now! 😊

[@chrisadamson5952]

It's not possible to guarantee finding the sub in FINITE attempts. If you can find me a puzzle that's NOT possible to solve with INFINITE time/resources, I'll be impressed.

[@IndependentQuark]

Can you define what you mean by "finite attempts"?

[@comma_thingy]

I imagine he means that the puzzle doesn't have an upper bound for how long it will take. However, for any given starting state, with a solution we should be able to find the sub in finite time.

[@rielco8442]

Not true. It is possible to find the submarine in a finite number of step. In particular there are strategies that guaranties you to find the submarine in at worst, a few attempts more than 2(|x_0|+|v|) since x_0 and v are finite, so the number of attempts

[@WilliamAndrea]

define "eventually". If it's bounded, then it's not possible, but I imagine it's unbounded (aleph 0).

[@chartroniumdude5870]

usually if you find ambiguity in the rules of a puzzle, it's safe to assume the interperetation that makes it impossible is not the correct one

[@duukvanleeuwen2293]

Imagine that you start counting 0,1,2,... Any natural number will _eventually_ be reached, even though the cardinality of the natural numbers is aleph 0

[@KingJAB_]

I’m gonna guess you need to search all primes or something along those lines

[@TheWin475]

just check every number. No, seriously, at some point you will get from negative infinity to positive infinity and since infinity + 1 is infinity you will catch up to the submarine

[@mathpuppy314]

Wow, really nice video, and thanks so much for not revealing the solution in the same vid! I needed to actually solve this and I might not have otherwise. SOLUTION SPOILER I relatively quickly solved the same way as @Sjoerd-gk3wr, representing each starting arrangement as a point (p, v), and tracing progressively bigger diamonds of such points in Z^2, guessing the point at r(p, v, t) where r is the position the sub would be given the starting conditions and time. (can you please add one more variable that I can call 'n' lol?) As for the extra challenge, that took a lot of thinking! I'm gonna say both velocity domains requested are impossible. I feel there must be a flaw in my logic because I doubt you would have asked it if it were actually impossible! Anyways, my reasoning is this: imagine the velocity *v* is confined to the 1x1 square around the origin, and assume the guessing square has open borders. (Alternatively, *v* could be confined to a square infinitesimally larger than 1x1 so that the guessing square can have closed borders.) A natural first guess would be around (0, 0), eliminating the vast majority of possibilities. If this does not reveal the submarine, *v* must rest on the perimeter of the 1x1 square. Each step forward in t causes each side of the square's perimeter to increase in length by 1. The guessing square can only ever cover a length of 1 on any given side of the square, so by the time any side has length > 1, it will no longer be possible to guess every possible real vector on that side of the square. Now (0, 0) is not an optimal starting location given these constraints, (dx, dy) would be a better guess. This square is translated infinitesimally up and right. Now the up and right sides of the square have been removed, but the bottom and left sides remain. These two sides still each grow by 1 each turn and are unguessable after the next move making the sides have length 2. Of course, the 1x1 velocity domain being impossible would imply that the larger domains of 2x2 or R^2 are also impossible. I would like to know what my error is, if someone can find it.

[@Quantris]

IMHO you don't have any error, this idea of your "probe" square becoming too small to cover the widening space of possibilities is a good argument. Maybe easier to think of it as probing the (fixed) initial state space with a shrinking square---if it shrinks too quickly then you can't cover the whole space. Relatedly we can ask how restricted does the velocity need to be for us to be able to catch the spy.

[@IndependentQuark]

I'm really glad to hear you liked the video & gave both puzzles a shot! Your solution for the bonus problem seems to be on the right track. Without revealing too much, I believe it is not necessarily true that it is impossible to find on an 1+epsilon x 1+epsilon starting square for example. Consider what would happen if instead of a choice of velocities on R^2 we would allow a choice on Q^2 only? Just to push the argument: what about if we go back to the one dimensional case. The velocity can now be any real number but you can search a range of numbers [x, x+1] (x is any real number) in each step. Pretty obvious perhaps, but might be able to help the thought process!