Maths Olympiad Prep

Library / /42 of 42

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Ireland

Let n3n \ge 3 be an integer and let (p1,p2,p3,,pn)(p_1, p_2, p_3, \dots, p_n) be a permutation of {1,2,3,,n}\{1, 2, 3, \dots, n\}. For this permutation we say that ptp_t is a turning point if 2tn12 \le t \le n-1 and
(ptpt1)(ptpt+1)>0. (p_t - p_{t-1})(p_t - p_{t+1}) > 0.
For example, for n=8n=8, the permutation (2,4,6,7,5,1,3,8)(2, 4, 6, 7, 5, 1, 3, 8) has two turning points: p4=7p_4 = 7 and p6=1p_6 = 1.
For fixed nn, let q(n)q(n) denote the number of permutations of {1,2,3,,n}\{1, 2, 3, \dots, n\} with exactly one turning point.
Find all n3n \ge 3 for which q(n)q(n) is a perfect square.

Solution

Solution 1. We claim that q(n)=2n4q(n) = 2^n - 4 and that this is a perfect square only when n=3n = 3.
If there is a unique turning point, then it is either a minimum or maximum. We count the number of permutations where the turning point is a maximum, and so q(n)q(n) is double this number. As we are interested in the permutations with a single turning point, the permutation must be increasing to the left of the maximum and decreasing to its right. So a permutation with a unique maximum is fully determined by the way the remaining numbers are allocated to the left or the right of the maximum.
The maximal value must be pt=np_t = n. Consider the n1n-1 numbers 1,2,,n11, 2, \dots, n-1. These must each be placed either to the left of the turning point tt or to the right of tt. There are 2n12^{n-1} ways of allocating the numbers between left and right sides, but as a turning point tt must (according to our definition) be an interior point, we must exclude the 2 cases where all the numbers from 1 to n1n-1 are placed the same side of tt. This leaves 2n122^{n-1} - 2 ways of allocating the points between left and right sides.
Doubling, it follows that there are 2n42^n - 4 permutations with exactly one turning point, either a minimum or a maximum.
Now for n3n \ge 3, 2n42^n - 4 is an even number, so is a perfect square, say (2r)2(2r)^2, if and only if a quarter of that number, namely 2n21=r22^{n-2} - 1 = r^2 is a perfect square. If n4n \ge 4 then 2n22^{n-2} is a multiple of 4, so 2n213(mod4)2^{n-2} - 1 \equiv 3 \pmod 4 and cannot be a perfect square. Therefore, the only n3n \ge 3 where q(n)=2n4q(n) = 2^n - 4 is a perfect square is q(3)=234=4q(3) = 2^3 - 4 = 4.

Solution 2. An alternative calculation of q(n)q(n) considers that if pt=np_t = n then there are (n1t1)\binom{n-1}{t-1} ways to allocate the remaining n1n-1 numbers such that t1t-1 are to the left of ptp_t and ntn-t are to the right. The total number of cases for which ptp_t is a maximum is then
q(n)2=t=2n1(n1t1) \frac{q(n)}{2} = \sum_{t=2}^{n-1} \binom{n-1}{t-1}
The binomial theorem gives
2n1=(1+1)n1=t=1n(n1t1)=2+t=2n1(n1t1) 2^{n-1} = (1+1)^{n-1} = \sum_{t=1}^{n} \binom{n-1}{t-1} = 2 + \sum_{t=2}^{n-1} \binom{n-1}{t-1}
The enumeration q(n)=2n4q(n) = 2^n - 4 follows. Finish as in Solution 1.

Solution 3. If a permutation has only one turning point, that point has to be 1 or nn. There is the same number of permutations in both cases. We find a recurrence relation for q(n)q(n):
q(n+1)=2q(n)+4for n3. q(n + 1) = 2q(n) + 4 \quad \text{for } n \ge 3.
Indeed, let σ\sigma be a permutation on {1,2,,n}\{1, 2, \dots, n\}. If σ\sigma has 1 as unique turning point, then we can add n+1n+1 either at the beginning or the end to get a permutation σ~\tilde{\sigma} with 1 turning point. If σ\sigma has nn as unique turning point, then we can add n+1n+1 either at immediately left or immediately right of nn to get a permutation σ~\tilde{\sigma} with n+1n+1 as unique turning point. If σ\sigma is strictly increasing, then add n+1n+1 either at the beginning or just left of nn and if σ\sigma is strictly decreasing, then add n+1n+1 either at the end or just right of nn. These are all possible permutations of {1,2,,n,n+1}\{1, 2, \dots, n, n+1\} with 1 turning point.
To prove that n=3n=3 is the unique number for which q(n)=m2q(n) = m^2, we first note that q(3)=4q(3) = 4, because there are only four permutations of {1,2,3}\{1, 2, 3\} with exactly one turning point, namely
(2,1,3)(3,1,2)(1,3,2)(2,3,1). (2, 1, 3) \quad (3, 1, 2) \quad (1, 3, 2) \quad (2, 3, 1).
Using induction and the recurrence relation we see that 4q(n)4 \mid q(n) for all n3n \ge 3. Writing q(n)=4xnq(n) = 4x_n we get xn+1=2xn+1x_{n+1} = 2x_n + 1 for all n3n \ge 3 from the recurrence relation for qq. If xn+1=k2x_{n+1} = k^2 is a square for some n3n \ge 3, kk must be odd, hence k21(mod4)k^2 \equiv 1 \pmod 4. Since k2=xn+1=2xn+1k^2 = x_{n+1} = 2x_n + 1, we have 2xn=k210(mod4)2x_n = k^2 - 1 \equiv 0 \pmod 4, hence 2xn2 \mid x_n. When n=3n=3, this contradicts x3=1x_3 = 1, and when n4n \ge 4 this contradicts xn=2xn1+1x_n = 2x_{n-1} + 1 which holds for n>3n > 3.

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 and solution reproduced as published; topic and difficulty added by this site.