Κάθε μέλος κάποιου κοινοβουλίου έχει το πολύ τρεις εχθρούς. Να αποδειχθεί ότι μπορεί το κοινοβούλιο αυτό να χωρισθεί σε δύο σώματα έτσι ώστε κάθε βουλευτής του ιδίου σώματος να έχει το πολύ έναν εχθρό.
Θεωρείται ότι, αν ο Β είναι εχθρός του Α, τότε και ο Α είναι εχθρός του Β.
13η Πανενωσιακή Μαθηματική Ολυμπιάδα 1979 (Τιφλίδα)
Χωρίζουμε τους βουλευτές σε δύο τυχαία σώματα. Ακ κάποιος βουλευτής σε ένα σώμα έχει τουλάχιστον δύο εχθρούς, συνεπάγεται ότι στο άλλο σώμα θα υπάρχει το πολύ ένας εχθρός, οπότε απλά τον μετακινούμε στο άλλο σώμα.
ΑπάντησηΔιαγραφήΒρίσκω ωραιότατη την απόδειξη, απλή, σύντομη και έξυπνη και συγχαίρω το Στράτο.
ΑπάντησηΔιαγραφήΝομίζω ότι το ίδιο ακριβώς αποτέλεσμα θα είχαμε αν κάναμε το εξής:
Εντοπίζουμε τους βουλευτές του αρχικού σώματος που έχουν 3 εχθρούς.
Διαλέγουμε έναν από αυτούς, έστω τον Α, και τον μετακινούμε σε ένα δεύτερο σώμα. Οι εχθροί του Α που παραμένουν στο αρχικό σώμα, έστω οι Β, Γ και Δ έχουν πλέον εντός του αρχικού σώματος από 1 εχθρό λιγότερο ο καθένας και κανένας τους περισσότερους από 2 εχθρούς.
Διαλέγουμε τον επόμενο από το αρχικό σώμα που εξακολουθεί να έχει εντός του σώματος 3 εχθρούς , έστω τον Ε (προφανώς αυτός δεν είναι κανείς από τους Β, Γ, Δ) και τον μετακινούμε επίσης στο δεύτερο σώμα.
Επαναλαμβάνουμε τη διαδικασία μέχρι να εξαντληθούν όσοι στο αρχικό σώμα είχαν αρχικά 3 εχθρούς. Στο τέλος αυτής της φάσης, στο αρχικό σώμα απομένουν όσοι πλέον έχουν μέχρι το πολύ 2 εχθρούς εσωτερικά, ενώ στο δεύτερο σώμα, εσωτερικά, κανένας δεν είναι εχθρός με κανέναν.
Μετακινούμε τώρα με ανάλογη διαδικασία στο δεύτερο σώμα όσους από το αρχικό σώμα έχουν πλέον 2 εχθρούς εσωτερικά. Αυτοί, μετακινούμενοι στο δεύτερο σώμα, θα συναντήσουν 1 το πολύ εχθρό τους.
Έτσι στο τέλος και αυτής της φάσης, τόσο αυτοί που θα απομείνουν στο αρχικό σώμα, όσο και εκείνοι που θα μετακινηθούν στο δεύτερο σώμα θα έχουν το πολύ 1 εχθρό εσωτερικά του σώματος που θα βρεθούν.