IR-MO 2009 Problem 8

Sone of vertices of the infinite grid $\mathbb{Z}^{2}$ are missing. Let's take the remainder as a graph. Connect two edges of the graph if they are the same in one component and their other components have a difference equal to one. Call every connected component of this graph a branch. Suppose that for every natural $n$ the number of missing vertices in the $(2n+1)\times(2n+1)$ square centered by the origin is less than $\frac{n}{2}$ . Prove that among the branches of the graph, exactly one has an infinite number of vertices.

Time allowed for this problem was 90 minutes.

Attachments: