How to draw Square Diagonal?

Question

Draw a 5x5 square. In 16 of 25 squares draw diagonals in such a way that no diagonal ends touch. How can I do this?

Answer 1

Posting a CW-copy of the image (linked to) given as a solution to the duplicate question. Just in case the link rots :-/

Answer 2

I think the best you can do may be fifteen...?

Answer 3

Here's a wrong (alas) proof that it can't be done.

There are 36 vertices in the grid.

Suppose you had a solution.

Your 16 diagonals will use up 32 of these vertices. So exactly four vertices are unused.

There are also 50 possible diagonals. Each (internal) vertex that goes unused corresponds to at most four edges that cannot be used. [N.B., added after comments: at this point the remainder of the argument is flawed, for there are other ways for an edge to be unused -- like other edges using one of its two endpoints. D'oh!] An external vertex corresponds to either 2 or 1 unused diagonals. So the largest number of unused diagonals in any arrangement that leaves only four unused vertices is 16. That means such an arrangement uses at least 34 diagonals. That's a contradiction.

Answer 4

Here's an argument why $16$ is optimal. Let $r_i$ be the number of diagonals drawn in the $i$-th row of squares. (So in the claimed optimal solution $r_1 = r_3 = r_5 = 4$ and $r_2 = r_4 = 2$.) Then $0 \le r_i \le 5$, and because each diagonal in row $i$ eliminates $1$ of the $6$ upper vertices for a a diagonal in row $i + 1$, we have $r_{i+1} \le 6 - r_i$. Let $d_{i+1} = 6 - r_i - r_{i+1}$ be the error in this inequality so that $d_{i+1} \ge 0$ and $r_{i+1} = 6 - r_i - d_{i+1}$. (So the $d_i$ are all $0$ in the claimed optimal solution.) The total number of diagonals is then:

$$ r_1 + r_2 + r_3 + r_4 + r_5= r_1 + 12 - d_3 - d_5 \le 17 $$

and we can only have equality if $r_1 = 5$ and $d_3 = d_5 = 0$. However, if $r_1 = 5$ and $r_2 = 1$, $r_3$ cannot be $5$ because the diagonal in row $2$ cannot have its lower vertex on the boundary of the array of squares. So $d_3 > 0$ and the optimal solution does indeed have at most $16$ diagonals as claimed.