We have an $n \times n$ square divided into unit squares. Each side of unit square is called unit segment. Some isoceles right triangles of hypotenuse $2$ are put on the square so all their vertices are also vertices of unit squares. For which $n$ it is possible that every unit segment belongs to exactly one triangle(unit segment belongs to a triangle even if it's on the border of the triangle)?
Problem
Source: Serbia TST 2017 #4
Tags: combinatorics
22.05.2017 17:46
The answer is $2|n$ ?
22.05.2017 20:30
Please ignore this post. I commited a mistake. Thanks @below for a correct solution.
22.05.2017 21:57
Answer is actually $3|n(n+1)$ and $2|n$. We can prove this by considering the number of unit segments in whole $n\times n$ and the number of unit segments on one side of $n\times n$ square. We have that the unit segments on the border of $n\times n$ square are all contained on diagonals of triangles therefore $2|n$. Now since each triangle has exactly $3$ unit segments and the whole square has $2n(n+1)$ we have that $3|2n(n+1)$. Now to construct an example. For $2\times 2$ just take four triangles.For $6\times 6$ take $5$ $2\times2$'s and place then one on each corner and one in center and fill the rest with triangles pointing in the same direction, that is four blocks of size $2\times 2$ . Now for induction step of $n\times n $ to $(n+6)\times(n+6)$ take one $nxn$ four blocks of triangles pointing in same direction of size $2\times(n+2)$ and one $(n+6)\times (n+6)- (n+5)\times (n+5)$ filled with triangles. They make $(n+6)\times(n+6)$ and every unit segment is in exactly one of triangles.Therefore we can construct example for all $n=6k+2$ or $n=6k$.