Find the number of ways to tile a 1000 by 1000 grid with white and black tiles so each tile is adjacent to exactly two tiles of the same color.
The adjacency condition means that colored regions will form simple closed loops since ends and splits are disallowed. The smallest allowed region is a 2x2 tiles. The basic “textures” will be checkerboards of 2x2 regions and longer alternating stripes or concentric rings.
There are two ways to choose the color of the first corner tile at (1,1) position. The two tiles adjacent to the corner, (2,1) and (1,2) must match the corner. This covers the first two diagonals.
This gives another choice for the color of the (3,1) tile—it can either match the corner or not. Choosing this tile’s color constrains other tiles, specifically any tile (x,y) with x+y ⇐ 5 (the next two diagonals). The (4,1) tile must match the (3,1) tile, the (3,2) tile must be different from the corner, the (2,2) tile must be different from the (3,1) tile, etc. All colors will be symmetrical about the x=y diagonal.
Each additional choice constrains another two diagonals until the corner is reached, at which point the entire rest of the grid is constrained (it symmetrically matches the first half). For a 2Nx2N grid, this results in N choices before the entire grid is constrained or 2^n tilings (this extends even to the single degenerate tiling of the 0x0 grid).
For a 1000x1000 grid, there are 2^500 tilings satisfying the condition.
The adjacency condition means that colored regions will form simple closed loops since ends and splits are disallowed. The smallest allowed region is a 2x2 tiles. The basic “textures” will be checkerboards of 2x2 regions and longer alternating stripes or concentric rings.
There are two ways to choose the color of the first corner tile at (1,1) position. The two tiles adjacent to the corner, (2,1) and (1,2) must match the corner. This covers the first two diagonals.
This gives another choice for the color of the (3,1) tile—it can either match the corner or not. Choosing this tile’s color constrains other tiles, specifically any tile (x,y) with x+y ⇐ 5 (the next two diagonals). The (4,1) tile must match the (3,1) tile, the (3,2) tile must be different from the corner, the (2,2) tile must be different from the (3,1) tile, etc. All colors will be symmetrical about the x=y diagonal.
Each additional choice constrains another two diagonals until the corner is reached, at which point the entire rest of the grid is constrained (it symmetrically matches the first half). For a 2Nx2N grid, this results in N choices before the entire grid is constrained or 2^n tilings (this extends even to the single degenerate tiling of the 0x0 grid).
For a 1000x1000 grid, there are 2^500 tilings satisfying the condition.
I can only find 4 tilings of the 6 by 6 grid:
And
As well as their inverses.
What am I missing?
This one, its rotation, and their inverses.