Σε έναν πολύ μακρινό γαλαξία, υπάρχει μια Ενωμένη Γαλαξιακή Γερουσία με $100$ γερουσιαστές. Κάθε γερουσιαστής δεν έχει περισσότερα από τρεις εχθρούς.
Κουρασμένοι από τις διαφωνίες τους, οι γερουσιαστές θέλουν να χωριστούν σε δύο κόμματα, έτσι ώστε κάθε Γερουσιαστής να μην έχει περισσότερους από έναν εχθρούς στο δικό του κόμμα.
Αποδείξτε ότι μπορούν να το κάνουν αυτό.
(Σημείωση: Αν ο $Α$ είναι εχθρός του $Β$, τότε ο $Β$ είναι εχθρός του $Α$).
Εξετάζουμε υποθετικά όλους τους δυνατούς τρόπους χωρισμού της Γερουσίας στα δύο. Σε κάθε τρόπο, βρίσκουμε το συνολικό πλήθος Π των ζευγαριών εχθρών που βρίσκονται στο ίδιο κόμμα και επιλέγουμε τον τρόπο που δίνει το ελάχιστο Π. Αν με τον συγκεκριμένο τρόπο χωρισμού υπήρχε γερουσιαστής με δύο εχθρούς στο κόμμα του, θα μπορούσε να μετακινηθεί στο άλλο κόμμα όπου έχει έναν το πολύ εχθρό, μειώνοντας έτσι κατά τουλάχιστον 1 το Π, άτοπο.
ΑπάντησηΔιαγραφή