IMC 2015/2/3

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8261
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

IMC 2015/2/3

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Ιούλ 31, 2015 10:02 am

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


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8261
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: IMC 2015/2/3

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Ιούλ 31, 2015 10:40 am

Πανέμορφο.

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

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


Ilias_Zad
Δημοσιεύσεις: 418
Εγγραφή: Δευ Ιαν 26, 2009 11:44 pm

Re: IMC 2015/2/3

#3

Μη αναγνωσμένη δημοσίευση από Ilias_Zad » Σάβ Αύγ 01, 2015 9:42 pm

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


Mikesar
Δημοσιεύσεις: 139
Εγγραφή: Σάβ Ιούλ 30, 2011 8:29 pm
Τοποθεσία: Αθήνα

Re: IMC 2015/2/3

#4

Μη αναγνωσμένη δημοσίευση από Mikesar » Πέμ Ιούλ 27, 2017 3:29 pm

Ας βάλω μία άλλη σχετικά σύντομη αλλά πιο τεχνική λύση (αν και μετά τη λύση του κύριου Δημήτρη περιττεύει). Για ένα αλφάβητο 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.


Μιχάλης Σαράντης
Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες