=====ММ32=====

**Конкурсная задача ММ32** (3 балла)

Рассмотрим векторы, координаты которых в некотором ортонормированном базисе n-мерного пространства представляют собой перестановки множества {1, 2,.., n}. Каким может быть максимальный угол между такими векторами?

**Решение**

Ясно, что надо минимизировать косинус угла между векторами. Произведение модулей векторов постоянно и равно 1+4+...+n<sup>2</sup>. Минимум же скалярного произведения достигается, например, когда один из векторов - (1, 2,.., n), а другой - (n, n-1,.., 1).
Для доказательства рассмотрим выражение 1*a<sub>1</sub>+2*a<sub>2</sub>+...+ n*a<sub>n</sub>, где (a<sub>1</sub>, a<sub>2</sub>,..., a<sub>n</sub>) - некоторая перестановка чисел 1, 2,..., n.
Пусть для некоторых i и j выполняются соотношения i<j и a<sub>i</sub>>a<sub>j</sub>. Тогда, поменяв местами a<sub>i</sub> и a<sub>j</sub> мы уменьшим скалярное произведение на (j-i)*(a<sub>i</sub>-a<sub>j</sub>).\\
Учитывая, что 1+4+...+n2 = n*(n+1)*(2n+1)/6, а
1*n + 2*(n-1) +...+ (n-1)*2+n*1 = n*(n+1)*(n*2)/6, окончательно получим, что наибольший угол между векторами будет равен arccos(n+2)/(2n+1).
Любопытно, что с ростом n этот угол асимптотически приближается к <m>pi/3</m>.

**Награды**

Зп правильное решение этой задачки Влад Франк, Макс Алексеев и Вячеслав Пономарев получают по 3 призовых балла. 
----