uniolympiads Ελληνικά

IMC 2015, Day 2, Problem 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}.

Original from the official 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.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(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}.

Transcribed from the official solutions, pages 2–3. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?