Algebra liniowaTrudneZadanie nr 1561
Niepuste podzbiory zbioru {2, 3, …, 20}, których iloczyn jest kwadratem liczby naturalnej
Ile jest niepustych podzbiorów zbioru \(\{2,3,4,\dots,20\}\), w których iloczyn wszystkich elementów jest kwadratem liczby naturalnej?
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Przypisz każdej liczbie wektor parzystości wykładników w jej rozkładzie na czynniki pierwsze (współrzędne w ciele Z₂). Podzbiory o iloczynie kwadratowym odpowiadają rozwiązaniom jednorodnego układu równań liniowych nad Z₂.
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Liczba jest kwadratem wtedy i tylko wtedy, gdy każda liczba pierwsza występuje w niej w parzystej potędze. Liczbom \(2,\dots,20\) przypisujemy wektory \(\varepsilon(n)\in\mathbb{Z}_2^8\) – parzystości wykładników przy \(2,3,5,7,11,13,17,19\).
- Iloczyn liczb z podzbioru \(S\) jest kwadratem \(\iff\sum_{n\in S}\varepsilon(n)=0\). Podzbiory utożsamiamy z wektorami \(s\in\mathbb{Z}_2^{19}\); warunek to \(Es=0\) dla macierzy \(E\) wymiaru \(8\times19\) o kolumnach \(\varepsilon(n)\).
- Rząd \(E\) wynosi 8: kolumny odpowiadające liczbom pierwszym \(2,3,5,\dots,19\) tworzą bazę standardową \(\mathbb{Z}_2^8\).
- Zbiór rozwiązań układu jednorodnego ma wymiar \(19-8=11\), czyli \(2^{11}=2048\) elementów, w tym podzbiór pusty.
- Niepustych podzbiorów o iloczynie kwadratowym jest \(2^{11}-1=2047\).
Odpowiedź: \(2047\)
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
- Ranking pięciu szachistów wektorem Perrona przy dwóch remisach w tabeli punktowej
- Ile baz ortonormalnych R⁴ składa się wyłącznie z wektorów postaci (±1, ±1, ±1, ±1)/2