IMC 2017/1/4

[Demetres]

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

[Demetres]

Σχετικά εύκολο για (4).

Θα κατασκευάσουμε το αλγοριθμικά. Στο βήμα οι κορυφές του γραφήματος θα είναι χωρισμένες σε τέσσερα σύνολα, τα και ώστε να ισχύουν τα εξής:

1) .
2) Κάθε κορυφή του έχει ακριβώς δύο γείτονες στο . [Άρα θα είναι και .]
3) Κάθε κορυφή του έχει γείτονες μόνο στα και . [Άρα θα είναι και .]
4) Κάθε κορυφή του έχει το πολύ δύο γείτονες στο .

Ξεκινάμε έχοντας όλες τις κορυφές στο . Στο πρώτο βήμα παίρνουμε οπoιαδήποτε κορυφή και την μεταφέρουμε στο . Μεταφέρουμε δύο γείτονές της στο και όλους τους υπόλοιπους γείτονές της στο . Τα (1)-(4) ισχύουν.

Σε κάθε βήμα κοιτάζουμε όλες τις κορυφές του οι οποίες έχουν τουλάχιστον δύο γείτονες στο . Από αυτές επιλέγουμε μία κορυφή με τον μέγιστο αριθμό γειτόνων στο και την μεταφέρουμε στο . Μεταφέρουμε επίσης όσους γείτονές της από το στο χρειαστεί ώστε να έχει δύο γείτονές στο . Όσους άλλους γείτονές της βρίσκονται στο τους μεταφέρουμε στο .

Παρατηρούμε ότι τα (1)-(4) εξακολουθούν να ισχύουν. Για να δούμε το (4) ας υποθέσουμε ότι μεταφέραμε μια κορυφή από το στο . Έστω ότι η είχε γείτονες στο . Οπότε προσθέσαμε κορυφές στο . Για να απέκτησε μια κορυφή του περισσότερους από δύο γείτονες στο , θα έπρεπε να είχε περισσότερους από γείτονες στο . Θα έπρεπε επίσης συνολικά να είχε περισσότερους από δύο γείτονες στο . Από τον ορισμό του αυτό είναι αδύνατο αφού θα έπρεπε να επιλέξουμε την και όχι την .

Συνεχίζουμε την διαδικασία μέχρι να μην είναι πλέον δυνατό. Δηλαδή μέχρι την στιγμή όπου όλες οι κορυφές του έχουν λιγότερους από δύο γείτονες στο . Άρα έχουν τουλάχιστον γείτονες στο .

Τότε όμως είναι .

Έχουμε λοιπόν



Δηλαδή . Οπότε το έχει την ζητούμενη ιδιότητα.

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