Diskrete Mathematik - Exam.pdf

Aufgabe 1)

Gegeben sei der Graph G = (V, E) mit den Knoten V = {A, B, C, D, E} und Kanten E = { (A, B), (A, C), (B, C), (C, D), (D, E), (E, A) }.

• Zeichne diesen Graphen und beschrifte die Knoten und Kanten entsprechend.

a)

1.

• Beschreibe einen möglichen Pfad von Knoten A zu Knoten D und gib die dazugehörige Knotenfolge an.

Lösung:

Gegeben sei der Graph G = (V, E) mit den Knoten V = {A, B, C, D, E} und Kanten E = { (A, B), (A, C), (B, C), (C, D), (D, E), (E, A) }.

• Zeichne diesen Graphen und beschrifte die Knoten und Kanten entsprechend.

Um den Graphen zu zeichnen, kannst Du die Knoten A, B, C, D und E anordnen und die Kanten {(A, B), (A, C), (B, C), (C, D), (D, E), (E, A)} einzeichnen. Eine mögliche Darstellung könnte wie folgt aussehen:

• A -- B
• A -- C
• B -- C
• C -- D
• D -- E
• E -- A

Löse die folgende Teilaufgabe:

1.

• Beschreibe einen möglichen Pfad von Knoten A zu Knoten D und gib die dazugehörige Knotenfolge an.

Lösung:

Ein möglicher Pfad von Knoten A zu Knoten D in dem gegebenen Graphen ist:

• Startknoten: A
• Nächster Knoten: C (über die Kante (A, C))
• Nächster Knoten: D (über die Kante (C, D))

Die dazugehörige Knotenfolge lautet: A - C - D

b)

2.

• Bestimme, ob es in diesem Graphen einen Zyklus gibt. Wenn ja, gib mindestens einen Zyklus an und erkläre, warum es ein Zyklus ist.

Lösung:

Gegeben sei der Graph G = (V, E) mit den Knoten V = {A, B, C, D, E} und Kanten E = { (A, B), (A, C), (B, C), (C, D), (D, E), (E, A) }.

• Zeichne diesen Graphen und beschrifte die Knoten und Kanten entsprechend.

Um den Graphen zu zeichnen, kannst Du die Knoten A, B, C, D und E anordnen und die Kanten {(A, B), (A, C), (B, C), (C, D), (D, E), (E, A)} einzeichnen. Eine mögliche Darstellung könnte wie folgt aussehen:

• A -- B
• A -- C
• B -- C
• C -- D
• D -- E
• E -- A

Löse die folgende Teilaufgabe:

2.

• Bestimme, ob es in diesem Graphen einen Zyklus gibt. Wenn ja, gib mindestens einen Zyklus an und erkläre, warum es ein Zyklus ist.

Lösung:

Ja, in diesem Graphen gibt es einen Zyklus. Ein Zyklus ist ein Pfad, der bei einem Knoten beginnt und endet, ohne einen Knoten mehr als einmal zu durchlaufen (außer dem Start- und Endknoten).

Ein Beispiel für einen Zyklus in diesem Graphen ist: A - B - C - A

• Startknoten: A
• Nächster Knoten: B (über die Kante (A, B))
• Nächster Knoten: C (über die Kante (B, C))
• Rückkehr zum Startknoten: A (über die Kante (A, C))

Dieser Weg erfüllt die Bedingungen eines Zyklus, da er bei Knoten A beginnt und endet, ohne unterwegs einen anderen Knoten doppelt zu besuchen (außer A).

Ein weiterer möglicher Zyklus ist: A - C - D - E - A

• Startknoten: A
• Nächster Knoten: C (über die Kante (A, C))
• Nächster Knoten: D (über die Kante (C, D))
• Nächster Knoten: E (über die Kante (D, E))
• Rückkehr zum Startknoten: A (über die Kante (E, A))

Auch dieser Weg erfüllt die Bedingungen eines Zyklus, da er bei Knoten A beginnt und endet, ohne einen anderen Knoten doppelt zu besuchen (außer dem Startknoten A).

Aufgabe 2)

Gegeben sei ein ungewichteter, zusammenhängender Graph G = (V, E) mit den Knoten V = \{ A, B, C, D, E, F, G, H\} und den Kanten E = \{ (A, B), (A, C), (B, D), (B, E), (C, F), (C, G), (D, H), (E, H), (F, H), (G, H) \}. Der Graph wird durch eine Adjazenzliste repräsentiert. Nachfolgend sind die Adjazenzlisten für jeden Knoten dargestellt:

• A: [B, C]
• B: [A, D, E]
• C: [A, F, G]
• D: [B, H]
• E: [B, H]
• F: [C, H]
• G: [C, H]
• H: [D, E, F, G]

a)

1. Führe die Tiefensuche (Depth-First Search, DFS) auf dem gegebenen Graphen G aus, beginnend bei Knoten A. Zeichne den resultierenden DFS-Baum und die Reihenfolge der Knotenbesuche auf.

Lösung:

Um d ie Tiefensuche (Depth-First Search, DFS) durchzuführen, beginnen wir mit dem Startknoten A und durchlaufen den Graphen wie folgt:

• Beginne bei Knoten A.
• Besuche den Knoten B, da er der erste unbesuchte Nachbar von A ist.
• Von B aus besuchen wir den Knoten D, da er der erste unbesuchte Nachbar von B ist.
• Von D aus besuchen wir den Knoten H, da er der erste unbesuchte Nachbar von D ist. Nun hat H folgende Nachbarn: D, E, F, G. Aber D ist bereits besucht.
• Von H aus besuchen wir den Knoten E, da er der erste unbesuchte Nachbar von H ist. Hier sind die Nachbarn von E: B, H. Beide sind bereits besucht.
• Zurück zu H und besuchen wir den Knoten F als nächsten unbesuchten Nachbarn.
• Von F aus gibt es keine unbesuchten Nachbarn mehr (alle Knoten sind bereits besucht: C, H), also gehen wir zurück zu H.
• Von H aus besuchen wir nun G.
• Von G gibt es auch keine unbesuchten Nachbarn mehr (nur C und H, die bereits besucht sind), also gehen wir zurück zu H und danach zu D, und schließlich zurück zu B.
• Zurück zu B und als letzten unbesuchten Nachbarn besuchen wir C.
• Von C aus gibt es keine unbesuchten Nachbarn mehr, außer A, F, und G, die bereits alle besucht sind.
• Jetzt sind alle Knoten besucht.

Die Reihenfolge der besuchten Knoten ist somit:

A, B, D, H, E, F, G, C

Der resultierende DFS-Baum sieht wie folgt aus:

 A | B | D | H / \ \  E F G C

b)

2. Führe die Breitensuche (Breadth-First Search, BFS) auf dem gegebenen Graphen G aus, beginnend bei Knoten A. Zeichne den resultierenden BFS-Baum und die Reihenfolge der Knotenbesuche auf.

Lösung:

Um die Breitensuche (Breadth-First Search, BFS) durchzuführen, beginnen wir mit dem Startknoten A und durchlaufen den Graphen wie folgt:

• Beginne bei Knoten A und füge ihn zur Warteschlange hinzu.
• Markiere A als besucht. Die derzeitige Warteschlange ist: [A]
• Besuche den ersten Knoten in der Warteschlange (A) und füge seine unbesuchten Nachbarn (B und C) zur Warteschlange hinzu.
• Die derzeitige Warteschlange ist: [B, C]. Markiere B und C als besucht.
• Besuche den ersten Knoten in der Warteschlange (B) und füge seine unbesuchten Nachbarn (D und E) zur Warteschlange hinzu. (A ist bereits besucht)
• Die derzeitige Warteschlange ist: [C, D, E]. Markiere D und E als besucht.
• Besuche den ersten Knoten in der Warteschlange (C) und füge seine unbesuchten Nachbarn (F und G) zur Warteschlange hinzu. (A ist bereits besucht)
• Die derzeitige Warteschlange ist: [D, E, F, G]. Markiere F und G als besucht.
• Besuche den ersten Knoten in der Warteschlange (D) und füge seinen unbesuchten Nachbarn (H) zur Warteschlange hinzu. (B ist bereits besucht)
• Die derzeitige Warteschlange ist: [E, F, G, H]. Markiere H als besucht.
• Besuche den ersten Knoten in der Warteschlange (E). Seine Nachbarn (B, H) sind bereits besucht.
• Die derzeitige Warteschlange ist: [F, G, H].
• Besuche den ersten Knoten in der Warteschlange (F). Seine Nachbarn (C, H) sind bereits besucht.
• Die derzeitige Warteschlange ist: [G, H].
• Besuche den ersten Knoten in der Warteschlange (G). Seine Nachbarn (C, H) sind bereits besucht.
• Die derzeitige Warteschlange ist: [H].
• Besuche den ersten Knoten in der Warteschlange (H). Seine Nachbarn (D, E, F, G) sind bereits besucht.
• Die derzeitige Warteschlange ist nun leer und die Suche ist beendet.

Die Reihenfolge der besuchten Knoten ist somit:

A, B, C, D, E, F, G, H

Der resultierende BFS-Baum sieht wie folgt aus:

    A  / \ B   C /\ /  \ D  E  F   G  \  / H

Aufgabe 3)

In einem Club gibt es 50 Mitglieder, die folgende Aktivitäten ausüben: Schach, Video-Spiel und Schach-Programmierung. Dabei interessieren sich:

• 20 Mitglieder für Schach
• 30 Mitglieder für Video-Spiel
• 15 Mitglieder für Schach-Programmierung
• 10 Mitglieder für Schach und Video-Spiel
• 5 Mitglieder für Schach und Schach-Programmierung
• 8 Mitglieder für Video-Spiel und Schach-Programmierung
• 3 Mitglieder für Schach, Video-Spiel und Schach-Programmierung

Verwende das Inklusions-Exklusions-Prinzip, um die folgenden Fragen zu beantworten:

a)

Wie viele Mitglieder interessieren sich mindestens für eine der Aktivitäten Schach, Video-Spiel oder Schach-Programmierung? Zeige den vollständigen Berechnungsprozess.

Lösung:

Um den vollständigen Berechnungsprozess zur Bestimmung der Anzahl der Mitglieder, die sich mindestens für eine der Aktivitäten Schach, Video-Spiel oder Schach-Programmierung interessieren, zu zeigen, verwenden wir das Inklusions-Exklusions-Prinzip.Das Inklusions-Exklusions-Prinzip wird verwendet, um die Anzahl der Elemente in der Vereinigung mehrerer Mengen zu berechnen. Es besagt:

• Sei A die Anzahl der Mitglieder, die sich für Schach interessieren (20 Mitglieder).
• Sei B die Anzahl der Mitglieder, die sich für Video-Spiel interessieren (30 Mitglieder).
• Sei C die Anzahl der Mitglieder, die sich für Schach-Programmierung interessieren (15 Mitglieder).

Nun müssen wir die Anzahl der Mitglieder berücksichtigen, die sich für mehrere Aktivitäten interessieren:

• A ∩ B (Mitglieder, die sich sowohl für Schach als auch für Video-Spiel interessieren): 10 Mitglieder
• A ∩ C (Mitglieder, die sich sowohl für Schach als auch für Schach-Programmierung interessieren): 5 Mitglieder
• B ∩ C (Mitglieder, die sich sowohl für Video-Spiel als auch für Schach-Programmierung interessieren): 8 Mitglieder
• A ∩ B ∩ C (Mitglieder, die sich für alle drei Aktivitäten interessieren): 3 Mitglieder

Das Inklusions-Exklusions-Prinzip besagt, dass die Anzahl der Mitglieder, die sich mindestens für eine der Aktivitäten interessieren, durch die Formel berechnet werden kann:\[|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|\]Nun setzen wir die gegebenen Werte ein:

• \[|A| = 20\]
• \[|B| = 30\]
• \[|C| = 15\]
• \[|A ∩ B| = 10\]
• \[|A ∩ C| = 5\]
• \[|B ∩ C| = 8\]
• \[|A ∩ B ∩ C| = 3\]

Setzen wir diese Werte in die Formel ein:\[|A ∪ B ∪ C| = 20 + 30 + 15 - 10 - 5 - 8 + 3\]\Berechnen wir diesen Ausdruck Schritt für Schritt:

• Schritt 1: \[20 + 30 = 50\]
• Schritt 2: \[50 + 15 = 65\]
• Schritt 3: \[65 - 10 = 55\]
• Schritt 4: \[55 - 5 = 50\]
• Schritt 5: \[50 - 8 = 42\]
• Schritt 6: \[42 + 3 = 45\]

Somit interessieren sich insgesamt 45 Mitglieder mindestens für eine der Aktivitäten Schach, Video-Spiel oder Schach-Programmierung.Antwort: Es gibt 45 Mitglieder, die sich mindestens für eine der Aktivitäten Schach, Video-Spiel oder Schach-Programmierung interessieren.

b)

Wie viele Mitglieder interessieren sich ausschließlich für Schach?

Lösung:

Um die Anzahl der Mitglieder zu berechnen, die sich ausschließlich für Schach interessieren, müssen wir Mitglieder herausrechnen, die sich sowohl für Schach als auch für mindestens eine andere Aktivität interessieren.Verwende dazu die gegebenen Daten:

• 20 Mitglieder interessieren sich für Schach.
• 10 Mitglieder interessieren sich für Schach und Video-Spiel.
• 5 Mitglieder interessieren sich für Schach und Schach-Programmierung.
• 3 Mitglieder interessieren sich für Schach, Video-Spiel und Schach-Programmierung.

Um die Mitglieder zu finden, die sich nur für Schach interessieren, müssen wir die Mitglieder, die sich für Schach und andere Aktivitäten interessieren, von der Gesamtzahl der Schachinteressierten abziehen:

• Mitglieder, die sich für Schach und Video-Spiel interessieren: 10
• Mitglieder, die sich für Schach und Schach-Programmierung interessieren: 5
• Mitglieder, die sich für Schach, Video-Spiel und Schach-Programmierung interessieren: 3

Einige dieser Mitglieder wurden jedoch doppelt gezählt, wir müssen die Mitglieder, die sich für alle drei Aktivitäten interessieren, ebenfalls subtrahieren, um eine korrekte Berechnung zu gewährleisten.Anzahl der Mitglieder, die sich ausschließlich für Schach interessieren:\[|A_{\text{nur Schach}}| = |A| - (|A \text{ und } B| + |A \text{ und } C| - |A \text{ und } B \text{ und } C|)\]Setzen wir die gegebenen Werte ein:

• \[|A| = 20\]
• \[|A \text{ und } B| = 10\]
• \[|A \text{ und } C| = 5\]
• \[|A \text{ und } B \text{ und } C| = 3\]

Setzen wir diese Werte in die Formel ein:\[|A_{\text{nur Schach}}| = 20 - (10 + 5 - 3)\]Berechnen wir diesen Ausdruck Schritt für Schritt:

• Schritt 1: \[10 + 5 = 15\]
• Schritt 2: \[15 - 3 = 12\]
• Schritt 3: \[20 - 12 = 8\]

Somit interessieren sich 8 Mitglieder ausschließlich für Schach.Antwort: Es gibt 8 Mitglieder, die sich ausschließlich für Schach interessieren.

c)

Wie viele Mitglieder interessieren sich ausschließlich für Schach-Programmierung und keine der anderen Aktivitäten?

Lösung:

Um die Anzahl der Mitglieder zu berechnen, die sich ausschließlich für Schach-Programmierung interessieren und keine der anderen Aktivitäten, müssen wir Mitglieder herausrechnen, die sich sowohl für Schach-Programmierung als auch für mindestens eine andere Aktivität interessieren.Verwende dazu die gegebenen Daten:

• 15 Mitglieder interessieren sich für Schach-Programmierung.
• 5 Mitglieder interessieren sich für Schach und Schach-Programmierung.
• 8 Mitglieder interessieren sich für Video-Spiel und Schach-Programmierung.
• 3 Mitglieder interessieren sich für Schach, Video-Spiel und Schach-Programmierung.

Um die Mitglieder zu finden, die sich nur für Schach-Programmierung interessieren, müssen wir die Mitglieder, die sich für Schach-Programmierung und andere Aktivitäten interessieren, von der Gesamtzahl der Schach-Programmierungsinteressierten abziehen:Das heißt:

• Mitglieder, die sich für Schach und Schach-Programmierung interessieren: 5
• Mitglieder, die sich für Video-Spiel und Schach-Programmierung interessieren: 8
• Mitglieder, die sich für alle drei Aktivitäten interessieren: 3

Einige dieser Mitglieder wurden jedoch doppelt gezählt, wir müssen die Mitglieder, die sich für alle drei Aktivitäten interessieren, ebenfalls subtrahieren, um eine korrekte Berechnung zu gewährleisten.Anzahl der Mitglieder, die sich ausschließlich für Schach-Programmierung interessieren:\[|C_{\text{nur Schach-Programmierung}}| = |C| - (|A \text{ und } C| + |B \text{ und } C| - |A \text{ und } B \text{ und } C|)\]Setzen wir die gegebenen Werte ein:

• \[|C| = 15\]
• \[|A \text{ und } C| = 5\]
• \[|B \text{ und } C| = 8\]
• \[|A \text{ und } B \text{ und } C| = 3\]

Setzen wir diese Werte in die Formel ein:\[|C_{\text{nur Schach-Programmierung}}| = 15 - (5 + 8 - 3)\]Berechnen wir diesen Ausdruck Schritt für Schritt:

• Schritt 1: \[5 + 8 = 13\]
• Schritt 2: \[13 - 3 = 10\]
• Schritt 3: \[15 - 10 = 5\]

Somit interessieren sich 5 Mitglieder ausschließlich für Schach-Programmierung.Antwort: Es gibt 5 Mitglieder, die sich ausschließlich für Schach-Programmierung interessieren.

d)

Berechne die Anzahl der Mitglieder, die sich weder für Schach, Video-Spiel noch für Schach-Programmierung interessieren.

Lösung:

Um die Anzahl der Mitglieder zu berechnen, die sich weder für Schach, Video-Spiel noch für Schach-Programmierung interessieren, müssen wir zunächst die Anzahl der Mitglieder ermitteln, die sich mindestens für eine der Aktivitäten interessieren.Wir verwenden dazu das Inklusions-Exklusions-Prinzip, um die Anzahl der Mitglieder zu berechnen, die sich für mindestens eine der Aktivitäten interessieren.Wir haben die folgenden Daten:

• 20 Mitglieder interessieren sich für Schach.
• 30 Mitglieder interessieren sich für Video-Spiel.
• 15 Mitglieder interessieren sich für Schach-Programmierung.
• 10 Mitglieder interessieren sich für Schach und Video-Spiel.
• 5 Mitglieder interessieren sich für Schach und Schach-Programmierung.
• 8 Mitglieder interessieren sich für Video-Spiel und Schach-Programmierung.
• 3 Mitglieder interessieren sich für Schach, Video-Spiel und Schach-Programmierung.

Gemäß dem Inklusions-Exklusions-Prinzip lautet die Formel zur Berechnung der Mitglieder, die sich mindestens für eine Aktivität interessieren:\[|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\]Nun setzen wir die gegebenen Werte ein:

• \[|A| = 20\]
• \[|B| = 30\]
• \[|C| = 15\]
• \[|A \cap B| = 10\]
• \[|A \cap C| = 5\]
• \[|B \cap C| = 8\]
• \[|A \cap B \cap C| = 3\]

Setzen wir diese Werte in die Formel ein:\[|A \cup B \cup C| = 20 + 30 + 15 - 10 - 5 - 8 + 3\]Berechnen wir diesen Ausdruck Schritt für Schritt:

• Schritt 1: \[20 + 30 = 50\]
• Schritt 2: \[50 + 15 = 65\]
• Schritt 3: \[65 - 10 = 55\]
• Schritt 4: \[55 - 5 = 50\]
• Schritt 5: \[50 - 8 = 42\]
• Schritt 6: \[42 + 3 = 45\]

Insgesamt interessieren sich also 45 Mitglieder mindestens für eine der Aktivitäten.Da es insgesamt 50 Mitglieder im Club gibt, können wir die Anzahl der Mitglieder, die sich für keine der Aktivitäten interessieren, durch Subtraktion ermitteln:\[\text{Mitglieder, die sich für keine der Aktivitäten interessieren} = \text{Gesamtzahl der Mitglieder} - |A \cup B \cup C|\]Setzen wir die Werte ein:\[50 - 45 = 5\]Somit interessieren sich 5 Mitglieder weder für Schach, Video-Spiel noch für Schach-Programmierung.Antwort: Es gibt 5 Mitglieder, die sich weder für Schach, Video-Spiel noch für Schach-Programmierung interessieren.

Aufgabe 4)

Sei p eine Primzahl und n eine natürliche Zahl mit n > 1. Betrachte die Aussage:

• Für alle m mit 2 ≤ m ≤ n gilt: p ist kein Teiler von m!.

Beweise diese Aussage durch Widerspruch, indirekten Beweis und Induktion.

a)

Führe einen indirekten Beweis, um die Aussage zu beweisen, dass p keine Primzahl ist, die m! für 2 ≤ m ≤ n teilt. Zeige konkret, dass die Negation der Aussage zu einem Widerspruch führt.

Lösung:

Um die Aussage durch einen indirekten Beweis zu beweisen, dass p keine Primzahl ist, die m! für 2 ≤ m ≤ n teilt, führen wir die Negation der Aussage ein und zeigen, dass dies zu einem Widerspruch führt.

Schritt für Schritt Vorgehen:

• 1. Annahme der Negation: Angenommen, es gibt ein m mit 2 ≤ m ≤ n, so dass p ein Teiler von m! ist.
• 2. Verständnis der Fakultät: Die Fakultät von m, \({m!}\), ist das Produkt aller positiven ganzen Zahlen von 1 bis m. Also, \({m! = 1 \times 2 \times 3 \times ... \times m}\).
• 3. Widerspruch herbeiführen: Wenn p eine Primzahl ist, dann ist p größer oder gleich 2. Da m eine Zahl in der Menge \({2, 3, ..., n}\) ist, gibt es keine Möglichkeit, dass p in \({m!}\) enthalten ist, weil p als Primzahl nicht in die Produktabfolge von m! passen kann. Folglich, wenn p ein Teiler von \({m!}\) ist, muss p gleich einer der Faktoren von m! sein. Dies ist aber nur möglich, wenn p selbst innerhalb der Zahlen 2 bis m liegt.
• 4. Unmöglicher Fall: Ein Primzahl \({p}\), die ein Teiler von \({m!}\) ist, bedeutet, dass sie eine ganze Zahl in der Reihenfolge 1 bis m ist (weil ansonsten p kein Teiler von m! wäre). Dies ist jedoch nur möglich, wenn p = m, denn alle anderen Zahlen sind bereits Produkte der Zahlen 1 bis m.
• 5. Zum Widerspruch gelangen: Dies steht im Widerspruch zu der Annahme, dass p ein Teiler von \({m!}\) ist, da nach der Definition von Fakultäten, die Primzahl p größer als das größte Element in der Menge \({1, 2, ..., m}\) sein müsste, um als Teiler zu fungieren.
• 6. Schlussfolgerung: Da die Annahme der Negation zu einem Widerspruch führt, muss die ursprüngliche Aussage wahr sein.
• Somit haben wir bewiesen, dass für alle m mit 2 ≤ m ≤ n, p kein Teiler von m! ist.

b)

Nutze einen Widerspruchsbeweis, um nachzuweisen, dass die Primzahl p keinen Teiler von m! für alle 2 ≤ m ≤ n hat. Gehe dabei davon aus, dass p m! teilt und zeige, wozu dies führt.

Lösung:

Um die Aussage durch einen Widerspruchsbeweis zu beweisen, dass die Primzahl p keinen Teiler von m! für alle 2 ≤ m ≤ n hat, gehen wir davon aus, dass p m! teilt, und zeigen, dass dies zu einem Widerspruch führt.

Schritt für Schritt Vorgehen:

• 1. Annahme der Negation: Angenommen, es gibt ein m mit 2 ≤ m ≤ n, so dass p ein Teiler von m! ist.
• 2. Verständnis der Fakultät: Die Fakultät von m, \(m!\), ist das Produkt aller positiven ganzen Zahlen von 1 bis m. Also, \(m! = 1 \times 2 \times 3 \times ... \times m\).
• 3. Eigenschaften von Primzahlen: Seien alle Primzahlen größer oder gleich 2. Also, p ist eine ganze Zahl größer oder gleich 2.
• 4. Beobachtung: Wenn p ein Teiler von \(m!\) ist, müsste p einer der Faktoren in \(m!\) sein. Da \(m!\) das Produkt aller Zahlen von 1 bis m ist, ist p also eine der Zahlen in dieser Menge (\{{1, 2, ..., m\}}).
• 5. Widerspruch bei \(p\) als Teiler: Dies bedeutet, dass p kleiner oder gleich m sein muss, wenn p ein Teiler von \(m!\) ist. Betrachten wir jedoch, dass p eine bestimmte Primzahl ist, die als Teiler in jeder Fakultät eines m enthalten ist (so dass sowohl m \geq 2 und m \leq n). Dann bleibt für m! = 1 \times 2 \times 3 \times ... \times m ein Bestandteil = p vorhanden, was aber widerspricht, dass diese einzelne p Bestandteil der Produktabfolge \(m!\) für allgemeine \(m\) überhaupt darstellen könnte.
• 6. Zum Widerspruch gelangen: Aus dieser Annahme würde sich demnach ergeben, dass bestimmte Primzahlen (sowie p) bereits Bestandteile der Grundfolgerungen von Produktabfolgen für \(m!\) von allen Betrachtungszahlen seien, die eigentümlich nicht sein könnten. Folglich führt die Annahme, dass p ein Teiler von m! ist, zu einem Widerspruch.
• 7. Schlussfolgerung: Da die Annahme zum Widerspruch führt, muss die ursprüngliche Aussage wahr sein.
• Hiernach müssen wir feststellen, dass für alle m mit 2 ≤ m ≤ n, p kein Teiler von m! ist.

c)

Führe einen Induktionsbeweis für die Aussage, dass eine Primzahl p keinen Teiler von m! für 2 ≤ m ≤ n hat.

• Beweise zunächst die Induktionsbasis für n = 2.
• Formuliere dann die Induktionsannahme für ein beliebiges k und beweise anschließend den Induktionsschritt, dass die Aussage auch für k+1 gilt.

Lösung:

Um die Aussage mittels Induktionsbeweis zu beweisen, dass eine Primzahl p keinen Teiler von m! für 2 ≤ m ≤ n hat, gehen wir nach den folgenden Schritten vor:

Schritte im Induktionsbeweis:

• 1. Induktionsbasis: Wir zeigen, dass die Aussage für n=2 gilt.

Die Behauptung lautet: p ist kein Teiler von \(2!\).

• a. Berechnung der Fakultät: \(2! = 2 \times 1 = 2\).
• b. Da p eine Primzahl ist, kann p nur 2 oder größer als 2 sein. Wenn p = 2, dann ist p tatsächlich ein Teiler von \(2!\). In allen anderen Fällen (wo p > 2) ist p kein Teiler von 2.
• c. Daher, für den Fall n = 2 speichern wir die Primzahl zu ein-begrenzten Aussage, dass p kein Teiler von \(2!\) darstellen könnte, weil nach anfänglichem Annahme sinnhaft nicht wieder wiedersprechbar und initial einfach integrierbar.

Nun zeigen wir die Induktionsannahme bemerkbar, was zeigt die allgemeingültig zusätzliche Structures:

• 2. Induktionsannahme: Angenommen, die Aussage gilt für k, d.h.: Für alle m mit 2 ≤ m ≤ k ist p kein Teiler von \(m!\).

Wir wollen nun zeigen, dass die Aussage auch für k+1 gilt.

• 3. Induktionsschritt: Wir müssen beweisen, dass p kein Teiler von \((k+1)!\) ist.

Die Fakultät von k+1 ist:

• a. \((k+1)! = (k+1) \times k!\)

Nach der Induktionsannahme wissen wir, dass p kein Teiler von \(k!\) ist. Wir müssen nun zeigen, dass p auch kein Teiler von \((k+1) \times k!\) ist.

• b. Betrachtungen: Es gibt zwei Fälle zu betrachten:

Fall 1: p ist größer als k+1

• In diesem Fall ist p kein Teiler von k+1, daher kann p auch nicht ein Teiler von \((k+1)! = (k+1) \times k!\) sein, da p nichts für k!\) Teiler wehrend würde darstellen.

Fall 2: p ist kleiner oder gleich k+1

• Dies widerspricht der Annahme, dass p ein Teiler von \((k+1)!\) ist, weil per zugrundeliegendem Annahme ergänzend (wo bereits etwas Primzahlen-Bedingenden) in keine andere spezifisch (erwachsend). Man würde einfach beschränkten Strukturen-Berechnenden nichts übersteigen könnten.

Schlussfolgerung:

• Da beide Fälle zum Ergebnis führen: p keinen Teiler von \((k+1)!\) gibt, zeigt es uns einfache (momentumme um grundformenden etc) zeit sich daraus dass nächste Wege-önig tatsächlichen notwendig.
• Somit ist die Induktionsschritt bewiesen und die ursprüngliche Aussage ist für alle m mit 2 ≤ m ≤ n wahr.