Fie \( D^2 \) discul inchis de raza unitate din \( \mathbb{R}^2 \) si \( n \ge 2 \) un numar intreg fixat.
Determinati numarul maxim de segmente de lungime supraunitara avand capetele in \( A_1, ..., A_n \), cand \( \{A_j\} \) parcurge seturile de puncte, nu neaparat distincte, apartinand lui \( D^2 \).
[ DMO 2008, Problema 4 ]
Geometrie combinatorica non-standard
Moderators: Laurian Filip, Filip Chindea, maky, Cosmin Pohoata, Virgil Nicula
-
Filip Chindea
- Newton
- Posts: 324
- Joined: Thu Sep 27, 2007 9:01 pm
- Location: Bucharest
Geometrie combinatorica non-standard
Life is complex: it has real and imaginary components.
-
Filip Chindea
- Newton
- Posts: 324
- Joined: Thu Sep 27, 2007 9:01 pm
- Location: Bucharest
-
maxim bogdan
- Thales
- Posts: 106
- Joined: Tue Aug 19, 2008 1:56 pm
- Location: Botosani
Solutie!
Evident daca determinam numarul minim de segmente de lungime \( \leq 1 \) problema este rezolvata.
Se demonstreaza usor faptul ca din oricare 6 puncte exista cel putin 2 astfel incat lungimea segmentului determinat de acestea este \( \leq 1\ (*) \)(se foloseste argumentul unghiului la centru!).
Acum sa transpunem problema in limbaj de grafuri.
Fie \( G=(V;E) \), \( |G|=n \). Punem muchie intre varfurile \( i \) si \( j \) daca \( A_{i}A_{j}\leq 1. \)
Din relatia \( (*) \) rezulta ca \( \alpha(G)\leq 5 \) (partea independenta - nr. maxim de vf. fara muchie intre ele dintr-un graf).
Daca ne uitam la graful complementar lui \( G \) avem ca \( \omega(\bar{G})\leq 5 \) (indicele ciclomatic). Deci \( G \) nu contine un \( K_{6}. \)
Din Teorema lui Turan rezulta ca:
\( |\bar{E}|\leq\frac{6-2}{6-1}\cdot\frac{n^2}{2}=\frac{2}{5}\cdot n^2 \).
De aici numarul cerut este \( \lfloor\frac{2}{5}\cdot n^2 \rfloor. \)
Observatie! Revenim in demonstratie la \( 5\geq\alpha(G). \)
Sa enuntam Teorema Caro-Wei:
Fie \( G=(V;E) \) un graf si \( \alpha(G) \) partea independenta a acestuia. Atunci are loc inegalitatea:
\( \alpha(G)\geq\sum_{v\in V}\frac{1}{d(v)+1}. \)
De aici revenind la problema rezulta:
\( 5\geq\alpha(G)\geq\sum_{v\in V}\frac{1}{d(v)+1}\geq n\cdot\frac{1}{\frac{\sum_{v\in V}d(v)}{n}+1}=\frac{n^2}{2|E|+n}, \) unde am aplicat Inegalitatea lui Jensen pentru functia convexa \( f(x)=\frac{1}{x+1}. \)
\( \Longrightarrow |E|\geq\frac{n(n-5)}{10}\Longrightarrow |\bar{E}|\leq (^n _2)-\frac{n(n-5)}{10}=\frac{2}{5}\cdot n^2. \)
Se demonstreaza usor faptul ca din oricare 6 puncte exista cel putin 2 astfel incat lungimea segmentului determinat de acestea este \( \leq 1\ (*) \)(se foloseste argumentul unghiului la centru!).
Acum sa transpunem problema in limbaj de grafuri.
Fie \( G=(V;E) \), \( |G|=n \). Punem muchie intre varfurile \( i \) si \( j \) daca \( A_{i}A_{j}\leq 1. \)
Din relatia \( (*) \) rezulta ca \( \alpha(G)\leq 5 \) (partea independenta - nr. maxim de vf. fara muchie intre ele dintr-un graf).
Daca ne uitam la graful complementar lui \( G \) avem ca \( \omega(\bar{G})\leq 5 \) (indicele ciclomatic). Deci \( G \) nu contine un \( K_{6}. \)
Din Teorema lui Turan rezulta ca:
\( |\bar{E}|\leq\frac{6-2}{6-1}\cdot\frac{n^2}{2}=\frac{2}{5}\cdot n^2 \).
De aici numarul cerut este \( \lfloor\frac{2}{5}\cdot n^2 \rfloor. \)
Observatie! Revenim in demonstratie la \( 5\geq\alpha(G). \)
Sa enuntam Teorema Caro-Wei:
Fie \( G=(V;E) \) un graf si \( \alpha(G) \) partea independenta a acestuia. Atunci are loc inegalitatea:
\( \alpha(G)\geq\sum_{v\in V}\frac{1}{d(v)+1}. \)
De aici revenind la problema rezulta:
\( 5\geq\alpha(G)\geq\sum_{v\in V}\frac{1}{d(v)+1}\geq n\cdot\frac{1}{\frac{\sum_{v\in V}d(v)}{n}+1}=\frac{n^2}{2|E|+n}, \) unde am aplicat Inegalitatea lui Jensen pentru functia convexa \( f(x)=\frac{1}{x+1}. \)
\( \Longrightarrow |E|\geq\frac{n(n-5)}{10}\Longrightarrow |\bar{E}|\leq (^n _2)-\frac{n(n-5)}{10}=\frac{2}{5}\cdot n^2. \)
Feuerbach
-
maxim bogdan
- Thales
- Posts: 106
- Joined: Tue Aug 19, 2008 1:56 pm
- Location: Botosani
La pagina 6 e enuntata. Demonstratie nu am gasit (teorema e recenta)!
www.cs.rhul.ac.uk/~gutin/paperstsp/ch5sec2.ps
www.cs.rhul.ac.uk/~gutin/paperstsp/ch5sec2.ps
Feuerbach
Eu am intalnit teorema folosita de Bogdan sub numele de Teorema lui Turan (e de fapt unul din multele rezultatele ale lui Turan, folosita pentru a demonstra celebra teorema care ii poarta numele).
Ea apare la pagina 248 in "Additive Combinatorics" de Terence Tao si Van Vu, de la Cambridge University Press (aparuta in 2006), dar si la pagina 209 in "Proofs from the Book" de M. Aigner si G. Ziegler, in capitolul "Turan's Graph Theorem". In ambele surse este demonstrata folosind metoda probabilistica.
Ea apare la pagina 248 in "Additive Combinatorics" de Terence Tao si Van Vu, de la Cambridge University Press (aparuta in 2006), dar si la pagina 209 in "Proofs from the Book" de M. Aigner si G. Ziegler, in capitolul "Turan's Graph Theorem". In ambele surse este demonstrata folosind metoda probabilistica.