PUMaC 2017 · 组合（A 组） · 第 5 题

PUMaC 2017 — Combinatorics (Division A) — Problem 5

Greedy Algorithms, Inc. offers the following string-processing service. Each string submitted for processing has a starting price of 1 dollar. The customer can then ask for any two adjacent characters in the string to be swapped. This may be done an arbitrary number of times, but each swap doubles the price for processing the string. Then the company returns the modified S string and charges the customer 2 dollars, where S is the number of swaps executed. If a customer submits all permutations of the string PUMAC for processing and wants all of the strings to be identical after processing, what is the lowest price, in dollars, she could pay?

解析

Without loss of generality, say that we would like all of the strings to be returned in alphabetical order. Note that the minimum number of swaps is exactly equal to the number of pairs of letters in the original string that appear in the wrong order. (Each swap may take exactly one such pair and fix it.) We claim that if there are n distinct letters in the string, then the minimum price is n − 1 i n ∏ ∑ ∏ j i 2 = (2 − 1) . i =0 j =0 i =1 We proceed by induction, building the string with characters that increase in alphabetical order. The base case is clear, since if there is only 1 character then there is only 1 possible 0 string, and the cost to process it is 2 = 1 dollar. For the inductive step, note that for every string of length n − 1, the new character can be inserted in of any n spaces, and then an efficient sort is to move the new character over to the last spot and then sort the string of size n − 1. Thus, using the inductive hypothesis, the total cost is n − 2 i i − 1 n − 1 i ( ) ( ) ∏ ∑ ∑ ∏ ∑ j k j 2 · 2 = 2 i =0 j =0 i =0 j =0 k =0 as desired. The final simplification is by the finite geometric series formula. Thus, the answer for n = 5 is 1 · 3 · 7 · 15 · 31 = 9765 . Problem written by Jacob Wachspress 17