MathDB

3

Part of 2022 Irish Math Olympiad

Problems(1)

Permutations and Turning points

Source: IrMO 2022

5/8/2022
Let n ≥\ge 3 be an integer and let (p1p_1, p2p_2, p3p_3, …\dots, pnp_n) be a permutation of {1, 2, 3, …\dots n}. For this permutation we say that ptp_t is a turning point if 2≤\le t ≤\le n-1 and
(ptp_t - pt−1p_{t-1})(ptp_t - pt+1p_{t+1}) > 0
For example, for n = 8, the permutation (2, 4, 6, 7, 5, 1, 3, 8) has two turning points: p4p_4 = 7 and p6p_6 = 1.
For fixed n, let q(n) denote the number of permutations of {1, 2, 3, …\dots n} with exactly one turning point. Find all n ≥\ge 3 for which q(n) is a perfect square.
combinatorics