Find all pairs of positive integers $n$ such that one can partition a $n\times (n+1)$ board with $1\times 2$ or $2\times 1$ dominoes and draw one of the diagonals on each of the dominos so that none of the diagonals share endpoints.
Problem
Source: 2024 Korea Summer Program Practice Test Junior P3
Tags: combinatorics
sami1618
12.08.2024 19:29
All $n$ work. Here are constructions for $n=6$ and $n=7$ [asy][asy] add(grid(6,7)); draw((0,0)--(1,2), red); draw((0,2)--(1,4), red); draw((0,4)--(1,6), red); draw((1,1)--(2,3), red); draw((1,3)--(2,5), red); draw((2,2)--(3,4), red); draw((3,2)--(4,4), red); draw((4,1)--(5,3), red); draw((4,3)--(5,5), red); draw((5,0)--(6,2), red); draw((5,2)--(6,4), red); draw((5,4)--(6,6), red); draw((1,0)--(3,1), red); draw((3,0)--(5,1), red); draw((2,1)--(4,2), red); draw((2,4)--(4,5), red); draw((1,5)--(3,6), red); draw((3,5)--(5,6), red); draw((0,6)--(2,7), red); draw((2,6)--(4,7), red); draw((4,6)--(6,7), red); [/asy][/asy] [asy][asy] add(grid(8,7)); draw((0,0)--(1,2), red); draw((0,2)--(1,4), red); draw((0,4)--(1,6), red); draw((1,1)--(2,3), red); draw((1,3)--(2,5), red); draw((2,2)--(3,4), red); draw((5,2)--(6,4), red); draw((6,1)--(7,3), red); draw((6,3)--(7,5), red); draw((7,0)--(8,2), red); draw((7,2)--(8,4), red); draw((7,4)--(8,6), red); draw((1,0)--(3,1), red); draw((3,0)--(5,1), red); draw((5,0)--(7,1), red); draw((2,1)--(4,2), red); draw((4,1)--(6,2), red); draw((3,2)--(5,3), red); draw((3,3)--(5,4), red); draw((2,4)--(4,5), red); draw((4,4)--(6,5), red); draw((1,5)--(3,6), red); draw((3,5)--(5,6), red); draw((5,5)--(7,6), red); draw((0,6)--(2,7), red); draw((2,6)--(4,7), red); draw((4,6)--(6,7), red); draw((6,6)--(8,7), red); [/asy][/asy]