Widerspruchsbeweis

Schreibe bei jeder Aufgabe deinen Lösungsweg auf.

1.
Du willst durch Widerspruch beweisen, dass $\sqrt{3}$ irrational ist. Wie lautet die richtige erste Zeile?
1. a)Angenommen, $3$ ist irrational
2. b)Angenommen, $\sqrt{3}$ ist rational
3. c)Angenommen, $\sqrt{3} = 3$
4. d)Angenommen, $\sqrt{3}$ ist irrational
Lösung: Angenommen, $\sqrt{3}$ ist rational
Die Aussage lautet " $\sqrt{3}$ ist irrational", ihre Negation ist also " $\sqrt{3}$ ist rational". Die Aussage selbst anzunehmen wäre ein Zirkelschluss.
2.
Wie viele Personen brauchst du mindestens, damit garantiert zwei von ihnen im selben Monat geboren sind?
Lösung: 13
Bei 12 Personen können alle Monate verschieden sein. Bei 13 bräuchte die Annahme lauter verschiedener Monate 13 Monate, es gibt aber nur 12. Die Antwort ist also $13$ .
3.
Welche Aussage ist für jeden Wahrheitswert von $p$ falsch und damit ein Widerspruch?
1. a) $p \lor \neg p$
2. b) $p \land \neg p$
3. c) $p \Rightarrow p$
4. d) $\neg\neg p$
Lösung: $p \land \neg p$
$p \land \neg p$ verlangt, dass $p$ und sein Gegenteil gleichzeitig wahr sind, was nie passiert, also ist es in jeder Zeile F. $p \lor \neg p$ und $p \Rightarrow p$ sind immer wahr, und $\neg\neg p$ hat denselben Wert wie $p$ .
4.
Jemand behauptet, $N = 100$ sei die größte gerade Zahl. Folge dem Beweis, um zu zeigen, dass die Behauptung falsch ist.
Lösung: 102
1. Schreibe $100 = 2k$ . Was ist $k$ ? 50
2. Was ist $N + 2$ ? 102
3. Schreibe $N + 2 = 2(k + 1)$ . Was ist $k + 1$ ? 51
5.
Im Beweis, dass $\sqrt{2}$ irrational ist, quadrierst du $\sqrt{2} = \frac{a}{b}$ und multiplizierst mit $b^2$ . Du erhältst $a^2 = k \cdot b^2$ . Was ist $k$ ?
Lösung: 2
Quadrieren ergibt $2 = \frac{a^2}{b^2}$ , und Multiplizieren mit $b^2$ ergibt $a^2 = 2b^2$ , also $k = 2$ . Das zeigt, dass $a^2$ gerade ist.
6.
Zeige mit dem Schubfachprinzip, dass in einer Gruppe von 13 Personen ein Geburtsmonat mehrfach vorkommt.
Lösung: 2
1. Wie viele Monate (Schubfächer) gibt es? 12
2. Wie viele Personen können höchstens alle verschiedene Geburtsmonate haben? 12
3. Wenn in jedem Monat eine Person ist, wie viele der 13 Personen bleiben übrig? 1
4. Wie viele Personen hat der vollste Monat also mindestens? 2
7.
Was ist die richtige Negation von "Jede Primzahl ist ungerade"?
1. a)Jede Primzahl ist gerade
2. b)Jede ungerade Zahl ist eine Primzahl
3. c)Keine Primzahl ist ungerade
4. d)Mindestens eine Primzahl ist nicht ungerade
Lösung: Mindestens eine Primzahl ist nicht ungerade
Die Negation von "jede ... ist ungerade" ist "mindestens eine ... ist nicht ungerade". Hier ist die Negation sogar wahr: $2$ ist eine Primzahl, die nicht ungerade ist.
8.
Du willst $x > 5$ durch Widerspruch beweisen. Was nimmst du an?
1. a) $x \le 5$
2. b) $x \ge 5$
3. c) $x \neq 5$
4. d) $x < 5$
Lösung: $x \le 5$
$x > 5$ ist genau dann falsch, wenn $x < 5$ oder $x = 5$ , also $x \le 5$ . Nur $x < 5$ anzunehmen würde den Fall $x = 5$ offen lassen.
9.
In einer Kiste liegen einzelne Handschuhe in 7 verschiedenen Farben. Wie viele Handschuhe musst du blind nehmen, um sicher zwei derselben Farbe zu haben?
Lösung: 8
7 Handschuhe können alle verschiedene Farben haben. Bei 8 bräuchte die Annahme lauter verschiedener Farben 8 Farben, es gibt aber nur 7. Also garantieren $8$ Handschuhe ein Paar.
10.
Zeige mit dem Taschenrechner, dass $\sqrt{2}$ echt zwischen $1{,}4142$ und $1{,}4143$ liegt und somit keiner der beiden Zahlen gleich ist.
Lösung: 0
1. Was ist $1{,}4142^2$ ? 1.99996164
2. Was ist $1{,}4143^2$ ? 2.00024449
3. Wie viele dieser beiden Quadrate sind genau gleich 2? 0
11.
Jemand behauptet, $\frac{1}{1000}$ sei die kleinste positive rationale Zahl. Halbiere sie wie im Beweis. Welche kleinere positive rationale Zahl erhältst du? Schreibe sie als Bruch.
Lösung: 1/2000
$\frac{1}{1000} : 2 = \frac{1}{2000}$ , das ist positiv, rational und kleiner als $\frac{1}{1000}$ . Die Behauptung ist also falsch, und derselbe Trick funktioniert bei jedem Kandidaten.
12.
Wie viele Personen garantieren, dass zwei von ihnen am selben Tag Geburtstag haben (Tag und Monat), wenn der 29. Februar als möglicher Geburtstag zählt?
Lösung: 367
1. Wie viele mögliche Geburtstage gibt es, einschließlich des 29. Februar? 366
2. Wie viele Personen können höchstens alle verschiedene Geburtstage haben? 366
3. Wie viele Personen garantieren einen gemeinsamen Geburtstag? 367
13.
Führe Euklids Beweis mit der Primzahlliste $2, 3, 5$ durch: Bilde $N = 2 \cdot 3 \cdot 5 + 1$ und prüfe, dass keine Primzahl der Liste sie teilt.
Lösung: 31
1. Was ist $2 \cdot 3 \cdot 5$ ? 30
2. Was ist $N = 2 \cdot 3 \cdot 5 + 1$ ? 31
3. Welcher Rest bleibt, wenn du $31$ durch $3$ teilst? 1
4. Welcher Rest bleibt, wenn du $31$ durch $5$ teilst? 1
14.
Berechne in Euklids Beweis $N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1$ für die ersten fünf Primzahlen.
Lösung: 2311
$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310$ , also $N = 2311$ . Beim Teilen von $2311$ durch 2, 3, 5, 7 oder 11 bleibt immer der Rest 1, also stehen ihre Primfaktoren nicht auf der Liste (hier ist $2311$ zufällig selbst eine Primzahl).
15.
Mit den Primzahlen $2, 3, 5, 7, 11, 13$ ist Euklids Zahl $N = 30031 = 59 \times 509$ , also keine Primzahl. Was bedeutet das für den Beweis?
1. a)Der Beweis scheitert, weil $N$ keine Primzahl ist
2. b)Es gibt nur sechs Primzahlen
3. c) $N$ hat Primfaktoren, die nicht auf der Liste stehen, also funktioniert der Beweis
4. d) $59$ ist die größte Primzahl
Lösung: $N$ hat Primfaktoren, die nicht auf der Liste stehen, also funktioniert der Beweis
Der Beweis behauptet nie, dass $N$ eine Primzahl ist. Er braucht nur einen Primfaktor von $N$ , der auf der Liste fehlt, und $59$ und $509$ sind genau solche Primzahlen. Der Beweis funktioniert also weiterhin.
16.
Folge dem Beweis, dass $\sqrt{2}$ irrational ist. Nimm $\sqrt{2} = \frac{a}{b}$ vollständig gekürzt an und setze die Zahlen ein.
Lösung: 2
1. Quadrieren ergibt $a^2 = m \cdot b^2$ . Was ist $m$ ? 2
2. $a$ ist gerade, also $a = 2k$ . Dann ist $a^2 = m \cdot k^2$ . Was ist $m$ ? 4
3. Aus $4k^2 = 2b^2$ folgt $b^2 = m \cdot k^2$ . Was ist $m$ ? 2
4. Durch welche Zahl sind $a$ und $b$ also beide teilbar? 2
17.
Beweise auf dieselbe Weise, dass $\sqrt{3}$ irrational ist. Nimm $\sqrt{3} = \frac{a}{b}$ vollständig gekürzt an und setze die Zahlen ein. Verwende: Teilt eine Primzahl $a^2$ , dann teilt sie $a$ .
Lösung: 3
1. Quadrieren ergibt $a^2 = m \cdot b^2$ . Was ist $m$ ? 3
2. $3$ teilt $a$ , also $a = 3k$ . Dann ist $a^2 = m \cdot k^2$ . Was ist $m$ ? 9
3. Aus $9k^2 = 3b^2$ folgt $b^2 = m \cdot k^2$ . Was ist $m$ ? 3
4. Durch welche Primzahl sind $a$ und $b$ also beide teilbar? 3
18.
Führe Euklids Beweis mit den Primzahlen $2, 3, 5, 7, 11, 13$ durch und finde die Primfaktoren von $N$ .
Lösung: 509
1. Was ist $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13$ ? 30030
2. Was ist $N$ , das Produkt plus 1? 30031
3. Welcher Rest bleibt, wenn du $N$ durch $13$ teilst? 1
4. $N = 59 \times q$ . Was ist $q$ ? 509