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
Problem
Source: Iranian TST 2017, first exam day 2, problem 6
Tags: combinatorics, Iran, Iranian TST, Hamiltonian path, catalan
06.04.2017 19:31
nice problem
06.04.2017 22:49
10.04.2017 19:53
I think the permutation 1,3,4,2 is a counter example for the first statement of your proof
10.04.2017 20:23
10.04.2017 21:18
Thank you for explaining me, now I understand it.
29.06.2019 23:38
Nice problem! Call a permutation of $1, 2, \cdots, n$ tasty if it can be folded from a tape as described in the problem, for any $n \in \mathbb{N}$. For $n \in \mathbb{N}$, let $f(n)$ be the number of tasty permutations of $1, 2, \cdots, n$. Lemma 1. $f(n+1) \ge 2f(n), \forall n \in \mathbb{N}.$ Proof. In the beginning, we can fold the line between the squares labeled $n$ and $n+1$ in one of two ways. Afterwards, we can treat this "double square" as a single square labeled with $n$, and proceed in any of the $f(n)$ folding methods. The effect of this is that we can insert $n+1$ on either side of $n$ in a tasty permutation of $1, 2, \cdots, n$ to get a tasty permutation of $1, 2, \cdots, n+1$, hence proving the lemma. $\blacksquare$ Since $f(5) \ge 32$ (easy to check), we get that $f(100) \ge 2^{100}$ from Lemma 1 and induction. Now, let's turn to the other part of the problem. Consider some tasty permutation $a_1, a_2, \cdots, a_{100}$ of $1, 2, \cdots, 100.$ We will represent it visually as follows. Firstly, write the numbers $a_1, a_2, \cdots, a_{100}$ from left to right in a straight line. Then, connect the pairs $(1, 2), (3, 4), (5, 6), \cdots, (99, 100)$ with an arc above the numbers, and connect the pairs $(2, 3), (4, 5), \cdots, (99, 100)$ with an arc below the numbers. Now, erase the numbers. From the conditions of the problem, we know that the drawn arcs will delineate a non-self-intersecting path which alternates between arcs above the line and below the line. Call this the underlying path of the tasty permutation $a_1, a_2, \cdots, a_{100}$. It suffices to show that the number of such paths is at most $\frac12 \cdot 4^{100}$, since each "valid" path is the underlying path of two permutations (a permutation and its reverse). So let's show this. Note that the number of ways to pair up numbers with $50$ arcs above the line so that no two arcs intersect is at most $C_{50}$, the $50$th Catalan number. This can be readily seen since there exists an obvious bijection between each pairing with arcs and an arrangement of $50$ $($'s and $50$ $)$'s so that no two pairs of parantheses "conflict" with each other. Similarly, the number of ways to pair up numbers with $49$ arcs below the line so that no two arcs intersect is at most $\binom{100}{2} \cdot C_{49}$, where here we first select the two unpaired numbers (corresponding to $1$ and $100$), and then use the same argument above. The bound given follows easily from the Multiplication Principle. From the two obtained bounds, we know that the number of tasty permutations is at most $2 \cdot C_{50} \cdot \binom{100}{2} \cdot C_{49}.$ Since $C_{50} = \frac{1}{51} \cdot \binom{100}{50} < \frac{1}{51} \cdot 2^{99}$ and $C_{49} = \frac{1}{50} \cdot \binom{98}{49} < \frac{1}{50} \cdot 2^{97}$, we get that: $$2 \cdot C_{50} \cdot C_{49} \cdot \binom{100}{2} < 2 \cdot \frac{\binom{100}{2}}{51 \cdot 50} \cdot 2^{196} < 2^{198} = 4^{99} < 4^{100},$$ which implies the other bound. $\square$
26.11.2021 06:04
MellowMelon wrote:
The problem is known as the stamp folding problem. This paper proves the first claim in the quote. Its 2D analogue is called map folding.
20.12.2024 20:34
induct go brrrr? Let $f(n)$ denote the answer for $n$ tapes. We inductively prove $2^n \le f(n)$ for large $n$. Note that $f(0) = f(1) = 1, f(2) = 2, f(3) = 6$. Note that $f(n) \ge 2^{n-1}$ for all $0 \le n \le 3$ and that $f(n) \le \frac{4^n}{n}$. As such, note that by considering the bottom tape, we get \[ f(N) \ge \sum_{i=0}^{N-1} f(i)f(N-1-i) \ge \sum_{i=0}^{N-1} \frac{2^i}{2} \cdot \frac{2^{(N-1-i)}}{2} = N \cdot 2^{N-2} \ge \frac{2^N}{2} \]so $f(100) \ge 2^{100}$. Likewise, by considering the last fold of the folding process, we get that if $a_1, a_2, \dots, a_{100}$ is a valid permutation, then there exists an $1 \le i \le 99$ such that $a_1, a_2, \dots, a_i$ is either $\{1, 2, \dots, i\}$ or $\{100, 99, \dots, 101-i\}$. This means that by considering this edge, \[ f(N) \le \sum_{i=0}^{N-1} 2f(i)f(N-1-i) \le 2 \cdot 4^{N-1} \cdot \left(\sum_{i=1}^{N} \frac{1}{(i)(N+1-i)}\right) \le 4^N \]as desired.