Consider a 7 \times 7 chessboard that starts out with all the squares white. We start painting squares black, one at a time, according to the rule that after painting the first square, each newly painted square must be adjacent along a side to only the square just previously painted. The final figure painted will be a connected “snake” of squares.
(a) Show that it is possible to paint 31 squares.
(b) Show that it is possible to paint 32 squares.
(c) Show that it is possible to paint 33 squares.