Stamp Folding Problem Stamp Folding Problem

The stamp‐folding problem is as follows: given a strip of paper with n creases spaced evenly along it, you may fold each crease either “mountain” or “valley.” After unfolding, the stamps (segments) end up in some order. How many distinct permutations of the n + 1 segments can be produced by all possible fold sequences? Das Stamp-Folding-Problem lautet wie folgt: Gegeben ist ein Papierstreifen mit n gleichmäßig verteilten Knicken, die jeweils als Berg- oder Talfalte ausgeführt werden können. Nach dem Auseinanderfalten entstehen Permutationen der n + 1 Segmente. Wie viele verschiedene Permutationen lassen sich auf diese Weise erzeugen?

We simulate all 2ⁿ possible fold patterns (each crease up or down) and record the resulting order of segments. This yields the total number of distinct permutations achievable for a given n. Here's code for simulating it: GitHub Gist von Noel Friedrich. Unfortunately, the code must contain some error, because it's producing a wrong sequence for n>5... If you can find the mistake, do let us know! Wir simulieren alle 2ⁿ möglichen Faltmuster (jeder Knick berg‐ oder talwärts) und notieren die Reihenfolge der Segmente nach dem Auseinanderfalten. Daraus ergibt sich die Gesamtzahl der erreichbaren Permutationen für ein gegebenes n. Hier ist der Code dazu: GitHub Gist von Noel Friedrich. Leider beinhaltet der Code Fehler und gibt ab n=6 falsche Zahlen. Wir haben den Fehler noch nicht gefunden.

For detailed background and enumeration methods, see Robert Dickau’s overview: Stamp Folding (Dickau). Für Hintergrundinformationen und Methoden zur Aufzählung siehe Robert Dickaus Übersicht: Stamp Folding (Dickau).

Have any ideas? Try them out and come to the next weekly recreational math meeting! Hast du Ideen zum Problem? Probiere sie aus und komm zum nächsten wöchentlichen Treffen für Recreational Maths!