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

Ιανουαρίου 23, 2009

Υπουργικό συμβούλιο

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

Ένας νεοεκλεγείς πρόεδρος σε μια μεγάλη χώρα με πληθυσμό από λευκούς και έγχρωμους (=όλοι οι μη λευκοί) θέλει να ορίσει το υπουργικό του συμβούλιο. Θέλει να χρησιμοποιήσει αυτή του την πράξη ώστε, μεταξύ άλλων, να προωθήσει τη συνεργασία λευκών και έγχρωμων στη χώρα του. Γι’ αυτό θεσπίζει τον εξής κανόνα:

κάθε λευκό μέλος του υπουργικού συμβουλίου θα πρέπει να έχει τουλάχιστον τόσους έγχρωμους συνεργάτες όσους και λευκούς και, ομοίως, κάθε έγχρωμο μέλος θα πρέπει να έχει τουλάχιστον τόσους λευκούς συνεργάτες όσους και έγχρωμους.

Οι θέσεις του υπουργικού συμβουλίου είναι δεδομένες όπως και το ποιος συνεργάζεται με ποιον (π.χ. ο υπουργός Οικονομικών συνεργάζεται με όλους, ο υπουργός Άμυνας δε συνεργάζεται με τον υπουργό Γεωργίας, κλπ).

Ο ίδιος ο πρόεδρος είναι κι αυτός μέλος του υπουργικού συμβουλίου και είναι έγχρωμος.

Δείξτε ότι μπορεί πάντα να επιλέξει υπουργούς του κατάλληλου χρώματος ώστε να πετύχει το σκοπό του αυτό.

Advertisements

5 Σχόλια »

  1. Υπόδειξη:

    Για ένα δεδομένο υπουργικό συμβούλιο ας είναι X το πλήθος των υπουργών που πληρούν τον κανόνα (έχουν δηλ. τουλάχιστον τόσους «διαφορετικούς» συνεργάτες όσους και «όμοιους»). Υποθέστε ότι έχετε ένα υπουργικό συμβούλιο όπου το X είναι το μέγιστο δυνατό. Τι πρέπει να συμβαίνει;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Φεβρουαρίου 5, 2009 @ 9:57 πμ

  2. Να δώσω μια διαφορετική υπόδειξη. Πάρτε ένα υπουργικό συμβούλιο που να μεγιστοποιεί τις συνεργασίες μεταξύ λευκών και μαύρων. Τι παρατηρείτε;

    Μου αρέσει!

    Σχόλιο από demetres — Μαρτίου 2, 2009 @ 8:46 μμ

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 20, 2009 @ 6:58 μμ

  4. Αν και νομίζω ότι οι υποδείξεις είναι και σχεδόν η λύση…

    Έστω k όλες οι συνεργασίες. Το k είναι συγκεκριμένη σταθερά (προφανώς ακέραιος).
    Έστω x_i οι ετερόχρωμες συνεργασίες (επίσης προφανώς ακέραιος).
    Πάντα x_i \le k .

    Αρχικά (βήμα 1) έχω x_1 \le k
    Αν όλοι οι υπουργοί πληρούν τον κανόνα είμαστε εντάξει.
    Αν υπάρχει ένας που δεν τον πληρεί τον αλλάζουμε με έναν άλλου χρώματος (είπαμε οι υποδείξεις είναι σχεδόν η λύση).
    Τότε αναγκαστικά (βήμα 2)
    x_2 \ge x_1 + 1
    Μετά από k βήματα ή θα έχω κάπου σταματήσει άρα όλοι πληρούν τον κανόνα ή αναγκαστικά x_k = k . Αυτό όμως σημαίνει ότι κανένας δεν συνεργάζεται με ομόχρωμό του άρα πάλι όλοι πληρούν τον κανόνα.

    Μου αρέσει!

    Σχόλιο από shortmanikos — Οκτώβριος 8, 2010 @ 11:12 μμ

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Οκτώβριος 9, 2010 @ 12:19 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

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

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