IMC 2009: Θεματα - Λυσεις - Σχολια - Δ1.39, ...

#21

Nick1990 έγραψε: 3) Σε μια πολη, καθε 2 κατοικοι οι οποιοι δεν ειναι φιλοι μεταξυ τους, εχουν ενα κοινο φιλο. Ακομα κανενας κατοικος δεν ειναι φιλος με ολους τους υπολοιπους. Εστω οτι οι κατοικοι ειναι ν, με α_ι συμβολιζουμε το πληθος των φιλων του ι κατοικου. Εστω οτι ισχυει (α_1)^2 + (α_2)^2 + ... + (α_ν)^2 = ν(ν-1). Εστω κ ειναι ο ελαχιστος αριθμος κατοικων (τουλαχιστον 3) οι οποιοι μπορουν να καθισουν σε ενα κυκλικο τραπεζι με τετοιο τροπο ωστε αναμεσα σε καθε δυο διπλανους κατοικους να υπαρχει φιλια. Βρειτε ολες τις δυνατες τιμες του κ.

Μετράμε όλες τις τριάδες (x,y,z)

όπου οι

είναι φίλοι του

. Υπάρχουν ακριβώς $a_1^2 + a_2^2 + \cdots + a_n^2 = n(n-1)$ τέτοιες τριάδες.

Ο αριθμός των τριάδων με y=z

είναι $a_1 + \cdots + a_n$ .

Για κάθε ζεύγος (y,z)

όπου $y \neq z$ και οι y,z

δεν είναι φίλοι υπάρχει τουλάχιστον ένα

που είναι φίλος και με τους δύο, άρα ο αριθμός των τριάδων με $y \neq z$ όπου οι y,z

δεν είναι φίλοι είναι τουλάχιστον ο αριθμός όλων των ζευγαριών (y,z)

όπου $y \neq z$ και οι y,z

δεν είναι φίλοι που είναι ίσος με $2\binom{n}{2} - (a_1 + \cdots + a_n)$ .

Άρα ο αριθμός των τριάδων είναι τουλάχιστον n(n-1)

με ισότητα αν και μόνο αν κάθε δυο φίλοι δεν έχουν κανένα κοινό φίλο και κάθε δυο μη φίλοι έχουν ακριβώς ένα κοινό φίλο. (Άρα πρέπει $k \geqslant 5$ .)

Ισχυρίζομαι ότι αν

και

δεν είναι φίλοι τότε έχουν τον ίδιο αριθμό φίλων. Πράγματι έστω

το σύνολο των φίλων του

που δεν είναι φίλοι του

και

το σύνολο των φίλων του

που δεν είναι φίλοι του

. Για κάθε $y_i \in Y$ έστω x_i

ο μοναδικός κοινός φίλος των

και

. Ο

δεν είναι φίλος του

, άρα $x_i \in X$ . Ακόμη, αν $y_i \neq y_j$ τότε έχουν κοινό φίλο τον

και άρα $x_i \neq x_j$ . Άρα $|X| \geqslant |Y|$ και από την συμμετρία του προβλήματος |X| = |Y|

.

Ισχυρίζομαι τώρα ότι κάθε δυο άτομα, έστω

και

, έχουν τον ίδιο αριθμό φίλων. Αν δεν είναι φίλοι τότε το έχουμε ήδη αποδείξει. Αν είναι φίλοι και υπάρχει

που δεν είναι φίλος κανενός τότε έχουν και οι δυο των ίδιο αριθμό φίλων με τον

. Μένει να ελέγξουμε την περίπτωση που είναι φίλοι μεταξύ τους, και κάθε άλλος κάτοικος είναι φίλος είτε του

είτε του

.
Επειδή κανείς δεν είναι φίλος όλων πρέπει να υπάρχουν τουλάχιστον άλλοι δύο κάτοικοι. Αν υπάρχουν ακριβώς άλλοι δύο κάτοικοι τότε ο ένας είναι φίλος του

,ο άλλος του

άρα ο

και ο

έχουν τον ίδιο αριθμό φίλων. Αν υπάρχουν τουλάχιστον πέντε κάτοικοι. Τότε (επειδή κανείς δεν είναι φίλος με όλους) μπορούμε να υποθέσουμε ότι ο

είναι φίλος του

και οι

είναι φίλοι του

. O

δεν μπορεί να είναι φίλος και του

και του

(αφού έχουν κοινό φίλο με τον

. Άρα ο

έχει τον ίδιο αριθμό φίλων με τον

και ένα εκ των u,v

ο οποίος έχει τον ίδιο αριθμό φίλων με τον

.

Έστω λοιπόν ότι όλοι έχουν

φίλους. Τότε πρέπει nm^2 = n(n-1)

και άρα

. Κοιτάζουμε τώρα ένα συγκεκριμένο άτομο

με όλους τους φίλους του και όλους τους φίλους των φίλων του. Είναι ακριβώς 1 + m + m(m-1) = n

άτομα. Άρα πρέπει $k \leqslant 5$ .

To k=5

εἰναι δυνατόν στο χωριό με άτομα a,b,c,d,e

και φιλίες ab,bc,cd,de,ea

.

Ουφ. Προσπάθησα να αποφύγω όρους από την θεωρία γραφημάτων και τελικά η λύση βγήκε πολύ πιο μεγάλη από ότι υπολόγιζα.

#22

Dimitris X έγραψε: Ο Σιλουανός δεν έγραφε???

Όχι δεν έγραφα. 'Εχω απομακρυνθεί λίγο από τους διαγωνισμούς.

#23

Επαναφέρω το θέμα μιας και αρκετά από τα θέματα του διαγωνισμού έχουν μείνει άλυτα.

IMC 2009: Θεματα - Λυσεις - Σχολια - Δ1.39, ...

Re: IMC 2009: Θεματα - Λυσεις - Σχολια

Re: IMC 2009: Θεματα - Λυσεις - Σχολια

Re: IMC 2009: Θεματα - Λυσεις - Σχολια

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