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

Ιανουαρίου 7, 2010

Φωτισμός δωματίου

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 11:39 πμ

Σ’ ένα νέο και μοντέρνο κτήριο μια αίθουσα έχει πολυγωνική κάτοψη (όχι κατ’ ανάγκη κυρτή). Η μοντέρνα αισθητική επιβάλλει τα φώτα να τοποθετηθούν στις γωνίες μόνο τις αίθουσας (κορυφές του πολυγώνου). Δείξτε ότι αν η αίθουσα έχει N γωνίες τότε αρκούν \lfloor N/3 \rfloor φώτα για το φωτισμό της αίθουσας.

Advertisements

11 σχόλια »

  1. Διευκρινιστική ερώτηση: υποθέτω οτι αν είχαμε ένα κυρτό πολύγωνο τότε θα έφτανε μια λάμπα. Σωστά;

    Μου αρέσει!

    Σχόλιο από Charalampos Tsourakakis — Ιανουαρίου 14, 2010 @ 10:09 μμ

  2. Ναι.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιανουαρίου 14, 2010 @ 10:28 μμ

  3. Υπόδειξη:

    Μπορείτε να θεωρήσετε ως δεδομένο ότι οποιοδήποτε πολυγωνικό χωρίο στο επίπεδο μπορεί να τριγωνοποιηθεί. Αυτό σημαίνει ότι μπορείτε να το γράψετε σα μια ένωση τριγώνων, που δεν αλληλοεπικαλύπτονται (εκτός φυσικά από τις πλευρές τους) και των οποίων οι κορυφές είναι κάποιες από τις κορυφές του πολυγωνικού χωρίου.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιανουαρίου 27, 2010 @ 9:06 πμ

  4. Υπόδειξη:

    Σε μια τριγωνοποίηση όπως αυτή που αναφέρεται στο προηγούμενο σχόλιο δείξτε ότι μπορείτε να χρωματίσετε τις κορυφές κόκκινες, πράσινες ή μπλέ με τέτοιο τρόπο ώστε δύο κορυφές που συνδέονται με ακμή να έχουν κατ’ ανάγκη διαφορετικά χρώματα.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Φεβρουαρίου 11, 2010 @ 8:52 μμ

  5. Με επαγωγή ως προς το πλήθος, n , των κορυφών.
    Για n=3 έχουμε ένα τρίγωνο το οποίο μπορεί να χρωματιστεί με 3 χρώματα.
    Υποθέστε ότι ισχύει για κάποιο n και θεωρείστε ένα πολύγωνο με n+1 κορυφές.
    Το πολύγωνο αυτό θα περιέχει μια »μύτη», δηλαδή μία κορυφή που συνδέεται με δύο άλλες κορυφές
    και όλες μαζί σχηματιζουν τρίγωνο που είναι υποσύνολο του πολυγώνου.
    Αφαιρέστε αυτή την κορυφή και χρωματίστε το πολύγωνο με n που προκύπτει με 3 χρώματα
    ώστε κορυφές που συνδέονται να έχουν κατάναγκη διαφορετικά χρώματα.
    Προσθέστε κατοπιν την κορυφή και χρωματίστε τη με το χρώμα που δεν εχει χρησιμοποιηθεί από τις γειτονικές κορυφες.

    Μου αρέσει!

    Σχόλιο από henk&christos — Δεκεμβρίου 27, 2010 @ 9:43 μμ

  6. Τοποθετούμε μία λάμπα σε κάθε κορυφή που έχει το χρώμα που εμφανίζεται τις
    λιγοτερες φορες και το οποίο εμφανίζεται το πολύ \lfloor N/3 \rfloor φορές.

    Μου αρέσει!

    Σχόλιο από henk&christos — Δεκεμβρίου 27, 2010 @ 9:51 μμ

  7. Σωστά.

    Αυτό με την ύπαρξη της «μύτης» (κορυφή του πολυγώνου στην οποία καταλήγουν μόνο δύο ακμές, αυτές προς τις γειτονικές της κορυφές) θέλει όμως κάποια επεξήγηση.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Δεκεμβρίου 31, 2010 @ 10:52 πμ

  8. Το θεώρησα προφανές αλλά ίσως δεν είναι.
    Θα δικαιολογούσα την ύπαρξη της ‘μύτης’ ως εξής:

    Μια τέτοια κορυφή θα αποτελεί ακραίο σημείο
    και κάθε φραγμένο πολυγωνικό χωρίο έχει τουλάχιστον ένα ακραίο σημείο.

    Καλή χρονιά !!

    Μου αρέσει!

    Σχόλιο από henk&christos — Ιανουαρίου 3, 2011 @ 7:43 μμ

  9. Όχι ακριβώς.

    Προφανώς κάθε πολύγωνο έχει κορυφές (εξ ορισμού, τα ακραία σημεία δεν έχουν να κάνουν τίποτε εδώ μια και δε μιλάμε για κυρτό πολύγωνο), αλλά αυτό που θέλουμε είναι μια κορυφή που αν ενώσουμε τις δύο γειτονικές της με ένα ευθύγραμμο τμήμα το τρίγωνο που προκύπτει να περιέχεται στο πολύγωνο. Το να δείξεις αυτό είναι σα να πηγαίνεις να δείξεις (με επαγωγή) την ύπαρξη τριγωνοποίησης, πράγμα που σας υπέδειξα να πάρετε δεδομένο.

    Αν τώρα θεωρήσουμε την ύπαρξη της τριγωνοποίησης δεδομένη τότε αυτό που πρέπει να δείξουμε είναι ότι υπάρχει (για τη συγκεκριμένη τριγωνοποίηση) μια κορυφή του πολυγώνου που συνδέεται μόνο με τις δύο γειτονικές της και όχι με άλλες.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιανουαρίου 3, 2011 @ 7:54 μμ

  10. Σταθεροποιείστε μια τριγωνοποίηση του πολυγώνου.
    Ενδιαφερόμαστε για την ύπαρξη τριγώνου που έχει 2 πλεύρες
    που ανήκουν στο σύνορο του πολυγώνου και μια πλευρά στο εσωτερικό.

    Θεωρώ επίσης ως δεδομένο πως κάθε τριγωνοποίηση αποτελείται από ακριβώς N-2 τρίγωνα.

    Έστω κ ο αριθμός των τριγώνων με 2 πλευρές στο σύνορο και μια στο εσωτερικό,
    λ ο αριθμός των τριγώνων με μία πλευρά στο σύνορο και 2 στο εσωτερικό,
    μ ο αριθμός των τριγώνων με 3 πλευρές στο εσωτερικό.
    Τότε
    κ + λ + μ = Ν-2.
    Επίπλέον κάθε πλευρά του πολυγώνου ανήκει σε ακριβώς ένα τρίγωνο.
    Μετρώντας τις πλευρές του πολυγώνου έχουμε
    2 κ + λ = Ν (Ν σημεία κάνουν Ν πλευρές).
    Αφαιρ’ωντας τις σχέσεις αυτές παίρνουμε
    κ = μ + 2.
    Στη χειρότερη περίπτωση μ = 0
    και άρα κ > 1.

    Μου αρέσει!

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

  11. Πολύ σωστά.

    Και το ότι είναι N-2 τα τρίγωνα βγαίνει πολύ εύκολα με επαγωγή.

    Μου αρέσει!

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


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: