Τετάρτη 24 Ιουλίου 2013

▪ Πάρτι

Σε ένα πάρτι με $n$ άτομα, είναι γνωστό ότι για κάθε μη κενό υποσύνολο $S$ ανθρώπων, υπάρχει τουλάχιστον ένα άτομο, μέσα ή έξω από $S$, έτσι ώστε το άτομο αυτό να έχει περιττό αριθμό φίλων στο $S$. Να αποδειχθεί ότι ο $n$ είναι άρτιος αριθμός.
Αναρτήθηκε από στις 24.7.13
Ετικέτες

1 σχόλιο:

  1. ΕΥΘΥΜΗΣ ΑΛΕΞΙΟΥ8 Αυγούστου 2013 στις 9:35 π.μ.

    Έστω 1,2,3,..,n τα άτομα στο πάρτι, S1,S2,S3,...Sn τα μη κενά υποσύνολα που αντιστοιχούν στα 1,2,3,..,n άτομα και Α1,Α2,Α3,...Αn οι περιττοί αριθμοί φίλων των 1,2,3,...,n στα S1,S2,S3,...,Sn αντίστοιχα. Επειδή η φιλία είναι αμοιβαία σχέση, δηλαδή αν ο αi έχει φίλο τον αj και ο αj θα έχει φίλο τον αi, συνεπάγεται ότι το άθροισμα ΣΑ=Α1+Α2+Α3+...+Αn θα είναι άρτιος αριθμός (2*κ, κ φυσικός αριθμός).
    Επειδή από τα δεδομένα ξέρουμε ότι όλα τα Α1,Α2,Α3,...Αn είναι περιττοί αριθμοί φίλων και το άθροισμα τους (ΣΑ) είναι άρτιος αριθμός συνεπάγεται ότι το πλήθος των Α1,Α2,Α3,...Αn είναι άρτιος αριθμός (μόνο άρτιο πλήθος περιττών αριθμών έχει άθροισμα άρτιο αριθμό, ενώ περιττό πλήθος περιττών αριθμών έχει άθροισμα περιττό αριθμό), άρα ο n είναι άρτιος αριθμός.

    ΑπάντησηΔιαγραφή

Εγγραφή σε: Σχόλια ανάρτησης (Atom)