不変量を見つける
1つを除くすべての頂点（たとえば $v$）の $12$-gonはマークされています $+1,$ そして $v$ マークされています $-1.$ 各ステップで、選択できます $3$隣接する頂点とその符号を変更します。
すべての頂点にマークを付けることは可能ですか？$+1$ 隣接するものを除いて $v?$
不変条件を検索して不可能であることを証明しようとしました。また、可能であることを証明しようとしましたが、成功しませんでした。
回答
ヒント：頂点を赤、緑、青の繰り返しパターンで色付けして、各色の4つの頂点が十二角形の周りに等間隔で配置されるようにします。しましょう$R$ ある赤い頂点の数である $+1$、同様に $G$ そして $B$。それぞれの動きはどのように影響しますか$R, B$ そして $G$？何ですか$R,B,G$最初は？あなたが成功した場合、これらの量はどうなりますか？
私の解決策はちょっとしたごまかしです。これは、基本的な光の中で示される非基本的な解決策です（コアアイデアは本質的にいくつかの線形代数です）。
これが可能であると仮定します。次に、の隣人を中心とした「フリップ」でこれを構成します$v$、1つの頂点記号だけが変更された構成（その隣接のもう一方の隣接）が見つかります。
したがって、問題は代わりに、許可された操作でシングルサインオンを反転できるかどうかです。
これが可能であれば、繰り返し許可された移動を適用することで、開始構成から任意の構成に到達できます。
今、あります $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$-シーケンス。だから2つの異なる$R$-シーケンスは異なる結果を生成する必要があります。
ただし、 $R$-シーケンス $f_1f_2f_4f_5f_7f_9f_{10}f_{11}$ 空のシーケンスでも同じ結果が得られ、矛盾が生じます。