OliForum Matematico

Un grafo ad albero infinito è costruito in modo che i suoi vertici siano tutti e soli i punti di $ \mathbb Z ^2 $; inoltre, un lato connette due vertici solo se la loro distanza euclidea è al massimo $ 2011 $. Dimostrare che esistono due punti a distanza $ 1 $ tali che la lunghezza del cammino più breve che li connette è di almeno $ 2011^{2011} $ unità.

Non mi è chiaro il testo.
1) il grafo definito così non è un albero perché contiene cicli, o ho capito male la definizione?
2) Nella seconda frase, distanza=numero di lati del grafo che bisogna percorrere per andare da A a B al minimo, o distanza=distanza euclidea? Stessa domanda per "lunghezza".

fph ha scritto:Non mi è chiaro il testo.
1) il grafo definito così non è un albero perché contiene cicli, o ho capito male la definizione?
2) Nella seconda frase, distanza=numero di lati del grafo che bisogna percorrere per andare da A a B al minimo, o distanza=distanza euclidea? Stessa domanda per "lunghezza".

1) Due vertici possono essere connessi se la loro distanza è minore di quella costante, ma non è detto che lo siano. Possono essere eventualmente connessi solamente se l'aggiunta di un arco tra di essi fa sì che il grafo rimanga un albero.
2) S'intende distanza euclidea. In particolare, la lunghezza di un cammino è la somma delle lunghezze dei lati che lo compongono (dove i vertici sono punti a coordinate intere e i lati sono segmenti che hanno come estremi due di tali punti, soggetti alla restrizione di cui sopra).

Ok, ora va meglio, grazie.

Fisso un vertice A e ne prendo uno B distante euclideamente almeno n, ove n è un numero gigantesco che definirò alla fine. Visto che il grafo è un albero, esso è connesso, per cui esiste un cammino da A a B che è costituito da $k\geq\frac{n}{2011}$ passi. Percorro il cammino fino a metà, ovvero percorro k/2 archi e arrivo a un vertice C (se k è dispari percorro (k-1)/2 archi del cammino da A a B, è la stessa cosa). Il vertice C è collegato con il vertice D, in modo che A, C-D, B siano in questo ordine. Se taglio l'arco C-D il grafo smette di essere un albero e resta diviso in due alberi, ovvero in due componenti connesse: quella dei vertici raggiungibili da C e quella dei vertici raggiungibili da D. Ciascuna componente contiene almeno k/2 vertici (perché i percorsi da A a C e da D a B sono lunghi almeno k/2 vertici). Se ho la garanzia che $\frac{k}{2}> 100^{100^{100}}$ allora senz'altro ogni componente connessa ha almeno un vertice esterno alla circonferenza di centro il punto medio di CD e raggio $2011^{2020}$, perché i punti di $\mathbb{Z}^2$ che cadono dentro questa circonferenza sono pochi rispetto a k/2. Chiamiamo E ed F due punti delle componenti connesse rispettivamente di C e D che si trovino entrambi abbastanza lontani, euclideamente parlando, da C e da D, ovvero fuori dalla circonferenza descritta prima. Allora partendo da E e camminando fuori dalla circonferenza lungo i segmenti di lunghezza 1 che collegano i punti di $ \mathbb{Z}^2 $ si può arrivare ad F, dunque ad un certo punto esistono punti G ed H a distanza 1 ma appartenenti a componenti connesse distinte. Per andare da G ad H con il grafo bisogna prima rientrare nella circonferenza fino circa al suo centro, quindi percorrere l'arco CD e infine riuscire fuori. Questo percorso è lungo almeno $2\cdot 2011^{2011}>2011^{2011}$, dunque avrei concluso.
Dato che $k\geq \frac{n}{2011}$, se prendo $n\geq 2\cdot 2011 \cdot 100^{100^{100}}$ ho k/2 abbastanza grande.