Q5 Matemática  (International Zhautykov Olympiad 2015)

Seja $A_n$ o conjunto de partições da sequência $1,2,...,n$ em várias subsequências tais que cada dois termos vizinhos de cada subsequência tenham paridade diferente, e $B_n$ o conjunto de partições da sequência $1,2,...,n$ em várias subsequências de modo que todos os termos de cada subsequência tenham a mesma paridade (por exemplo, a partição $(1,4,5,8),(2,3),(6,9),(7)$ é um elemento de $A_9$, e a partição $(1,3,5),(2,4),(6)$ é um elemento de $B_6$ ). Prove que para todo inteiro positivo $n$ os conjuntos $A_n$ e $B_{n+1}$ contêm o mesmo número de elementos.