MathDB

C4

Part of 2022-IMOC

Problems(1)

SUPER BALANCED PERMUTATIONS

Source: 2022 IMOC C4

9/6/2022
Let NN be a given positive integer. Consider a permutation of 1,2,3,⋯ ,N1,2,3,\cdots,N, denoted as p1,p2,⋯ ,pNp_1,p_2,\cdots,p_N. For a section pl,pl+1,⋯ ,prp_l, p_{l+1},\cdots, p_r, we call it "extreme" if plp_l and prp_r are the maximum and minimum value of that section. We say a permutation p1,p2,⋯ ,pNp_1,p_2,\cdots,p_N is "super balanced" if there isn't an "extreme" section with a length at least 33. For example, 1,4,2,31,4,2,3 is "super balanced", but 3,1,2,43,1,2,4 isn't. Please answer the following questions: 1. How many "super balanced" permutations are there? 2. For each integer M≤NM\leq N. How many "super balanced" permutations are there such that p1=Mp_1=M?
Proposed by ltf0501
combinatoricsIMOC