11. (POL 1) Find the number of partitions of the set $\{1,2, \ldots, n\}$ into three subsets $A_{1}, A_{2}, A_{3}$, some of which may be empty, such that the following conditions are satisfied:
(i) After the elements of every subset have been put in ascending order, every two consecutive elements of any subset have different parity.
(ii) If $A_{1}, A_{2}, A_{3}$ are all nonempty, then in exactly one of them the minimal number is even.
11. Let $A_{1}$ be the set that contains 1 , and let the minimal element of $A_{2}$ be less than that of $A_{3}$. We shall construct the partitions with required properties by allocating successively numbers to the subsets that always obey the rules. The number 1 must go to $A_{1}$; we show that for every subsequent number we have exactly two possibilities. Actually, while $A_{2}$ and $A_{3}$ are both empty, every successive number can enter either $A_{1}$ or $A_{2}$. Further, when $A_{2}$ is no longer empty, we use induction on the number to be placed, denote it by $m$ : if $m$ can enter $A_{i}$ or $A_{j}$ but not $A_{k}$, and it enters $A_{i}$, then $m+1$ can be placed in $A_{1}$ or $A_{k}$, but not in $A_{j}$. The induction step is finished. This immediately gives us that the final answer is $2^{m-1}$.