Teoria liczbWyzwanieZadanie nr 3850
Największy podzbiór {1, …, 50}, w którym żaden element nie dzieli iloczynu pozostałych
Ile co najwyżej elementów może mieć zbiór \(X\subseteq\{1,2,\ldots,50\}\) o własności: żaden element zbioru \(X\) nie jest dzielnikiem iloczynu wszystkich pozostałych elementów \(X\)? (Iloczyn pustego zbioru liczb przyjmujemy za \(1\).)
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Jeśli x nie dzieli iloczynu pozostałych, to dla pewnej liczby pierwszej p wykładnik p w x jest większy niż suma wykładników p w pozostałych elementach. Przypisz każdemu elementowi taką liczbę pierwszą.
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Niech \(x\in X\) nie dzieli iloczynu \(\Pi_x\) pozostałych elementów. Wtedy istnieje liczba pierwsza \(p\) z \(v_p(x)>v_p(\Pi_x)=\sum_{y\ne x}v_p(y)\) (\(v_p\) — wykładnik \(p\) w rozkładzie). W szczególności \(p\mid x\), więc \(p\le50\). Przypiszmy elementowi \(x\) jedną taką liczbę \(p(x)\).
- Jeśli \(p(x)=p(x')=p\) dla \(x\ne x'\), to \(v_p(x)>v_p(x')\) (bo \(x'\) jest wśród „pozostałych” dla \(x\)) oraz symetrycznie \(v_p(x')>v_p(x)\) — sprzeczność. Przypisanie jest różnowartościowe.
- Liczb pierwszych nie większych od \(50\) jest \(15\): \(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47\). Zatem \(|X|\le15\).
- Zbiór tych \(15\) liczb pierwszych ma żądaną własność: żadna liczba pierwsza nie dzieli iloczynu innych liczb pierwszych.
- Odpowiedź: \(15\).
Odpowiedź: \(15\)
Czego warto się nauczyć?
Teoria liczb to podzielność, reszty i cykle potęg — dział, w którym krótki pomysł zastępuje długi rachunek.