I used inversions as proof for the finite amount of steps (each swapping decreases the number of inversions by exactly one.) and the increasing order part can be proven by contradiction.

I used monovariants and then the increasing part was a pretty easy contradiction.

omg $n \ge 2$. For a whole day I thought I got a 6 because of the $n=1$ case and I used $<$ signs to bound my monovariant.

I said that any two books can only be swapped with each other at most 1 (pretty easy to prove). Then, that means each book can only move right at most (n-1) times, so each book only moves finitely many times and Carl can only make finitely many moves. Then use proof by contradiction for increasing order of width.

proceed with induction

Awesome_guy wrote: proceed with induction That's what I did too

I used a mono-variant of a weighted sum to show termination and then a contradiction argument to show that it has to end in increasing order of width

Yeah, but my weighted sum definition was a little vague so I'm worried the graders might not follow

Say two adjacent elements x(i) and x(i+1) are switched -- then the number of inversions goes up by 1 if x(i)<x(i+1), goes down by 1 if x(i)>x(i+1) So as long as we do not get stuck, the entire sequence ends in a maximum of nC2 moves. Of course, we also need to prove that there is always a move available.

Part 1: Let the height of the book in the ith position from left to right be $h_i.$ Then define the number of inversion pairs as the number of pairs $h_i,h_j$ such that $i<j$ and $h_i<h_j.$ We can easily see that switching two adjacent books decreases the number of inversion pairs by $1,$ since all other inversion pairs remain constant but $h_i,h_{i+1}$ are swapped. Part 2: Now we show that the widest book ends at the right. After we do this we can just repeat for the $n-1$ slot, $n-2$ slot, etc. The widest book by definition is shorter and wider than any book at its right at any time by definition. It cannot swap to the left. So if it is not at the rightmost position the book to the right of it can be swapped, so it must end up at the right.

Is this trivial or did I fakesolve? If there are two adjacent books with the left book taller, then it must have been swapped with the right book at one point. Therefore, their widths are already in increasing order. So we can ignore the height condition of swapping entirely, at which point the desired conclusion is obvious. That was pretty much my entire solution except I added more details just to be safe.

It is possible that left book wider than the right one, but it is also taller than the right one, so they can't switch

@above I already described why that isn't possible. If the left book is taller, it must have already been swapped with the right book at some point (because they're sorted by height at the beginning), so their widths are already in increasing order. Thus a "left book is taller and wider" scenario is not possible. So if the left book is wider, it is also shorter. Boom, heights are gone completely, and now we have some bubble sort stuff which is trivial.

This problem is literally my least favorite oly problem, sorry.

Emathmaster wrote: This problem is literally my least favorite oly problem, sorry. this was an oly problem???

dchenmathcounts wrote: Emathmaster wrote: This problem is literally my least favorite oly problem, sorry. this was an oly problem??? I know that this might be easy, but I can't combo for my life.

Can someone check my sol?

Attachments:
prob1-compressed_compressed.pdf (448kb)

Prove that he stops after a finite number of moves because he never reaches the same arrangement twice. Then we show that he always has a legal switch unless they are already in increasing order of width, which relies on the fact that he starts in increasing order of height. There's a pretty neat contrapositive argument that can be used here.

Proposed by Milan Haiman

nvm redacted im dumb

GoodMorning wrote: HamstPan38825 wrote: When Carl performs any move on the $n+1$ books, it either involves $W$, which does not change the relative order of the other $n$ books, or swaps two of the other $n$ books. I think your claim on a move involving $W$ not changing the relative order of the other $n$ books is not correct. For example, assume the five books are originally numbered $1, 2, 3, 4, 5$, and $3$ is the widest book. A valid move would be to swap $3$ and $5$, yielding $1, 2, 5, 4, 3$, of which the relative order of $1, 2, 4, 5$ is not the same. how can you swap 3 and 5

megarnie wrote: GoodMorning wrote: HamstPan38825 wrote: When Carl performs any move on the $n+1$ books, it either involves $W$, which does not change the relative order of the other $n$ books, or swaps two of the other $n$ books. I think your claim on a move involving $W$ not changing the relative order of the other $n$ books is not correct. For example, assume the five books are originally numbered $1, 2, 3, 4, 5$, and $3$ is the widest book. A valid move would be to swap $3$ and $5$, yielding $1, 2, 5, 4, 3$, of which the relative order of $1, 2, 4, 5$ is not the same. how can you swap 3 and 5 if 3 is shorter and fatter than 5? originally 12345 is in increasing height order

OOPS NEVERMIND I DID NOT READ WORD ADJACENT im so dumb EDIT: wait so i think I proved a generalization of the problem? So based on an inductive hypothesis that no matter the starting order, one can always arbitrarily make moves finitely to reach a width-increasing order, I think it follows that if you remove the adjacent condition from this problem, it still works? Write-up: Induct on hypothesis that regardless of the starting order of $n$ books, any arbitrary finite procedure is able to result in the desired claim. The base case of $n=1$ is trivial. Then for $n+1$ books, mark the thinnest book as book $A$. Any move will either be with $A$, or without $A$. For any move with $A$, $A$ will be shifted towards the left. Therefore, there is a finite number of moves with $A$, until $A$ reaches the leftmost position. Meanwhile, between two moves with $A$, the number of moves of the other $n$ books until it reaches width-increasing order has to be finite by the inductive hypothesis. Note that swapping $A$ with something else may alter the ordering of the other $n$ books, but that is taken care of by our inductive hypothesis being regardless of starting order. Assume that $A$ is moved $k$ times, where $k$ is an integer. Then, there are at most $k+1$ series of consecutive moves not changing $A$ (between the gaps of the $A$-moves). Since each series is finite as well, we conclude that the procedure will be finite. In addition, the books will be in width-increasing order as after $A$ is placed at the leftmost position, the other $n$ books will be in width-increasing order by the inductive hypothesis, and this works as $A$ is the thinnest. $\blacksquare$

Lemma 1: You must operate on the book with the largest width until it goes to the rightmost position proof: FTSOC if you do not operate on the book with the largest width then we we won't have a complete sequence where we are done operating because we can operate with respect to the largest width and the width to the right of the book with the largest width QED We have that after we send the book with the largest width to the righmost position of all of the books we similarly have to operate on the 2nd largest book width since the largest book width is irrelevant as you can't do any operations with it we will treat it as it is not there at all. So we get that the second largest width book becomes the first and we can apply Lemma 1 again and we will keep on doing that until we get to our shortest book width so the order of the book width's will be in increasing order. QED REMARKS: This problem reminded me of 2012 ISL C1

Label the books $1,2,\dots,n$ from tallest to shortest. Then, notice that each swap strictly decreases the lexicographic value of the set. Hence, the process must terminate since the lexicographic value cannot be negative. We proceed by induction on the number of books to show all the book are sorted in increasing order of width when the process terminates. Consider a sequence of swaps that eventually terminates, and remove all swaps that involve the widest book. Then, we have one less book and so by the inductive hypothesis the books will eventually be ordered by width. When we add the widest book back in, the movement of the other books will not be altered as the widest book cannot swap the change the order of two other books. Hence, when we add the widest book's swaps back in, we have the books sorted by width except the widest book. But notice that the widest book will be wider and shorter than all the books to the right of it at all times, so swapping it with the book to the right is always a valid move. Therefore, the widest book must end up in the rightmost position, completing our induction. $\square$

why do these solutions have no numbers in them

First we will prove that the number of swaps will always be finite - we can see that two books will be swapped with each other at most once, meaning that the number of swaps is less than or equal to $\binom{n}{2}$. Now assume WLOG that the books have heights $1$ to $n$, the book with a height of $k$ for an integer $k$ such that $1\leq{}k\leq{}n$, we can call this book $b_k$, which also has width $w_k$ and started as the $i_k$-th book on the shelf. Consider the widest book, $b_x$. Notice that the book will never swap with a book to its left, meaning that all books to the right of it will always be taller than it. This means that unless the widest book is the last book(most rightmost) on the bookshelf, there will always be a move left. Since there are always a finite number of moves, the last book will end up at the last index. Inductively, we can prove this for the rest of the books - for each book, the books to the right of it are either wider or taller and thinner than it, so if this book is the $m$-th widest book, unless this book is the $m$-th to last book on the bookshelf, there will always be a move left. Again, since there are a finite number of moves, this book must end up as the $m$-th to last book and thus the books will be sorted by width from left to right in the end and we are done.

Carl can perform at most $\tbinom{n}{2}$ operations, since every pair of books can be swapped at most once. Assume for sake of contradiction that the widest book will not end up at the rightmost position after all moves are performed. This book will never be swapped to the left, and since the books are originally arranged in increasing height, all books right to it will be taller than it, contradicting that all legal moves have been performed. Therefore, the widest book will end up at the rightmost position. This argument can be extended to show the second widest book will end up at position $n-1,$ the third widest will end up at position $n-2,$ etc.

Firstly, let the sequence of the height of the books be represented as $(h_1,h_2,\ldots,h_n)$. Define the sequence for the width of the books similarly. Note that after each move, the width sequence gets lexicographically smaller. And since there are only $n!$ possible sequences, it must terminate at some point. Now $b_w$ denote the widest book. Now if this book is not at the right end, then there must be a book to the right of this book say $b_1$. But as $b_1$ is thinner than $b_w$, we must have that the height of $b_1$ is lesser than that of $b_w$ otherwise we could've just swapped these two books which contradicts the fact that we were done with all our moves. But initially, the heights of all the books were in an increasing order and so at some point, $b_w$ must have entered to the left of $b_1$ from its right. But in order for $b_w$ to come to the left of $b_1$, it must've swapped its places with $b_1$ itself since it cannot simply jump over books because of our adjacent condition, which is a clear contradiction. Thus $b_w$ must be at the end and we can continue doing this for all the books and we are done.

A sorted sequence is one that has no inversions. Observe that in every operation, the number of inversions reduces by $1$. Thus after $\binom{n}{2}$ moves, the sequence is guaranteed to be sorted.

Is it possible to just grab the minimum width between all of the values and swap it until that book goes to the end of the left? And repeat that attempt by increasing minimum values? for example, books(height, width)$=(5, 9), (4, 10), (2, 6), (1, 11)$ $1. (5, 9), (4, 10), (2, 6), (1, 11)$ $2. (5, 9), (4, 10), (1, 11), (2, 6)$ $3. (4, 10), (5, 9), (1, 11), (2, 6)$ $4. (4, 10), (1, 11), (5, 9), (2, 6)$ $5. (1, 11), (4, 10), (5, 9), (2, 6)$ and finish.

First we prove that the process terminates in a finite number of moves. Let us represent the i-th book by $(h_i, w_i)$ where $h_i$ is its height and $w_i$ is its width. Note that $\sum{ih_i}$ monotonically decreases each time Carl makes a move, and it can't go below 0 so the process must terminate in a finite number of steps. Now we will prove that all the books will get into the right order. Note that for any $j$-th widest book that isn't in the $j$-th to last position, all books left of it will be less wide than it so it can never be swapped left. It will be shorter and wider than books on its right, so it will always be swapped right. This reasoning holds for all its positions until it is in the $j$-th to last position, in which case no more operations can be done on it. Since this reasoning holds for all $j$-th widest books, we are done.

This problem follows after seeing that the number of inversions for both height and width decreases by exactly $1$ every move, and that the initial number of inversions for height is greater than or equal to the initial number of inversions for width. This is because the initial configuration maximizes the number of inversions for height.So then the number of inversions for width will reach $0$ before it does for height, from which we reach our final configuration where no further moves are possible.

WLOG let the heights of the books be $1,2,\dots, n$ in that order, and let the widths of the books be $1,2,\dots, n,$ in some order (not necessarily increasing). Call a pair of (not necessarily adjacent) books height-increasing if the leftmost of the two books is shorter than the rightmost of the two, and width-increasing if the leftmost of the two books is thinner (has less width) than the rightmost of the two. On every move, note that we get rid of one height-increasing pair of books and create one width-increasing pair of books. Eventually, since the number of width-increasing pairs is capped by $\frac{n(n-1)}{2},$ this process is guaranteed to end after a finite number of moves, and in the end, because we reach the maximum, the books are in increasing order of width from left to right.