In 2008, the American Mathematics Competition AMC 12 asked a simple question about heavy-tailed permutations of size 5, elements are the n distinct elements 1 to n. A heavy tail permutation of odd size n means that the first (n-1)/2 elements are less than the last (n-1)/2 elements, so here a1 + a2 < a4 + a5. The problem is trivial for small sizes but proved to be difficult for me when trying to expand it to large n, which is why I ask for help after this blog to improve what I know so far.

If you're interested, here is the problem link and a YouTube video explaining the problem:

2008 AMC 12A Problem 21 Video Explanation by Jaymin Shah

Let's start by covering the simple n = 5 case: A natural way to develop a solution in combinatorics is by developing a correspondence with other things you can count. Notice that heavy tail permutations can be mapped to a unique heavy head. So basically, any permutation where a1 + a2 < a4 + a5, if we reverse it, we get a unique permutation where a1 + a2 > a4 + a5 (so 3 2 4 5 1 can be mapped to its unique reverse 1 5 4 2 3) Formally, we say the reverse is bijective from heavy tail to heavy head, each one matches another, so their counts must be equal. Now, out of all total permutations n!, they can either have heavy tail, heavy head, or be balanced. If we let balanced count be B, then the answer to our problem will be

It remains to find B, the number of permutations satisfying a1 + a2 = a4 + a5. To make this problem easier, we make the observation that for n = 5, 9, 13... or simply 4k + 1, for integer k, the sum of all elements is odd, for n = 5, the sum of all elements is a1 + a2 + a3 + a4 + a5 = 15, since a1 + a2 = a4 + a5 = x, 2x + a3 = 15 a3, the middle element, has to be odd to make this sum true. So for all candidates for middle element, we need to find the number of permutations. Similary for n = 7, 11.. 4k+3, it can be shown that the middle element is even. Now, given a middle elemnet c, we can make another simplification and say a1 + a2 = (15 — c)/2, or (S-c)/2. now we need to find all unique unordered pairs that satisfy this for each middle element c, then we can multiply the final answer by (((n-1)/2)!)^2 because both ends can permute freely. Let m = (n-1)/2, so now

This is the hardest part of the problem in which I ask for improvement, I will highlight a couple of approaches, obviously not the brute force one tho!

1. Knapsack DP

Say n = 9, m = 4, S9 = 45, and choose middle element c = 3, We want to find all unique combination of 4 numbers such that their sum is (45-3)/2 = 21 This is knapsack like subset sum dp, with dp[j][s] number of j element subsets (no repeats) with sum s, and there is more clever tricks to avoid re running dp for every middle element as well. However, I was not satisfied because the dp has n elements and sums up to n^2, so n^3 memory and up to n^4 run time, even with many simplifications this is very unreasonable

2. Generating Functions

This is a unique trick which I am fond of even tho it is similar to knapsack dp but it is more rigourous, and I wanted to put it out because of potential ideas and solutions that may arise. If you use random dummy variables y and z, let y's power keep track of subset size and z's power be subset sum, for each 'i' we get a choice of nothing or multplying by yz^i, the generating function from the product will produce a polynomial where the answer is the coefficient of y^m * z^(S-c/2)

3. Other

Here is some incomplete ideas I had: - Recursion style solution to avoid repeated calculation, if the viable transitions can be found, perhaps between n=4k+1, and n=4k+3

• Gaussian Binomial Polynomial, similar ideas to knapsack and generating function, probably better but I am not very knowledgable of it

• The subproblem of unique combinations can be turned into a string of 0,1,-1 ; -1 on the middle element, 0 on unused, 1 on used. Then from a valid combination, other combinations can bea achieved by shifting 1s so that the shift left = shifts right, balancing the sum, but you are only allowed to shift to a 0, perhaps some simplification or observation is required

Final Thoughts:

The optimal solution to large odd n remains unknown unless obviously it is found somewhere on the internet but I could not find. It is an interesting question to me and any help will be massively appreciated!