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

Ιουνίου 2, 2013

Πόλεις και μονόδρομοι

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

Image

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

Ας ονομάσουμε Z τον αριθμό των πόλεων στις οποίες δεν καταλήγει κανείς δρόμος και E τον αριθμό των πόλεων στις οποίες καταλήγει άρτιος αριθμός δρόμων (του 0 συμπεριλαμβανομένου). Στο σχήμα παραπάνω Z=2 και E=4.

Δείξτε ότι 2Z \ge E.

Προτάθηκε από το Χρήστο Πελέκη.

Advertisements

11 Σχόλια »

  1. Φανταζόμαστε το σύνολο των πόλεων ως το Α={1,2,…, N} και κάθε μονόδρομο τον παριστάνουμε με ένα διατεταγμένο ζεύγος στοιχείων του Α, π.χ. τον μονόδρομο από το 1 στο 2 τον αντιστοιχούμε στο (1,2). Άρα η επιλογή των Ν μονόδρομων αντιστοιχεί σε μια ακολουθία Ν διατεταγμένων ζευγών. Έστω Χ:Α->Α η απεικόνιση που αντιστοιχεί σε κάθε n το δεύτερο στοιχείο του n-οστου ζεύγους. Έστω, επίσης Ε_0 το σύνολο των nεΑ με Χ^(-1)(n) έχει τουλάχιστον 2 στοιχεία, Ζ_0 το σύνολο των nεΑ με Χ^(-1)(n) είναι κενό και Κ_0 το σύνολο των nεΑ με Χ^(-1)(n) να έχει ακριβώς ένα στοιχείο. Προφανώς, ΙΕ_0Ι=Ε και ΙΖ_0Ι=Ζ. Άρα,
    Ν=ΙΑΙ=ΙΧ^(-1)(Ε_0)Ι +ΙΧ^(-1)(Ζ_0)Ι+ΙΧ^(-1)(Κ_0)Ι>=2Ε+ΙΚ_0Ι=
    2Ε+Ν-Ζ-Ε=Ν+Ε-Ζ άρα Ζ>=Ε.

    Βασίλης Αιμονιώτης

    Μου αρέσει!

    Σχόλιο από Βασιλης Αιμονιωτης — Ιουνίου 11, 2013 @ 11:31 πμ

  2. Όπως έχεις ορίσει το σύνολο E_0 αυτό είναι το σύνολο εκείνων των πόλεων στις οποίες καταλήγουν τουλάχιστον δύο δρόμοι, αν καταλαβαίνω σωστά αυτά που γράφεις.

    Γιατί ισχύει |E_0|=|E|;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 12, 2013 @ 12:04 πμ

  3. Ναι, διότι για την πόλη n, υπάρχουν δύο δρόμοι που καταλήγουν σ’ αυτήν αν και μόνο αν εμφανίζεται στην ακολουθία Χ δυο φορές το n ή ισοδύναμα το Χ^(-1)(n) έχει τουλάχιστον 2 στοιχεία. Ομοίως, το Ζ_0 αντιστοιχεί στις πόλεις που δεν καταλήγει κανένας μονόδρομος.

    Μου αρέσει!

    Σχόλιο από Βασιλης Αιμονιωτης — Ιουνίου 12, 2013 @ 12:25 πμ

  4. Αλλά το E δεν είναι οι πόλεις με τουλάχιστον δύο δρόμους αλλά με άρτιο αριθμό δρόμων να καταλήγουν σε αυτές.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 12, 2013 @ 12:31 πμ

  5. Έχετε δίκιο, λάθος μου, αν και δεν επηρεάζει τη λύση, αφού ο αριθμός των πόλεων με τουλάχιστον 2 δρόμους να καταλήγουν σε αυτές είναι μεγαλύτερος από τον αριθμό των πόλεων με άρτιο αριθμό δρόμων να καταλήγουν σε αυτές (χωρίς το 0), άρα 2Ζ>=αριθμός πόλεων με άρτιο αριθμό δρόμων να καταλήγουν σε αυτές (με το 0).

    Μου αρέσει!

    Σχόλιο από Βασιλης Αιμονιωτης — Ιουνίου 12, 2013 @ 11:37 πμ

  6. Σωστά, έχεις δίκιο.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 13, 2013 @ 12:17 πμ

  7. Βασικά, μας ενδιαφέρει το που καταλήγουνε οι δρόμοι και όχι το από που ξεκινάμε, άρα για να περιγραφεί ο κάθε δρόμος αρκεί να ξέρουμε που καταλήγει. Έστω οτι έχουμε την περίπτωση όπου σε όλες ις πόλεις καταλήγει ένας δρόμος. Έχουμε Ζ =0 & Ε = 0. Ορίζουμε την πράξη της μεταφοράς ενός τέρματος δρόμου από μία πόλη που έχει 1 δρόμο σε μία άλλη που έχει τουλάχιστον ένα δρόμο. Με την παραπάνω πράξη εφαρμοζόμενη κατάληλλα όσες φορές χρειάζεται μπορεί από την αρχική κατάσταση να κατασκευαστεί οποιαδήποτε διάταξη δρόμων. Κάθε φορά που εφαρμόζουμε αυτή την πράξη, το Ζ αυξάνει κατά 1, ενώ το Ε αυξάνει κατά 1 ή 2 ανάλογα με το αν με αυτή την πράξη ο δρόμος πάει σε πόλη που έχει ήδη άρτιο ή περιτό αριθμό δρόμων. Άρα Ζ * α = Ε, με 2 >= α >= 1, οπότε 2 * Ζ >= Ε >= Ζ.

    Μου αρέσει!

    Σχόλιο από Thanos Makris — Σεπτεμβρίου 22, 2013 @ 12:05 μμ

  8. Αυτό θέλει απόδειξη:

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

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 22, 2013 @ 9:25 μμ

  9. Όχι, καλά τα λέω, εφόσον πέρνεις πάντα από μία πολή που έχει 1, πάντα την αφήνεις με 0, οπότε έχεις πάντα αύξηση του Ε κατά 1 τουλάχιστον, και 2 αν ο δρόμος πάει σε πόλη με περιτό αριθμό δρόμων.
    Όσο για την απόδειξη οτι όλες οι πιθανές διατάξεις φτιάχνονται από την αρχική διάταξη με την πράξη που περιγράφω, είναι πολύ απλή για αυτό και δεν μπήκα στον κόπο να την αναφέρω :
    Σε κάθε διάταξη το άθροισμα των επιπλέον της μονάδας δρόμων σε όλες τις πόλεις ισούτε με τον αριθμό των πόλεων με δρόμους 0. Οπότε ο αλγόριθμος για την κατασκευή οποιασδήποτε θέσεις με την πράξη που περιγράφω έχει ως εξής :
    Για κάθε πόλη που θέλουμε να έχει ν δρόμους με ν > 1, πέρνουμε από ν -1 πόλεις που θέλουμε να έχουνε 0 δρόμους τον δρόμο τους και τον πάμε σε αυτή.

    Μου αρέσει!

    Σχόλιο από Thanos Makris — Σεπτεμβρίου 23, 2013 @ 8:39 μμ

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 23, 2013 @ 9:53 μμ

  11. Έχεις δίκιο, συγνώμη για την βιαστική απάντηση. Το γράφω αναλυτικά :
    Σύμφωνα με τον ορισμό της πράξης, πέρνουμε ένα δρόμο από μια πόλη με 1 δρόμο ακριβώς και τον πάμε σε μία πόλη με ν δρόμους, με ν >= 1. (χωρίς η ανισότητα να παίζει ρόλο στο συμπέρασμα)
    Πέρνοντας τον δρόμο από την πόλη με 1 δρόμο, την αφήνουμε με 0, άρα αυξάνεται το Ε κατά 1.
    Στην άλλη πόλη έχουμε 2 περιπτώσεις :
    ν άρτιος, άρα ν + 1 περιτός, οπότε το Ε μειώνεται κατά 1
    ν περιτός, άρα ν + 1 άρτιος, οπότε το Ε αυξάνεται κατά 1
    οπότε συνολικά το Ε μεταβάλεται κατά 0 ή 2 σε ανάλογα με το ν.

    Μου αρέσει!

    Σχόλιο από Thanos Makris — Σεπτεμβρίου 23, 2013 @ 10:42 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

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

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