Sbírka matematických úloh

Znaménko permutace

Úloha číslo: 2450

• Varianta

  \(p=(1\ 3\ 5\ \cdots\ (2n-1)\ 2\ 4\ 6\ \cdots\ 2n)\)

• Nápověda

  Znaménko je rovno paritě počtu inversí.

  Počet inverzí určíme tak, že pro každé \(p(i)\) určíme počet \(p(j):j<i\land p(j)>p(i)\).

  Mnemotechnicky, procházíme posloupnost \(p(1),p(2),\dots\) a ptáme se „kolik je větších čísel v zápisu před \(p(i)\)“.

• Řešení

  Za \(1{,}3,5,\dots,2n-1\) nezapočítáme žádnou inverzi. Za 2 započítáme \(n-1\) inverzí. Za 4 započítáme \(n-2\) inverzí atd až za \(2n\) nezapočítáme žádnou inverzi.

  Celkový počet inverzí je \(0+0+\cdots+0+(n-1)+(n-2)+\cdots+1+0=\sum\limits_{i=1}^{n-1}=\frac{n(n-1)}{2}\)

  Odtud \(sgn(p)=(-1)^{\frac{n(n-1)}{2}}\).

• Odpověď

  Znaménko je kladné pro \(n\equiv 0 \pmod 4\) a \(n\equiv 1 \pmod 4\). Znaménko je záporné pro \(n\equiv 2 \pmod 4\) a \(n\equiv 3 \pmod 4\).

• Varianta

  \(p=(1\ 4\ 7\ \cdots\ (3n-2)\ 2\ 5\ 8\ \cdots\ (3n-1)\ 3\ 6\ 9\ \cdots\ 3n)\)

• Výsledek

  \(sgn(p)=(-1)^{\frac{3n(n-1)}{2}}=(-1)^{\frac{n(n-1)}{2}}\) protože \(3n(n-1)\equiv -n(n-1) \pmod 4\)

  Čili znaménko je kladné pro \(n \bmod 4\in\{0{,}1\}\) a záporné pro \(n \bmod 4\in\{2{,}3\}\).

• Varianta

  \(p=(2\ 5\ 8\ \cdots\ (3n-1)\ 3\ 6\ 9\ \cdots\ 3n\ 1\ 4\ 7\ \cdots\ (3n-2))\)

• Výsledek

  \(sgn(p)=(-1)^{\frac{n(3n+1)}{2}}=(-1)^{\frac{n(n-1)}{2}}\) protože \(3n^2+n \equiv -n^2+n=-n(n-1) \pmod 4\)

  Čili znaménko je kladné pro \(n \bmod 4\in\{0{,}1\}\) a záporné pro \(n \bmod 4\in\{2{,}3\}\).

• Varianta

  \(p=(3\ 6\ 9\ \cdots\ 3n\ 2\ 5\ 8\ \cdots\ (3n-1)\ 1\ 4\ 7\ \cdots\ (3n-2))\)

• Výsledek

  \(sgn(p)=(-1)^{\frac{3n(n+1)}{2}}=(-1)^{\frac{n(n+1)}{2}}\) protože \(3n(n+1)\equiv -n(n+1) \pmod 4\)

  Čili znaménko je kladné pro \(n \bmod 4\in\{0{,}3\}\) a záporné pro \(n \bmod 4\in\{1{,}2\}\).