新規性はないのですが、解けて嬉しかったため記念に書いていきます。

解法

$n = 0, 1 \pmod 3$ のときに可能で、$n = 2 \pmod 3$ のときには不可能です。前者は易しいので後者を示します。そのために不変量を定義します。

不変量 $ι(P)$ の定義

$n$ 頂点白黒パスグラフ $P$ に対して、左から順に頂点に $1, 2, \dots, n$ と番号を振ります。黒頂点が順に $x₁, \dots, xₖ$ であったとき、列 $d = (d _ 0, d _ 1, \dots, d _ k) ∈ ( ℤ/3ℤ ) ^ { k + 1 }$ を $d _ i = x _ { i + 1 } - x _i$ (ただし $x _ 0 = 0, \ x _ {k + 1} = n + 1$) によって定め、その交代和 を

$$ ι(P) = \sum _ {i  = 0} ^ k ( -1) ^ i d _ i $$

で表すと、実はこれが不変量になります。なおこの量は初期状態で $ι(P) = 1$、目的のグラフでは $ι(P) = n + 1 = 0$ です。

不変性の証明

辺操作が列 $d$ に与える影響は、次のように辺の端点の頂点の色により場合分けして書けて、どの場合も $ι(P)$ は不変です。

辺の両端店の頂点の色	影響	イラスト
白白	$(x) \mapsto (t, 2, x - 1 - t)$	▢—○—–—○—▢ ▢—●—○—●—▢
白黒	$(x, y) \mapsto (x + 2, y - 1)$	▢—○—–—●—▢ ▢—●—○—○—▢
黒白	$(x, y) \mapsto (x - 1, y + 2)$	▢—●—–—○—▢ ▢—○—○—●—▢
黒黒	$(x, 1, y) \mapsto (x + 2 + y)$	▢—●—–—●—▢ ▢—○—○—○—▢

頂点の後ろ挿入は、$P$ に —●—○—○ を push back しても $ι(P)$ の値が変わらないことに注意すると辺操作と同一視することができます。一方頂点の前挿入は ○—○—●— を push front して考えればよいです。この場合は $ι(P)$ が $-1$ 倍されますが、そもそも不変性の主張で $±1$ 倍の差を除いていたので問題なしです。これで証明終わりです。

感想

これ最初に見たの実は高校生の頃なのですよね。そのころはさっぱりでしたが印象には残っていて、いつか解きたくてネタバレを踏まないように生きてきたのですが、最近たまたままたお見かけしたので挑戦したら解けてびっくり！ 競プロのおかげですね。大学入試史上最難問（ほんまか？）なんて言われることがありますけれども、1998 年当時よりこの手の問題に慣れた方も増え、難易度評価も変わってきているかもです。