Teoria liczbWyzwanieZadanie nr 3850

Największy podzbiór {1, …, 50}, w którym żaden element nie dzieli iloczynu pozostałych

Rozkład na czynniki pierwsze Zadania konkursoweZadania olimpijskiePrzygotowanie do Olimpiady Matematycznej

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\).)

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

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
  1. 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)\).
  2. 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.
  3. 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\).
  4. Zbiór tych \(15\) liczb pierwszych ma żądaną własność: żadna liczba pierwsza nie dzieli iloczynu innych liczb pierwszych.
  5. 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.

Więcej zadań z teorii liczb →

Podobne zadania