For an integer $$n\geq 3$$ and a permutation $$\sigma=(p_{1},p_{2},...,p_{n})$$ of $$\{1,2,...,n\}$$, we say $$p_{l}$$ is a landmark point if $$2\leq l\leq n-1$$ and $$(p_{l-1}-p_{l})(p_{l+1}-p_{l})>0$$. For example, for $$n=7$$ the permutation $$(2,7,6,4,5,1,3)$$ has four landmark points: $$p_{2}=7$$, $$p_{4}=4$$, $$p_{5}=5$$ and $$p_{6}=1$$. For a given $$n\geq 3$$, let $$L(n)$$ denote the number of permutations of $$\{1,2,...,n\}$$ with exactly one landmark point. Find the maximum $$n\geq 3$$ for which $$L(n)$$ is a perfect square.

Let $$\sigma=(p_1,p_2,\dots ,p_n)$$ be a permutation of $$\{1,2,\dots ,n\}$$ and put

$$s_i = p_{i+1}-p_i \quad(1\le i \le n-1).$$

A point $$p_\ell \;(\,2\le \ell \le n-1\,)$$ is a landmark when

$$\bigl(p_{\ell-1}-p_\ell\bigr)\bigl(p_{\ell+1}-p_\ell\bigr) \gt 0.$$(-1)

Because $$p_{\ell-1}-p_\ell = -s_{\ell-1}$$ and $$p_{\ell+1}-p_\ell=s_\ell$$, condition (-1) rewrites as

$$-s_{\ell-1}s_\ell \gt 0 \;\Longrightarrow\; s_{\ell-1}s_\ell \lt 0,$$

i.e. the two consecutive differences have opposite signs. Hence

landmark points are exactly the local extrema (first change from increasing to decreasing or vice-versa).

So, “exactly one landmark” means “exactly one sign change” in the sequence $$s_1,s_2,\dots ,s_{n-1}$$. Two patterns are possible:

1. strictly increasing up to some position $$k$$ and strictly decreasing afterwards (a single peak), or
2. strictly decreasing up to $$k$$ and strictly increasing afterwards (a single valley),

where $$k$$ is the (unique) landmark index and $$2\le k \le n-1$$.

Case 1: single peak
Because the sequence first rises then falls, the element at the peak is the global maximum $$n$$. Fix the landmark position $$k$$ and place $$n$$ at position $$k$$. Choose any $$k-1$$ of the remaining $$n-1$$ numbers for the left block; they must be written in increasing order. The other $$n-k$$ numbers form the right block and must be written in decreasing order. Thus, the number of peak permutations with landmark at $$k$$ is

$$\binom{n-1}{\,k-1\,}.$$

Case 2: single valley
Analogously, the valley element is the global minimum $$1$$. Placing $$1$$ at position $$k$$ and repeating the same choice argument gives again

$$\binom{n-1}{\,k-1\,}$$ permutations.

Therefore, for each $$k\;(2\le k\le n-1)$$ we have twice the above count (peak + valley). Summing over all admissible $$k$$:

$$\begin{aligned} L(n) &= 2\sum_{k=2}^{n-1} \binom{n-1}{k-1}\\ &= 2\!\!\sum_{j=1}^{n-2} \binom{n-1}{j} \quad (j=k-1)\\ &= 2\!\bigl(2^{\,n-1}-\binom{n-1}{0}-\binom{n-1}{n-1}\bigr)\\ &= 2\,(2^{\,n-1}-2)\\ &= 2^{\,n}-4. \; -(2) \end{aligned}$$

We need $$L(n)$$ to be a perfect square:

$$2^{\,n}-4 = m^{2} \quad\text{for some integer } m.$$

Write $$m=2k$$ (since the left side is even). Then

$$2^{\,n}-4 = 4k^{2}\;\Longrightarrow\;2^{\,n-2} = k^{2}+1.$$(-3)

Equation (-3) asks for a power of two that is one more than a perfect square. Let $$a=n-2\;(a\ge 1)$$; then

$$k^{2}+1 = 2^{\,a}. $$(-4)

Squares modulo $$8$$ are $$0,1,4$$. For $$a\ge 3$$ we have $$2^{\,a}\equiv 0 \pmod 8$$, which would force $$k^{2}\equiv -1\equiv 7\pmod 8,$$ impossible. Thus $$a\lt 3$$; check the two possibilities:

• $$a=1:\;2^{\,1}=2\Rightarrow k^{2}=1 \Rightarrow k=1 \Rightarrow m=2.$$ • $$a=2:\;2^{\,2}=4\Rightarrow k^{2}=3$$ (no integer solution).

Hence the only solution of (-4) is $$a=1,\;k=1$$, giving $$n=a+2=3$$.

So the largest integer $$n\ge 3$$ for which $$L(n)$$ is a perfect square is

$$\boxed{03}$$