Problem

Source: Iran 3rd round 2009 - final exam problem 8

Tags: combinatorics unsolved, combinatorics



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: