# How prove there are two lattice points, distance 1 apart, such that the length of the path in the tree which connects themis at least $10^{ 2014}$ .

A tree is a graph such that between any two vertices, there is a unique path made up of edges of the graph. A tree is given such that

1：The set of vertices is the integer lattice $Z^2$

2 :If there is an edge between vertices $x$ and $y$ then the Euclidean distance between $x$ and $y$ is at most $2014$.

Prove that ：there are two lattice points, distance $1$ apart, such that the length of the path in the tree which connects them (i.e. the sum of the Euclidean lengths of its edges) is at least $10^{2014}$

This problem is from High school math contest in 2014 in chin ShangHai, I think this problem use Graph theory.Thank you very much

• It's really unclear what 'tree' you are talking about here. By 2, any edges that are distance $1$ apart are joined by an edge, so the smallest such path is always $1$. – Thomas Andrews Apr 21 '14 at 15:11
• Consider the graph where we draw the x-axis, and every line $x=n$. Doesn't this satisfy your condition 2, but not the statement that you want to show? – Calvin Lin Apr 21 '14 at 23:27
• Very nice problem. Thomas: 2 only states that there can be an edge between vertices that are 1 apart. @Calvin: in your example the distance between $(n,10^{2014})$ and $(n+1,10^{2014})$ is larger than $10^{2014}$: you need to walk to the $x$-axis first, because that is the only line that connects the vertical lines. – Leen Droogendijk Apr 22 '14 at 5:52
• Yes, I figured that out. I wonder if the statement is true for all lattice trees with bounded edge lengths, there exists an arbitrarily long distance between two points. – Calvin Lin Apr 22 '14 at 13:07

Consider an infinite path $V_0 \to V_1 \to V_2 \to V_3 \to \ldots$ (in the tree). For each $n$, let $B_n$ be the connected component containg $V_{n+1}$ after removing $V_n$ from the tree, and let $A_n$ be the complement of $\{V_n \}\cup B_n$. The path from any vertex in $A_n$ to any vertex in $B_n$ has to go through $V_n$. Also, $A_n$ is a strictly increasing sequence of sets, and $B_n$ is a strictly decreasing sequence of infinite sets.
Let $A'_n$ be the frontier of $A_n$ (those vertices that are at distance $1$ with $B_n$).
If one of the $A_n$ is infinite, then so is $A'_n$, and so $A'_n$ contains vertices arbitrarily far away from $V_n$ since each step in the tree is bounded.
Even if every $A_n$ is finite, since $|A_n| \to \infty$ as $n \to \infty$, we also have $|A'_n| \to \infty$ (I believe the biggest region enclosed by the smallest frontier is square-shaped so you have something like $|A'_n| \ge C \sqrt {|A_n|}$). From there it follows again that there are some arbitrarily long paths from vertices of $A'_n$ to $V_n$, hence some arbitrarily long paths from vertices of $A'_n$ to their neighboor in $B_n$.