Κοινός γνωστός

#1

Σε μια συνάντηση

ατόμων υπάρχουν τουλάχιστον n^2 + 1

ζευγάρια $\{a,b\}$ (με $a\neq b$ ) όπου ο

γνωρίζει τον

. Να δειχθεί ότι υπάρχουν δυο γνωστοί που έχουν τουλάχιστον ένα κοινό γνωστό.

Έγινε διόρθωση της άσκησης.

billy_scabilly · #2

Mια ιδέα στα γρήγορα,μπορεί να λέω και μεγάλες βλακείες(το συνηθίζω άλλωστε

).(Sorry για το μη Latex,θα προσπαθήσω να επανορθώσω)

Oυσιαστικά έχουμε γράφημα με 2n κορυφές και n^2 +1 ακμές και θέλουμε να δείξουμε ότι υπάρχει μονοπάτι μήκους 2,έστω ΑΒΓ με Γ διάφορο του Α.
Μετράμε τα μονοπάτια μήκους 2.Έστω di ο βαθμός της i-οστής κορυφής.Τότε υπάρχει μια αμφιμονοσήμαντη απεικόνιση ανάμεσα σε όλα τα μονοπάτια μήκους 2 με ενδιάμεση κορυφή την i και στα ζεύγη (α,i,b) όπου b και α κορυφές που ενώνονται με την i.Oπότε έχουμε di*di μονοπάτια μήκους 2 με ενδιάμεση κορυφή την i.Aθροίζοντας πάνω σε όλα τα i έχουμε το πλήθος των συνολικών μονοπατιών μήκους 2.
Όμως για κάθε i εμείς θέλουμε να μετρήσουμε τα μονοπάτια μήκους δύο της μορφής ΑΒΓ με Γ διάφορο του Α,τα οποία είναι di*(di -1) .
Aρκεί Σdi*(di -1) >0 για να υπάρχει τουλάχιστον ένα μονοπάτι μήκους 2 με τις ζητούμενες προυποθέσεις.
Όμως από τη σχέση Σ(di-1)^2 >=0 αν αναπτύξουμε έχουμε ότι Σdi*(di -1) >= Σdi - 2n >= 2(n^2 +1) -2n >(n-1)^2 >=0.

#3

Βασίλη απολογούμαι. Εγώ σήμερα λέω βλακείες. (Η άσκηση δεν είναι λάθος, αλλά δεν είναι αυτό που ήθελα να ζητήσω. Θα διορθώσω σύντομα την άσκηση.)

billy_scabilly · #4

Στην ουσία ψάχνουμε τρίγωνο.Έστω ότι δεν υπάρχει,τότε απ'το Θεώρημα του Τuran για r=2 έχουμε άτοπο

Τώρα για το Θεώρημα αυτό just look http://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem
Προσπάθησα λίγο να βρω κάτι trivial με βάση το παρακάτω που γράφω και την προηγούμενη απόδειξη της λανθασμένης άσκησης αλλά δεν βρήκα.
Eντωμεταξύ,για αυτό που είχα γράψει πιο πριν,είναι τελείως προφανές ότι θα υπάρχει μονοπάτι μήκους δύο βασικά,στην ουσία αποδεικνύω ότι υπάρχουν n^2 +1 μονοπάτια μήκους 2,διότι
Σdi*(di -1) >= Σdi - 2n >= 2(n^2 +1) -2n >=(n-1)^2 + (n^2+1) >n^2+1.

#5

Ακριβώς για το θεώρημα Turan την έβαλα. Υπάρχουν πιο απλές λύσεις από αυτήν της wikipedia. Για την περίπτωση r=2

που μας ενδιαφέρει υπάρχει ακόμη μια πιο απλή λύση.

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

#6

Χρησιμοποιήστε ότι για κάθε ακμή

έχουμε $d(x) + d(y) \leqslant n$ (αφού οι x,y

δεν έχουν κοινό γνωστό) και προσθέστε όλες αυτές τις ανισότητες.

#7

Demetres έγραψε:Χρησιμοποιήστε ότι για κάθε ακμή έχουμε $d(x) + d(y) \leqslant n$ (αφού οι δεν έχουν κοινό γνωστό) και προσθέστε όλες αυτές τις ανισότητες.

Απολογούμαι. Στην υπόδειξη έπρεπε να πω $d(x) + d(y) \leqslant 2n$

Κοινός γνωστός

Κοινός γνωστός

Re: Κοινός γνωστός

Re: Κοινός γνωστός

Re: Κοινός γνωστός

Re: Κοινός γνωστός (Θεώρημα Turan για τρίγωνα)

Re: Κοινός γνωστός

Re: Κοινός γνωστός

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