CMO-2018-P1

Enunciado

Supoñamos que temos un certo número de moedas no plano euclídeo, non necesariamente en puntos distintos (é dicir, dúas moedas poden estar nun mesmo punto). Podemos mover as moedas seguindo a seguinte regra: collemos dúas moedas $A$ e $B$ calquera (obviamente distintas) e movémolas ambas ao punto medio de $A$ e $B$.

Dicimos que una disposición de moedas é colapsable se, aplicando un número finito movementos como o indicado anteriormente, podemos colocar todas as moedas nun único punto. Demostra que toda configuración de $n$ moedas e colapsable se e só se $n$ é unha potencia de dous.

---

Resolución

Pista

Nótese que en caso de poder colapsar un conxunto de moedas, o punto no cal terminarán todas será o centro de masas da configuración orixinal.

Solución

Supoñamos que $n=2^k$ con $k\in {\mathbb{Z}}^{+}$. Vexamos que podemos colapsar toda configuración de $n$ moedas mediante indución en $k$.

No caso $k=1$ temos $n=2$. É obvio que toda configuración de $n=2$ moedas é colapsable tras un único movemento.

Supoñamos entón que se cumpre para $k$. Consideremos entón unha configuración de $n=2^{k+1}$ moedas, que chamaremos $A_1,A_2,\dots ,A_{2^{k+1}}$. Separemos as moedas en dous conxuntos de $2^k$ elementos, por exemplo $\{A_1,A_2,\dots ,A_{2^k}\}$ e $\{A_{2^k+1},A_{2^k+2},\dots ,A_{2^{k+1}}\}$. Cada un de estes conxuntos constitúe una configuración de $2^k$ moedas, polo que pola hipótese de indución podemos colapsalos a un punto $Q_1$ e $Q_2$, respectivamente.

Polo tanto agora temos $2^k$ moedas no punto $Q_1$ e $2^k$ moedas no punto $Q_2$. Se eliximos agora unha moeda sobre $Q_1$ e outra sobre $Q_2$ reiteradamente, é fácil ver que despois de $2^k$ movementos todas as moedas estarán no mesmo punto (concretamente o punto medio entre $Q_1$ e $Q_2$), polo tanto a configuración inicial é colapsable.

Agora temos que probar que se toda configuración de $n$ moedas é colapsable, entón $n$ é unha potencia de dous. Isto e equivalente a demostrar que se $n$ non é potencia de dous, entón existe al menos unha configuración de $n$ moedas que non é colapsable.

Nótese que en caso de que unha configuración sexa colapsable, o punto onde colapsa é o centro de masas da configuración orixinal. Isto é debido a que o centro de masas non cambia ao aplicar os movementos, é obviamente o centro de masas da configuración colapsada e exactamente o punto onde colapsa.

A idea entón é a seguinte: vamos deseñar unha configuración tal que todos os puntos nos que poden estar as moedas (despois de un número finito de movementos) cumpran unha certa propiedade que o centro de masas non, e polo tanto teríamos unha configuración non colapsable.

Para encontrar tal propiedade, compre estudar o movemento posible máis a fondo. Supoñamos que temos moedas $A_1,\dots ,A_n$ nos puntos $(x_1,y_1),\dots ,(x_n,y_n)$. Se escollemos as moedas $A_1$ e $A_2$ e as colapsamos, ambas terán coordenadas $\left(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2}\right)$. Se agora escollemos $A_1$ e $A_3$, levaremos as moedas ao punto $\left(\frac{x_1+x_2+2x_3}{4},\frac{y_1+y_2+2y_3}{4}\right)$. Mediante este razoamento é fácil ver que as coordenadas de calquera moeda sempre serán da forma

$$\left(\frac{\Sigma {\alpha }_i{x}_i}{2^m},\frac{\Sigma {\beta }_i{y}_i}{2^m}\right)$$

onde $m$ é un natural calquera e os coeficientes ${\alpha }_i,{\beta }_i$ son tamén naturais.

Nótese que o feito de que o denominador sexa tan “sinxelo” é moi sospeitoso, ademais de que é unha potencia de dous. Podemos entón intentar encontrar unha configuración de moedas tal que o seu centro de masa non teña coordenadas que podan expresarse como en (\ref{ji}), pero nótese que isto a priori non é posible, xa que o numerador pode ser calquera número real, incluso irracional.

Agora ben, podemos facer que o numerador sexa enteiro simplemente impoñendo que $x_i$ e $y_i$ sexan todas números enteiros, e agora a idea si que é moi prometedora. Ademais para facilitar a busca, podemos colocar todas as moedas no eixo $OX$, da tal forma que so temos que preocuparnos dunha coordenada.

Unha configuración válida é colocar $n-1$ moedas no orixe de coordenadas e 1 moeda no punto $(1,0)$. Neste caso o centro de masa estará en $\left(\frac{1}{n},0\right)$, e se $n\ne 2^k$ entón $\frac{1}{n}$ non pode expresarse como unha fracción con numerador enteiro e denominador igual a unha potencia de dous. Concluímos que esta configuración non é colapsable.

---

Dúbidas & Comentarios

Nesta sección pódesnos deixar as túas dúbidas e comentarios a cerca do problema anterior. Non teñas teima en preguntar, estamos aí para botar unha man!