Problem

Source: Iranian TST 2017, first exam day 2, problem 6

Tags: combinatorics, Iran, Iranian TST, Hamiltonian path, catalan



In the unit squares of a transparent $1 \times 100$ tape, numbers $1,2,\cdots,100$ are written in the ascending order.We fold this tape on it's lines with arbitrary order and arbitrary directions until we reach a $1 \times1$ tape with $100$ layers.A permutation of the numbers $1,2,\cdots,100$ can be seen on the tape, from the top to the bottom. Prove that the number of possible permutations is between $2^{100}$ and $4^{100}$. (e.g. We can produce all permutations of numbers $1,2,3$ with a $1\times3$ tape) Proposed by Morteza Saghafian