Algebra liniowaTrudneZadanie nr 1561

Niepuste podzbiory zbioru {2, 3, …, 20}, których iloczyn jest kwadratem liczby naturalnej

Baza i wymiar Zadania konkursowePoziom pierwszego roku studiów

Ile jest niepustych podzbiorów zbioru \(\{2,3,4,\dots,20\}\), w których iloczyn wszystkich elementów jest kwadratem liczby naturalnej?

+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ę

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
  1. 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\).
  2. 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)\).
  3. Rząd \(E\) wynosi 8: kolumny odpowiadające liczbom pierwszym \(2,3,5,\dots,19\) tworzą bazę standardową \(\mathbb{Z}_2^8\).
  4. Zbiór rozwiązań układu jednorodnego ma wymiar \(19-8=11\), czyli \(2^{11}=2048\) elementów, w tym podzbiór pusty.
  5. 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.

Więcej zadań z algebry liniowej →

Podobne zadania