## 4 Results on \(d\)-Dimensional Grids  
### An upper bound  
As mentioned in the introduction, one could conjecture \(k_{d}(n)=n^{d-1}\). However, this does not even hold for \(d=3\), see Figure 5. The movement can be done such that only one lion changes its location within each time step. All remaining lions can stay at their current positions and protect the cleared vertices. Even if the moving lion needs several steps to reach its destination, no problem arises. For any grid vertex \(v\), we denote the \(L_{1}\)-distance from \(v\) to the origin \(0\) as \(|v|\). The idea is to sweep the vertices layer by layer, where the \(r\)-th layer is the set of vertices of \(L_{1}\)-distance \(r\) to the origin. It is denoted by  
\[L(r,n,d)\ :=\ \{v\in[n]^{d}\ |\ |v|=r\}\]  
For \(r\leq d(n-1)\) the value of \(|L(r,n,d)|\) can be computed recursively by:  
\[|L(r,n,d)|=\sum_{i=\max(r-n+1,0)}^{\min(r,(d-1)(n-1))}|L(i,n,d-1)| \tag{3}\]  
As start of the recursion, we can use \(|L(r,n,1)|=1\) for \(0\leq r\leq n-1\). To the best of our knowledge, no closed formula is known, but it is not difficult to prove the following Lemma. Figure 5: Eight lions (rather than \(n^{d-1}=9\)) suffice to clear the \(3\times 3\times 3\)-grid. If two lions occupy the same vertex at the same time, this is indicated by two crosses of different orientation. **Lemma 6**. : \(|L(r,n,d)|\) _is increasing in \(r\) for \(0\leq r\leq\frac{d(n-1)}{2}\)._  
Proof. : We use induction on \(d\). For \(d=1\), we have \(|L(r,n,1)|=1\) for \(0\leq r\leq\frac{n-1}{2}\), which is monotonously increasing. Now, let us assume, we already showed for dimension \(d\) that \(|L(r,n,d)|\) is increasing in \(r\) in the range of \(0\leq r\leq\frac{d(n-1)}{2}\). Our task is to prove the monotonicity for dimension \(d+1\). Due to the symmetry \(|L(r,n,d)|=|L(d(n-1)-r,n,d)|\), the induction hypothesis implies that \(|L(r,n,d)|\) decreases monotonously in \(r\) in the range of \(\frac{d(n-1)}{2}\leq r\leq d(n-1)\). The symmetry \(|L(r,n,d)|=|L(d(n-1)-r,n,d)|\) holds, because all grid points with distance \(r\) from the origin have distance \(d(n-1)-r\) from the grid point \((n-1,\ldots,n-1)\) and vice versa. Clearly, \(|L(r,n,d+1)\) is monotonously increasing for \(0\leq r\leq n-1\). For the remaining range \(n-1\leq r\leq\frac{(d+1)(n-1)}{2}-1\), we have \(r-n+1\geq 0\) and \(r+1\leq d(n-1)\). Hence, formula 3 leads to  
\[|L(r+1,n,d+1)|-|L(r,n,d+1)| = \sum_{i=\max(r-n+2,0)}^{\min(r+1,d(n-1))}|L(i,n,d)|\] \[- \sum_{i=\max(r-n+1,0)}^{\min(r,d(n-1))}|L(i,n,d)|\] \[= |L(r+1,n,d)|-|L(r-n+1,n,d)|\] \[=: x(r,n,d)\]  
We will prove the monotonicity of \(|L(.,n,d+1)|\) by showing \(x(r,n,d)\geq 0\). If \(r+1\leq\frac{d(n-1)}{2}\), then \(r-n+1\) as well as \(r+1\) are in the increasing part of \(s\mapsto|L(s,n,d)|\), hence \(x(r,n,d)\geq 0\) and the monotonicity holds. For \(\frac{d(n-1)}{2}<r+1\leq\frac{(d+1)(n-1)}{2}\), the term \(x(r,n,d)\) is monotonously decreasing in \(r\), since \(r+1\) is in the decreasing part of \(s\mapsto|L(s,n,d)|\), while \(r-n+1\leq\frac{d(n-1)}{2}-\frac{n+1}{2}\) is still in the increasing part. But even if we chose \(r=\lfloor\frac{(d+1)(n-1)}{2}\rfloor-1\), which is the maximum value for \(r\) we have to consider, we can still show \(x(r,n,d)\geq 0\):  
If \(d\) is odd or \(n\) is odd, we obtain \(x(r,n,d)=|L(\frac{d(n-1)}{2}+\frac{n}{2}-\frac{1}{2},n,d)|-|L(\frac{d(n-1)}{2 }-\frac{n}{2}-\frac{1}{2},n,d)|\), which equals \(|L(\frac{d(n-1)}{2}-\frac{n}{2}+\frac{1}{2},n,d)|-|L(\frac{d(n-1)}{2}-\frac{n }{2}-\frac{1}{2},n,d)|\geq 0\) due to the symmetry. This shows that the monotonicity of \(|L(.,n,d)|\) implies the monotonicity of \(|L(.,n,d+1)|\) within the range needed for Lemma 6. Accordingly, if \(d\) is even and \(n\) is even, we obtain \(x(r,n,d)=|L(\frac{d(n-1)}{2}+\frac{n}{2}-1,n,d)|-|L(\frac{d(n-1)}{2}-\frac{n }{2}-1,n,d)|\geq 0\). This proof shows that the _middle layer_, \(L(\lfloor\frac{(n-1)d}{2}\rfloor,n,d)\), is the biggest, which will be important for our estimates.