Maths Olympiad Prep

Library / /291 of 520

Combinatorics Difficulty 6.8 National olympiad Find the answer

3. 23 Given the numbers 1,2,22,,2n11,2,2^{2}, \cdots, 2^{n-1}, for any permutation σ=(x1\sigma=\left(x_{1}\right., x2,,xn)\left.x_{2}, \cdots, x_{n}\right) of them, define S1(σ)=x1,S2(σ)=x1+x2,S3(σ)=x1+x2+S_{1}(\sigma)=x_{1}, S_{2}(\sigma)=x_{1}+x_{2}, S_{3}(\sigma)=x_{1}+x_{2}+ x3,,Sn(σ)=x1+x2++xnx_{3}, \cdots, S_{n}(\sigma)=x_{1}+x_{2}+\cdots+x_{n}, and let Q(σ)=S1(σ)Q(\sigma)=S_{1}(\sigma) \cdot S2(σ)Sn(σ)S_{2}(\sigma) \cdots S_{n}(\sigma), try to find 1Q(σ)\sum \frac{1}{Q(\sigma)} (the sum is taken over all permutations).

A number or a short expression. Spacing and $ signs are ignored.

Solution

[Solution] We prove a more general conclusion:
For any nn positive numbers a1,a2,,ana_{1}, a_{2}, \cdots, a_{n}, the sum 1Q(σ)=\sum \frac{1}{Q(\sigma)}= S(a1,a2,,an)=1a1a2anS\left(a_{1}, a_{2}, \cdots, a_{n}\right)=\frac{1}{a_{1} a_{2} \cdots a_{n}}.

We use induction on nn.
When n=1n=1, S(a1)=1Q(σ)=1a1S\left(a_{1}\right)=\sum \frac{1}{Q(\sigma)}=\frac{1}{a_{1}}, so the conclusion holds for n=1n=1.
Assume the conclusion holds for n=kn=k. We will prove it for n=k+1n=k+1.
Indeed, the (k+1)(k+1) numbers a1,a2,,ak,ak+1a_{1}, a_{2}, \cdots, a_{k}, a_{k+1} can be divided into k+1k+1 classes, each containing k!k! permutations that end with the same element aia_{i}. The last factor of Q(σ)Q(\sigma) for these permutations is Sk+1(σ)=a1+a2++ak+ak+1S_{k+1}(\sigma)=a_{1}+a_{2}+\cdots+a_{k}+a_{k+1}. The first kk factors are given by all possible permutations of the other kk elements.

By the induction hypothesis, the sum of 1Q(σ)\frac{1}{Q(\sigma)} for these k!k! permutations is
aia1a2akak+1Sk+1(σ)\frac{a_{i}}{a_{1} a_{2} \cdots a_{k} a_{k+1} S_{k+1}(\sigma)}

Summing over ii gives
1Q(σ)=S(a1,a2,,ak+1)=1a1a2akak+1Sk+1(σ)i=1k+1ai=1a1a2akak+1\begin{aligned} \sum \frac{1}{Q(\sigma)} & =S\left(a_{1}, a_{2}, \cdots, a_{k+1}\right) \\ & =\frac{1}{a_{1} a_{2} \cdots a_{k} a_{k+1} S_{k+1}(\sigma)} \cdot \sum_{i=1}^{k+1} a_{i} \\ & =\frac{1}{a_{1} a_{2} \cdots a_{k} a_{k+1}} \end{aligned}

By the principle of mathematical induction, the general conclusion holds.
Thus, the result for this problem is
1Q(σ)=112222n1=2n(n1)2\sum \frac{1}{Q(\sigma)}=\frac{1}{1 \cdot 2 \cdot 2^{2} \cdots 2^{n-1}}=2^{-\frac{n(n-1)}{2}}

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

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.