Prove or disprove the existence of random variables X_n so that the expected value of X_n goes to infinity as n goes to infinity but X_n goes to 0 almost surely (maybe not as much of a problem, but a pretty useful thing to think about for people who use EV calculations to make decisions).
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.
I’ve determined computationally that for an n×n grid the number of tilings is 2n/2 if n is even and 0 if n is odd, but I don’t have a proof of this fact yet. I’ll be looking for one—the answer looks quite nice so there ought to be a neat argument for seeing why it’s like this.
More precisely, it looks like the possible tilings correspond to the ways of tiling the first row of the grid with 2x1 white or black dominoes. It’s easy to see that the first row has to be of this form and that any such first row can’t correspond to more than one tiling of the grid, but showing that there is always a valid extension of the coloring to the whole grid seems to be the hard part.
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.
Prove or disprove the existence of random variables X_n so that the expected value of X_n goes to infinity as n goes to infinity but X_n goes to 0 almost surely (maybe not as much of a problem, but a pretty useful thing to think about for people who use EV calculations to make decisions).
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.
First is much easier than 2nd.
About the second problem:
I’ve determined computationally that for an n×n grid the number of tilings is 2n/2 if n is even and 0 if n is odd, but I don’t have a proof of this fact yet. I’ll be looking for one—the answer looks quite nice so there ought to be a neat argument for seeing why it’s like this.
More precisely, it looks like the possible tilings correspond to the ways of tiling the first row of the grid with 2x1 white or black dominoes. It’s easy to see that the first row has to be of this form and that any such first row can’t correspond to more than one tiling of the grid, but showing that there is always a valid extension of the coloring to the whole grid seems to be the hard part.
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.
For the 2nd, does adjacent include diagonals?
If it does, I don’t think there are any valid tilings.
My University has a problem sheet question that presents the first problem in a nice way that feels more real-worldy