In an $n\times n$ board, what is the number of ways to color the squares in black and white so that there exists a path from some square in the top row to some square in the bottom row, going only through squares with adjacent edges, such that all squares in the path are white? If there is no closed form, what are good upper or lower bounds?

The total number of colorings is $2^{n^2}$. If we color the first column white, the condition is already satisfied regardless of the remaining columns, so this contains $2^{n(n-1)}$ colorings. We can do this to the other columns as well but need to apply inclusion-exclusion, so we get slightly less than $n\cdot 2^{n(n-1)}$ colorings.


You could use a taxi-cab metric, where:

$$ d(p,q) = \sum_{i} |p_{i} - q_{i}| $$

for each co-ordinate on a p x q board.

so that the co-ordinates are now: $$ (p, d(p,q))$$

so that if we have p = 3 and q = 2 we have:

|3-0| + |2-2| + |1-1| = d(3,2) = 3

so that the metric only exists if $$ p \neq q $$

this will create paths from the top to bottom row that are not linear


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.