
Problem T-3. There are $n \geq 2$ houses on the northern side of a street. Going from the west to the east, the houses are numbered from 1 to $n$. The number of each house is shown on a plate. One day the inhabitants of the street make fun of the postman by shuffling their number plates in the following way: for each pair of neighbouring houses, the current number plates are swapped exactly once during the day.

How many different sequences of number plates are possible at the end of the day?


Solution 1. Let $f(n)$ denote the answer. We shall prove by induction that $f(n)=2^{n-2}$. For $n=2$, the answer is clearly $2^{2-2}=1$. We also define $f(1)=1$. Now we consider arbitrary $n>2$.

Let $H_{i}$ denote the house with number $i$ at the start of the day, and let $(i \rightleftarrows i+1)$ denote the swap between $H_{i}$ and $H_{i+1}$. Let $H_{k}$ be the house that has plate $n$ at the end of the day. It follows that the swaps $(n-1 \rightleftarrows n),(n-2 \rightleftarrows n-1), \ldots,(k \rightleftarrows k+1)$ must have happened in this order, for otherwise plate $n$ could not have reached the house $H_{k}$. In addition, $(k-1 \rightleftarrows k)$ must have happened before $(k \rightleftarrows k+1)$, otherwise plate $n$ would have ended up somewhere between $H_{1}$ and $H_{k-1}$.

It follows that for any $k \leq i<n$ the plate $i$ will be on $H_{i+1}$, while plates $1, \ldots, k$ will be on the houses $H_{1}, H_{2}, \ldots, H_{k-1}$, and $H_{k+1}$ in some mixed order. If we restrict our attention to the first $k$ houses: the same happens that would happen if the only houses were $H_{1}, H_{2}, \ldots, H_{k}$; the only difference is that at the end of the game, $H_{k}$ should change its plate to $n$. So there are $f(k)$ different final orderings of the plates such that $n$ is on $H_{k}$ (for $k=1, \ldots, n-1$ ).

Therefore,

$$
f(n)=\sum_{k=1}^{n-1} f(k)=1+\sum_{i=0}^{n-3} 2^{i}=2^{n-2}
$$
