Vollständige Induktion

Neue Frage »

winki2008 Auf diesen Beitrag antworten »
Vollständige Induktion
Hallo!

Folgende Aufgabenstellungen zu vollständiger Induktion!

Lösung zu Bsp. 18?

(Hatte Probleme mit dem Summensymbol, deswegen definiere ich * und #)





Behauptung: ist durch 2 teilbar





Induktionsanfang: j=1

...... RICHTIG!

Induktionsschritt:

=

wahre Aussage ist durch 2 teilbar

Ist das so richtig?

Zu Bsp. 19)

Fläche des Quadrats:

Nettofläche (mit Abzug des Ständers)= muss durch 3 teilbar sein (Pflaster ist aus 3 Quadraten)....muss eine gerade Zahl ergeben

Induktionsanfang: n=1

4-1=3......3 ist durch 3 teilbar......WAHRE AUSSAGE

Induktionsschritt:

ist durch 3 teilbar (Induktionsbehauptung); +3 auch natürlich

ist dies so etwa richtig, habe es jetzt nur grob aufgeschrieben.

[attach]35728[/attach]
HAL 9000 Auf diesen Beitrag antworten »

Zu Lösung 18) Ist in Ordnung. Freude


\sum_{j=1}^{4n} j

winki2008 Auf diesen Beitrag antworten »

Danke, dass mit der Klammer wusste ich leider nicht.

Und Bsp. 19)?
tmo Auf diesen Beitrag antworten »

Lustigerweise unterliegst du bei Aufgabe 19 dem selben Denkfehler wie ein Kollege vor über 4 Jahren:

Schachbrett mit der Seitenlänge 2^n - Beweis mittels Vollständiger Induktion?

Es reicht natürlich nicht die Teilbarkeit durch 3 zu zeigen. Ein Rechteck der Größe 1x3 hat auch eine durch 3 teilbare Gesamtfläche, aber lässt sich sicher nicht mit L-förmigen Steinen pflastern...
winki2008 Auf diesen Beitrag antworten »

danke für deinen Tipp:

leider bin ich dem Ergebnis noch nicht ganz schlüssig....Aber wenn ich mir z.B. ein Quadrat vorstelle mit der Seitenlänge 8x8...und ich betrachte jetzt alle anderen kleinen Quadrate mit der Seitenlänge 2x2 darin, dann fällt auf, dass jedes Quadrat genau mit einem ganzen L-förmigen Pflasterstein gepflastert werden muss....
Es ist nicht möglich ein Quadrat mit 2 Pflastersteine zu pflastern, ohne das einer vollkommen darin liegt oder?

Führt dies zum richtigen Weg?
tmo Auf diesen Beitrag antworten »

Wenn du ein 8x8-Quadrat hast, so musst du doch die 4 kleineren 4x4-Quadrate darin betrachten.

Eigentlich ist die Skizze im Hinweis schon die Lösung:

Das große Quadrat zerfällt in 4 Quadrate der halben Seitenlänge. Aus allen diesen 4 Quadraten ist jeweils ein einziges Feld entfernt (1 mal durch den "Pfeiler" und bei den anderen drei Quadraten durch den geschickt platzierten L-Stein). Vermöge Induktion kann man also die 4 kleinen Quadrate pflastern, dies liefert natürlich eine Pflasterung für das große Quadrat.
 
 
winki2008 Auf diesen Beitrag antworten »

Es klingt sehr logisch, was du sagst...nur das ganze in eine Induktionsbehauptung zu gießen ist für mich eben sehr schwierig
tmo Auf diesen Beitrag antworten »

Der Induktionsanfang ist natürlich, dass die Pflasterung für ein Quadrat der Seitenlänge 2 möglich ist. Das sollte offensichtlich sein.

Dann setzt du voraus, dass es für ein Quadrat der Seitenlänge möglich ist.

Und im Induktionsschritt kommt dann das Argument aus meinem letzten Beitrag.

Wo genau haperts nun noch?
winki2008 Auf diesen Beitrag antworten »

Ich weiß nicht, es ist verwirrend...aber es müsste so gehören wie in dieser Erklärung oder?

http://www.projektwoche.jku.at/2005/prae...schachbrett.pdf
winki2008 Auf diesen Beitrag antworten »

also eig. ist meine Induktion richtig....nur darf ich nicht behaupten, dass das Pflaster durch 3 teilbar ist oder?
tmo Auf diesen Beitrag antworten »

Was ist denn "deine" Induktion? Die aus dem ersten Beitrag? Die Induktion ist zwar an sich richtig, aber zeigt nicht die Behauptung, weil sie ja nirgends auf die L-Form eingeht...

Und natürlich darfst du behaupten, dass das die Größe des Pflasters durch 3 teilbar ist. Denn das stimmt ja auch. Aber wie gesagt: Das ist nicht hinreichend für die Behauptung.
winki2008 Auf diesen Beitrag antworten »

Ja der erste Beitrag...

Das heißt ich muss beweisen, dass in 3 Quadrate eine gerade Anzahl an Pflastersteine passt...und das ist schwieriger als man glaubt

Aber das ist doch schon bewissen, wenn man sich das eine Quadrat als Ständer vorstellt.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von winki2008
Das heißt ich muss beweisen, dass in 3 Quadrate eine gerade Anzahl an Pflastersteine passt...

Erstaunt1

Tatsächlich passt in jedes der Quadrate (mit Ausnahme des einen 1x1-Feldes) immer eine ungerade Anzahl an L-Stücken.
winki2008 Auf diesen Beitrag antworten »

sorry, ich meinte es muss eine ganzzahlige Anzahl an Pflastersteinen herauskommen.
Ist die hinreichende Bedingung, dass immer ein Pflasterstein in die Mitte gelegt werden muss, aber nicht in dem Quadrat, wo der "Pfeiler" steht....eigentlich ist es notwendig
HAL 9000 Auf diesen Beitrag antworten »

Dein wirrer Kommentar/Nachfrage zeigt, dass du total auf dem falschen Dampfer bist und überhaupt nicht realisierst, was hier die Beweisidee ist. unglücklich


Nochmal Restart: Was wollen wir hier eigentlich beweisen?

Zitat:
Aussage : Ein Quadrat der Seitenlänge lässt sich mit Ausnahme eines beliebigen, aber vorher festgelegten (!) 1x1-Feldes komplett mit L-Stücken parkettieren.

Induktionsanfang sollte kein Problem sein.

Induktionsschritt :

Hier ist nachzuweisen, d.h. wir haben ein Quadrat der Seitenlänge vorliegen, in dem ein 1x1-Feld besonders gekennzeichnet ist, welches nicht vom Parkett erfasst werden soll. Jetzt unterteilen wir dieses Quadrat in vier Teilquadrate der Seitenlänge , wobei in einem davon dann unser 1x1-Ausnahmefeld liegt (siehe obige Skizze).

Wie lässt sich hier jetzt die Induktionsvoraussetzung einsetzen? Klar, wie können sie auf jedes der vier Teilquadrate loslassen, und haben in jedem der vier noch die Wahl, wo wir das jeweilige Ausnahmefeld hinlegen. Eins ist - na klar - das Ausnahmefeld unserer nachzuweisenden Behauptung . Und die anderen drei?

Eigentlich "erzählt" die Skizze im Hinweis alles Nötige, man muss es nur im Kontext der vollständigen Induktion richtig zu lesen wissen.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »