Was ist die kleinste Anzahl an Kästchen, die ausgemalt werden müssen?

Question

Aufgabe:

In einem 5× 5-Quadrat sollen einige Kästchen ausgemalt werden. Dabei soll in
jedem 1× 4-Rechteck und in jedem 4× 1-Rechteck mindestens ein ausgemaltes
Kästchen liegen. Was ist die kleinste Anzahl an Kästchen, die ausgemalt werden
müssen?

Comments

Stell dir vor, du spielst mit deinem Kumpel Schiffeversenken und gehst als Erstes auf die Suche nach seinem 4*1 Kreuzer. Wie sieht deine Strategie aus. Wohin schießt du damit du den Kreuzer auf alle Fälle mit der geringsten Anzahl an Schüssen findest.

Ich habe früher Schiffeversenken geliebt :) Leider war ich irgendwann so gut, dass keiner mehr gegen mich verlieren wollte.

---

Wie sollen denn die 1× 4-Rechtecke und die 4× 1-Rechtecke angeordnet sein? Mit oder ohne Überlappungen?

---

in JEDEM 1× 4-Rechteck und in JEDEM 4× 1-Rechteck.

Also dürfen sich die eingezeichneten Rechtecke auch überlappen.

Lege ich meinen 4x1 Kreuzer senkrecht in mein Raster, so müsstest du jede Spalte wenigstens einmal beschießen, um ihn zu treffen.

Lege ich meinen 4x1 Kreuzer horizontal in mein Raster, so müsstest du jede Zeile wenigstens einmal beschießen, um ihn zu treffen.

---

Schöne Aufgabe. Die gebe ich nachher meiner 5. Klasse.

---

@Mathecoach:

Leider war ich irgendwann so gut, dass keiner mehr gegen mich verlieren wollte.

Ok - dann frage ich mal den Profi: schafft man es mit weniger als 7 ausgemalten Kästchen?

---

schafft man es mit weniger als 7 ausgemalten Kästchen?

Nein. 7 ist die Untergrenze. Da in jede Zeile und in jede Spalte mind. 1 Kästchen angemalt sein muss, kann man erstmal die Diagonale bestücken.

Auch wenn ich nicht die Diagonale nehme, sondern eben in jeder Zeile und Spalte ein Kästchen bemale, lässt es sich nicht vermeiden, dass dabei ein Kästchen am Rand bemalt wird. Nun kann man über, unter oder neben den Randfeldern immer ein Rechteck bilden. Um diese auch noch abzudecken braucht man immer mind. 2 weitere angemalte Felder.

Answer 1

Fünf Kästchen

|x| | | | |
| | |x| | |
| |x| | | |
| | | | |x|
| | | |x| |

Bei vier ausgemahlten Kästchen gibt es eine Zeile, in der kein Kästchen ausgemahlt ist und eine Spalte in der kein Kästchen ausgemahlt ist. Das Kästchen an dieser Stelle liegt in keinem geeignetem 4×1- oder 1×4-Rechteck. Vier Kästchen reichen deshalb nicht aus.

Comments

5 Kästchen reichen auch nicht aus (siehe eingezeichnete Gründe).

Das mit der "besten Antwort" sollte sich der Fragesteller nochmal überlegen.

---

Ja, hast recht. Da habe ich die Aufgabe wohl falsch aufgefasst.

Answer 2

Warst du wirklich so gut ?

Comments

Nein. 7 ist die Untergrenze.

Also meine Mathe-AG der Klasse 5 ist heute auch auf eine Minimallösung von 6 Kästchen gekommen.

---

Meine Hochachtung. Gegen dich hätte ich vermutlich haushoch verloren.

Vielleicht war ich auch nur so gut, weil die Gegner zu schwach waren :)