Maths Olympiad Prep

Library / /89 of 94

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

You want to sort the numbers 5432154321 using block moves. In other words, you can take any set of numbers that appear consecutively and put them back in at any spot as a block. For example, 653421426531653421 \rightarrow 426531 is a valid block move for 6 numbers. What is the minimum number of block moves necessary to get 1234512345?

Solutions — 2

Solution 1

Solution:

Here is a sequence of 3 moves that works: 5432132541341251234554321 \rightarrow 32541 \rightarrow 34125 \rightarrow 12345.

But how do we know we can't do it in 2 moves? From any position there are 20 possible permutations via block moves, 16 from moving a block of size 1 and 4 from moving a block of size 2. One could simply write the 20 permutations of 5432154321 and the 20 permutations of 1234512345 and try to see that they have nothing in common, which would suffice since the inverse of a block move is also a block move. A more clever method is to notice that if we could sort 5432154321 in 2 moves then we could sort 43214321 in 2 moves as well by simply deleting the 5 from each step. But 43214321 has only 10 permutations from block moves, namely 3421,3241,3214,4231,4213,2431,4312,1432,41323421,3241,3214,4231,4213,2431,4312,1432,4132, and 21432143. The 10 permutations of 12341234 are 2134,2314,2341,1324,1342,3124,1243,4123,14232134,2314,2341,1324,1342,3124,1243,4123,1423, and 34123412. These two sets of permutations have nothing in common, thus it takes at least 3 moves to sort 43214321, and hence at least 3 moves to sort 5432154321.

Solution 2

Solution:

There is a more elegant way to show we need at least 3 moves. Given a permutation of {1,2,3,4,5}\{1,2,3,4,5\} (or any ordered set), define a descent to be an adjacent pair of numbers in the permutation such that the left number is greater than the right one. For example, 1234512345, 3421534215, and 5432154321 have 00, 22, and 44 descents, respectively. Any permutation obtained from 1234512345 by one block move has (at most) one descent, at the left edge of the moved block. Similarly, any permutation obtained from 5432154321 by one block move has (at least) three descents, so that we can't get from 5432154321 to 1234512345 by two block moves.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.