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

  • $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Apr 21 '14 at 15:11
  • $\begingroup$ 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? $\endgroup$ – Calvin Lin Apr 21 '14 at 23:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Leen Droogendijk Apr 22 '14 at 5:52
  • $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.