uniolympiads English

IMC 2015, Ημέρα 2, Θέμα 8

Consider all 262626^{26} words of length 2626 in the Latin alphabet. Define the weight of a word as 1/(k+1)1/(k+1), where kk is the number of letters not used in this word. Prove that the sum of the weights of all words is 3753^{75}.

Πρωτότυπο από το επίσημο PDFConsider all 26 26 words of length 26 in the Latin alphabet. Dene the weight of a word as 1/(k + 1) , where k is the number of letters not used in this word. Prove that the sum of the weights of all words is 3 75 . Problem 8.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(Proposed by Fedor Petrov, St. Petersburg State University)

Solution. Let n=26n = 26, then 375=(n+1)n−13^{75} = (n+1)^{n-1}. We use the following well-known

Lemma. If f(x)f(x) is a polynomial of degree at most nn, then its (n+1)(n+1)-st finite difference vanishes: Δn+1f(x):=∑i=0n+1(−1)i(n+1i)f(x+i)≡0\Delta^{n+1}f(x) := \sum_{i=0}^{n+1}(-1)^i\binom{n+1}{i}f(x+i)\equiv 0.

Proof. If Δ\Delta is the operator which maps f(x)f(x) to f(x+1)−f(x)f(x+1)-f(x), then Δn+1\Delta^{n+1} is indeed (n+1)(n+1)-st power of Δ\Delta and the claim follows from the observation that Δ\Delta decreases the power of a polynomial.

In other words, f(x)=∑i=1n+1(−1)i+1(n+1i)f(x+i)f(x) = \sum_{i=1}^{n+1}(-1)^{i+1}\binom{n+1}{i}f(x+i). Applying this for f(x)=(n−x)nf(x) = (n-x)^n, substituting x=−1x = -1 and denoting i=j+1i = j+1 we get

(n+1)n=∑j=0n(−1)j(n+1j+1)(n−j)n=(n+1)∑j=0n(nj)⋅(−1)jj+1⋅(n−j)n.(n+1)^n = \sum_{j=0}^{n}(-1)^j\binom{n+1}{j+1}(n-j)^n = (n+1)\sum_{j=0}^{n}\binom{n}{j}\cdot\frac{(-1)^j}{j+1}\cdot(n-j)^n.
The jj-th summand (nj)⋅(−1)jj+1⋅(n−j)n\binom{n}{j}\cdot\frac{(-1)^j}{j+1}\cdot(n-j)^n may be interpreted as follows: choose jj letters, consider all (n−j)n(n-j)^n words without those letters and sum up (−1)jj+1\frac{(-1)^j}{j+1} over all those words. Now we change the order of summation, counting at first by words. For any fixed word WW with kk absent letters we get ∑j=0k(kj)⋅(−1)jj+1=1k+1⋅∑j=0k(−1)j⋅(k+1j+1)=1k+1\sum_{j=0}^{k}\binom{k}{j}\cdot\frac{(-1)^j}{j+1} = \frac{1}{k+1}\cdot\sum_{j=0}^{k}(-1)^j\cdot\binom{k+1}{j+1} = \frac{1}{k+1}, since the alternating sum of binomial coefficients ∑j=−1k(−1)j⋅(k+1j+1)\sum_{j=-1}^{k}(-1)^j\cdot\binom{k+1}{j+1} vanishes. That is, after changing order of summation we get exactly initial sum, and it equals (n+1)n−1(n+1)^{n-1}.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 2–3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;