4. A square $15 \times 15$ is divided into $1 \times 1$ squares. Some of these squares were chosen, and one or two diagonals were drawn in each of the chosen squares. It turned out that no two drawn diagonals share a common endpoint. What is the maximum number of diagonals that can be drawn? (In your solution, provide the answer, a way to draw the diagonals, and a proof that this number of diagonals is indeed the maximum possible.)
Answer: 128. Solution. Let's number the rows and columns of the square in order with numbers from 1 to 15 and draw two diagonals in the cells located at the intersection of odd-numbered rows with odd-numbered columns. There are 64 such cells, meaning 128 diagonals will be drawn. On the other hand, the diagonals should not share endpoints, and there are a total of $16 x 16=256$ vertices in the 15x15 square. Therefore, the number of diagonals that can be drawn is no more than $256: 2=128$.