Cómo se demuestra que hay dos puntos de celosía, distantes 1 entre sí, tales que la longitud del camino en el árbol que los une es al menos $10^{ 2014}$ .

Question

Un árbol es un grafo tal que entre dos vértices cualesquiera, t formado por aristas del grafo. Se da un árbol tal que

1El conjunto de vértices es la red de enteros $Z^2$

2 Si hay una arista entre los vértices $x$ y $y$ entonces la euclidiana entre $x$ y $y$ es como máximo $2014$ .

Demostrar que hay dos puntos de celosía, distancia $1$ a longitud del camino en el árbol que los conecta (es decir, la suma de las longitudes euclidianas de sus aristas) sea al menos $10^{2014}$

Este problema es de la escuela secundaria concurso de matemáticas en 2014 en chin ShangHai, creo que este problema uso Graph theory.Thank mucho

Answer 1

Considere un camino infinito $V_0 \to V_1 \to V_2 \to V_3 \to \ldots$ (en el árbol). Para cada $n$ , dejemos que $B_n$ sea la componente conexa que contiene $V_{n+1}$ después de quitar $V_n$ del árbol, y que $A_n$ sea el complemento de $\{V_n \}\cup B_n$ . La ruta desde cualquier vértice en $A_n$ a cualquier vértice de $B_n$ tiene que pasar por $V_n$ . También, $A_n$ es una sucesión estrictamente creciente de conjuntos, y $B_n$ es una sucesión estrictamente decreciente de conjuntos infinitos.

Sea $A'_n$ sea la frontera de $A_n$ (los vértices que están a una distancia $1$ con $B_n$ ).

Si uno de los $A_n$ es infinito, entonces también lo es $A'_n$ y así $A'_n$ contiene vértices arbitrariamente alejados de $V_n$ ya que cada paso del árbol está acotado.

Aunque cada $A_n$ es finito, ya que $|A_n| \to \infty$ como $n \to \infty$ también tenemos $|A'_n| \to \infty$ (Creo que la región más grande encerrada por la frontera más pequeña tiene forma cuadrada por lo que tienes algo como $|A'_n| \ge C \sqrt {|A_n|}$ ). De ahí se deduce de nuevo que hay algunos caminos arbitrariamente largos desde vértices de $A'_n$ a $V_n$ por lo que existen caminos arbitrariamente largos desde los vértices de $A'_n$ a su vecino en $B_n$ .