Trouver une quantité invariante

Question

Tous les sommets, sauf un (disons $v$) d'un $12$-gon sont marqués $+1,$ et $v$ est marqué $-1.$ A chaque étape, nous pouvons choisir $3$sommets adjacents et modifiez leurs signes.
Est-il possible de marquer chaque sommet$+1$ sauf un adjacent à $v?$

J'ai essayé de prouver que c'était impossible en recherchant des invariants, et j'ai également essayé de prouver que c'était possible, mais je n'ai pas réussi.

Answer 1

Astuce: coloriez les sommets en rouge, vert et bleu dans un motif répétitif, de sorte qu'il y ait quatre sommets de chaque couleur espacés de manière égale autour du dodécagone. Laisser$R$ être le nombre de sommets rouges qui sont $+1$, de même pour $G$ et $B$. Comment chaque mouvement affecte-t-il$R, B$ et $G$? Que sont$R,B,G$initialement? Que deviendraient ces quantités si vous réussissiez?

Answer 2

Ma solution est un peu une triche. C'est une solution non élémentaire (l'idée principale est essentiellement une algèbre linéaire) présentée sous un jour élémentaire.

Supposons que cela soit possible. Ensuite, en composant ceci avec un «flip» centré sur le voisin de$v$, nous trouvons une configuration où un seul signe de sommet a été changé (l'autre voisin dudit voisin).

La question est donc plutôt la suivante: pouvons-nous, avec les opérations autorisées, inverser un seul signe?

Si cela était possible, nous pourrions atteindre n'importe quelle configuration à partir de n'importe quelle configuration de départ en appliquant des mouvements itérativement autorisés.

Maintenant il y a $2^{12}$ configurations possibles, cela signifie donc qu'il y a exactement $2^{12}$ séquences possibles de mouvements faisant des choses différentes chacun.

Étant donné que tous les «mouvements élémentaires» font la navette et sont des involutions, toute séquence de mouvements produit le même résultat que certains $f_{i_1}\ldots f_{i_p}$ où $1 \leq i_1 < \ldots < i_p \leq 12$ et $f_k$ est le mouvement inversant le signe du sommet $k$et ses voisins. Ces séquences sont appelées les séquences R.

Encore une fois, il doit y avoir $2^{12}$ $R$-des séquences produisant des résultats différents, et il y a exactement $2^{12}$ $R$-séquences. Donc deux différents$R$-les séquences doivent produire des résultats différents.

Cependant, le distinct $R$-séquences $f_1f_2f_4f_5f_7f_9f_{10}f_{11}$ et la séquence vide produit le même résultat et nous obtenons une contradiction.