Consider the unit square $ S = [0,1] \times [0,1] $. For each $ n \in \mathbb{N} $, we can tessellate $ S $ by the collection $$ A = \left\{ \left[ \frac{i}{n},\frac{i + 1}{n} \right] \times \left[ \frac{j}{n},\frac{j + 1}{n} \right] ~ \Bigg| ~ i,j \in \{ 0,\ldots,n - 1 \} \right\} $$ of $ n^{2} $ smaller squares whose sides have length $ \dfrac{1}{n} $.
Let $ C_{1} $ be a finite sequence $ (S_{k})_{k = 1}^{M} $ of squares in $ A $ such that
- $ S_{1} = \left[ 0,\dfrac{1}{n} \right] \times \left[ 0,\dfrac{1}{n} \right] $;
- $ S_{M} = \left[ \dfrac{n - 1}{n},1 \right] \times \left[ \dfrac{n - 1}{n},1 \right] $;
- $ S_{k} $ and $ S_{k + 1} $ share a common side for each $ k \in \{ 1,\ldots,M - 1 \} $.
Similarly, let $ C_{2} $ be a finite sequence $ (T_{k})_{k = 1}^{N} $ of squares in $ A $ such that
- $ T_{1} = \left[ 0,\dfrac{1}{n} \right] \times \left[ \dfrac{n - 1}{n},1 \right] $;
- $ T_{N} = \left[ \dfrac{n - 1}{n},1 \right] \times \left[ 0,\dfrac{1}{n} \right] $;
- $ T_{k} $ and $ T_{k + 1} $ share a common side for each $ k \in \{ 1,\ldots,N - 1 \} $.
Geometrically speaking, $ C_{1} $ is a chain of side-touching squares in $ A $ from the bottom leftmost corner of $ S $ to its upper rightmost corner, and $ C_{2} $ is a chain of side-touching squares from the upper leftmost corner of $ S $ to its bottom rightmost corner.
Combinatorial problem. Find a combinatorial proof that $ C_{1} $ and $ C_{2} $ contain a common square in $ A $. (It is intuitively obvious that the chains contain a common square in $ A $.)
If we let $ n \to \infty $, then we obtain a
Continuous version of the problem. Let $ \gamma_{1} $ be a continuous path in $ S $ from $ (0,0) $ to $ (1,1) $ and $ \gamma_{2} $ a continuous path in $ S $ from $ (0,1) $ to $ (1,0) $. Then prove that $ \gamma_{1} $ and $ \gamma_{2} $ intersect, i.e., $ {\gamma_{1}}(a) = {\gamma_{2}}(b) $ for some $ a,b $ in the interval $ ]0,1[ $.
The continuous version of the problem has a well-known solution via Brouwer’s Fixed Point Theorem, but most proofs of Brouwer’s Fixed Point Theorem require algebraic topology. Even Sperner’s combinatorial proof requires some effort to understand. If, however, we can solve the combinatorial problem above, then by a limiting argument, we can solve the continuous version rather easily, thus avoiding Brouwer.
There are certain similarities between this problem and the Game of Hex, where elementary properties of the game are a consequence of non-trivial topological arguments, as first demonstrated by John Nash.
