OMM 1997 Problem 3

The numbers $1$ through $16$ are to be written in the cells of a $4\times 4$ board. (a) Prove that this can be done in such a way that any two numbers in cells that share a side differ by at most $4$ . (b) Prove that this cannot be done in such a way that any two numbers in cells that share a side differ by at most $3$ .