Προβλήματα Μαθηματικών

Απρίλιος 29, 2008

Ευθείες και Σημεία

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Themis Mitsis @ 4:23 μμ

Στο επίπεδο δίνονται n ευθείες \ell_i, 1\leq i\leq n και n σημεία p_j, 1\leq j\leq n. Βρείτε ένα άνω φράγμα για τον πληθάριθμο του συνόλου

\{(i,j):p_j\in \ell_i\}.

H εντελώς τετριμμένη απάντηση είναι, βέβαια, n^2. Προσπαθήστε να μειώσετε τον εκθέτη 2.

Advertisements

3 Σχόλια »

  1. A=\{(i,j):p_j\in \ell_i\}.
    B=\{(i,j_1,j_2):p_{j_1},p_{j_2}\in \ell_i\}.
    Βρείτε ένα άνω φράγμα για τον πληθάριθμο του B (από δυο σημεία περνάει μια μόνο ευθεία). Τώρα, πώς σχετίζονται τα A και B;

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Μαΐου 1, 2008 @ 1:32 μμ

  2. Ένα άνω φράγμα για το {|B|} είναι το \frac{n(n-1)}{2}.
    Αν τώρα ονομάσουμε k_i το πλήθος των j για τα οποία το (i,j) ανήκει στο A ,τότε είναι \displaystyle{|A|=\sum_{i=1}^{n}k_i} και
    {\displaystyle{{|B|} = \sum_{i=1}^{n}\frac{k_i(k_i-1)}{2}}}.
    Άρα \displaystyle{\sum_{i=1}^{n}k_i^2 \le n(n-1)+\sum_{i=1}^{n}k_i} και από την ανισότητα \displaystyle{\frac{\sum_{i=1}^{n}k_i}{n} \le \sqrt{\frac{\sum_{i=1}^{n}k_i^2}{n}}} προκύπτει \frac{|A|}{n} \le \sqrt{\frac{n(n-1)+|A|}{n}}, από το οποίο βγαίνει ότι |A| \le \frac{n(\sqrt{4n-3}+1)}{2}.

    Μου αρέσει!

    Σχόλιο από steliosdes — Μαΐου 1, 2008 @ 6:08 μμ

  3. Πάρα πολύ ωραία. n^{3/2} είναι ακριβώς η τάξη μεγέθους που είχα στο νου. Η λύση που έδωσες είναι στην πραγματικότητα μια γενικότερη μέθοδος για να αντιμετωπίσει κανείς συνδυαστικά προβλήματα τέτοιου είδους. Μια πολύ καλη παραπομπή είναι το βιβλίο «Combinatorial Geometry» των J. Pach και P. Agarwal (1995).
    To 3/2 δεν είναι παρ’ όλα αυτά ο βέλτιστος εκθέτης. Ο βέλτιστος εκθέτης είναι 4/3. Η απόδειξη όμως απέχει ΠΑΡΑ ΠΟΛΥ από το να είναι άσκηση (δες το παραπάνω βιβλίο).

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — Μαΐου 1, 2008 @ 7:37 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: