Ile liczb 3-cyfrowych zawiera co najmniej jedną z cyfr 2 lub 3?
🚀 Krok 1: Określamy zakres liczb 3-cyfrowych:
Najmniejsza liczba: 100, największa: 999
Ilość wszystkich liczb:
\[
999 - 100 + 1 = 900
\]
(dodajemy 1, bo wliczamy obie końcowe wartości)
🚀 Krok 2: Obliczamy liczby bez cyfr 2 i 3.
Analizujemy każdą cyfrę osobno:
① Cyfra setek:
Możliwe cyfry: {1, 4, 5, 6, 7, 8, 9} (cyfry 2 i 3 wykluczone, 0 niedozwolone)
Liczba możliwości: 7
② Cyfra dziesiątek:
Możliwe cyfry: {0, 1, 4, 5, 6, 7, 8, 9} (cyfry 2 i 3 wykluczone)
Liczba możliwości: 8
③ Cyfra jedności:
Analogicznie do dziesiątek: {0, 1, 4, 5, 6, 7, 8, 9}
Liczba możliwości: 8
🚀 Krok 3: Mnożymy możliwości dla każdej pozycji:
\[
7 \times 8 \times 8 = 448
\]
Sprawdzenie: \(7 \times 8 = 56\), \(56 \times 8 = 448\) ✓
🚀 Krok 4: Obliczamy liczby zawierające cyfrę 2 lub 3:
\[
900\text{ (wszystkie)} - 448\text{ (bez 2 i 3)} = 452
\]
Weryfikacja:
Przykład dla liczby 100:
Cyfry: 1, 0, 0 – brak 2 i 3 ✓
Przykład dla liczby 123:
Cyfry: 1, 2, 3 – zawiera 2 i 3 ✓
Ostateczny wynik: \(\boxed{452}\)
Korzystając z zasady włączeń i wyłączeń oblicz, ile liczb całkowitych większych od 0 i mniejszych od 100 nie jest podzielnych przez 4 ani przez 6.
🚀 Krok 1: Określamy zakres:
Liczby całkowite większe od 0 i mniejsze od 100 to
\(\{1, 2, 3, \dots, 99\}\) → 99 liczb
🚀 Krok 2: Liczby podzielne przez 4:
Pierwsza liczba: 4 (\(4 \times 1\)), ostatnia: 96 (\(4 \times 24\))
Ilość:
\[
\left\lfloor \frac{99}{4} \right\rfloor = 24
\]
Sprawdzenie: \(4 \times 24 = 96 \le 99\) ✓
🚀 Krok 3: Liczby podzielne przez 6:
Pierwsza: 6 (\(6 \times 1\)), ostatnia: 96 (\(6 \times 16\))
Ilość:
\[
\left\lfloor \frac{99}{6} \right\rfloor = 16
\]
Sprawdzenie: \(6 \times 16 = 96 \le 99\) ✓
🚀 Krok 4: Liczby podzielne przez 4 i 6 (NWW = 12):
Pierwsza: 12 (\(12 \times 1\)), ostatnia: 96 (\(12 \times 8\))
Ilość:
\[
\left\lfloor \frac{99}{12} \right\rfloor = 8
\]
Obliczenie NWW:
\[
\mathrm{NWW}(4,6) = \frac{4 \times 6}{\gcd(4,6)} = \frac{24}{2} = 12
\]
✓
🚀 Krok 5: Zastosuj zasadę włączeń i wyłączeń:
\[
|A \cup B| = |A| + |B| - |A \cap B| = 24 + 16 - 8 = 32
\]
(Najpierw sumujemy, potem odejmujemy liczby liczone podwójnie)
🚀 Krok 6: Obliczamy liczby niepodzielne:
\[
99\text{ (wszystkie)} - 32\text{ (podzielne)} = 67
\]
Test dla n = 12:
\(12 \div 4 = 3\) ✓, \(12 \div 6 = 2\) ✓
Liczba 12 jest liczona tylko raz (w \(|A \cap B|\)) ✓
Ostateczny wynik: \(\boxed{67}\)
Korzystając z rozszerzonego algorytmu Euklidesa wyznacz element odwrotny do elementu \(a = 17\) w pierścieniu \(\mathbb{Z}_{40}\).
🚀 Krok 1: Znajdź \(\gcd(17, 40)\) używając algorytmu Euklidesa
① \[ 40 = 2 \times 17 + 6 \quad (\text{reszta } 6) \]
② \[ 17 = 2 \times 6 + 5 \quad (\text{reszta } 5) \]
③ \[ 6 = 1 \times 5 + 1 \quad (\text{reszta } 1) \]
④ \[ 5 = 5 \times 1 + 0 \quad \Rightarrow \gcd(17,40)=1 \]
🚀 Krok 2: Rozszerzamy algorytm do tyłu:
\[ \begin{aligned} 1 &= 6 - 1 \times 5 \\ &= 6 - 1 \times \bigl(17 - 2 \times 6\bigr) \quad (\text{z kroku ②})\\ &= 3 \times 6 - 1 \times 17 \\ &= 3 \times \bigl(40 - 2 \times 17\bigr) - 1 \times 17 \quad (\text{z kroku ①})\\[1mm] &= 3 \times 40 - 7 \times 17 \end{aligned} \]
🚀 Krok 3: Odczytujemy współczynniki:
Mamy:
\[
1 = 3 \times 40 - 7 \times 17
\]
W modulo 40: \(-7 \times 17 \equiv 1 \pmod{40}\), czyli
\[
x = -7.
\]
🚀 Krok 4: Znajdź dodatni odpowiednik:
\[
-7 \mod 40 = 40 - 7 = 33.
\]
Sprawdzenie: \(17 \times 33 = 561\) oraz \(561 \mod 40 = 1\) ✓
Element odwrotny: \(\boxed{33}\)
Zbadaj własności relacji \(R \subseteq \mathbb{R} \times \mathbb{R}\) (zwrotność, symetrię, przechodniość, antysymetrię).
Definicje własności relacji:
Uwaga: Konkretna postać relacji nie została podana w zadaniu.
Rozwiąż układ równań rekurencyjnych:
\(T(1) = 1\)
\(T(n) = 8T\Bigl(\frac{n}{2}\Bigr) + n^2\) dla \(n \ge 2\)
🚀 Krok 1: Identyfikacja parametrów Master Theorem:
Postać równania: \(T(n) = a\,T(n/b) + f(n)\)
W naszym przypadku: \(a = 8\), \(b = 2\), \(f(n) = n^2\)
🚀 Krok 2: Oblicz \(n^{\log_b a}\):
\(\log_2 8 = 3\) (ponieważ \(2^3 = 8\))
Zatem:
\[
n^{\log_2 8} = n^3.
\]
🚀 Krok 3: Porównaj z \(f(n) = n^2\):
Mamy: \(n^2\) vs \(n^3\).
Ponieważ \(n^2 = O(n^{3 - \varepsilon})\) dla \(\varepsilon = 1\),
🚀 Krok 4: Stosujemy przypadek 1 Master Theorem:
Gdy \(f(n) = O(n^{\log_b a - \varepsilon})\) dla \(\varepsilon > 0\),
wtedy:
\[
T(n) = \Theta\Bigl(n^{\log_b a}\Bigr) = \Theta(n^3).
\]
Test dla małych \(n\):
Dla \(n = 2\): \(T(2) = 8T(1) + 4 = 8 \times 1 + 4 = 12\)
Dla \(n = 4\): \(T(4) = 8T(2) + 16 = 8 \times 12 + 16 = 112\)
Wzrost zgodny z \(n^3\) (mimo stałych): \(2^3 = 8\), \(4^3 = 64\).
Rozwiązanie: \(\boxed{\Theta(n^3)}\)