DENK m a l   2005:  des Rätsels Lösung 


  Lösung der 5. Aufgabe  vom 10.6. 2005

Karten falten


 

 


von mathefifi

bekam ich die komplette Liste aller Faltungen für 4, 5 und 6 Spalten
(im "pdf-Format", was mit dem "Acrobat-Reader" problemlos geöffnet werden kann)


 Lex Bedijs schickt einige interessante Ansätze zur Formel:

In meinem Ansatz platziere ich die Blätter in allen möglichen Varianten übereinander. Die Seite 1 hat dabei ihr "Gesicht" immer oben (Seite 3,5,7,... ebenfalls). Wie von Herbert Nell vermutet, gibt es dafür tatsächlich n! Möglichkeiten, ABER ...

Dies ist z.B. eine Faltungsmöglichkeit, die tatsächlich möglich ist :

falten

Dies jedoch ist nicht möglich, da sich die Faltung von Blatt 3 nach
Blatt 4 mit der Faltung von Blatt 1 nach Blatt 2 schneiden würde.


falten

Die tatsächlichen Möglichkeiten liegen also unter n!.


Bis zu 6 Faltungen kann man das mit etwas zeitlichem Aufwand noch manuell untersuchen. Für höhere Blattzahlen kann man den Rechenknecht benutzen.

Meine Untersuchungen ergaben :
 
Blätter n! möglich Bemerk

2 2 2 alle
3 6 6 alle
4 24 16  
5 120 50  
6 720 144  
7 5040 462  
8 40320 1392  
9 362880 4536  
10 3628800 14060  
11 39916800 46310  
12 479001600 146376  
13 6227020800 485914  
14 87178291200 1557892  
15 1307674368000 5202690  

Die "Weltformel" für die mögliche Anzahl ist nicht offensichtlich.


Die Ideen zur "Weltformel" von Thomas Hähndel

diese Aufgabe hat es doch in sich, so einfach sie auch klingt. Sie hat mir einige Freizeit "geraubt" - sehr zum Verdruss meiner Familie. Die 4-und die 6-Spalten-Faltungen waren ja noch relativ harmlos. Mit einigem Probieren, vielleicht sogar Basteln hat man dann irgendwie sicher die Lösung herausbekommen, aber die allgemeine Formel, so man diese in üblicher mathematischer Schreibweise überhaupt darstellen kann, erweist sich schnell als äußerst komplex. Egal von welcher Seite man da herangeht.

Meine Ansätze waren:
  1. Alle Permutationen aufschreiben und dann die herausnehmen, welche sich offensichtlich nicht falten lassen. Bei vier Blättern denkt man noch, wenn eine Permutation rausfällt, dann braucht man die nicht weiter bei den nächst höheren Spaltenzahlen (n) zu verfolgen, aber das stimmt natürlich nicht. Das merkt man dann bei sechs sehr schnell. Die einzige Systematik scheint zu sein, dass die Anzahl der zulässigen Permutationen pro gleicher Anfangszahl immer gleich ist. Warum das so ist, kann ich aber nicht beweisen. Es spart zumindest einiges an Falten :-)
    Die Permutation (n!) ist also eine Zahl an Varianten, die höchstens erreicht werden kann,
  2. Wenn wir die Falze betrachten, dann haben wir jeweils zwei Möglichkeiten: nach oben oder nach unten falten. Es gibt somit 2(n-1) Möglichkeiten zu falten, wobei jedoch noch die Reihenfolge des Faltvorganges entscheidend ist, welcher (n-1)! Permutationen zulässt. Hierbei hat man aber mit Schwierigkeiten zu kämpfen, dass manche Lösungen doppelt sind, es also keine Rolle spielt, in welcher Reihenfolge man faltet. Auch hier gibt es Faltungen die nicht zulässig sind, wenn z.B.. im Moment der Faltung eine andere Spalte unterliegt. Die Möglichkeit, hier Wiederholungen auszunutzen, ist sehr begrenzt. Maximal Faktor 4.
  3. Wir nehmen fertige Faltungen mit (n-1) Spalten und ergänzen nur die n-te Spalte, finden also alle Möglichkeiten, wo diese neue Spalte zu liegen kommen könnte. Auch hier ist die Freude kurz, eine allgemeine Lösung zu finden, da es beginnt, komplex zu werden, wenn das (n-1)-te Spaltenende (Falte) irgendwo in der Mitte tief vergraben ist.
  4. Nachdem man sich mit dem Falten abgequält hat, mit der Methode des genauen Hinsehens etwas zu finden, klappt auch nicht. Zwar sehen die Zahlen in der Reihe sehr ähnlich aus, aber eine Logik konnte ich nicht erkennen:

Andreas Nagel ... hat zusätzlich Google bemüht und schreibt:

 

Ein gewisser W.F.Lunnon hat sich schon in den sechziger Jahren mit dem Problem beschäftigt:
W.F. Lunnon, A map-folding problem, Mathematics of Computation, 22
(101):193-199, 1968

Auch von J.E.Koehler gab es zur gleichen Zeit Untersuchungen über die Faltmöglichkeiten eines Briefmarkenstreifens, so wie er aus den Automat kommt:
Koehler, J. E. "Folding a Strip of Stamps." Journal of Combinatorial Theory, 5:135-152, 1968
 


Franjo schlug nach bei Gardner:

 

man findet 16 Möglichkeiten für den Streifen aus vier Spalten, nämlich

1234, 1243, 1342, 1432, 2341, 2431, 2134, 2143, 
3412, 3124, 3421, 3214, 4123, 4312, 4213, 4321.
Wie genau, das steht im Buch „Martin Gardner’s mathematische Denkspiele“ (Hugendubel, München 1987) auf  S. 33.
Das Kapitel heißt „Die Kombinatorik des Papierfaltens
und der zitierte Sinnspruch ist der Untertitel dort.
Für n = 5 gibt Gardner den Wert 50, für n = 6 den Wert 144 an.
Noch scheint niemand eine nicht-rekursive Formel gefunden zu haben.
Die „Zusatzaufgabe“ wird somit wohl niemand lösen ...

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

STIMMT... leider!

 

Auswertung:

eingegangene Lösungen richtige Lösungen falsche Lösungen
21 16 5
Bemerkungen : nur ein wenig Falten...

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

aktuelle Aufgabe 5. Aufgabe Hall of FAME
 

_>^..^<____________________________________________________________
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Das ist der ganze Jammer:
die Dummen sind so sicher und die Gescheiten so im Zweifel.
      Helmut Schmidt 
 
<^>
~~~~~~~~~~~~~~
 "blättern"

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

© Karin S., Sept. 2005