IRL_ABooklet

Solution 1. We claim that $q(n)=2^n-4$ and that this is a perfect square only when $n=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)$ 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 $p_t=n$. Consider the $n-1$ numbers $1,2,\dots ,n-1$. These must each be placed either to the left of the turning point $t$ or to the right of $t$. There are $2^{n-1}$ ways of allocating the numbers between left and right sides, but as a turning point $t$ must (according to our definition) be an interior point, we must exclude the 2 cases where all the numbers from 1 to $n-1$ are placed the same side of $t$. This leaves $2^{n-1}-2$ ways of allocating the points between left and right sides. Doubling, it follows that there are $2^n-4$ permutations with exactly one turning point, either a minimum or a maximum. Now for $n\ge 3$, $2^n-4$ is an even number, so is a perfect square, say $(2r{)}^2$, if and only if a quarter of that number, namely $2^{n-2}-1=r^2$ is a perfect square. If $n\ge 4$ then $2^{n-2}$ is a multiple of 4, so $2^{n-2}-1\equiv 3(\mathrm{mod}4)$ and cannot be a perfect square. Therefore, the only $n\ge 3$ where $q(n)=2^n-4$ is a perfect square is $q(3)=2^3-4=4$.

Solution 2. An alternative calculation of $q(n)$ considers that if $p_t=n$ then there are $\left(\genfrac{}{}{0ex}{}{n-1}{t-1}\right)$ ways to allocate the remaining $n-1$ numbers such that $t-1$ are to the left of $p_t$ and $n-t$ are to the right. The total number of cases for which $p_t$ is a maximum is then $$\frac{q(n)}{2}=\sum _{t=2}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{t-1}\right)$$ The binomial theorem gives $$2^{n-1}=(1+1{)}^{n-1}=\sum _{t=1}^n(\genfrac{}{}{0ex}{}{n-1}{t-1})=2+\sum _{t=2}^{n-1}(\genfrac{}{}{0ex}{}{n-1}{t-1})$$ The enumeration $q(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 $n$. There is the same number of permutations in both cases. We find a recurrence relation for $q(n)$: $$q(n+1)=2q(n)+4\text{for }n\ge 3.$$ Indeed, let $\sigma$ be a permutation on $\{1,2,\dots ,n\}$. If $\sigma$ has 1 as unique turning point, then we can add $n+1$ either at the beginning or the end to get a permutation $\tilde{\sigma }$ with 1 turning point. If $\sigma$ has $n$ as unique turning point, then we can add $n+1$ either at immediately left or immediately right of $n$ to get a permutation $\tilde{\sigma }$ with $n+1$ as unique turning point. If $\sigma$ is strictly increasing, then add $n+1$ either at the beginning or just left of $n$ and if $\sigma$ is strictly decreasing, then add $n+1$ either at the end or just right of $n$. These are all possible permutations of $\{1,2,\dots ,n,n+1\}$ with 1 turning point. To prove that $n=3$ is the unique number for which $q(n)=m^2$, we first note that $q(3)=4$, because there are only four permutations of $\{1,2,3\}$ with exactly one turning point, namely $$(2,1,3)(3,1,2)(1,3,2)(2,3,1).$$ Using induction and the recurrence relation we see that $4\mid q(n)$ for all $n\ge 3$. Writing $q(n)=4x_n$ we get $x_{n+1}=2x_n+1$ for all $n\ge 3$ from the recurrence relation for $q$. If $x_{n+1}=k^2$ is a square for some $n\ge 3$, $k$ must be odd, hence $k^2\equiv 1(\mathrm{mod}4)$. Since $k^2=x_{n+1}=2x_n+1$, we have $2x_n=k^2-1\equiv 0(\mathrm{mod}4)$, hence $2\mid x_n$. When $n=3$, this contradicts $x_3=1$, and when $n\ge 4$ this contradicts $x_n=2x_{n-1}+1$ which holds for $n>3$.