ライツアウトを代数的に見る (1)

みなさん, ライツアウトというゲームは知ってますか? 少し前に流行ったので知ってる人も多いでしょう. 4×4のマス目にボタンが配置されていて, ゲームの初期状態ではいくつかは光っています.

光ってるボタン:

光っていないボタン:

初期状態:

■ □ □ ■
■ ■ □ □
□ ■ ■ ■
□ □ □ □

ここで真ん中のボタンを1つ押すと次のように光り方が変化します.

□ □ □
□ □ □
□ □ □
↓
□ ■ □
■ ■ ■
□ ■ □

■ ■ □
■ ■ □
□ □ □
↓
■ □ □
□ □ ■
□ ■ □

このゲームのゴールは全てのボタンを光らせることです. (全てのボタンの光を消す, というのも考えられますが, 問題としては同じなので光る方を選びました.)

問題になるのは,

  • 初期状態だけを見てこのゲームはクリアできるのか?
  • 任意の初期状態に対してクリアする方法があるのか?

といったところです. これを数学的に扱っていきます.