Algebra liniowaTrudneZadanie nr 1609

Ranking pięciu szachistów wektorem Perrona przy dwóch remisach w tabeli punktowej

Sieci i rankingi Poziom pierwszego roku studiów

W turnieju każdy z pięciu zawodników rozegrał jedną partię z każdym innym. Zawodnik 1 pokonał 5 i przegrał z 2, 3, 4. Zawodnik 2 pokonał 1 i 4, przegrał z 3 i 5. Zawodnik 3 pokonał 1 i 2, przegrał z 4 i 5. Zawodnik 4 pokonał 1 i 3, przegrał z 2, zremisował z 5. Zawodnik 5 pokonał 2 i 3, przegrał z 1, zremisował z 4.

Tworzymy macierz \(A\) wymiaru \(5\times5\): \(a_{ij}=1\), gdy \(i\) wygrał z \(j\), \(a_{ij}=\frac12\) przy remisie, \(a_{ij}=0\) przy porażce \(i\) oraz \(a_{ii}=0\). Siły zawodników to współrzędne wektora Perrona macierzy \(A\) (wektora własnego o dodatnich współrzędnych, odpowiadającego największej wartości własnej).

Uporządkuj zawodników od najsilniejszego do najsłabszego i zapisz ich numery w tej kolejności jako liczbę pięciocyfrową.

+16 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

Jak rozwiązać to zadanie?

Potrzebujesz pomocy? Pokaż wskazówkę

Wektor Perrona można przybliżać iteracją: zacznij od wektora jedynek i wielokrotnie mnóż przez \(A\). Pierwszy krok daje zwykłą tabelę punktów, a kolejne rozstrzygają równości punktowe, premiując zwycięstwa nad silnymi rywalami.

Chcesz poznać sposób? Rozwiązanie krok po kroku
  1. Macierz wyników: \(A=\begin{pmatrix}0&0&0&0&1\\1&0&0&1&0\\1&1&0&0&0\\1&0&1&0&\frac12\\0&1&1&\frac12&0\end{pmatrix}\). Graf zwycięstw jest silnie spójny (np. \(1\to5\to2\to1\), \(2\to4\to3\to1\)), więc wektor Perrona jest jedyny i ma dodatnie współrzędne.
  2. Iteracja od \(\mathbf r_0=(1,1,1,1,1)\): \(\mathbf r_1=A\mathbf r_0=\left(1,2,2,\frac52,\frac52\right)\) — to punkty; zawodnicy 4 i 5 oraz 2 i 3 są równi.
  3. \(\mathbf r_2=A\mathbf r_1=\left(\frac52,\frac72,3,\frac{17}{4},\frac{21}{4}\right)\), \(\mathbf r_3=\left(\frac{21}{4},\frac{27}{4},6,\frac{65}{8},\frac{69}{8}\right)\), \(\mathbf r_4=\left(\frac{69}{8},\frac{107}{8},12,\frac{249}{16},\frac{269}{16}\right)\) — od drugiego kroku kolejność się nie zmienia: \(5>4>2>3>1\).
  4. Granica: największa wartość własna \(\lambda\approx1{,}891\), a znormalizowany wektor Perrona \(\mathbf r\approx(0{,}137;\ 0{,}196;\ 0{,}176;\ 0{,}234;\ 0{,}258)\). Zawodnik 5 wyprzedza 4, bo pokonał silniejszych (2 i 3), a 2 wyprzedza 3 dzięki zwycięstwu nad 4.
  5. Kolejność od najsilniejszego: \(5, 4, 2, 3, 1\), czyli liczba \(54231\).

Odpowiedź: \(54231\)

Czego warto się nauczyć?

Algebra liniowa to język geometrii i fizyki kwantowej: wektory, macierze i przekształcenia. W zadaniach mnożysz macierze, liczysz wyznaczniki i wartości własne, rozwiązujesz układy równań i opisujesz obroty, rzuty i symetrie.

Więcej zadań z algebry liniowej →

Podobne zadania