Encontre uma quantidade invariável

Question

Todos os vértices, exceto um (digamos $v$) de um $12$-gon são marcados $+1,$ e $v$ é marcado $-1.$ Em cada etapa, podemos escolher $3$vértices adjacentes e mudam seus sinais.
É possível ter todos os vértices marcados$+1$ exceto por um adjacente a $v?$

Tentei provar que é impossível pesquisando invariante, e também tentei provar que é possível, mas não tive sucesso.

Answer 1

Dica: pinte os vértices de vermelho, verde e azul em um padrão repetido, de forma que haja quatro vértices de cada cor igualmente espaçados ao redor do dodecágono. Deixei$R$ seja o número de vértices vermelhos que são $+1$, da mesma forma para $G$ e $B$. Como cada movimento afeta$R, B$ e $G$? O que são$R,B,G$inicialmente? O que essas quantidades se tornariam se você tivesse sucesso?

Answer 2

Minha solução é um pouco trapaceira. É uma solução não elementar (a ideia central é essencialmente alguma álgebra linear) mostrada sob uma luz elementar.

Suponha que isso seja possível. Então, compondo isso com um "flip" centrado no vizinho de$v$, encontramos uma configuração onde apenas um sinal de vértice foi alterado (o outro vizinho do referido vizinho).

Portanto, a questão é - podemos, com as operações permitidas, inverter um único sinal?

Se isso fosse possível, poderíamos alcançar qualquer configuração a partir de qualquer configuração inicial, aplicando movimentos autorizados iterativamente.

Agora estão aí $2^{12}$ configurações possíveis, o que significa que existem exatamente $2^{12}$ possíveis sequências de movimentos fazendo coisas diferentes cada um.

Dado que todos os "movimentos elementares" comutam e são involuções, qualquer sequência de movimentos produz o mesmo resultado que alguns $f_{i_1}\ldots f_{i_p}$ Onde $1 \leq i_1 < \ldots < i_p \leq 12$ e $f_k$ é o movimento invertendo o sinal do vértice $k$e seus vizinhos. Essas sequências são chamadas de sequências-R.

Novamente, deve haver $2^{12}$ $R$- sequências que produzem resultados diferentes, e há exatamente $2^{12}$ $R$-sequências. Então dois diferentes$R$- as sequências devem produzir resultados diferentes.

No entanto, o distinto $R$-sequências $f_1f_2f_4f_5f_7f_9f_{10}f_{11}$ e a sequência vazia produz o mesmo resultado e obtemos uma contradição.