Schüler Projekt 2007 Schiffe versenken mit Günter, Jens und Martin

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