1. $n$ houses with house numbers 1 to $n$ are located on SMO Street, where $n$ is a natural number. The houses with odd numbers are on the left-hand side of the street, the houses with even numbers are on the right-hand side. The letter carrier Quirin wants to deliver a newspaper to each house. How many ways does he have to do this if he wants to change sides of the street after each newspaper he delivers?

## Solution
We distinguish between $n$ even and $n$ odd:

$n$ even: In this case, there are the same number of houses on both sides of the street. Quirin can therefore choose one side of the street first. On the chosen side of the street, he now has $\frac{n}{2}$ houses to choose from. After he has handed in the newspaper there, he can choose between $\frac{n}{2}$ houses on the other side of the street again. He then changes sides of the street and is back on the side where he started. Here, however, he only has $\frac{n}{2}-1$ options, as he has already distributed a newspaper. Now he changes sides of the street again, etc. Quirin therefore has a total of $2 \cdot \frac{n}{2} \cdot \frac{n}{2} \cdot\left(\frac{n}{2}-1\right) \cdot \ldots \cdot 1=2 \cdot\left(\frac{n}{2}!\right)^{2}$ possibilities if $n$ is even.

$n$ odd: In this case, there are $\frac{n+1}{2}$ houses on the left-hand side of the street and only $\frac{n-1}{2}$ on the right-hand side. Quirin must therefore start distributing the newspapers on the left-hand side, otherwise he cannot change sides after each newspaper he delivers. Similar to above, you therefore get $\frac{n+1}{2} \cdot \frac{n-1}{2} \cdot \frac{n-1}{2} \cdot \ldots \cdot 1=\frac{n+1}{2} \cdot\left(\frac{n-1}{2}!\right)^{2}$ possibilities if $n$ is odd.