Assume you have an $n\times n$ grid, and a set W of white and a set B of black tiles that are placed randomly on this grid.
I think that at least one of the sets W, B must include a connected path of tiles from one side of the grid to the opposite side of the grid.
What I mean by connected path: the tiles have the same color, and they are pairwise neighbors to each other (each pair of them shares an edge or a vertex).
I think such a connected path, connecting one side of the grid with the opposite side, must be included in B or W, regardless of the distribution of tiles.
I suspect it is sufficient to prove this for the case when W and B have equal size $n^2/2$. I also suspect that one could start from a chess board style pattern, and go from there to cover all other distributions of black and white tiles. Finally, I suspect the Pigeon Hole Principle might prove it in one go; but I have not found the right entry point to this route.
Does anybody know a short simple proof?
Best Answer
Yes, there is always such a path. Think of this as a maze – you can walk on the black tiles, and the white tiles are walls. Start, say, at the bottom right corner, just below the maze, facing the maze. Step into the maze if you can, or else turn left. Now put your hand to the wall on your right. (If necessary, add a column of white tiles at the right of the maze.) Start walking, always keeping your hand on the wall. You will either get through from the bottom to the top, or your hand will trace a contiguous wall from the right to the left.
This recently came up at Possibility of ants not being able to cross a grid shaped bridge.