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

Σεπτεμβρίου 12, 2009

Συνδέσεις

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 1:23 πμ

points

Στο επίπεδο βρίσκονται N κόκκινα και N πράσινα σημεία, αν τρία μη συνευθειακά. Δείξτε ότι μπορούμε να ταιριάσουμε κάθε κόκκινο με ένα πράσινο σημείο ενώνοντάς τα με ένα ευθύγραμμο τμήμα,με τέτοιο τρόπο ώστε τα N αυτά ευθύγραμμα τμήματα να μην τέμνονται.

Advertisements

5 Σχόλια »

  1. Θα το αποδειξουμε με επαγωγη. Για N=1 απλα ενωνουμε το τα ακρα και δημιουργουμε το μοναδικο ευθυγραμμο τμημα.
    Εστω οτι ισχυει για k=1,2,3,...,N-1. Θα δειξουμε οτι ισχυει για N επιλεγοντας καταλληλα ενα ζευγαρι του
    οποιου το ευθυγραμμο τμημα αν το προεκτεινουμε θα χωρισει το επιπεδο σε δυο ημιεπιπεδα που θα εχουν ισοποσα κοκκινα και
    πρασινα σημεια. Σιγουρα σε καθε ημιεπιπεδο θα εχουμε λιγοτερα απο N σημεια για καθε χρωμα. Οποτε απο το επαγωγικο
    βημα, θα μπορουμε να συνδεσουμε τα σημεια του καθε ημιεπιπεδου με ευθυγραμμα τμηματα τα οποια δεν τεμνονται.

    Μενει να δειξουμε οτι μπορουμε να βρουμε τετοιο ζευγαρι. Πραγματι μπορουμε ως εξης:
    Διαλεγουμε το σημειο που εχει την μικροτερη y-συντεταγμενη, το οποιο θεωρουμε ως την αρχη των (νεων) αξονων και εστω οτι ειναι πρασινο.
    Υπολογιζουμε τις γωνιες των υπολοιπων N-1 πρασινων σημειων και των N κοκκινων σημειων και τις ταξινομουμε.
    Επειδη εχουμε επιλεξει το σημειο με την μικροτερη y-συντεταγμενη οι γωνιες παιρνουν τιμες μεταξυ 0 και π και ειναι
    ολες διαφορετικες αφου δεν μπορουμε να εχουμε τρια συνευθειακα σημεια απο υποθεση. Τελος, επιλεγουμε το κοκκινο σημειο που εχει
    στα δεξια του (κατα συνεπεια και στα αριστερα του) των ιδιο αριθμο πρασινων και κοκκινων σημειων. Παντα μπορουμε να το κανουμε
    αυτο γιατι μπορουμε να «ζευγαρωσουμε» σε καθε πρασινο σημειο ενα κοκκινο και το κοκκινο που περρισευει να ειναι το ζητουμενο.

    Παρατηρηση: Ο λογος που θελουμε τις γωνιες μεταξυ 0 και π ειναι για να αποφυγουμε προβληματα οταν θα προεκτεινουμε το ευθυγραμμο
    τμημα σε ευθεια.

    Μου αρέσει!

    Σχόλιο από yannispantazis — Σεπτεμβρίου 13, 2009 @ 7:53 μμ

  2. Μπορείς να επεξηγήσεις λίγο το παρακάτω γιατί δεν το καταλαβαίνω;


    Τελος, επιλεγουμε το κοκκινο σημειο που εχει
    στα δεξια του (κατα συνεπεια και στα αριστερα του) των ιδιο αριθμο πρασινων και κοκκινων σημειων. Παντα μπορουμε να το κανουμε
    αυτο γιατι μπορουμε να “ζευγαρωσουμε” σε καθε πρασινο σημειο ενα κοκκινο και το κοκκινο που περρισευει να ειναι το ζητουμενο.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 13, 2009 @ 8:00 μμ

  3. Εστω οτι η ταξινομηση μας δινει το παρακατω αποτελεσμα:
    +++—++–+-++-
    οπου + ειναι τα κοκκινα και – τα πρασινα που ειναι ενα λιγοτερο. Τοτε αφαιρουμε ενα ενα τα ζευραγια +- ή -+ (το θετικο
    εξαφανιζει το αρνητικο οπως στη φυσικη). Οποτε η παραπανω διαταξη γινεται διαδοχιχα
    ++ –++–+-++-
    + -++–+-++-
    ++–+-++-
    + -+-++-
    +-++-
    ++-
    +
    Το «μπακουρι» που επιβιωνει ειναι το ζητουμενο σημειο, δλδ, αυτο που χωριζει τα υπολοιπα σημεια σε δυο συνολα που εχουν
    τον ιδιο αριθμο + και -.

    Μου αρέσει!

    Σχόλιο από yannispantazis — Σεπτεμβρίου 14, 2009 @ 10:04 πμ

  4. Πολύ σωστά (και κατασκευαστικά).

    Ιδού κι ένας άλλος τρόπος: απ’ όλα τα ζευγαρώματα πράσινα-κόκκινα επιλέγουμε εκείνο με το λιγότερο συνολικό μήκος.Μπορούν τώρα δύο ευθύγραμμα τμήματα του ταιριάσματος αυτού να τέμνονται;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 14, 2009 @ 10:23 πμ

  5. Οχι. Γιατι αν τεμνονταν θα μπορουσαμε να μειωσουμε το συνολικο μηκος. Πως? Σχηματιζοντας το τετραπλευρο με κορυφες τα ακρα
    των ευθυγραμμων τμηματων που τεμνονται και παιρνοντας σαν ευθυγραμμα τμηματα δυο πλευρες αντι των διαγωνιων. Ομως εχουμε
    διαλεξει το ταιριασμα με το μικροτερο συνολικο μηκος αρα ατοπο.

    Αλγοριθμικα, το να βρουμε το ζευγαρωμα με το ελαχιστο βαρος ειναι ισοδυναμο με το «αναποδο» προβλημα ?αναθεσης? (Assignment problem)

    Μου αρέσει!

    Σχόλιο από yannispantazis — Σεπτεμβρίου 14, 2009 @ 11:31 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

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

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