Evaluate \(a(4,4)\) for the function \(a(m,n)\), which is defined for integers \(m,n\ge0\) by \[\begin{align*} a(0,n)&=n+1\text{, if }n\ge0;\\ a(m,0)&=a(m-1,1)\text{, if }m>0;\\ a(m,n)&=a(m-1,a(m,n-1))\text{, if }m>0\text{, and }n>0. \end{align*}\]
We bet that some of you play chess and are pretty good. Someone may be better than all of the tutors. Unfortunately for that person, and fortunately for the rest of you, that won’t help too much with the problems today. You’ll need to know how the pieces move and that’s it.
There are various themes of knight’s tours, independence and queens’ domination. We also won’t just look at typical \(8\times8\) chessboards, but grids of different sizes, and even ones that aren’t flat.
Show that a knight’s tour is impossible on a \(3\times3\) grid.
Show that two queens together can attack every square on a \(4\times4\) grid, but one queen on her own cannot do it. This type of problem is called ‘queen’s domination’.
How many queens can you place on a \(4\times4\) grid so that none of them attack each other?
Show an knight’s tour on a \(5\times6\) chessboard. That is, a path where a knight starts at one square, and then visits every square exactly once, making only moves legal to a knight.
Show how five queens can dominate a standard \(8\times8\) chessboard. That is, each square is attacked by some queen.
How many independent queens can you place on a \(5\times5\) grid? That is, so none of them attack each other.
How many ways can you place \(8\) rooks independently on a chessboard? That is, so that none of them attack each other.