MathDB

A4

Part of 2006 Putnam

Problems(1)

Putnam 2006 A4

Source:

12/4/2006
Let S={1,2…,n}S=\{1,2\dots,n\} for some integer n>1.n>1. Say a permutation π\pi of SS has a local maximum at k∈Sk\in S if (i)π(k)>π(k+1)for k=1(ii)π(k−1)<π(k) and π(k)>π(k+1)for 1<k<n(iii)π(k−1)Mπ(k)for k=n\begin{array}{ccc}\text{(i)}&\pi(k)>\pi(k+1)&\text{for }k=1\\ \text{(ii)}&\pi(k-1)<\pi(k)\text{ and }\pi(k)>\pi(k+1)&\text{for }1<k<n\\ \text{(iii)}&\pi(k-1)M\pi(k)&\text{for }k=n\end{array} (For example, if n=5n=5 and π\pi takes values at 1,2,3,4,51,2,3,4,5 of 2,1,4,5,3,2,1,4,5,3, then π\pi has a local maximum of 22 as k=1,k=1, and a local maximum at k−4.k-4.) What is the average number of local maxima of a permutation of S,S, averaging over all permuatations of S?S?
Putnamprobabilityinductionexpected valuecollege contests