Trova una quantità invariante

Question

Tutti i vertici, tranne uno (diciamo $v$) di una $12$-gon sono contrassegnati $+1,$ e $v$ è segnato $-1.$ Ad ogni passaggio possiamo scegliere $3$vertici adiacenti e cambiano i loro segni.
È possibile contrassegnare ogni vertice$+1$ tranne uno adiacente a $v?$

Ho provato a dimostrare che è impossibile cercando invarianti e ho anche provato a dimostrare che è possibile, ma non ci sono riuscito.

Answer 1

Suggerimento: colora i vertici di rosso, verde e blu in uno schema ripetuto, in modo che ci siano quattro vertici di ogni colore equidistanti attorno al dodecagono. Permettere$R$ essere il numero di vertici rossi che sono $+1$, allo stesso modo per $G$ e $B$. Come influisce ogni mossa$R, B$ e $G$? Cosa sono$R,B,G$inizialmente? Cosa diventerebbero queste quantità se ci riuscissi?

Answer 2

La mia soluzione è un po 'un trucco. È una soluzione non elementare (l'idea centrale è essenzialmente un'algebra lineare) mostrata in una luce elementare.

Supponiamo che sia possibile. Quindi, componendo questo con un "capovolgimento" centrato sul vicino di$v$, troviamo una configurazione in cui è stato cambiato solo un segno di vertice (l'altro vicino di detto vicino).

Quindi la domanda è invece: possiamo, con le operazioni consentite, invertire un singolo segno?

Se fosse possibile, potremmo raggiungere qualsiasi configurazione da qualsiasi configurazione iniziale applicando mosse autorizzate iterativamente.

Ora ci sono $2^{12}$ possibili configurazioni, quindi questo significa che ci sono esattamente $2^{12}$ possibili sequenze di mosse che fanno cose diverse ciascuna.

Dato che tutti i “movimenti elementari” sono pendolari e sono involuzioni, qualsiasi sequenza di movimenti produce lo stesso risultato di alcuni $f_{i_1}\ldots f_{i_p}$ dove $1 \leq i_1 < \ldots < i_p \leq 12$ e $f_k$ è la mossa che capovolge il segno del vertice $k$e dei suoi vicini. Tali sequenze sono chiamate sequenze R.

Di nuovo, deve esserci $2^{12}$ $R$-seguenze che producono risultati diversi, e ci sono esattamente $2^{12}$ $R$-seguenze. Quindi due diversi$R$-le sequenze devono produrre risultati diversi.

Tuttavia, il distinto $R$-seguenze $f_1f_2f_4f_5f_7f_9f_{10}f_{11}$ e la sequenza vuota produce lo stesso risultato e otteniamo una contraddizione.