IMC 2017/1/4

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8587
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

IMC 2017/1/4

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Αύγ 02, 2017 7:20 pm

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



Λέξεις Κλειδιά:
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8587
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: IMC 2017/1/4

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Αύγ 03, 2017 5:38 pm

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

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

1) |A| = k.
2) Κάθε κορυφή του A έχει ακριβώς δύο γείτονες στο B. [Άρα θα είναι και |B| \leqslant 2k.]
3) Κάθε κορυφή του A έχει γείτονες μόνο στα B και D. [Άρα θα είναι και |D| \leqslant 1000k.]
4) Κάθε κορυφή του C έχει το πολύ δύο γείτονες στο B.

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

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

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

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

Τότε όμως είναι |C| \leqslant 1000|D|/999 \leqslant 1002k.

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

\displaystyle{ n = |A| + |B| + |C| + |D| \leqslant 2005k}

Δηλαδή k \leqslant n/2005 < n/2017. Οπότε το S = A \cup B έχει την ζητούμενη ιδιότητα.

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


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες