Library / NMO Selection Tests for BMO and IMO /8 of 47

NMO Selection Tests for BMO and IMO

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Romania

Let $m$ be a positive integer and let $A$ , respectively $B$ , be an alphabet with $m$ , respectively $2m$ letters. Let $n$ be an even integer greater than or equal to $2m$ . Let $a_n$ be the number of words of length $n$ made of letters from $A$ such that every letter in $A$ occurs a positive even number of times. Let $b_n$ be the number of words of length $n$ made of letters from $B$ such that every letter in $B$ occurs an odd number of times. Determine the ratio $b_n/a_n$ .

Solution

Deletion of all bars in a word in $B^n$ produces a word in $A^n$ . Now let $\alpha$ be a word in $A^n$ and let $a_i$ occur $k_i$ times in $\alpha$ ; the $k_i$ are positive even integers which add up to $n$ . Since there are exactly $2^{k_i-1}$ distinct ways to bar $a_i$ an odd number of times in $\alpha$ , the preimage of $\alpha$ under deletion of all bars has exactly $2^{k_1-1} \cdots 2^{k_m-1} = 2^{n-m}$ elements. The conclusion follows.

Alternative Solution:
The number $a_n$ is the coefficient of $x^n/n!$ in the formal expansion
$A(x) = \left( \sum_{k \ge 1} \frac{x^{2k}}{(2k)!} \right)^m = \left( \frac{(e^x + e^{-x})}{2} - 1 \right)^m = 2^{-m} \left( e^{x/2} - e^{-x/2} \right)^{2m}.$

Similarly, $b_n$ is the coefficient of $x^n/n!$ in the formal expansion
$B(x) = \left( \sum_{k \ge 1} \frac{x^{2k-1}}{(2k-1)!} \right)^{2m} = 2^{-2m} (e^x - e^{-x})^{2m}.$

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.