Antwort 4?

[Anonymous]

Ich hab eine gute Weile gezeichnet, aber es ist mir nicht gelungen, mehr wie 17 Quadrate unterzubringen. Hat jemand mehr?

[Anonymous]

Ich habe versucht das Färbungsprinzip zu nutzen und damit zu zeigen, dass es nicht mehr als 17 Quadrate geben kann. Nur ist es mir nicht wirklich gelungen, dass zu beweisen, deshalb füge ich keine Zeichnung an^^

[Anonymous]

Färbungsprinzip habe ich auch genutzt. Am Ende konnte ich zeigen, dass kein Verbindung zwischen rechter und linker Seite aus nur Quadraten und einem einzigen 1×2 Rechteck zwischen den zwei Sternen unten links und dem einen oben rechts vorhanden sein kann. Das gleiche gilt für Verbindungen zwischen oben und unten zwischen diesen. Der Grund ist jeweils, dass es in einem durch eine solche Verbindung abgetrennten Gebiet immer entweder eine gerade Anzahl an Kästchen und zwei mehr zu überdecken schwarze als weiße Kästchen gibt, oder aber eine ungerade Anzahl an Kästchen, mit einem mehr zu überdecken schwarzen, aber so, dass der 2×1 Stein (der dann in das Gebiet eindringen muss) dort immer ein weißes Feld überdeckt.
Innerhalb des Gebietes kann es also keine Überdeckung mit den Teilen geben, da sie immer die gleiche Anzahl schwarz und weiß überdecken.

Ich hatte nicht die Zeit, das ganze nochmal rigoros zu überdenken und aufzuschreiben, bin mir aber sicher, dass damit bewiesen werden kann, dass 17 optimal ist und erwarte gespannt die formulierte Musterlösung 🙃

[Anonymous]

Zuerst habe ich einige Kästchen in Excel angemalt bis ich erkannt habe, dass es um das blockierte Feld links unten genau 3 mögliche Positionen für ein 2×2-Quadrat gibt und dass dazu jeweils passend 16 weitere 2×2-Quadrate untergebracht werden können. Die linke untere und rechte obere Ecke müssen dabei mit 2×1-Kacheln verbunden werden wodurch jeweils 3 Spalten und Reihen am Rand ‘verbraucht’ werden. Das Ergebnis lautete damit 17.

[Anonymous]

Anonymous wrote:

Zuerst habe ich einige Kästchen in Excel angemalt bis ich erkannt habe, dass es um das blockierte Feld links unten genau 3 mögliche Positionen für ein 2×2-Quadrat gibt und dass dazu jeweils passend 16 weitere 2×2-Quadrate untergebracht werden können. Die linke untere und rechte obere Ecke müssen dabei mit 2×1-Kacheln verbunden werden wodurch jeweils 3 Spalten und Reihen am Rand ‘verbraucht’ werden. Das Ergebnis lautete damit 17.

Du brauchst halt eigentlich noch da Argument, dass ein Pfad von links unten nach rechts oben nicht ausreicht. Ansonsten könnten rein rechnerisch deutlich mehr Quadraten da sein. Am Ende sind es eher drei Pfade, aber die können auch teilweise in anderen Ecken enden. Ich war auch überzeugt genug, dass ich es stehen lassen habe, aber bin wie gesagt gespannt auf den rigorosen Beweis.

[Anonymous]

Auf den freue ich mich auch schon

[Anonymous]

Ich wuerde den Beweis so konstruieren:

1. Zaehlen, wieviele vertikale 1×2 Rechtecke es mindestes geben muss
2. Zaehlen, wieviele horizontale 1×2 Rechtecke es mindestens geben muss

Die Summe lautet 25 (also sind mindestens 50 der 118 Kaestchen von 1×2 Rechtecken bedeckt und die restlichen 68 = 17 * 4 Kaestchen koennen von Quadraten bedeckt sein).

Fuer 1. wuerde ich folgendermassen vorgehen (2. funktioniert analog):

1. Die Spalten werden von 1 bis 11 durchnummeriert
2. Ein horizontales 1×2 Rechteck oder ein Quadrat bedeckt immer eine Spalte mit ungeradem Index und eine mit geradem Index (Faerbungsprinzip)
3. Wir gehen Zeile fuer Zeile, von oben nach unten vor: In der ersten Zeile gibt es 6 Kaestchen mit ungeradem Index und 4 Kaestchen mit geradem Index, deshalb muss es mindestens zwei vertikale 1×2 Rechtecke geben, die von der ersten Zeile in die zweite Zeile ragen (jeweils in einer Spalte mit ungeradem Index)
4. In der zweiten Zeile gibt es 6 Kaestchen mit ungeradem Index und 5 Kaestchen mit geradem Index, wobei allerdings mindestens zwei der Kaestchen mit ungeradem Index von den vertikalen Rechtecken aus Zeile 1 bedeckt sein muessen. (Genauer gesagt: es ist immer so, dass es in der zweiten Zeile genau ein “freies” Kaestchen mit geradem Index mehr gibt als “freie” Kaestchen mit ungeradem Index)
5. In Zeile 2 faengt also mindestens 1 vertikales Rechtecke an, diesmal in einer Spalte mit geradem Index
6. Analog verfahren wir mit allen weiteren Zeilen und summieren die Anzahl der vertikalen Rechtecke, die in jeder Zeile mindestens anfangen muessen…

[Anonymous]

Die quadratische Weihnachtskarte enthält k * k quadratische Zellen, hier ist k = 11.
Ich habe das Problem verallgemeinert. Die beiden Sterne habe ich ausgehend von der linken unteren Ecke und den einen Stern ausgehend von der rechten oberen Ecke positioniert.
Für k = 5, 7, 9, 11 habe ich Lösungen gefunden und gesehen, wie sich die Anzahl a der 2×2-Quadrate vermehrt.
n := (k-3)/2

n  k  a
1  5  2
2  7  5
3  9 10
4 11 17

a(n) = n² + 1, https://oeis.org/A002522

[Author]

Posts