5. there are $n$ pieces on a board with $5 \times 9$ squares, with a maximum of one piece on each square at any time. A move consists of moving each piece to one of the adjacent squares at the top, bottom, left or right. This is done simultaneously for all pieces. If a piece is moved horizontally in one turn, it must be moved vertically in the next turn and vice versa. Determine the largest value for $n$ so that there is a starting position for the $n$ pieces and a sequence of moves so that this game can continue for as long as you like.
## Solution:

Answer: $n=32$

Insert coordinates so that the bottom left field gets $(1,1)$ and the top right field gets $(9,5)$. Now color the fields with three colors:

- The fields $(2,2),(4,2),(6,2),(8,2),(2,4),(4,4),(6,4),(8,4)$ red
- The fields $(1,1),(3,1),(5,1),(7,1),(9,1),(1,3),(3,3),(5,3),(7,3),(9,3),(1,5)$, $(3,5),(5,5),(7,5),(9,5)$ blue
- The rest yellow

There is a maximum of 8 pieces on the red squares at any one time. The stones on the blue squares lie on a red square two moves later, so there can also always be a maximum of 8 stones on blue squares. The checkers on the yellow squares are either on a red or a blue square one move later, so at any time there can be a maximum of $8+8=16$ checkers on yellow squares. At the start of the game, there can therefore be no more than $8+8+16=32$ pieces on the board, i.e. $n \leq 32$.

On the other hand, $n=32$ is possible: Place stones on all squares except those with coordinates $(1, k)$ and $(l, 1)$ and move them all simultaneously to the left, down, right, up, left, down, ... This can be continued for as long as you like.