International Mathematics Competition for University StudentsJuly 27  Aug 2 2015, Blagoevgrad, Bulgaria  
Day 1
Day 2
Results
Download

Problem 88. Consider all $26^{26}$ words of length 26 in the Latin alphabet. Define 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}$. Proposed by Fedor Petrov, St. Petersburg State University Solution 1. Let $n=26$, then $3^{75}=(n+1)^{n1}$. We use the following wellknown Lemma. If $f(x)$ is a polynomial of degree at most $n$, then its $(n+1)$st finite difference vanishes: $\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)$ to $f(x+1)f(x)$, then $\Delta^{n+1}$ is indeed $(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)=\sum_{i=1}^{n+1} (1)^{i+1}\binom{n+1}{i} f(x+i)$. Applying this for $f(x)=(nx)^n$, substituting $x=1$ and denoting $i=j+1$ we get $$ (n+1)^n=\sum_{j=0}^n (1)^j \binom{n+1}{j+1} (nj)^n=(n+1) \sum_{j=0}^n \binom{n}{j}\cdot \frac{(1)^j}{j+1}\cdot (nj)^n. $$ The $j$th summand $\binom{n}{j}\cdot \frac{(1)^j}{j+1}\cdot (nj)^n$ may be interpreted as follows: choose $j$ letters, consider all $(nj)^n$ words without those letters and sum up $\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 $W$ with $k$ absent letters we get $\sum_{j=0}^k \binom{k}{j}\cdot \frac{(1)^j}{j+1}=\frac1{k+1}\cdot \sum_{j=0}^k (1)^j\cdot \binom{k+1}{j+1}=\frac1{k+1}$, since the alternating sum of binomial coefficients $\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)^{n1}$. Solution 2 (based on students' papers). Define by $W$ the set of all $26$strings of Latin letters, and let $W^*$ be the set of all $25$strings of the alphabet $\{A,B,\ldots,Z,*\}$. For any string in $W$ or $W^*$, denote by $\ell(w)$ the number of different Latin letters (excluding stars) in $w$. According the definition, the weight of any word $w\in W$ is $\frac{1}{27\ell(w)}$. Define a map $\varphi:W\to W^*$ in the following way. Suppose that $w\in W$ is an arbitrary $26$string and $x$ is its first letter. Remove the leading $x$ from $w$ and replace all other occurences of $x$ by the character $*$. Let $\varphi(w)\in W^*$ be the resulting $25$string. Notice that the number of different Latin letters decreases by $1$, so we have $\ell(\varphi(w))=\ell(w)1$. The map $\varphi$ is not injective. For every $u\in W^*$, as $u$ contains $\ell(u)$ different characters, there are $26\ell(u)$ different Latin letters that are not used in $u$, there are $26\ell(u)$ possible preimages of $u$. The preimages of $u$ contain $\ell(u)+1$ Latin letters, so their weights are equal to $\frac{1}{26\ell(u)}$. Hence, the total weight of the preimages of $u$ is equal to $1$. Therefore, the total weight of the words in $W$ is equal to the number of strings in $W^*$, which is $W^*=27^{25}$. 