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
Notifications
Mark all as read
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 »

This community is part of the Codidact network. We have other communities too — take a look!

You can also join us in chat!

Want to advertise this community? Use our templates!

Like what we're doing? Support us! Donate