Vorherige Aufgabe   Übersicht 2005   Nächste Aufgabe 

Lösungen der DENKmal-Knobelaufgaben

5. Aufgabe 2005

gestellt am 10. Juni 2005 in der Knobelecke von
Abenteuer Mathematik - die Welt des Knobelns

Karten falten

  Aufgabe   Lösung   Antwort 

Aufgabe

Wir alle kennen das:
Nachdem man sich in einem Stadtplan oder in einer Landkarte kundig gemacht hat, wo der gewünschte Ort zu finden ist, stellt man fest, dass sich die widerspenstige Landkarte nur schwer wieder zusammenfalten lässt, schon gar nicht in den Ausgangszustand.

Dies führt zu dem Sinnspruch:
"Der schnellste Weg eine Landkarte zusammenzufalten ist sie anders zusammenzufalten."

Und das bringt uns zur aktuellen Rätselfrage:
Ein Blatt mit n = 2 Spalten lässt sich auf 2 Arten spaltenweise (hier in der Mitte) falten: rechte Seite nach vorne oder rechte Seite nach hinten, also aus -- wird > oder <.

Wenn man nun das Blatt in 3 Spalten (n = 3) teilt,
3-Spalten-Karte
gibt es bereits 6 Varianten:

3-Spalten-Karte 2 auf 1
dann
3 auf 2
3-Spalten-Karte 2 hinter 1
dann
3 hinter 2
2 auf 1
dann
3 hinter 2
2 auf 1
dann
3 hinter 1
2 hinter 1
dann
3 vor 1
2 hinter 1
dann
3 vor 2

Hier sieht es nach einer einfachen Permutation aus (n!); aber bleibt es auch so?

Frage 1:
Auf wie viele Arten lässt sich eine Seite mit n = 4 Spalten falten?
4-Spalten-Karte

Frage 2:
Auf wie viele Arten lässt sich eine Seite mit n=6 Spalten falten?
6-Spalten-Karte

Zusatzaufgabe für Super-Mathe-Freaks:
Finde die allgemeine Formel für n Spalten.

(eingesandt von Herbert Nell)

Lösung

Es sei (fn)n∈N die Folge der Anzahl von Möglichkeiten, ein Blatt aus n Spalten zusammen zu falten:
(1) (fn)n∈N = (1, 2, 6, ...)

Eine eindeutige Darstellung dieser Möglichkeiten besteht darin, die Spaltennummern in der Reihenfolge zu nennen, in der sie von unten nach oben auftreten, wenn man festlegt, dass die erste Spalte immer die selbe Orientierung hat, also beispielsweise die Kartenseite nach oben zeigt.

Es ist schnell zu erkennen, dass mit jeder Spalte, die hinzu kommt, mindestens zwei Möglichkeiten entstehen, dieses erweiterte Blatt zusammen zu falten, indem nämlich die neue Spalte innerhalb des gefalteten Blattes eng nach unten oder eng nach oben gefaltet wird. Maximal können ⌈n/2⌉+1 Möglichkeiten entstehen, wenn die letzte Faltkante außen liegt und alle benachbarten Faltkanten Lücken umschließen, in die die letzte Spalte hinein gefaltet werden kann, beispielsweise bei einer Zickzackfaltung.
(2) 2 ≤ fn+1/fn ≤ ⌈n/2⌉+1

Wegen dieser Mindestanzahl und der eindeutigen Darstellbarkeit als Permutation der Spalten gilt für die Folgenglieder folgende Abschätzung:
(3) 2n ≤ fn ≤ n!

Eine Übersicht der möglichen Permutationen bis 5 Spalten zeigt die folgende Liste. Für die Spaltenzahl 6 sind nur die Anzahlen angegeben, die sich aus der Erweiterung der zugehörigen Permutation aus 5 Spalten ergibt.

1 2  3   4    5     6   Spaltenzahl
1
  12
     123
         1234
              12345 4
              12354 2
              15234 2
              51234 4
         1243
              12453 2
              12543 4
         4123
              41235 3
              41523 2
              45123 3
              54123 3
     132
         1342
              13452 3
              13542 2
         1432
              14325 3
              14532 2
              15432 3
              51432 3
     312
         3124
              31245 3
              31254 3
              53124 3
         3412
              34152 2
              34512 4
              35412 2
         4312
              43125 4
              45312 2
              54312 4
  21
     213
         2134
              21345 4
              21354 2
              52134 4
         2143
              21453 2
              21543 4
              25143 2
         4213
              42135 3
              45213 3
              54213 3
     231
         2341
              23415 3
              23451 3
              23541 2
              52341 3
         2431
              24531 2
              25431 3
     321
         3214
              32145 3
              32154 3
              32514 2
              53214 3
         3421
              34521 4
              35421 2
         4321
              43215 4
              43251 2
              45321 2
              54321 4

1  2   6   16    50 144   Anzahl

Siehe auch Stamp Folding -- from MathWorld

Antwort

Ein Blatt mit 4 oder 6 Spalten lässt sich sich auf 16 bzw. 144 Arten zusammenfalten.

Eine allgemeine Formel für n Spalten ist mir nicht bekannt.