Torneo Internacional de las Ciudades - Marzo 2019 - NM P7

[BR1]

En el plano cuadriculado se construyen todas las posibles líneas quebradas con las siguientes propiedades: cada una de ellas comienza en el punto $(0, 0)$, tiene todos sus vértices en puntos enteros, y cada segmento lineal va ya sea hacia arriba o hacia la derecha a lo largo de las líneas de la cuadrícula. Para cada línea quebrada, considera el correspondiente gusano, el subconjunto del plano que consiste en todas las celdas que comparten al menos un punto con la línea quebrada. Demuestra que el número de gusanos que se pueden dividir en dominós (rectángulos $2 \times 1$ y $1 \times 2$) de exactamente $n > 2$ maneras diferentes es igual al número de enteros positivos que son menores que $n$ y relativamente primos a $n$.