Testo nascosto:
Lemma brutto:
consideriamo una generica colorazione accettabile delle $n$ rette e introduciamo la seguente notazione:
-$\mathfrak{A}$ sarà l'insieme di tutti i punti di intersezione di coppie di rette evidenziate
-Numeriamo i poligoni pericolosi della configurazione, e si indichi con $p_i$ il poligono pericoloso $i$-esimo.
-Si indichi con $\vert p_i\vert$ il numero di lati del poligono $p_i$.
-Si indichi con $\overline{p_i}$ la retta relativa al lato di $p_i$ non evidenziato.
-Dato $A\in\mathfrak{A}$, e numerati tutti i possibili insiemi di poligoni pericolosi con un vertice in $A$, si indichi con $\mathfrak{B}_{A,i}$ l'$i$-esimo tra questi insiemi (con ovvi vincoli su $i$). Per comodità $\mathfrak{B}_{A,1}$ sarà l'insieme di tutti i poligoni pericolosi di vertice $A$.
Allora$$\forall \left(A,i\right)\in\mathfrak{A}\times\mathbb{Z}^+:\hspace{1.3cm}\overline{p_j}\not\equiv\overline{p_k}\ \ \forall\ \ p_j,p_k\in\mathfrak{B}_{A,i},\ j\ne k$$$$\sum_{p_l\in\mathfrak{B}_{A,i}}\frac{1}{\vert p_l\vert -2}\le 2.$$
Dimostrazione.
Innanzitutto si nota facilmente che tra i $4$ poligoni di vertice $A$ non ci possono essere più di $2$ triangoli.
Supponendo per assurdo falsa la tesi è ovviamente necessario (ma non sufficiente) che $$\sum_{p_l\in\mathfrak{B}_{A,1}}\frac{1}{\vert p_l\vert -2}>2$$
Approfittiamo di questa cosa per poter fare delle semplici stime arrivando a dire che un eventuale controesempio della tesi deve essere classificabile per forza in uno di questi sotto casi:
1) In $\mathfrak{B}_{A,1}$ ci sono due triangoli e almeno un altro poligono.
2) In $\mathfrak{B}_{A,1}$ c'è solo un triangolo, e altri tre poligoni.
1) Questo caso è da escludere, poiché la retta relativa al lato non evidenziato di ciascun triangolo deve per forza essere anche la retta relativa a un lato di ciascuno degli altri due poligoni di vertice $A$. Quindi questi ultimi hanno almeno due lati non evidenziati, quindi non possono appartenere a $\mathfrak{B}_{A,1}$.
2) Anche questo caso è da escludere. Infatti tutti i poligoni di vertice $A$ devono essere pericolosi. Inoltre, poiché si vede facilmente che i $2$ poligoni (che per comodità chiameremo $p_1,p_2$) di vertice $A$ adiacienti (con un lato in comune) al triangolo dovranno per forza essere tali che $\overline{p_1}\equiv\overline{p_2}$, allora non possono entrambi stare in un generico insieme $\mathfrak{B}_{A,i}$ che verifichi il vincolo $\overline{p_j}\not\equiv\overline{p_k}\ \ \forall\ \ p_j,p_k\in\mathfrak{B}_{A,i},\ j\ne k$. Questo porta facilmente a un assurdo poiché si ottiene che ogni $\mathfrak{B}_{A,i}$ che rispetti il vincolo avrà cardinalità al più $3$ e, potendo inoltre contenere solo un triangolo, sarà tale che $$\sum_{p_l\in\mathfrak{B}_{A,i}}\frac{1}{\vert p_l\vert -2}\le 1+\frac{1}{2}+\frac{1}{2}=2.$$
Il lemma brutt(issim)o è dimostrato.
Utilizziamo la notazione $c=numero\ di\ rette\ non\ evidenziate$, $b=numero\ di\ poligoni\ pericolosi$, $a=numero\ di\ rette\ evidentiate$.
Supponiamo di trovarci in una situazione dove Albarbaro non può più colorare.
Innanzitutto riciclando il ragionamento della dimostrazione precedente si vede che $c\le b$.
\ begin{euristica}Inoltre si vede abbastanza bene che $$b=\sum_{A\in\mathfrak{A}}\sum_{p_l\in\mathfrak{B}_{A,1}}\frac{1}{\vert p_l\vert -2}.$$Tuttavia noi stiamo cercando di dimostrare qualcosa di più forte di $c\le b$: stiamo cercando di sfruttare (anche se in modo per niente ottimale, per cui penso che esistano bound abbastanza migliori di $\sqrt{n}$) il fatto che una retta non evidenziata può costituire il lato non evidenziato di più di un poligono pericoloso.\ end{euristica}
Associamo a ogni retta non evidenziata uno (ne esisterà sempre almeno uno sennò Albarbaro potrebbe continuare a colorare) e uno solo dei poligoni pericolosi di cui costituisce il lato non evidenziato. Ogni poligono pericoloso è associato a $0$ o una delle rette non evidenziate, quindi chiamando $\mathfrak{P}$ l'insieme dei poligoni pericolosi associati a una delle rette non evidenziate si ha che $$c=\sum_{p_i\in\mathfrak{P}}1=\sum_{p_i\in\mathfrak{P}}\left(\vert p_i\vert-2\right)\cdot\frac{1}{\vert p_i\vert-2}$$ (ho fatto questo passaggio (piuttosto inutile) perché fra poco il termine $i$-esimo della sommatoria verrà "distribuito" sui $\vert p_i\vert-2$ vertici $\in\mathfrak{A}$ del poligono $p_i$).
Adesso, per ogni vertice $A\in\mathfrak{A}$, definiamo $f\left(A\right)$ in modo che $p_i\in\mathfrak{B}_{A,f\left(A\right)}\Longleftrightarrow A\in p_i, p_i\in\mathfrak{P}$. Ovviamente non c'è rischio di VIOLA(ORO ALLE IMO)re il vincolo $$\overline{p_j}\not\equiv\overline{p_k}\ \ \forall\ \ p_j,p_k\in\mathfrak{B}_{A,f\left(A\right)},\ j\ne k.$$ Quindi
$$a\left(a-1\right)\ge\sum_{A\in\mathfrak{A}}\sum_{p_l\in\mathfrak{B}_{A,f\left(A\right)}}\frac{1}{\vert p_l\vert -2}=c$$
dove il $\ge$ deriva dal lemma (che abbiamo potuto applicare, poiché il vincolo era rispettato), mentre l'uguale lo abbiamo ottenuto per costruzione.
A questo punto, poiché $a+c=n$, abbiamo che $a+a\left(a-1\right)=a^2\ge n$, quindi $a\ge\sqrt{n}\ \ \ \forall n$.
Non abbiamo nemmeno usato che Albarbaro può colorare intelligentemente, infatti per quanto fatto vedere nella dimostrazione, comunque colori non può incartarsi prima di aver colorato $\sqrt{n}$ rette.
consideriamo una generica colorazione accettabile delle $n$ rette e introduciamo la seguente notazione:
-$\mathfrak{A}$ sarà l'insieme di tutti i punti di intersezione di coppie di rette evidenziate
-Numeriamo i poligoni pericolosi della configurazione, e si indichi con $p_i$ il poligono pericoloso $i$-esimo.
-Si indichi con $\vert p_i\vert$ il numero di lati del poligono $p_i$.
-Si indichi con $\overline{p_i}$ la retta relativa al lato di $p_i$ non evidenziato.
-Dato $A\in\mathfrak{A}$, e numerati tutti i possibili insiemi di poligoni pericolosi con un vertice in $A$, si indichi con $\mathfrak{B}_{A,i}$ l'$i$-esimo tra questi insiemi (con ovvi vincoli su $i$). Per comodità $\mathfrak{B}_{A,1}$ sarà l'insieme di tutti i poligoni pericolosi di vertice $A$.
Allora$$\forall \left(A,i\right)\in\mathfrak{A}\times\mathbb{Z}^+:\hspace{1.3cm}\overline{p_j}\not\equiv\overline{p_k}\ \ \forall\ \ p_j,p_k\in\mathfrak{B}_{A,i},\ j\ne k$$$$\sum_{p_l\in\mathfrak{B}_{A,i}}\frac{1}{\vert p_l\vert -2}\le 2.$$
Dimostrazione.
Innanzitutto si nota facilmente che tra i $4$ poligoni di vertice $A$ non ci possono essere più di $2$ triangoli.
Supponendo per assurdo falsa la tesi è ovviamente necessario (ma non sufficiente) che $$\sum_{p_l\in\mathfrak{B}_{A,1}}\frac{1}{\vert p_l\vert -2}>2$$
Approfittiamo di questa cosa per poter fare delle semplici stime arrivando a dire che un eventuale controesempio della tesi deve essere classificabile per forza in uno di questi sotto casi:
1) In $\mathfrak{B}_{A,1}$ ci sono due triangoli e almeno un altro poligono.
2) In $\mathfrak{B}_{A,1}$ c'è solo un triangolo, e altri tre poligoni.
1) Questo caso è da escludere, poiché la retta relativa al lato non evidenziato di ciascun triangolo deve per forza essere anche la retta relativa a un lato di ciascuno degli altri due poligoni di vertice $A$. Quindi questi ultimi hanno almeno due lati non evidenziati, quindi non possono appartenere a $\mathfrak{B}_{A,1}$.
2) Anche questo caso è da escludere. Infatti tutti i poligoni di vertice $A$ devono essere pericolosi. Inoltre, poiché si vede facilmente che i $2$ poligoni (che per comodità chiameremo $p_1,p_2$) di vertice $A$ adiacienti (con un lato in comune) al triangolo dovranno per forza essere tali che $\overline{p_1}\equiv\overline{p_2}$, allora non possono entrambi stare in un generico insieme $\mathfrak{B}_{A,i}$ che verifichi il vincolo $\overline{p_j}\not\equiv\overline{p_k}\ \ \forall\ \ p_j,p_k\in\mathfrak{B}_{A,i},\ j\ne k$. Questo porta facilmente a un assurdo poiché si ottiene che ogni $\mathfrak{B}_{A,i}$ che rispetti il vincolo avrà cardinalità al più $3$ e, potendo inoltre contenere solo un triangolo, sarà tale che $$\sum_{p_l\in\mathfrak{B}_{A,i}}\frac{1}{\vert p_l\vert -2}\le 1+\frac{1}{2}+\frac{1}{2}=2.$$
Il lemma brutt(issim)o è dimostrato.
Utilizziamo la notazione $c=numero\ di\ rette\ non\ evidenziate$, $b=numero\ di\ poligoni\ pericolosi$, $a=numero\ di\ rette\ evidentiate$.
Supponiamo di trovarci in una situazione dove Albarbaro non può più colorare.
Innanzitutto riciclando il ragionamento della dimostrazione precedente si vede che $c\le b$.
\ begin{euristica}Inoltre si vede abbastanza bene che $$b=\sum_{A\in\mathfrak{A}}\sum_{p_l\in\mathfrak{B}_{A,1}}\frac{1}{\vert p_l\vert -2}.$$Tuttavia noi stiamo cercando di dimostrare qualcosa di più forte di $c\le b$: stiamo cercando di sfruttare (anche se in modo per niente ottimale, per cui penso che esistano bound abbastanza migliori di $\sqrt{n}$) il fatto che una retta non evidenziata può costituire il lato non evidenziato di più di un poligono pericoloso.\ end{euristica}
Associamo a ogni retta non evidenziata uno (ne esisterà sempre almeno uno sennò Albarbaro potrebbe continuare a colorare) e uno solo dei poligoni pericolosi di cui costituisce il lato non evidenziato. Ogni poligono pericoloso è associato a $0$ o una delle rette non evidenziate, quindi chiamando $\mathfrak{P}$ l'insieme dei poligoni pericolosi associati a una delle rette non evidenziate si ha che $$c=\sum_{p_i\in\mathfrak{P}}1=\sum_{p_i\in\mathfrak{P}}\left(\vert p_i\vert-2\right)\cdot\frac{1}{\vert p_i\vert-2}$$ (ho fatto questo passaggio (piuttosto inutile) perché fra poco il termine $i$-esimo della sommatoria verrà "distribuito" sui $\vert p_i\vert-2$ vertici $\in\mathfrak{A}$ del poligono $p_i$).
Adesso, per ogni vertice $A\in\mathfrak{A}$, definiamo $f\left(A\right)$ in modo che $p_i\in\mathfrak{B}_{A,f\left(A\right)}\Longleftrightarrow A\in p_i, p_i\in\mathfrak{P}$. Ovviamente non c'è rischio di VIOLA(ORO ALLE IMO)re il vincolo $$\overline{p_j}\not\equiv\overline{p_k}\ \ \forall\ \ p_j,p_k\in\mathfrak{B}_{A,f\left(A\right)},\ j\ne k.$$ Quindi
$$a\left(a-1\right)\ge\sum_{A\in\mathfrak{A}}\sum_{p_l\in\mathfrak{B}_{A,f\left(A\right)}}\frac{1}{\vert p_l\vert -2}=c$$
dove il $\ge$ deriva dal lemma (che abbiamo potuto applicare, poiché il vincolo era rispettato), mentre l'uguale lo abbiamo ottenuto per costruzione.
A questo punto, poiché $a+c=n$, abbiamo che $a+a\left(a-1\right)=a^2\ge n$, quindi $a\ge\sqrt{n}\ \ \ \forall n$.
Non abbiamo nemmeno usato che Albarbaro può colorare intelligentemente, infatti per quanto fatto vedere nella dimostrazione, comunque colori non può incartarsi prima di aver colorato $\sqrt{n}$ rette.