## 5 Flying lions in the \(2\)-dimensional grid  
We are not aware of any strategy with fewer than \(n\) lions to clear the two-dimensional \(n\times n\)-grid. Indeed, we conjecture that \(n\) is the clearing number of the \(n\times n\)-grid. In this section, we will establish that fewer than \(n\) lions are sufficient, if the lions are able to fly. To be more precise, we consider the problem variant where the movement of the lions is not restricted to the edges of the grid. If a lion moves from a grid vertex to an adjacent grid vertex, this still prevents the contamination from using the corresponding edge in the other direction. However, if a lion flies from a grid vertex to another vertex which is not adjacent in the grid, no edge is protected. Our proof of Theorem 1 in Section 3. does not take any advantage of the fact that the movement of the lions is restricted to grid edges. This means, the lower bound of \(\frac{n}{2}\) is still valid for the case of flying lions. Our main result is that \(\frac{n}{2}+O(\sqrt{n})\) flying lions can clear the \(n\times n\)-grid. However, we start with showing the weaker result that \(\frac{2}{3}n+O(1)\) lions are enough in order to illustrate the idea of our method in a simpler case. For \(h:=2\lceil\frac{n}{3}\rceil\), we denote the grid vertices with \(x\)-coordinate at most \(h-1\) as the _left part of the grid_, while the vertices with \(x\)-coordinate at least \(h+1\) are the _right part_. The vertices with \(x\)-coordinate equal to \(h\) are called _separator vertices_. Our strategy guarantees that the set of lions occupying separator vertices stays the same all the time. Lions belonging to this set are called _separator lions_. We will describe a strategy enabling \(h+11\) lions to clear one row of the grid after the other. Suppose, we are given a situation where the \(0\)th, \(1\)st, \(\ldots\), \(v\)-th row of the grid are free of contamination, where \(5\leq v\leq n-6\). The vertices \((0,v),(1,v),\ldots,(h-1,v)\) as well as the separator vertices \((h,v-5),(h,v-4),\ldots,(h,v+5)\) are occupied by the lions. The movement of the lions is illustrated in Figure 6. The \(11\) lions located on the separator vertices keep their position until all of them move one row upwards when the complete \((v+1)\)-th row and everything below is free of contamination. The first \(5\) steps are used to move the lions in the left part of the grid upwards. Afterwards, all lions from the left part fly to the right part, where they occupy all vertices of the \((v-5)\)-th and \((v-4)\)-th row. In the following \(3\) steps, the lions move upwards in the right part of the grid. Within each step, they gain two rows in the right part of the grid. For each such step, the upper lion in each column uses the grid edge to move one row upwards, while the lower lion flies to its new location three rows upwards. This kind of movement avoids any recontamination in the right part of the grid. Afterwards, all lions of the right part of the grid fly into the left part again, namely into the \((v+1)\)-th row. What we obtained is the initial situation with \(v+1\) instead of \(v\). Or, to say it with other words: the lions gained one row. Notice that, if \(v<5\) or \(v>n-6\), the situation is even better for the lions. Starting from the \(0\)th row, they can consecutively clear one row after the other. After each gained row, all separator lions move one row upwards during the next time step. This happens simultaneously to the lions in the left part of the grid moving upwards. The total number of lions needed for this strategy is \(h+11\in\frac{2}{3}n+O(1)\). **Lemma 12**. : \(\frac{2}{3}n+O(1)\) _flying lions can clear the \(n\times n\)-grid._  
For a strategy in the above manner, the speed ratio between the upwards moving lions in one part of the grid and the downwards moving contamination in the other part does not have to be \(2\). If we save  
Figure 6: Flying lions gain one row. The vertical black line segments partition the grid with ratio 2:1.