TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 197

Wieviele natürliche Zahlen n mit $1 \leq n \leq 10^6$ gibt es, die weder durch 2 teilbar, noch Quadratzahlen, noch dritte, noch vierte Potenz einer natürlichen Zahl sind?

Lösungsvorschlag von mnemetz

$n = 10^6$

• $a \in A:$ a ist gerade
• $b \in B: b = x^2$
• $c \in C: c = x^3$
• $d \in D: d = x^4$

D fällt weg, denn irgendwas hoch 4 ist ja auch irgendwas hoch 2:

• $x * x * x * x = x^4$
• $y = x * x = x^2$
• $\Rightarrow y^2 = x * x * x * x = x^4$

Berechnung der Anzahl der Elemente in Menge A:

die Hälfte aller Zahlen von 1 bis 10^6 ist gerade:

$|A| = 10^6 / 2 = 500000$

Berechnung der Anzahl der Elemente in Menge B:

$|B| = \sqrt[2]{10^6}=10^3$

Berechnung der Anzahl der Elemente in Menge C:

$|C| = \sqrt[3]{10^6}=10^2$

Berechnung der Anzahl der Elemente in Menge $A \cap B$:

Jede gerade Zahl hoch x ist gerade, jede ungerade Zahl hoch x ist ungerade $\Rightarrow$ die Hälfte aller Zahlen aus B.

$|A \cap B| = \frac{|B|}{2} = \frac{10^3}{2} = 500$

Berechnung der Anzahl der Elemente in Menge $B \cap C$:

Welche $x^2$ sind ein $y^3$? Jedes $z^6$ ist ein $x^2$ oder ein $y^3$ $\Rightarrow$: Ermittlung aus dem kgV der Hochzahlen!

$|B \cap C| = \sqrt[6]{10^6}=10^1 = 10$

Berechnung der Anzahl der Elemente in Menge $A \cap C$:

(Wie bei $A \cap B$)

$|A \cap C| = \frac{|C|}{2} = \frac{10^2}{2} = 50$

Berechnung der Anzahl der Elemente in Menge $A \cap B \cap C$: Ist ja wie $A \cap (B \cap C)$ und $B \cap C$ ist ja wie für $x^6$.

$|A \cap B \cap C| = \frac{|B \cap C|}{2} = \frac{10}{2} = 5$

Die Anzahl der Elemente im "Universum" ist: $|E| = 10^6$

Es ist nun die Anzahl der Elemente die in keiner der Mengen A,B,C liegen gesucht, also $|A' \cap B' \cap C'|$.

Diese lässt sich nun mittels des Inklusions-Exklusions-Prinzip berechnen:

$|A' \cap B' \cap C'| = |E| - |A| - |B| - |C| + |A \cap B| + |A \cap C| + |B \cap C| - |A \cap B \cap C| = 10^6 - 500000 - 1000 - 100 + 500 + 50 + 10 - 5 = 499455$

Links zu ähnlichen Aufgaben

TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 161