Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Q&A

organizing a library

+3
−0

Suppose you have $n>1$ books lined up on a shelf, numbered $1$ to $n$, not in the correct order, and you wish to put them in order. Here's your method: Choose a misplaced book[1] at random, and put it in its correct spot. For example, if $n=5$ and you pick book number $2$ out of spot number $4$, there are now four books left, and you put the book back between the first two, since it's book number $2$.

What's the maximum number of times you might have to do the pick-and-replace before the books are in order?


[1] meaning, a book numbered $k$ which is not in position $k$

Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

2 comment threads

What happens with the other books when you put a book in the right spot? Do you exchange the book wit... (4 comments)
what I know so far (2 comments)

1 answer

+2
−0

$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.

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

Sign up to answer this question »