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

Νοέμβριος 27, 2010

Πόσες διαφορετικές αποστάσεις;

Filed under: Άλυτα Προβλήματα — Mihalis Kolountzakis @ 2:00 μμ

Έστω E ένα σύνολο από N σημεία στο επίπεδο και D(E) το σύνολο των αποστάσεων που αυτά ορίζουν:

D(E) = \{ |x-y|:\ x, y \in E\}

όπου |(u_1, u_2)|=\sqrt{u_1^2+u_2^2} παριστάνει το Ευκλείδιο μέτρο ενός διανύσματος.

Δείξτε ότι υπάρχει μια σταθερά C>0 (που δεν εξαρτάται από το N δηλαδή) ώστε να ισχύει

|D(E)| \ge C \sqrt{N}.

(Με |\cdot| συμβολίζουμε το μέγεθος ενός συνόλου.)

Advertisements

6 Σχόλια »

  1. […] συνδεδεμένο με το προηγούμενο πρόβλημα είναι το εξής: Δείξτε ότι το πλήθος των ζευγαριών […]

    Μου αρέσει!

    Πίνγκμπακ από Πόσες μοναδιαίες αποστάσεις; « Προβλήματα Μαθηματικών — Δεκέμβριος 1, 2010 @ 9:30 μμ

  2. Πως ορίζεται το μέγεθος ενός συνόλου?

    Μου αρέσει!

    Σχόλιο από Christian — Δεκέμβριος 2, 2010 @ 11:48 μμ

  3. Christian: Το μέγεθος ενός συνόλου είναι το πόσα στοιχεία έχει.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Δεκέμβριος 2, 2010 @ 11:49 μμ

  4. Μάλλον κάτι δε πάει καλά με το παρακάτω επιχείρημα.
    Για παράδειγμα για Ν=4 δεν είναι σωστό αλλά θα μπορούσα τις περιπτώσεις
    για μικρά Ν να τις μελετήσω χώρια και να υποθέσω πως, π.χ, Ν > 10 ή και μεγαλύτερο.

    Έστω τα Ν σημεία του επιπέδου. Έστω u = (u_1,u_2) ένα από τα σημεία για τα οποία
    η τεταγμένη u_2 είναι μέγιστη, το οποίο μπορούμε να υποθέσουμε πως είναι μοναδικο.
    Αν δεν είναι, στρέφουμε κατάλληλα τους άξονες.
    Ενώνουμε το u με τα υπόλοιπα Ν-1 σημεία u_i, i=1,2,\ldots , N-1
    και κοιτάμε τα ημικύκλια που σχηματίζονται με κέντρο το u και ακτίνες uu_i , i=1,2,\ldots , N-1 .
    Έστω \Delta το πλήθος των διαφορετικών αποστάσεων, r το πλήθος των
    διαφορετικών ημικυκλίων, a_i , i=1,2\ldots , r το πλήθος των σημείων που ανήκουν στο ημικύκλιο i.
    Παρατηρήστε ότι τα a_i σημεία του ημικυκλίου i δημιουργούν τουλάχιστον a_i -1 διαφορετικές αποστάσεις.
    Αν x_1 , x_2, \ldots x_{a_i} είναι τα σημεια του ημικυκλίου, οι αποστάσεις x_1x_2 , x_1x_3 , \ldots x_1x_{a_i}
    είναι διαφορετικές.
    Συνεπώς το πλήθος των διαφορετικών αποστάσεων είναι τουλάχιστον
    r + (a_1 - 1) + (a_2 - 1) + \cdots (a_r - 1) = \sum a_i = N-1 .

    Μου αρέσει!

    Σχόλιο από henk&christos — Ιανουαρίου 30, 2011 @ 8:49 μμ

  5. Με συγχωρείτε. Βιάστηκα να γράψω το σχόλιο.
    Οι διαφορετικές αποστάσεις που παίρνουμε από τα r ημικύκλια
    δεν είναι κατ’ανάγκη διαφορετικές των αποστάσεων που δημιουργούνται απο τα σημεία των ημικυκλίων.

    Μου αρέσει!

    Σχόλιο από henk&christos — Ιανουαρίου 30, 2011 @ 9:28 μμ

  6. Ναι, οι αποστάσεις που δημιουργούν μεταξύ τους τα σημεία ενός ημικυκλίου μπορούν να είναι οι ίδιες με αυτές ενός άλλου ημικυκλίου, άρα δε μπορείς να τις προσθέσεις.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιανουαρίου 31, 2011 @ 11:57 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Blog στο WordPress.com.

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