The following puzzle can be solved by the same technique.  A *mountain range* is a piecewise linear function $f$ defined on a closed interval $[a,b]$ which satisfies $f(a)=f(b)=0$, and $f(c) > 0$ for all $c \in (a,b)$.  There is hiker $A$ at the point $(a,0)$ and a hiker $B$ at the point $(b,0)$.  The two hikers begin moving along the mountain range, the only restriction being that they must always be at the same elevation.  Prove that $A$ and $B$ can always meet at some point of the mountain range.  

On a slightly more serious note, I vaguely remember that the existence of Nash equilibria can be proved by a parity argument (via Sperner's lemma).  

As requested by Fedor Petrov in the comments, here is a proof for the mountain range puzzle.  Draw a horizontal line through each "valley" or "peak" of the mountain range.  Let $P$ be the set of points of the mountain range that intersect these horizontal lines together with the points $(a,0)$ and $(b,0)$.  Let $V$ be the set of pairs of points in $P$ which have the same elevation ($y$-coordinate).  We interpret each $(p,q) \in V$ to mean that hiker $A$ is at $p$ and hiker $B$ is at $q$.  Make a graph $G$ with vertex set $V$ where $(p_1,q_1)$ and $(p_2,q_2)$ are adjacent if the hikers can move from position $(p_1, q_1)$ to position $(p_2,q_2)$ in "one step".  Now, it is easy to check that every vertex of $G$ has degree $0, 2$, or $4$, except for $u:=((a,0), (b,0))$ and $v:=((b,0), (a,0))$, which both have degree $1$.  By the Handshaking lemma, there is a path from $u$ to $v$ in $G$. Hence, the hikers can reach each other, since there is a sequence of moves that interchanges their starting positions.