Battleship Bombing (2/3 – 2/16)
Kyrie being shocked by the Luka Doncic trade challenged Nico Harrison, the GM, to a game of Battleship. Nico can place \(n\) ships in any lattice point (\(a_i \in \mathbb{Z}^2)\) and can set the speed of each ship to be \(s_i \in \mathbb{Z}^2\) per second. The location of ship \(i\) at time \(t\) would be \(a_i + t \cdot s_i\).
Kyrie can guess a spot for each battleship each second. At times \(t_0, t_1, \dots\) he guesses a lattice point. If there are any ships on the location he guessed, all the ships in that location sink.
Ex: If \(n=3\), Nico can set up the ships as \(a_1 = (-1,-3), a_2 = (1, 0), a_3 = (1, 2)\) and \(s_1 = (0, 2), s_2 = (0, 1), s_3 = (0, 0)\). If Kyrie guesses \((-1,-3), (2, 0), (1,2)\) at times \(t = 0, 1, 2\). Then, the first ship would sink on \(t = 0\) and the second and third ship would sink on \(t = 2\).
(a) Suppose \(n = 1\) and \(s_1 = (0, 0)\). Find a strategy that guarantees Kyrie to sink the ship eventually.
(b) Suppose \(n = 1\) and \(s_1 \in \mathbb{Z}^2\). Find a strategy that guarantees Kyrie to sink the ship eventually.
(c) For the rest of the problems, suppose \(n\) is any positive integer. Find a strategy that guarantees Kyrie to sink all the ships eventually.
(d) Now, Nico can change the location and speed of each ship exactly once at any point of the game. Find a strategy that guarantees Kyrie to sink all the ships eventually.
(e) Now, Nico can change the location and speed of each ship \(m\) times at any point of the game where \(m\) is any positive integer. Find a strategy that guarantees Kyrie to sink all the ships eventually.
Solution
(a) Find a bijection \(f: \mathbb{N} \to \mathbb{Z}^2\) and at time \(t\), guess the location corresponding to \(f(t)\).
(b) Find a bijection \(f: \mathbb{N} \to \mathbb{Z}^2 \times \mathbb{Z}^2\) (location \((a)\), speed \((s)\)) and at time \(t\), guess the location corresponding to \(a_t + s_t \cdot t\).
(c) Do strategy from (b) \(n\) times.
(d) Now, we want a sequence \((A_t)_{t=0}^{\infty} \to \mathbb{Z}^2 \times \mathbb{Z}^2\) (location, speed) such that at any point \(t_0\), the sequence \((A_t)_{t=t_0}^{\infty}\) is a surjection to \(\mathbb{Z}^2 \times \mathbb{Z}^2\). Consider the sequence:
\[a_0 = f(0), a_1 = f(0), a_2 = f(1), a_3 = f(0), a_4 = f(1), a_5 = f(2), \dots\]
Clearly, at any point \(t_0\), the sequence \((A_t)_{t=t_0}^{\infty}\) is a surjection to \(\mathbb{Z}^2 \times \mathbb{Z}^2\). At time \(t\), guess the location corresponding to \(A_t(a) + A_t(s) \cdot t\). Copy this for every ship.
(e) The same strategy works. Suppose we can break the ship if they can switch \(k\) times. We show that even if they can switch \(k+1\) times, we can break their ship. Since we can break the ship if they can switch \(k\) times, they will have to use all the \(k+1\) switches at some \(t = t_0\). However from part (d), we know that \((A_t)_{t=t_0}^{\infty}\) is a surjection to \(\mathbb{Z}^2 \times \mathbb{Z}^2\).