Μια λύση για το πρόβλημα 4, ελπίζω να είναι σωστή.
Το μεταφράζουμε σε γράφημα ως εξής: ενώνουμε

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

και

εκτός του

, το

είναι συνδεδεμένο το πολύ σε ένα μέλος του

. Το ζητούμενο γίνεται: μπορούμε να χρωματίσουμε τις κορυφές με

χρώματα ώστε κάθε

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

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

, κλπ).
Ας υποθέσομε ότι υπάρχει τέτοιο γράφημα με κάθε κορυφή να έχει βαθμό πάνω από

.
Ένα μονοπάτι

ονομάζεται αμείωτο αν οι κορυφές

δεν συνδέονται για οποιοδήποτε

. Θεωρούμε ένα αμείωτο μονοπάτι μέγιστου μήκους

.
Τότε, θεωρούμε κορυφές

που συνδέονται με την

(υπάρχουν, καθώς ο βαθμός της

είναι τουλάχιστον

). Τότε, προφανώς δεν θα ανήκουν στο μονοπάτι. Αν μια από τις

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

συνδέεται με την

και η

με την

. Χωρίς βλάβη της γενικότητας,

. Τότε, η

συνδέεται με 2 στοιχεία του κύκλου

, τα στοιχεία

, που οδηγεί σε άτοπο από την συνθήκη του προβλήματος. Άρα, υπάρχει κορυφή με βαθμό το πολύ

.
Να σημειώσω ότι σαν να μην έφτανε η φυσική δυσκολία του προβλήματος, υπήρχε επιπλέον "τεχνητή" δυσκολία: το πρόβλημα προκύπτει άμεσα από μια πολύ πιο ισχυρή συνθήκη από αυτή που ζητάει η εκφώνηση. Έλυσα το πρόβλημα μόνο μετά από hint (υπάρχει κορυφή με βαθμό το πολύ 2), δεν πιστεύω ότι στην πίεση του διαγωνισμού θα έκαναν πολλά άτομα τέτοια μαντεψιά. Πάντως, δεδομένης της τεράστιας δυσκολίας του 4 σε σχέση με τα άλλα 3 προβλήματα, λογικά θα υπάρχουν αρκετά άτομα με βαθμολογία

.
Επίσης, συγχαρητήρια στην ομάδα για τις επιτυχίες της!
Καλή επιτυχία και στην ΙΜΟ.