A $45 \times 45$ grid has had the central unit square removed. For which positive integers $n$ is it possible to cut the remaining area into $1 \times n$ and $n\times 1$ rectangles?
Problem
Source: Baltic Way 2024, Problem 7
Tags: combinatorics, combinatorics proposed, Tiling
17.11.2024 19:59
Is it 1,2,4,11,22,23?....not too hard....the gap in the centre divides the 45×45 into four 22×22 in four corners and two 22×1 and 1×22 strips adjacent to the gap. Now the maximum value of n is 23. Now required values of n we will get when n will divide both 2024 and 1012 provided n≤23.
11.12.2024 12:20
45^2-1=44*46=2^3*11*23, n must divide it which means n\in{1,2,4,1,2,4,8,11,22,23,44,…} . Omit the ones that are bigger than 45, we check 1,2,4,8,11,22,23,44. Splitting the area to 2 22*23 and 2 23*22 blocks, then it's obvious that n=1,2,11,22,23 are good. Coloring a 46*46 grid with the the below 2x4 pattern, 0 0 1 1 1 1 0 0 and remove the right column and bottom row, we get a 45*45 colored grid. After removing the central unit, we can see that we have 2 more "0" units comparing to "1" units. On the other hand, putting 1*4 and 4*1 rectangles on the area will always cover 2 "0" and 2 "1". It means if 1*4 and 4*1 rectangles can cover the area, there must be same amount of "0" and "1" units which is not the case. So we know 1*4k and 4k*1 can't meet the target. Then the answer is n=1,2,11,22,23.