Let a, b, and n be positive integers with both a and b greater than or equal to 2 and less than or equal to 2n. Define an a×b cell loop in a 2n×2n grid of cells to be the 2a+2b−4 cells that surround an (a−2)×(b−2) (possibly empty) rectangle of cells in the grid. For example, the following diagram shows a way to partition a 6×6 grid of cells into 4 cell loops.
Find the number of ways to partition a 10×10 grid of cells into 5 cell loops so that every cell of the grid belongs to exactly one cell loop.
Find the number of ways to partition a 2×2 grid of cells into 1 cell loop so that every cell of the grid belongs to exactly one cell loop. ⇒1 Case
Find the number of ways to partition a 4×4 grid of cells into 2 cell loops so that every cell of the grid belongs to exactly one cell loop. ⇒3 Cases
By checking more small examples you can get the following hints.
Suppose a 2m×2n grid (m≤n) is completely partitioned into N cell loops, then N≥mProof.
Case 1) If every row contains the top or the bottom edge of at least one loop 2m≤Number(top and bottom edges of the loops)=2N⇒N≥m Case 2) There exists a row that contains neither top edge nor bottom edge of any loops.Then each loop covers 0 or 2 cells of this row so we need at least n loops to cover this row. ⇒N≥n≥m
Suppose a 2m×(2n+1) grid is completely partitioned into N cell loops, then N≥m Each row has odd cells. It needs to contain the top edge or the bottom edge of at least one loop otherwise each loop covers 0 or 2 cells of that row but the number of cells in this row is odd. ⇒2m≤2N⇒N≥m
There is no odd × odd loop.
Proof. Then inside that there would be odd cells but each loop covers even number of cells.
Suppose a 2m×2n grid (m<n) is completely partitioned into m cell loops, then the loop that contains the top left corner should have size 2p×2n where 1≤p≤m.
Suppose a 2m×2m grid is completely partitioned into m cell loops, then the loop that contains the top left corner should reach the right or bottom side of the main grid.
Let a2m,2n be the number of ways to partition a 2m×2n grid into m cell loops.
