Grundlegende Lösungstechniken
Zu große Formen müssen leer sein (Teil 2)
Wenn beide Zahlen identisch sind (hier: 4 und 4), bedeutet dies, dass alle Blöcke 1er-Blöcke sind.
Formen, die größer als 1 Kästchen sind, müssen demnach frei sein.
Wenn die erste Zahl um 1 größer als die zweite Zahl ist (hier 4 und 3), dann gibt es sicher keine Blöcke, die länger als 2 Kästchen sind.
Begründung: Wenn die erste Zahl um 1 größer als die zweite Zahl ist, dann gibt es genau einen 2er-Block; alle anderen Blöcke sind 1er-Blöcke. Eine andere Aufteilung ist nicht möglich.
Allgemein gilt (fortgeschrittene Technik):
Wenn wir die erste Zahl mit k, und die zweite Zahl mit b bezeichnen, gilt:
Es gibt keine Blöcke, die länger als k − b + 1 Kästchen sind.
Begründung: Einen möglichst langen Block erhalten wir, wenn alle anderen Blöcke so kurz wie möglich sind (d.h. 1er-Blöcke sind). Soll es also insgesamt b Blöcke geben, wären b − 1 Blöcke 1er-Blöcke und würden genau b − 1 Kästchen verbrauchen. Für den verbleibenden Block bleiben dann noch k − (b − 1) = k − b + 1 Kästchen übrig.
Beispiel [7 3]: Es soll 7 schwarze Kästchen, aufgeteilt in 3 Blöcke, geben. Es gibt sicher keinen Block, der länger als 7 − 3 + 1 = 5 Kästchen ist. Denn wenn zwei Blöcke 1er-Blöcke sind, bleiben noch 5 Kästchen für den dritten Block.
| < Zurück |
© 2008—2010 PuzLogical