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 Proof.
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 and not divisible by 2. 2m≤Number(top and bottom edges of the loops)=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
Proof. Assume on contrary that it doesn't have form 2p×2n(1≤p≤m)
Case 1) The loop contains (1,1) is odd by even
Case 1-1) 2a×(2b+1)By Hint 5 the top left 2a×(2b+1) need at least a loops.
In the last 2m−2a rows if there exist a row that doesn't contain the top or the bottom edge of any loops, by the same way of proof in Hint 4 Number of loops≥n+a>m✗ ⇒ So each of the last 2m−2a rows contain the top or the bottom edge of at least one loop Number of loops≥a+(m−a+1)=m+1✗ Here a comes from the 2a×(2b+1) part, and m−a+1 comes from the last 2m−2a rows and the last cell of the first row
Case 1-2) (2b+1)×2aSimilarly Number of loops≥a+min{n−a+1,m}=min{n+1,m+a}>m✗ Here min{n−a+1,m} comes from the last 2n−2a columns and the last cell of the first column
Case 2) The loop contains (1,1) has sides 2a and 2b (WLOG a≤b)
(By Contrary b<n)
Case 2-1) 2a×2bNumber of loops≥a+min{m−a+1,n}=min{m+1,n+a}>m✗ Here min{m−a+1,n} comes from the last 2m−2a rows and the last cell of the first row
Case 2-2) 2b×2aNumber of loops≥a+min{n−a+1,m}=min{n+1,m+a}>m✗ Here min{n−a+1,m} comes from the last 2n−2a columns and the last cell of the first column
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.
Proof. Suppose if the loop contains (1,1) is odd by even, the even side is 2a, and if it is even by even the shorter side is 2a.Assume, to the contrary, that the loop does not reach the right or bottom side of the main grid, similar to Hint 7. Number of loops≥a+min{m−a+1,m}=min{m+1,m+a}>m✗ Here a comes from the 2b×2a loop.
min{m−a+1,m} comes from the last 2m−2a columns and the last cell of the first column.
Let a2m,2n be the number of ways to partition a 2m×2n(m≤n) grid of cells into m cell loops so that every cell of the grid belongs to exactly one cell loop.Let's calculate a10,10.
Consider the loop that contains the top left corner. By Hint 8, the size is2×10 or 10×2:2a8,104×10 or 10×4:2a2,8a6,106×10 or 10×6:2a4,8a4,108×10 or 10×8:2a6,8a2,1010×10:a8,8⇒a10,10=2a8,10+2a2,8a6,10+2a4,8a4,10+2a6,8a2,10+a8,8
a2,2m=1m≥1 Since we should place one loop.
Let's find a4,2m, m≥2.
Base your casework on the loop that contains the top left corner.a4,4={2a2,2a2,22×4 or 4×24×4By Hint 10, a4,4=2a2,2+a2,2=2+1=3For m≥3, a4,2m={a2,2ma2,2m−22×2m4×2mBy Hint 10, a4,2m=a2,2m+a2,2m−2=1+1=2m≥3
Let's find a6,2m, m≥3.
Base your casework on the loop that contains the top left corner.a6,6=⎩⎨⎧2a4,62a2,4a2,6a4,42×6 or 6×24×6 or 6×46×6By Hints 10 and 11, a6,6=2a4,6+2a2,4a2,6+a4,4=2(2)+2(1)(1)+3=9For m≥4, a6,2m=⎩⎨⎧a4,2m=2a2,2m−2a2,2m=1a4,2m−2=22×2m4×2m6×2ma6,2m=a4,2m+a2,2m−2a2,2m+a4,2m−2=2+1+2=5m≥4
a8,8 Base your casework on the loop that contains the top left corner.By Hints 10, 11, and 12, a8,8=⎩⎨⎧2a6,8=102a2,6a4,8=2(1)(2)=42a4,6a2,8=2(2)(1)=4a6,6=92×8 or 8×24×8 or 8×46×8 or 8×68×8⇒a8,8=10+4+4+9=27
a8,10 Base your casework on the loop that contains the top left corner.By Hints 10, 11, and 12, a8,10=⎩⎨⎧a6,10=5a2,8a4,10=2a4,8a2,10=2a6,8=52×104×106×108×10⇒a8,10=14
By Hints 10, 11, 12, 13, and 14, a10,10=2a8,10+2a2,8a6,10+2a4,8a4,10+2a6,8a2,10+a8,8=2(14)+2(1)(5)+2(2)(2)+2(5)(1)+27=28+10+8+10+27=83 Final Answer 83
