Finden Sie eine unveränderliche Menge

Question

Alle Eckpunkte bis auf einen (sagen wir $v$) von a $12$-gon sind markiert $+1,$ und $v$ ist markiert $-1.$ Bei jedem Schritt können wir wählen $3$benachbarte Eckpunkte und ändern ihre Vorzeichen.
Ist es möglich, jeden Scheitelpunkt markieren zu lassen?$+1$ bis auf eine neben $v?$

Ich habe versucht zu beweisen, dass es unmöglich ist, indem ich invariant suche, und ich habe auch versucht zu beweisen, dass es möglich ist, aber es ist mir nicht gelungen.

Answer 1

Tipp: Färben Sie die Scheitelpunkte rot, grün und blau in einem sich wiederholenden Muster, sodass vier Scheitelpunkte jeder Farbe gleichmäßig um das Zwölfeck verteilt sind. Lassen$R$ sei die Anzahl der roten Eckpunkte, die sind $+1$ähnlich für $G$ und $B$. Wie wirkt sich jede Bewegung aus?$R, B$ und $G$? Was sind$R,B,G$anfänglich? Was würden diese Mengen werden, wenn Sie erfolgreich wären?

Answer 2

Meine Lösung ist ein bisschen betrügen. Es ist eine nicht-elementare Lösung (die Kernidee ist im Wesentlichen eine lineare Algebra), die in einem elementaren Licht gezeigt wird.

Angenommen, dies ist möglich. Dann komponieren Sie dies mit einem "Flip", der auf den Nachbarn von zentriert ist$v$finden wir eine Konfiguration, bei der nur ein Scheitelpunktzeichen geändert wurde (der andere Nachbar des Nachbarn).

Die Frage ist also stattdessen: Können wir mit den erlaubten Operationen ein einzelnes Vorzeichen umkehren?

Wäre dies möglich, könnten wir jede Konfiguration von jeder Startkonfiguration aus erreichen, indem wir iterativ autorisierte Bewegungen anwenden.

Jetzt sind da $2^{12}$ mögliche Konfigurationen, das heißt, es gibt genau $2^{12}$ mögliche Abfolgen von Bewegungen, die jeweils unterschiedliche Dinge tun.

Angesichts der Tatsache, dass alle „Elementarbewegungen“ pendeln und Involutionen sind, führt jede Folge von Bewegungen zum gleichen Ergebnis wie einige andere $f_{i_1}\ldots f_{i_p}$ wo $1 \leq i_1 < \ldots < i_p \leq 12$ und $f_k$ ist die Bewegung, die das Vorzeichen des Scheitelpunkts umdreht $k$und seine Nachbarn. Solche Sequenzen werden als R-Sequenzen bezeichnet.

Wieder muss es sein $2^{12}$ $R$-Sequenzen führen zu unterschiedlichen Ergebnissen, und es gibt genau $2^{12}$ $R$Folgen. Also zwei verschiedene$R$-Sequenzen müssen unterschiedliche Ergebnisse liefern.

Allerdings ist das deutlich $R$Folgen $f_1f_2f_4f_5f_7f_9f_{10}f_{11}$ und die leere Sequenz erzeugt das gleiche Ergebnis und wir bekommen einen Widerspruch.