불변 수량 찾기

Question

하나를 제외한 모든 정점 (예 : $v$) / $12$-gon 표시 $+1,$ 과 $v$ 표시됩니다 $-1.$ 각 단계에서 우리는 선택할 수 있습니다 $3$인접한 정점과 기호를 변경합니다.
모든 정점을 표시 할 수 있습니까?$+1$ 인접한 것을 제외하고 $v?$

불변을 찾아서 불가능 함을 증명하고 가능함을 증명하려했지만 성공하지 못했다.

Answer 1

힌트 : 정점을 반복 패턴으로 빨강, 녹색 및 파랑으로 색칠하여 십 각형 주위에 균등 한 간격으로 각 색상의 4 개의 정점이 있도록합니다. 허락하다$R$ 빨간색 정점의 수는 $+1$, 유사하게 $G$ 과 $B$. 각 움직임이 어떤 영향을 미치는지$R, B$ 과 $G$? 무엇인가$R,B,G$처음에? 성공한다면이 수량은 어떻게 될까요?

Answer 2

내 솔루션은 약간의 속임수입니다. 그것은 기초적인 빛으로 보여지는 비 기초적인 해결책입니다 (핵심 아이디어는 본질적으로 선형 대수학입니다).

이것이 가능하다고 가정하십시오. 그런 다음 이웃을 중심으로 "뒤집기"로 구성합니다.$v$, 우리는 하나의 정점 기호 만 변경된 구성을 찾습니다 (이웃의 다른 이웃).

따라서 질문은 대신 – 허용 된 작업으로 단일 부호를 뒤집을 수 있습니까?

이것이 가능하다면 반복적으로 승인 된 이동을 적용하여 시작 구성에서 모든 구성에 도달 할 수 있습니다.

이제 $2^{12}$ 가능한 구성이므로 정확히 $2^{12}$ 각각 다른 일을하는 가능한 일련의 움직임.

모든 "기본 동작"이 출퇴근하고 인볼 루션이라는 점을 감안할 때 모든 일련의 동작은 일부 동작과 동일한 결과를 생성합니다. $f_{i_1}\ldots f_{i_p}$ 어디 $1 \leq i_1 < \ldots < i_p \leq 12$ 과 $f_k$ 정점의 부호를 뒤집는 움직임입니다. $k$그리고 그 이웃. 이러한 시퀀스를 R- 시퀀스라고합니다.

다시 말하지만, $2^{12}$ $R$-시퀀스가 다른 결과를 생성하며 정확히 $2^{12}$ $R$-시퀀스. 그래서 두 가지$R$-시퀀스는 다른 결과를 생성해야합니다.

그러나 뚜렷한 $R$-시퀀스 $f_1f_2f_4f_5f_7f_9f_{10}f_{11}$ 빈 시퀀스는 동일한 결과를 생성하고 모순을 얻습니다.