A Permutation Teaser

By AM-GM, $a_{i}+i \geq 2\sqrt {ia_{i}}$ with equality only if $a_{i}=i, i=1, 2, 3, ..., 6$ . Hence the product is always greater than or equal to $\sqrt {1×2×3×4×5×6×a_{1}×a_{2}×...×a_{6}}= 6!$

However equality can occur (by AM-GM) iff $a_{i}=i$ for $i=1, 2, ..., 6$ . The other $6!-1$ permutations thus satisfy the condition and the answer is $6!-1=719$ .

The general answer for the number of permutations of $\{1,2,\ldots,n\}$ that satisfy $\frac{a_1+1}{2}\cdots\frac{a_n+n}{2}\gt n!$ is $n! -1$ , and here is an inductive proof.

The solution is easily confirmed for $n=2$ .

Assume the solution is correct for $n=k-1$ . For the $n=k$ case, division by $k$ shows that the inequality holds for all non-trivial permutations with $a_{k}=k$ .

Next, assume we have a permutation where $k=a_i$ with $i<k$ . Then by the above paragraph, it suffices to show that $\frac{a_1+1}{2}\cdots\frac{a_{k}+k}{2}\gt\frac{a_1+1}{2}\cdots \frac{a_{k}+i}{2}\cdots\frac{k+k}{2}$ where the second expression is gotten from the first by swapping $a_i$ and $a_{k}$ , and letting all other terms stay.

Cancelling equal terms and multiplying by $4$ , this is equivalent to $(k+i)(a_{k} +k)\gt (a_{k}+i)((k+k)$ Distributing and simplifying gives $k^2+ia_k\gt ka_k + ik$ which is true by the rearrangement inequality.

By simple observation, one could say that, smallest possible arrangement satisfying the condition is 123456 rest all permutations would result in a greater number hence the answer would be 6!-1