A problem on chains of squares — can one find an easy combinatorial proof? 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.
 A: You could google digital Jordan curve theorem and you could also add some of the following names in your search: Khalimsky, Kiselman, Kopperman, Rosenfeld, Slapal. The papers you get are likely to be along the lines of what you are looking for, I hope.
In particular see several papers in a Special issue on digital topology, 
Topology and its Applications 
http://www.sciencedirect.com/science/article/pii/016686419290013P 
or  a recent paper by J Šlapal, [Jordan Curves in the Digital Plane, 
http://www.emis.de/journals/BMMSS/pdf/acceptedpapers/2011-06-033_R1.pdf 
or an older survey, T. Yung Kong, Ralph Kopperman, Paul R. Meyer, 
A topological approach to digital topology. 
Amer. Math. Monthly 98 (1991), no. 10, 901–917. 
http://www.jstor.org/discover/10.2307/2324147
A: I used to think that Sperner's proof is simple enough, but if you don't like it, maybe it's because what you're really looking for is an algorithm.
I can show that there is no fast algorithm for your problem, at least not something faster than for Sperner's lemma.
This is because your question, if defined appropriately, becomes PPAD-complete.
This means that if there was a fast algorithm for your problem, then one could convert it into a fast algorithm for finding a solution to a large class of other problems, like finding a Brouwer like fixed point or a a Nash equilibrium (if defined appropriately).
I really don't think that you are interested in the details, the proof is quite straightforward and similar to showing the PPAD-completeness of 2D-SPERNER or 2D-TUCKER.
In case you are, here is a list of papers: http://www.cs.princeton.edu/~kintali/ppad.html
If you don't like complexity theory, then here is the draft of a paper from whose proofs it follows that you can find a common square in O(n) steps, where one step is to ask of any one square whether it belongs to $C_1$ or $C_2$: http://arxiv.org/abs/1211.3000
