Mengen mit Teilern nat. Zahlen < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Man zeige: Für alle [mm] $n\in\IN$ [/mm] gilt: Jede Teilmenge $T$ von [mm] $\IN_{\leq 2n}$ [/mm] mit $|T| = n+1$ enthält zwei verschiedene Zahlen, von denen die eine die andere teilt. |
Hallo liebes Forum,
An der o.g. Aufgabe sitze ich nun schon eine ganz Weile fest und komme auf keine Lösung. Ich bin mir mittlerweile nicht sicher, ob ich mit einem (Abschnitts-)Induktionsbeweis in die richtige Richtung gehe, darum bitte ich Euch um Rat.
Mein bisheriger Beweisanfang ist nicht viel, aber er zeigt, woran es scheitert:
Induktionsanfang: $n = 1$: Klar, da [mm] $\{1,2\}$ [/mm] die einzige Teilmenge von [mm] $\IN_{\leq 2n}$ [/mm] ist mit Mächtigkeit 2, und 2 teilt 1.
Induktionsvoraussetzung:
Sei [mm] $n\in\IN$, [/mm] so daß für jedes $n' [mm] \leq [/mm] n$ gilt, daß jede Teilmenge $T$ von [mm] $\IN_{\leq 2n'}$ [/mm] mit $|T| = n'+1$ zwei verschiedene Zahlen enthält, von denen die eine die andere teilt.
Induktionsschluß:
Fall 1: $T$ enthält weder $n+1$ noch $n+2$. Dann ist $T [mm] \subseteq \IN_{\leq 2n'}$, [/mm] und nach I.V. gilt die Beh.
Fall 2: [mm] $n+2\in [/mm] T$. ...
Und hier scheitert es bereits. Ich habe, ehrlich gesagt, keine Idee, wie ich die I.V. in die restlichen Fälle hineinbringen soll.
Kann mir jemand einen Tipp geben?
Vielen lieben Dank für jede Hilfe!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:23 Do 03.05.2007 | | Autor: | MicMuc |
> Induktionsschluß:
> Fall 1: [mm]T[/mm] enthält weder [mm]n+1[/mm] noch [mm]n+2[/mm]. Dann ist [mm]T \subseteq \IN_{\leq 2n'}[/mm],
> und nach I.V. gilt die Beh.
> Fall 2: [mm]n+2\in T[/mm]. ...
Ich denke hier hast Du Dich erst einmal vertippt:
1. Fall: T[/mm] enthält weder [mm]2n+1[/mm] noch [mm]2n+2[/mm].
Erster Tipp:
2. Fall: [mm]2n+1\in T[/mm] und [mm]2n+2 \not\in T[/mm] bzw.
[mm]2n+1 \not\in T[/mm] und [mm]2n+2 \in T[/mm] geht glatt durch. Hier benutzt Du deine Induktionsvoraussetzung
Zweiter Tipp:
Der Fall: [mm]2n+1\in T[/mm] und [mm]2n+2 \in T[/mm] funktioniert mit Deiner Induktion so nicht.
|
|
|
|
