IMC 2015/2/3

#1

Θεωρούμε τις $26^{26}$ λέξεις μήκους

στο Λατινικό αλφάβητο. Το βάρος μια λέξης είναι 1/(k+1)

, όπου

ο αριθμός των γραμμάτων που δεν εμφανίζονται στην λέξη. Να δειχθεί ότι το άθροισμα των βαρών όλων των λέξεων είναι $3^{75}$ .

#2

Πανέμορφο.

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

Ο προσδοκόμενος αριθμός

των εμφανίσεων του γράμματος $\ast$ είναι ακριβώς το ζητούμενο άθροισμα βαρών. Ασφαλώς το

είναι το ίδιο για οποιοδήποτε γράμμα. Οπότε $27X = 27^{26}$ και άρα $X = 27^{25} = 3^{75}$ .

Ilias_Zad · #3

Πολύ ωραία λύση Δημήτρη!

Mikesar · #4

Ας βάλω μία άλλη σχετικά σύντομη αλλά πιο τεχνική λύση (αν και μετά τη λύση του κύριου Δημήτρη περιττεύει). Για ένα αλφάβητο

γραμμάτων, το άθροισμα των βαρών των λέξεων μήκους

είναι
$A=\displaystyle\sum_{k=1}^{n}\frac{S(n,k)\binom{n}{k}k!}{n-k+1}$
Ας εξηγήσω. Οι λέξεις που χρησιμοποιούνται ακριβώς

γραμματά ορίζονται αμφιμονοσήμαντα διαμερίζοντας τις θέσεις

ως

σε

μέρη (στις θέσεις κάθε μέρους θα μπει το ίδιο γράμμα) και έπειτα επιλέγοντας μια

-αδα γραμμάτων από τα

που θα βάλουμε στη λέξη και τοποθετώντας τα στα μέρη με

τρόπους. Τέλος πολλαπλασιάσαμε με το βάρος.
Άρα,
$\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

.

IMC 2015/2/3

IMC 2015/2/3

Re: IMC 2015/2/3

Re: IMC 2015/2/3

Re: IMC 2015/2/3

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