4
$\begingroup$

Suppose we have a rectangular floor, $a$ units long by $b$ units wide, which we need to tile with black and white unit square tiles. We flip a coin to decide whether the first tile will be black or white, and lay it down in the top left corner. The second and all subsequent tiles will also have a 50-50 chance of being black and white.

A 'region' is defined as a contiguous area of same-colour tiles, touching each other by their sides (just a corner is not enough). Thus, the maximum number of regions possible is $ab$ (checkerboard tiling), while the minimum number is 1 (the whole floor is either black or white).

What is the expected number of regions on the board, as a function of $a$ and $b$?

$\endgroup$
3
$\begingroup$

At first I won't take the edges into account. Suppose the board wraps around, in a torus shape.

The expected number of 1-square regions is $ab/2^4$ because all four edges must be the opposite colour.

The expected number of vertical dominoes is $ab/2^7$, as the six edges and one internal match must be correct. So is the number of horizontal dominoes, so that gives $2ab/2^7$ 2-square regions.

For triominoes, there are eight edges and two internal lines. The L triomino has four orientations, and the I triomino has two, so you get $6ab/2^{10}$ three-square regions.

For tetrominoes, I get $18ab/2^{13}$. The square contributes $ab/2^{12}$, and the others various multiples of $ab/2^{13}$.

The total looks like $$ab\left[\frac1{16}+\frac2{128}+\frac6{1024}+\frac{18}{8192}+\cdots\right]$$

So it looks like only a small portion of the area - say, a quarter - is covered with small regions.

You get a rectangle from a torus by cutting along a horizontal line and a vertical line to make the edges. Some of these polynomials are cut into two pieces. That gives an extra $$(a+b)\left[\frac0{16}+\frac1{128}+\frac6{1024}+\frac{23}{8192}+\cdots\right]$$ Some polyominos, including the U-pentomino, are cut into three or more pieces. Also, the square tetromino and P-pentomino can be cut into four pieces if they end up at all four corners of the rectangle.

$\endgroup$
1
$\begingroup$

In the case of a checkerboard, the number of regions is simply $ab$.

When two adjacent squares are of the same colour, this reduces the number of regions by 1. There are $a$($b$-1) + $b$($a$-1) total possible connections between two adjacent squares. For any given pair of adjacent tiles, there is a 50% chance that they are the same colour. Consequently, the expected number of connections is simply $ab$ - ($a$+$b$)/2. We now subtract this from the total number of tiles. Thus, the expected number of regions is ($a$+$b$)/2 .

However, consider the case when a 2*2 square of 4 tiles are all the same colour. Here, there are 4 tiles and 4 same-color connections between adjacent tiles. However, the number of regions is not 4-4=0, but rather, it is 1. Consequently, for every same-colour square that appears, we need to add 1 to the count of regions. For any given 2*2 square, there is a 1/8 chance that all tiles are the same colour. There are ($a$-1)($b$-1) total squares, so an expected value of ($a$-1)($b$-1)/8 same-colour squares.

Putting the pieces together, the expected number of regions simplifies to: (($a$+3)($b$+3)/8) - 1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.