Schüler Projekt 2007
Schiffe versenken mit Günter, Jens und Martin
Mathematisierung
s1 s2 ... sn
z1 ...
z2 ...
... ... ... ...
zm ...
Reduzierung
3 1 3 2 3 2
2 x x
2 x x
1 x
0
6 x x x x x x
3 x x x
Reduzierung
3 1 3 2 3 2
2 x x
2 x x
1 x
6 x x x x x x
3 x x x
3-1 1-1 3-1 2-1 3-1 2-1
2 x x
2 x x
1 x
3 x x x
Reduzierung
2 0 2 1 2 1
2 x x
2 x x
1 x
3 x x x
2 2 1 2 1
2 x x
2 x x
1 x
3 x x x
1. Bedingung
Für Z = x dann müssen x-mal S ≥ 1 sein
Für S = y dann müssen y-mal Z ≥ 1 sein
Beispiel
4 1 1 1 1
4
1
1
1
1
5 1 2 1 0
5
1
1
2
0
2. Bedingung
∑ ∑i = 1 j = 1
n m
=Si Zj
1. Beispiel
2 2 1 2 1
2
2
1
3
+ + + + = 8
+ +
+
=
8
8 = 8
OkaY √
2. Beispiel
3 2 1 2 1
2
2
1
3
+ + + + = 9
+ +
+
=
8
8 = 9
Nicht OkaY X
Problembeispiel
4 4 4 1 1
4
4
4
1
1
+ + + + = 14
+ +
+ +
=
14
14 = 14
Eigentlich OkaY
Doch nicht realisierbar !!!
3. Bedingung: Verschieben
4 4 4 1 1
4
4
4
1
1
3. Bedingung: Verschieben
4 4 4 1 1
4 x x x x
4 x x x x
4 x x x x
1 x
1 x
3. Bedingung: Verschieben
4 4 4 1 1
4 x x x x
4 x x x x
4 x x x x
1 x
1 x
3. Bedingung: Verschieben
4 4 4 1 1
4 x x x x
4 x x x x
4 x x x x
1 x
1 x
Wiederspruch
nicht realisierbar
3. Bedingung: Verschieben
S5
=4S4
= 4S3
= 4S2 =
1S1
= 1
4 x x x x
4 x x x x
4 x x x x
1 x
1 x
S‘5 = 5
S‘4 = 3
S‘3 = 3
S‘2 = 3
S‘1
= 0
s1 > 0
s1 + s2 ≥ s1' + s2'
s1 + s2 + s3 ≥ s1' + s2' + s3'
. . . s1 + s2 + ... + sn-1 ≥ s1' + s2'+ ... + sn-1 '
s1 + s2 + ... + sn = s1' + s2' + ... + sn'
Das Programm
Nimmt ein beliebiges System entgegen Reduziert dieses soweit möglich Prüft es auf Gültigkeit Gibt alle Lösungen aus Zeigt die Trefferverteilung an
Der Lösungs-Algorithmus
Mit Hilfe eines rekursiven Algorithmus werden alle Lösungen für das System bestimmt
1 1
1 1 2
1 3 4
Sonderfall
1 1 1 1 1
1
1
1
1
1
Ein Treffer pro Zeile/Spalte
Anzahl der Möglichkeiten = n!
Projektzusammenfassung
Danksagung
Ein riesen-wahnsinns super Danke an die Robert-Bosch-Stiftung für die Ermöglichung dieses einmaligen geistigen Ausflugs in die mathematischen Höhen
Vielen Dank an Günter, Jens, Martin (und auch Björn) für euer Verständnis und den Versuch der Verständigung