On an $n\times n$ grid, with white and black tiles: is there always a connected path across the grid? 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?
 A: 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.
A: A different approach.
Assume for a contradiction that there is no such path. Now consider some connected component of maximum width (i.e. the difference of the distance of the rightmost tile and the leftmost tile is maximised). Wlog it is a white connected component. Notice that the connected component has to be surrounded by only black tiles and grid-wall tiles. But it cannot be the case that it is surrounded by some grid-wall tile on the top AND on the bottom because otherwise we would have a connected path. The same argument applies for left/right. Thus we can assume wlog that our connected component is surrounded by black tiles (no wall) on the top and on the right. But the connected component of these black tiles has a larger width than our connected component. A contradiction.
