Let $n$ be a positive integer. A panel of dimenisions $2n\times2n$ is divided in $4n^2$ squares with dimensions $1\times1$. What is the highest possible number of diagonals that can be drawn in $1\times1$ squares, such that each two diagonals have no common points.
Problem
Source: Moldova TST 2021
Tags: combinatorics
x3yukari
22.09.2021 03:01
Suppose we have a grid of dimensions $2n\times2n$. Draw all diagonals of the $1 \times 1$ squares. The points the diagonals touch form a $2n+1 \times 2n+1$ grid of lattice points. In this lattice grid, it is evident that the diagonals form two distinct "four sided staircase" patterns. Examples: $n=2$ and $n=4$. Green and red denote the two distinct staircase patterns I showed here. We take each staircase pattern separately. We cannot have two diagonals touch the same vertex, so we want to touch as many vertices as possible with our diagonals. With the green figure, we can (after turning the figure $45$ degrees), touch all of the vertices in this figure by just filling in each row of vertices from left to right with diagonals that don't touch, since in each row, there's an even number of vertices. With the red figure, there's an odd number of vertices in each row. Thus in each row, we must leave one vertex untouched when filling in the rows of vertices. We can't connect the untouched vertices vertically either, because they'll always be an even number of vertices away from the endpoints of the rows, and since consecutive rows have their endpoints one vertex apart horizontally, the untouched vertices cannot coincide and allow us to form another diagonal that we can touch. So we fill in all the diagonals we can, from left to right, throughout the rows of the vertices and parallel to the diagonals from the first staircase pattern, ensuring all of the diagonals are parallel and thus do not touch. This leaves $2n+1$ untouched vertices. To count the total number of diagonals we take the total number of vertices ($(2n+1)^2$), subtract the untouched vertices ($2n+1$, and divide by $2$ since we're pairing up the remaining vertices. This gives us $n(2n+1)$ diagonals in total.
P2nisic
04.10.2022 16:18
There are $(2n+1)^2$ vertices. If we draw a diagonal the at exactly on of the end point belongs to a even column. So there are at most $n(2n+1)$ diagonals. This can be achieved. For example for $n=4$ XXOXOXOX XOOXOXOX XOXXOXOX XOXOOXOX XOXOXXOX XOXOXOOX XOXOXOOX XOXOXOXX