Q8 Matemática  (Tuymaada 2020)

Em uma faixa horizontal $1\times n$ feita de $n$ quadrados unitários os vértices de todos os quadrados são marcados. A tira é dividida em partes por segmentos que conectam pontos marcados e não ficam nas laterais da tira. Os segmentos não podem ter pontos internos comuns; a extremidade superior de cada segmento deve estar acima da extremidade inferior ou mais à direita. Prove que o número de todas as partições é divisível por $2^n$. (A partição onde nenhum segmento é desenhado também é contada.) (E. Robeva, M. Sun)