26/01/10 00:17:26.72 9327Ur+i.net
操作1
頂点をひとつ選んで、○をつけ足す。
選んだ頂点の色は反転する。
操作2
辺をひとつ選んで、─○─で置き換える。
両端の頂点の色は反転する。
2:１３２人目の素数さん
26/01/10 00:21:48.57 os/eEvBf.net
n = 1
○
可能
n = 2
●─○しかない
不可能
n = 3
●─○
↓
○─○─○ 左端に足す
可能
n = 4
●─○
↓
●─●─○ 右端に足す
↓
○─○─○─○ 左の辺を置き換え
可能
3:１３２人目の素数さん
26/01/10 00:34:11.78 J+brZf9G.net
n = 3の全パターン
●─○
↓
(1) ●─●─○ 右端につける
(2) ○─○─○ 左端につける
(3) ○─○─● 辺を置き換え
n = 4の全パターン
●─●─●─○ (1)の右端につける
○─○─●─○ (1)の左端につける
○─○─○─○ (1)の左の辺を置換
●─○─○─● (1)の右の辺を置換
●─○─●─○ (2)の辺を置換
●─○─●─● (3)の左の辺を置換
もし、n = 5が可能なら、n = 4に
・片端だけ●、あと全部○
・●─●が一つ、あと全部○
のいずれかがある必要があるが、無いのでn = 5は不可能
4:１３２人目の素数さん
26/01/10 00:38:55.87 etRy3AMJ.net
もし、nが可能ならば
...─○─○
↓右端の頂点に操作1
...─○─●─○
↓右端の辺に操作2
...─○─○─○─●
↓右端に操作1
..─○─○─○─○─○
とできるので、n + 3も可能。
よって、n ≡ 0, 1 (mod 3)はすべて可能。
5:１３２人目の素数さん
26/01/10 02:10:01.79 flbEr88S.net
端の頂点に操作1をすることは、端にダミーの頂点をつけ足して操作2をして、ダミーの頂点を取り除くことと同じなので
初期状態を
●─○─●
と考えて操作2だけ考える
グラフの●を│に変えて、部屋に分割する
左の部屋から順番に+1, -1, +1, ...を割り振る
たとえば、
●─●─○─●
なら、
+1 │ -1 │ +1 | -1
各部屋にある白丸の数と部屋の符号をかけて足して3で割ったあまりを考える
この量は操作2の前後で変わらない
○が3m + 2個続くグラフが可能なら、そのグラフの上記の量は2にならないといけないが、両端にどうダミーをつけても、そうはならない
6:poem
26/01/10 05:19:16.09 Wt55uN2Z.net
つまりオセロ問題？
7:poem
26/01/10 05:19:52.30 Wt55uN2Z.net
オセロのゲーム理論を考えてるん？
8:１３２人目の素数さん
26/01/10 08:10:35.08 OQQ9FvTc.net
n ≡ 0,1 ( mod 3 )
9:１３２人目の素数さん
26/01/10 14:06:45.83 eVNjNCWn.net
オイラー標数？ホモロジー代数で定式化できん？
10:１３２人目の素数さん
26/01/10 16:23:06.06 GMHnexO3.net
東大の入試問題か？
11:１３２人目の素数さん
26/01/12 15:06:51.56 bYjIKTNP.net
東大の入試なら、グラフ理論らしいけど…。