Στο πάρτυ!

#1

Σε ένα πάρτυ, δύο οποιοιδήποτε καλεσμένοι που δεν είναι φίλοι μεταξύ τους έχουν ακριβώς δύο κοινούς φίλους.
Ο Α και ο Β είναι φίλοι, δεν έχουν όμως κοινούς φίλους.
Δείξτε ότι έχουν τον ίδιο αριθμό φίλων στο πάρτυ.

Πηγή:
http://euclid.ucc.ie/pages/MATHENR/EGMO ... 3_EGMO.pdf

#2

Έστω $\mathcal{A}$ το σύνολο των φίλων του

εκτός από τον

και $\mathcal{B}$ το σύνολο των φίλων του

εκτός από τον

. Θα αποδείξουμε ότι $\left| \mathcal{A}\right | = \left| \mathcal{B}\right |$ .

Έστω τυχαίο $X \in \mathcal{A}$ . Επειδή $\mathcal{A} \cap \mathcal{B} = \varnothing$ , ο

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

. Άρα, ο

έχει ακριβώς δύο κοινούς φίλους με τον

, εκ των οποίων ο ένας είναι ο

. Ορίζουμε τη συνάρτηση

$\displaystyle{f:\mathcal{A} \to \mathcal{B}:X \mapsto f\left( X \right): = Y}$ ,

όπου για $X \in \mathcal{A}$ , ο

είναι ο διάφορος του

κοινός φίλος του

και του

.

Η συνάρτηση

είναι καλά ορισμένη. Θα αποδείξουμε ότι η

είναι 1-1. Πράγματι, έστω $X_1, X_2 \in \mathcal{A}$ με $X_1 \ne X_2$ . Αν είχαμε ότι $\displaystyle{f\left( {{X_1}} \right) = Y = f\left( {{X_2}} \right),}$ τότε οι

και

θα ήταν τρεις κοινοί φίλοι των

και

, πράγμα άτοπο. Επομένως, θα είναι $\displaystyle{f\left( {{X_1}} \right) \ne f\left( {{X_2}} \right),}$ οπότε η η

είναι 1-1 και άρα $\left| \mathcal{A}\right | \le \left| \mathcal{B}\right |$ .

Όμοια, δείχνουμε ότι $\left| \mathcal{B}\right | \le \left| \mathcal{A}\right |$ , οπότε τελικά $\left| \mathcal{A}\right | = \left| \mathcal{B}\right |$ και η απόδειξη ολοκληρώνεται.

Στο πάρτυ!

Στο πάρτυ!

Re: Στο πάρτυ!

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