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
guangzhou-2015
06.04.2017 19:31
nice problem
MellowMelon
06.04.2017 22:49
The problem is equivalent to taking a convex 100-gon with labelled vertices and drawing a directed Hamiltonian path on its vertices, with the edges on the path colored red, blue, red, blue, ..., red in alternating fashion. The path must satisfy the condition that no two edges of the same color intersect (else the two corresponding folds would go through each other). This characterization is easily shown to be necessary and sufficient.
To show at least $2^{100}$ such paths exist, we'll just look at paths where no edges intersect except at vertices. This means that the first $k$ vertices of the path are contiguous (no unchosen vertices in between) for all $k$. So we first choose a starting vertex in 100 ways, then at each step the next vertex is counterclockwise or clockwise from the block of vertices chosen so far. This is two distinct choices for all of the next 99 vertices except the last, for a total of $100 \cdot 2^{98} > 2^{100}$ ways.
To show at most $4^{100}$ such paths exist, we first note that the number of ways to do just the red edges is well-known to be $C_{50}$, the 50th Catalan number. The number of ways to do just the blue edges is $100 \cdot 99 \cdot C_{49}$, since we choose the start and end vertex and then the blue edges on the remaining 98. So there are at most $(100 \cdot 99) C_{50} C_{49}$ permutations.
Since $\binom{2n}{n} < 4^n$ by the Binomial Theorem, we have
\[ (100C_{50}) (99C_{49}) < \frac{100 \cdot 4^{50}}{51} \cdot \frac{99 \cdot 4^{49}}{50} < 4^{100}. \]
liorz2000
10.04.2017 19:53
I think the permutation 1,3,4,2 is a counter example for the first statement of your proof
MellowMelon
10.04.2017 20:23
[asy][asy]size(100);
draw(circle((0,0),sqrt(2)));
draw((0,1.6)--(0,1.2), black+2bp);
draw(arc((0,0),sqrt(2),90,110),black+2bp,EndArrow);
draw((-1,1)--(1,1), red, EndArrow);
draw((1,1)--(-1,-1), blue, EndArrow);
draw((-1,-1)--(1,-1), red, EndArrow);
dot((-1,1)); label("1", (-1,1), NW);
dot((1,1)); label("2", (1,1), NE);
dot((-1,-1)); label("3", (-1,-1), SW);
dot((1,-1)); label("4", (1,-1), SE);[/asy][/asy]
The permutation can be obtained by taking the rightmost stack of squares and folding it one square to the left three times.
Sorry, I might not have made the mapping between the 100-gon and the permutation/folding clear. The permutation is obtained by numbering the vertices on the path in order, and then reading them off the circle in order starting from some point and direction (this is fixed by labelling the 100-gon's vertices before we start).
liorz2000
10.04.2017 21:18
Thank you for explaining me, now I understand it.
Pathological
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$
quangminh1173
26.11.2021 06:04
MellowMelon wrote:
The problem is equivalent to taking a convex 100-gon with labelled vertices and drawing a directed Hamiltonian path on its vertices, with the edges on the path colored red, blue, red, blue, ..., red in alternating fashion. The path must satisfy the condition that no two edges of the same color intersect (else the two corresponding folds would go through each other). This characterization is easily shown to be necessary and sufficient.
To show at least $2^{100}$ such paths exist, we'll just look at paths where no edges intersect except at vertices. This means that the first $k$ vertices of the path are contiguous (no unchosen vertices in between) for all $k$. So we first choose a starting vertex in 100 ways, then at each step the next vertex is counterclockwise or clockwise from the block of vertices chosen so far. This is two distinct choices for all of the next 99 vertices except the last, for a total of $100 \cdot 2^{98} > 2^{100}$ ways.
To show at most $4^{100}$ such paths exist, we first note that the number of ways to do just the red edges is well-known to be $C_{50}$, the 50th Catalan number. The number of ways to do just the blue edges is $100 \cdot 99 \cdot C_{49}$, since we choose the start and end vertex and then the blue edges on the remaining 98. So there are at most $(100 \cdot 99) C_{50} C_{49}$ permutations.
Since $\binom{2n}{n} < 4^n$ by the Binomial Theorem, we have
\[ (100C_{50}) (99C_{49}) < \frac{100 \cdot 4^{50}}{51} \cdot \frac{99 \cdot 4^{49}}{50} < 4^{100}. \]
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.
YaoAOPS
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.