Algebra liniowaTrudneZadanie nr 1609
Ranking pięciu szachistów wektorem Perrona przy dwóch remisach w tabeli punktowej
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ą.
Świetnie.
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
- 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.
- 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.
- \(\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\).
- 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.
- 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.
Podobne zadania
- Wyznacznik macierzy 6×6 złożonej z cyklicznych przesunięć ciągu 1, 2, …, 6
- Cykliczny układ z sumami trzech sąsiednich niewiadomych: dla ilu n rozwiązanie jest jedyne
- Ile baz ortonormalnych R⁴ składa się wyłącznie z wektorów postaci (±1, ±1, ±1, ±1)/2
- Macierz incydencji płaszczyzny Fano: różnica rzędu nad R i nad Z₂