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