Chessboard Rook Problem

Question

Let's say that you have a chessboard (they are 8x8 spaces) with a rook on it (only moves horizontally & vertically). You can put walls horizontally or vertically between the spaces. If the rook can get to every possible space on the chessboard without going over a wall, then it is a good chessboard. If the rook can not get to every possible space, it is a bad chessboard. It doesn't matter where the rook starts, as it needs to be able to get to every space anyways.

1) Are there more possible good or bad chessboards?

2) Can you prove this?

______
^{Source: University of Calgary's "Math Nite"}

Answer 1

There are

more bad chessboards than good.

Proof:

Imagine picking configurations at random, where each possible wall is independently present or absent with probability 1/2. The question is equivalent to asking whether Pr(good) is above or below 1/2.

Now

the board is bad if any one of the corner squares is cut off, which happens with probability 1/4 for each of these squares. And the corners are independent of one another, so the probability that no corner square is cut off is (3/4)^4 = 81/256 < 1/2. So the probability that the board is good is certainly < 1/2, and we're done.

I bet the ratio of good to bad is

much smaller than the bound above. Here's another crude bound on it. Every edge is adjacent to one black and one white square. Ignore the white ones and look only at the black. The board will be bad if any of these squares is entirely surrounded by walls (together with the edge of the board, if appropriate). Two of these squares have 2 edges that would have to be walls. 12 more have 3 edges that would have to be walls. And the remaining 18 have 4 such edges. So the probability that a board is good is at most $\left(\frac34\right)^2\left(\frac78\right)^{12}\left(\frac{15}{16}\right)^{18}$ or about 3.5%. A similar but slightly fancier way of dividing up edges, which I won't detail here, gives $\left(\frac34\right)^2\left(\frac58\right)^2\left(\frac78\right)^{8}\left(\frac{15}{16}\right)^{18}$ or about 2.4%.This is probably still a big overestimate.

I wrote a little Python program (possibly buggy, so apply some skepticism, but I've tested the bit most likely to have bugs and it seems OK) to estimate the ratio by generating lots of random boards and counting good and bad ones. The result is

that somewhere around 1/10000 of all boards are good. After about 11 million boards, the actual figure I've got is 0.000106. If my trials are genuinely independent and random, the standard deviation in that figure should be about 0.000003, so the estimate is probably pretty good. Aside from any bugs in my code and deficiencies in Python's random number generator, that is. This is a somewhat higher proportion than I expected, but not outrageously so. (Thanks to Jaap Scherphuis for pointing out in comments that I somehow turned 0.0001 into 1/1000 in an earlier version of this answer. Oops.)

Answer 2

There are more

bad

ones.

---

Proof:

I can make pairs of chessboards by "flipping all the walls", so if there is a wall, I erase it, and if there isn't I put one there. A pair can be bad-bad, bad-good, but it can't be good-good.

There are bad-bad pairs (for example, all walls in the upper half, and no walls in the lower half, it is still bad after flipping). There are bad-good ones (for example, empty/full of walls).

If i can prove there are no good-good pairs, then bad ones outnumber good ones, because of the existence of bad-bad pairs.

Prove that there can't be good-good pairs:

Consider the following: there are $7 \times 8 \times 2 = 112$ possible walls.

All good chessboards contain maximum 49 walls (at least 63 non-walls), because you have to able to reach every spaces.

You always need at least 1 new non-wall to reach a new location. If it has less then 63 non-walls, then you can't go to all 63 non-starting spaces (wherever you start). Imagine as if you pour water from first location, surrounded by walls, and you expand it by putting down 1 non-wall.

So, you can't have good-good pairs (because all pairs consist of exactly 112 walls, and you could only use max 49 + max 49).

Answer 3

Gareth's answer is the best, but just for fun, I wanted to get some actual numbers of $\color{Red}{BAD}$ boards.

The starting board looks like this: (# space, | or — place where a wall could go.)

# | # | # | # | # | # | # | #
—   —   —   —   —   —   —   —
# | # | # | # | # | # | # | #
—   —   —   —   —   —   —   —
# | # | # | # | # | # | # | #
—   —   —   —   —   —   —   —
# | # | # | # | # | # | # | #
—   —   —   —   —   —   —   —
# | # | # | # | # | # | # | #
—   —   —   —   —   —   —   —
# | # | # | # | # | # | # | #
—   —   —   —   —   —   —   —
# | # | # | # | # | # | # | #
—   —   —   —   —   —   —   —
# | # | # | # | # | # | # | #

That's 112 places a wall could go, and each one has 2 options, so using some basic probability, there are $2^{112} \approx 5.19 * 10^{33}$ total permutations.

Now, of the spaces the rook could be on (#'s above), most of them (36) are core (24 are edges, and only 4 are corners). For these, let us take the simplified scenario where all 4 wall places are consumed surrounding the space, making the whole board $\color{Red}{BAD}$. The remaining 108 wall places can take any permutations, giving $2^{108}$ possibilities just for this one space. To avoid counting permutations twice, I will keep reducing by 4 for each square, yielding:

which WolframAlpha says is about $3.46 * 10^{32}$. This is still an order of magnitude off from my goal (makes sense because I didn't consider areas larger than one cell blocked off), but hey, it was fun for a while.

Answer 4

Consider the problem on an $n\times n$ board rather than necessarily an $8\times8$ one. If $n=1$ then there is 1 good board and there are no bad ones, so there are more good boards than bad. I claim that there are no other values of $n$ for which there are more good boards than bad. Assume therefore that $n\geq2$.

There are $2n(n-1)$ positions where a wall may be found. The number of possible boards is therefore $2^{2n(n-1)}$. I claim that a good board has no more than $(n-1)^2$ walls. If it is so, then for the board to be good, the number of positions with a wall has to be less than the number of positions with no wall, since the difference between the two (#positions with walls minus #positions without) is at least

$2n(n-1) - 2(n-1)^2 = 2(n - 1) > 0$

for $n \geq 2$. The fact that there are more bad boards then follows by symmetry of binomial coefficients.

It remains to be shown that a good board has no more than $(n-1)^2$ walls. Indeed, suppose I have constructed a good board which cannot support the addition of any more walls without being bad as a result. Then I could construct this board iteratively, starting with only the board edges and adding walls one by one, at each stage joining a new (previously uncontacted) interior vertex with a wall either to the board edge or another wall. (I must join a previously uncontacted vertex at each step because if I join an interior vertex already touched by a wall to the edge, or if I join two previously touched vertices together, then I must have formed a cycle consisting in part of walls and possibly in part of board edges, which means I must have split the board in two.) Since there are $(n-1)^2$ interior vertices, this establishes the needed result.