# Lab 11, Nick Cardenas and Jeronimo Camargo
## Constructive Proof
### Problem 1: Contradictory Thoughts

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

**Claim:** If `(not (sorted? l))` then `(sort l) ≠ l`
Proof by contradiction, assume if `(not (sorted? l))` then `(sort l) = l`
Because we know the `not` function must return true to continue, we must assume that `sorted` returns false. Therefore, `l` must be `(cons x (cons y tail))`
We are trying to prove `(sort l) = l`, or `(sort (cons x (cons y tail)))` = `(cons x (cons y tail))`. However, we know this cannot be true, because the sort function will rearrange `l`–an unsorted list–making the two lists different.

### Problem 2: Constructive Thoughts
**Claim:** There exists a knight’s walk for any chessboard of size $n \geq 4$
**Induction hypothesis:** There exists a knight’s walk for any chessboard of size $k \geq 4$
Proof:
To prove the n = 4 case, we depict a chessboard using x = {1, 2, 3, 4} and y = {1, 2, 3, 4}
We proceed like this, with R showing the return to an already visited square:
(1, 1)
(2, 3)
(3, 1)
(4, 3)
(2, 4)
(1, 2)
(3, 3)
(2, 1)
(1, 3)
(3, 4)
(2, 2)
(4, 1)
R (2, 2)
(1, 4)
R (2, 2)
R (4, 3)
R (2, 4)
(3, 2)
(4, 4)
R (2, 3)
(4, 2)

Thus we have hit every square in a 4x4 grid at least once.
Using induction on the size of the chessboard, we introduce k with is equal to n - 1, and therefore must be greater than or equal to 4. If k is 4, we have already proven the claim. If k is 5, then there is one extra row and column of sqaures that the knight must reach. Because we know that for any 4x4 grid there exists a knight's walk, then we can simply step out of the 4x4 grip and into a new square, step back into the 4x4 grid, and repeat. This way we reach all of the new squares. Thus we have proven that for there is a knight's walk for any chessboard of size n $\geq$ 4

B. The algorithm for performing a walk in a knight's walk in an NxN where $N>=4$ consists in brute forcing the walk if N =4. If N >4, then we know that there is a section N-1 X N-1, where by definition there is a walk. So the algorithm is recursive.

C. When the n is odd, start in the top right, and when n is even, start in the top left. Then move n - 1 squares toward the othr side of the board (left or right). Next move one square down, and then n - 1 squares in the opposite direction, repeating until you are in the bottom left. For a board n + 1 x n + 1, repeat this for n, and once you reach the bottom left of nxn, move down one and all then right n - 1 squares, and finally up n - 1 sqaures.

D. **Claim:** There exists a rook’s tour for any chessboard of size $n \geq 1$
**Induction hypothesis:** There exists a rooks’s tour for any chessboard of size $k \geq 1$
Proof:
Using our algorithm, we have shown that a for any chess board of size n, there is a knight's tour that ends in the bottom left corner. Thus, performing induction on the size n and using a chess board of size n + 1, we complete the original walk, then move down one, right n - 1, and up n - 1, hitting every square.