# oh54321 answers What are the best elementary math problems you know?

• 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 grid the number of tilings is if is even and if 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.

• I can only find 4 tilings of the 6 by 6 grid:

110011
110011
001100
001100
110011
110011


And

111111
100001
101101
101101
100001
111111


As well as their inverses.

What am I missing?

• 111100
100100
100111
111001
001001
001111


This one, its rotation, and their inverses.

• My University has a problem sheet question that presents the first problem in a nice way that feels more real-worldy

• For the 2nd, does adjacent include diagonals?

• If it does, I don’t think there are any valid tilings.

• [ ]
[deleted]
• [ ]
[deleted]