Theorem: For the 2k X m problem, the optimal solution has size k*(m+1). Proof: First assume that m is odd. Since there are even number of rows in the grid, you can color the grid intersection points line-by-line, say the top line red, the next line of intersection points blue, then red again, and so on, till the last,(2k+1)-th, which is red. This coloring results in k lines of blue, and k+1 lines of red grid intersection points. Since every diagonal connects a blue point with a red point, there cannot be more diagonals than blue intersection points, which is k*(m+1). The L-shaped arrangement provides a way to place k*(m+1) diagonals as can be seen by pairing up rows, e.g., in the 4 x 7 case: /o/oooo /o///// /oooooo /////// Now, let's assume that m is even, that is, m=2n, and k<=n. Then the same argument works, and we could do the coloring above either row-by-row, or column-by-column. The former results in k*(2n+1) as an upper the bound on the number of diagonals that can be placed, while the latter gives n*(2k+1). Since k<=n, k*(m+1)=k*(2n+1)<= n*(2k+1)=n*(m+1), so k*(m+1) is a sharper bound. The L-shaped arrangement provides a way to place k*(m+1) diagonals in this case again.