Σελίδα 1 από 1

IMC 2015/2/3

Δημοσιεύτηκε: Παρ Ιούλ 31, 2015 10:02 am
από Demetres
Θεωρούμε τις 26^{26} λέξεις μήκους 26 στο Λατινικό αλφάβητο. Το βάρος μια λέξης είναι 1/(k+1), όπου k ο αριθμός των γραμμάτων που δεν εμφανίζονται στην λέξη. Να δειχθεί ότι το άθροισμα των βαρών όλων των λέξεων είναι 3^{75}.

Re: IMC 2015/2/3

Δημοσιεύτηκε: Παρ Ιούλ 31, 2015 10:40 am
από Demetres
Πανέμορφο.

Βάζουμε ένα καινούργιο γράμμα \ast στο αλφάβητο. Θεωρούμε όλες τις 27^{26} λέξεις μήκους 26 που παίρνουμε σε αυτό το αλφάβητο. Από κάθε μία παίρνουμε ομοιόμορφα στην τύχη ένα γράμμα που δεν εμφανίζεται στην λέξη.

Ο προσδοκόμενος αριθμός X των εμφανίσεων του γράμματος \ast είναι ακριβώς το ζητούμενο άθροισμα βαρών. Ασφαλώς το X είναι το ίδιο για οποιοδήποτε γράμμα. Οπότε 27X = 27^{26} και άρα X = 27^{25} = 3^{75}.

Re: IMC 2015/2/3

Δημοσιεύτηκε: Σάβ Αύγ 01, 2015 9:42 pm
από Ilias_Zad
Πολύ ωραία λύση Δημήτρη! :coolspeak:

Re: IMC 2015/2/3

Δημοσιεύτηκε: Πέμ Ιούλ 27, 2017 3:29 pm
από Mikesar
Ας βάλω μία άλλη σχετικά σύντομη αλλά πιο τεχνική λύση (αν και μετά τη λύση του κύριου Δημήτρη περιττεύει). Για ένα αλφάβητο n γραμμάτων, το άθροισμα των βαρών των λέξεων μήκους n είναι
A=\displaystyle\sum_{k=1}^{n}\frac{S(n,k)\binom{n}{k}k!}{n-k+1}
Ας εξηγήσω. Οι λέξεις που χρησιμοποιούνται ακριβώς k γραμματά ορίζονται αμφιμονοσήμαντα διαμερίζοντας τις θέσεις 1 ως n σε k μέρη (στις θέσεις κάθε μέρους θα μπει το ίδιο γράμμα) και έπειτα επιλέγοντας μια k-αδα γραμμάτων από τα n που θα βάλουμε στη λέξη και τοποθετώντας τα στα μέρη με k! τρόπους. Τέλος πολλαπλασιάσαμε με το βάρος.
Άρα,
\displaystyle A=\sum_{k=1}^{n}S(n,k)n(n-1)...(n-k+2)=
=\displaystyle\frac{1}{n+1}\sum_{k=1}^{n}S(n,k)(n+1)n(n-1)...(n-k+2)=\frac{(n+1)^n}{n+1}=(n+1)^{n-1},
όπου χρησιμοποιήθηκε η γνωστή ταυτότητα \displaystyle x^n=\sum_{k=1}^{n}S(n,k)x(x-1)...(x-k+1) για x=n+1.