Trovando bound minori di quanto richiesto

[lucaboss98]

Sono date $n$ rette nel piano a tre a tre non concorrenti e a due a due non parallele. Albarbaro ha una matita arancione fluoresciente e decide di colorare un po' di rette di arancione fluoresciente. Vi è solo un problema: i genitori di Albarbaro, Alromano e Algreca credo in una strana religione, di derivazione ignota a noi mortali: vi sono tre dei principali : Isideus , Osirideus e Setheus. I primi due sono buoni e cercano di sconfiggere infinite volte il dio cattivo , ma purtroppo, per qualche rito satanico misterioso, non possono esistere sulla terra poligoni chiusi in cui tutti i lati sono arancioni fluorescienti altrimenti Setheus prenderà possesso dell'anima di tutti i terrestri e sconfiggerà una volta per tutte Isideus e Osirideus. Quindi è tassativamente proibito ad Albarbaro di colorare tutti i lati di un poligono chiuso di arancione fluoresciente.
Albarbaro peró adora colorare e vuole colorare quante più rette puó.
Dimostrare che Albarbaro puó colorare almeno $\sqrt{n} \cdot (\frac{2}{3})^{\frac{3}{2}}$ rette senza che Setheus vinca.
BONUS : farlo senza trovare bound migliori.

[bern1-16-4-13]

Visto che nessuno posta qualcosa metto la mia soluzione (che tuttavia lascia irrisolto il bonus).
Ogni volta che parlerò di poligono ovviamente intenderò un'area di piano chiusa che non ha nessun punto interno (cioè non sul contorno) in comune con l'insieme delle $n$ rette.

Testo nascosto:

1. Fino a prova contraria ogni poligono ha un numero di lati maggiore o uguale a $3$
2. diciamo che un poligono è pericoloso in un certo istante se in quell'istante ha tutti i lati eccetto uno evidenziati.
3. Se a un certo istante Albarbaro ha colorato $j$ rette, allora il numero di poligoni pericolosi in quell'istante non supera $2j\left(j-1\right)$.
   Dimostrazione: consideriamo la funzione: $\{punti\ di\ intersezione\ di\ rette\ evidenziate\}\longrightarrow\{poligoni\ pericolosi\}^4$ che associa a ogni punto di intersezione di due rette evidenziate, i $4$ poligoni che hanno tale punto di intersezione come vertice. La funzione è chiaramente tale da includere almeno una volta nelle quaterne di arrivo ogni poligono pericoloso, quindi è evidente che il numero di poligoni pericolosi non supererà $4$ volte il numero di punti di intersezione di rette evidenziate, quindi non supererà $4\binom{j}{2}=2j\left(j-1\right)$.
4. Se a un certo istante sono state colorate $a$ rette e ci sono $b$ poligoni pericolosi, allora se $n>a+b$ Albarbaro potrà sempre colorare almeno un'altra retta senza far vincere Sitheus.
   Dimostrazione: se Albarbaro non può colorare una certa retta in un certo istante, vuol dire che quella retta va a completare di evidenziare un poligono pericoloso di quell'istante. Quindi se a un certo istante Albarbaro non può più colorare, questo significa che la funzione: $\{poligoni pericolosi\}\longrightarrow\{rette\ non\ colorate\}$ è suriettiva. Ma questo vuol dire che le rette non colorate sono al più tante quante i poligoni pericolosi (di quell'istante), quindi $n-a\le b$. Quindi se $n>a+b$ allora è sicuramente possibile colorare almeno un'altra retta.
5. Adesso supponiamo che non sia effettivamente più possibile colorare rette. Allora $n\le a+b$. Ma per quanto visto prima $b\le 2a\left(a-1\right)$, quindi $n\le a+2a\left(a-1\right)$. Risolvendo nei positivi (e supponendo $n>1$) si ha che $$a\ge \frac{1+2\sqrt{2n-1}}{4}\ge\frac{2\sqrt{2n}}{4}=\frac{\sqrt{2}}{2}\cdot\sqrt{n}.$$Ma $\frac{\sqrt{2}}{2}>\left(\frac{2}{3}\right)^{\frac{3}{2}}$, e questo conclude la nostra dimostrazione.

Morale della favola: quanto sono belle le stime stralarghe!

[lucaboss98]

Ok ci sta, il tuo bound in gara valeva 4 punti (il mio 2), ora il BONUS!!

[bern1-16-4-13]

Era richiesto un bound migliore?

[lucaboss98]

Era richiesto un bound migliore?

Era richiesto $1$ per $n$ sufficientemente grande.

[bern1-16-4-13]

Ti ricordi anche qual era?

[lucaboss98]

Ti ricordi anche qual era?

Qual era cosa?

[bern1-16-4-13]

Come cosa?
Il bound che era richiesto!

[lucaboss98]

Come cosa?
Il bound che era richiesto!

$1$, cioè $\sqrt{n}$ ! Pensavo di averlo detto prima (cioè pensavo si capisse, sorry)

[bern1-16-4-13]

Era richiesto $1$ per $n$ sufficientemente grande.

ahahah, infatti io dicevo: certo che poteva scriverlo anche in lettere quell'uno! (l'avevo interpretato "(ne) era richiesto uno per $n$ sufficientemente grande")