Problem 1: Contradictory Thoughts

Consider the following Racket function

(define sorted?
  (lambda (l)
    (match l
      ['() #t]
      [(cons x '()) #t]
      [(cons x (cons y tail))
       (and (<= x y) (sorted? (cons y tail)))])))

And suppose the existence of a function (sort l) which is known to return list l, but sorted. Prove the following claim using proof by contradiction:

To prove this claim by contradiction, consider (a) what relationships must be true of the elements of l if l is sorted and (b) what additional information about the elements of l does the assumption (not (sorted? l)) give you?

Problem 2: Constructive Thoughts

Chess is played on a \(n \times n\) board (with \(n = 8\)) usually). There are a variety of pieces in chess, each of which move in a different way. For these claims, we will consider two pieces:

• The rook which can move any number of squares in a cardinal (non-diagonal) direction.
• The knight which moves in a L-shaped pattern: 2 squares horizontally, 1 square vertically or 2 squares vertically, 1 square horizontally.

Furthermore, we will consider two problems (really, thought experiments because these specific situations never arise in a real chess game) when only one such piece is on the board.

• The walk is a sequence of moves for this single piece that causes the piece to visit every square of the board.
• A tour is a walk with the additional property that the piece visits every square exactly once.

When considering walks and tours, we are free to initially place our piece on the board at any position. In addition, we only consider a square visited if the piece ends its movement on that square. Putting it all together, here are the two claims that we will consider and ultimately prove:

1. Proof the Knight’s Walks claim by induction on the size of the chessboard.

2. From your proof, describe an algorithm for performing a Knight’s walk on an \(n \times n\) chessboard with \(n \geq 4\). Because your proof is inductive, your algorithm should be recursive, following the structure of your proof.

3. Next, describe an algorithm for performing a Rook’s tour on an \(n \times n\) chessboard of size \(n \geq 1\). Try to describe it recursively, similarly to your proof/algorithm for the Knight’s walk.

   (Hint: be mindful of how an \(n \times n\) chessboard grows to an \((n+1) \times (n+1)\) chessboard. How does our recursive algorithm account for this growth? It is more complicated that it looks at first glance!

4. Finally, translate your Rook’s tour algorithm into a proof of the Rook’s Tour claim by induction on the dimensions of the chessboard.