Post History
Answer
#2: Post edited
by
r~~
·
2022-09-13T02:19:44Z (over 2 years ago)
- $2^{n-1}-1$ is a lower bound on the maximum, at least. For $n$ books, if you start with the ordering $n, 1, 2, \ldots, n - 1$ (I'm following your convention of 1-indexing the books), then the books could be reordered via the sequence $S_n$ defined as follows:
- $$
- \begin{align}
- S_1 &= () \\\\
- S_{n + 1} &= ([S_{n} + 1], 1, [S_{n} + 1])
- \end{align}
- $$
- (Here $[S_n + 1]$ means to include the sequence $S_n$, adding 1 to each element.)
- I'll walk through $n = 4$, where $S_4 = (3, 2, 3, 1, 3, 2, 3)$:
- ```
- 4 1 2 3 (choose 3)
- 4 1 3 2 (choose 2)
- 4 2 1 3 (choose 3)
- 4 2 3 1 (choose 1)
- 1 4 2 3 (choose 3)
- 1 4 3 2 (choose 2)
- 1 2 4 3 (choose 3)
- 1 2 3 4
- ```
- It should be clear that the length of $S_n$ is $2^{n-1} - 1$. Slightly less clear is why this strategy is always valid, though an inductive argument should be within reach.
I don't know if this is optimal, though.
- $2^{n-1}-1$ is a lower bound on the maximum, at least. For $n$ books, if you start with the ordering $n, 1, 2, \ldots, n - 1$ (I'm following your convention of 1-indexing the books), then the books could be reordered via the sequence $S_n$ defined as follows:
- $$
- \begin{align}
- S_1 &= () \\\\
- S_{n + 1} &= ([S_{n} + 1], 1, [S_{n} + 1])
- \end{align}
- $$
- (Here $[S_n + 1]$ means to include the sequence $S_n$, adding 1 to each element.)
- I'll walk through $n = 4$, where $S_4 = (3, 2, 3, 1, 3, 2, 3)$:
- ```
- 4 1 2 3 (choose 3)
- 4 1 3 2 (choose 2)
- 4 2 1 3 (choose 3)
- 4 2 3 1 (choose 1)
- 1 4 2 3 (choose 3)
- 1 4 3 2 (choose 2)
- 1 2 4 3 (choose 3)
- 1 2 3 4
- ```
- It should be clear that the length of $S_n$ is $2^{n-1} - 1$. Slightly less clear is why this strategy is always valid, though an inductive argument should be within reach.
- I don't know if this is the worst case, though.
#1: Initial revision
by
r~~
·
2022-09-13T02:18:18Z (over 2 years ago)
$2^{n-1}-1$ is a lower bound on the maximum, at least. For $n$ books, if you start with the ordering $n, 1, 2, \ldots, n - 1$ (I'm following your convention of 1-indexing the books), then the books could be reordered via the sequence $S_n$ defined as follows:
$$
\begin{align}
S_1 &= () \\\\
S_{n + 1} &= ([S_{n} + 1], 1, [S_{n} + 1])
\end{align}
$$
(Here $[S_n + 1]$ means to include the sequence $S_n$, adding 1 to each element.)
I'll walk through $n = 4$, where $S_4 = (3, 2, 3, 1, 3, 2, 3)$:
```
4 1 2 3 (choose 3)
4 1 3 2 (choose 2)
4 2 1 3 (choose 3)
4 2 3 1 (choose 1)
1 4 2 3 (choose 3)
1 4 3 2 (choose 2)
1 2 4 3 (choose 3)
1 2 3 4
```
It should be clear that the length of $S_n$ is $2^{n-1} - 1$. Slightly less clear is why this strategy is always valid, though an inductive argument should be within reach.
I don't know if this is optimal, though.