Euler 2014-4

#1

Σε ένα πάρτι έλαβαν μέρος

αγόρια και

κορίτσια. Κάθε αγόρι χόρεψε με ακριβώς

κορίτσια και κάθε δύο αγόρια χόρεψαν με ακριβώς d < k

κοινά κορίτσια.

Να δειχθεί ότι κάθε κορίτσι χόρεψε με ακριβώς

αγόρια και κάθε δύο κορίτσια χόρεψαν με ακριβώς

κοινά αγόρια.

Mikesar · #2

Ας κάνω μια προσπάθεια...
Δημιουργούμε το προφανές γράφημα και έστω

ο πίνακας γειτνίασής του. Τότε, θεωρώντας ως πρώτες

κορυφές τα αγόρια, ο

είναι της μορφής $\left( {\begin{array}{cc} O & C \\ C^t & O \\ \end{array} } \right)$ για κάποιον $n\times n$ πίνακα

.
Έτσι $A^2= \left( {\begin{array}{cc} CC^t & O \\ O & C^tC \\ \end{array} } \right)$ .
Ως γνωστόν το ij-

στοιχείo του A^2

είναι το πλήθος των κοινών γειτόνων των κορυφών i,j

. Συνεπώς, από τις συνθήκες του προβλήματος έχω $CC^t=\left( {\begin{array}{ccccc} k & d & d & \ldots & d \\ d & k & d & \ldots & d \\ d & d & k & \ldots & d \\ \vdots& \vdots& \vdots& \ddots& \vdots\\ d & d & d & \ldots & k \\ \end{array} } \right)=(k-d)I+dJ$ ,
όπου

ο πίνακας που έχει όλα του τα στοιχεία ίσα με

. Θέλω να δείξω ότι C^tC=CC^t=(k-d)I+dJ

.
Επειδή κάθε αγόρι χόρεψε με ακριβώς

κορίτσια, ισχύει CJ=kJ

και άρα

. Επιπλέον J^2=nJ

.
$(\sqrt{d}J-\sqrt{n}C)(\sqrt{d}J+\sqrt{n}C^t)=dJ^2-\sqrt{dn}(CJ-JC^t)+nCC^t=$
=n(dJ-CC^t)=n(d-k)I

Αφού $k\neq d$ , θα πρέπει να ισχύει
$(\sqrt{d}J-\sqrt{n}C)(\sqrt{d}J+\sqrt{n}C^t)=(\sqrt{d}J+\sqrt{n}C^t)(\sqrt{d}J-\sqrt{n}C)\Leftrightarrow$
$n(CC^t-C^tC)=\sqrt{dn}(JC-C^tJ)$
Το δεξί μέλος της τελευταίας σχέσης είναι αντισυμμετρικός πίνακας ενώ το αριστερό συμμετρικός. Άρα πρέπει τα δύο μέλη να ισούνται με το μηδενικό πίνακα.

Euler 2014-4

Euler 2014-4

Re: Euler 2014-4

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