◆東京都 サボテン さんからの解答。
ルールを自分なりに書き換えて考えてみました。
もしかしたら問題で意図されているルールと異なるかもしれません。
一筆書きのルール
補題:C_{i}∈RかつC_{j}∈Rならば、線のつなぎかえでC_{i}とC_{j}を一つのループC_{i}+C_{j}にすることが できる。
以下に場合わけして考える。
P_{k}∈Rとする。
1)C_{i}:P_{1}→P_{1} ,C_{j}:P_{2}→P_{2}と結ばれているとき
このときはP_{1}→P_{2}のつなぎかえによってループが結合可能
2)C_{i}:P_{1}→P_{1} ,C_{j}:P_{2}→P_{3}
P_{1}→P_{2}, P_{1}→P_{3} のつなぎかえで結合可能
3)C_{i}:P_{1}→P_{2} ,C_{j}:P_{2}→P_{1}
P_{1}→P_{1}, P_{2}→P_{2} のつなぎかえで結合可能
3)C_{i}:P_{1}→P_{2} ,C_{j}:P_{2}→P_{3}
P_{1}→P_{3},P_{2}→P_{2}のつなぎかえで結合可能
4)C_{i}:P_{1}→P_{2} ,C_{j}:P_{3}→P_{4}
P_{1}→P_{3},P_{2}→P_{4}のつなぎかえで結合可能
証明終
証明
・「Terの任意の分割に対し、その境界線上に必ず1つ以上の交点がある→全ての正方形を通る一筆書きが可能」の証明
任意の分割を正方形1つに適用すると、仮定からどの正方形にも必ず1つ以上交点が存在する。
正方形の個数は有限なので、必ずループを描くことになる。
その時できるループをC_{1},C_{2},....C_{n}とする。
またそれに対応してTer_{i}を取る。
どの正方形にも交点が存在するので、
C_{1}∪C_{2},...∪C_{n}は全ての正方形を通過する。
今Ter_{1}に注目して考える。
仮定よりTer_{1}の境界線上に交点Pが存在する。
この時ある∃i,C_{i}の一部がTer_{1}に含まれる。
なぜなら、Pを通る線がC_{1}のものだけであったと仮定すると、
Ter_{1}を拡張することができ、Ter_{1}の定義に反するからである。
よって∃i,C_{i}がPを通過することになる。
よって∃R,R∈Ter_{i} ,C_{1}∈RかつC_{i}∈R。
すると補題からループを結合してC_{1}+C_{i}なるループができる。
Ter{1}∪Ter{i}⊃Ter{1}である。
同様にしてこの操作を繰り返すとTerを次々に拡大して、最終的に一つのループが完成する。
前述のことからC_{1}∪C_{2},...∪C_{n}は全ての正方形を通過するので、完成したループも全ての正方形を通過する。
よって全ての正方形を通る一筆書きが可能である。//
・「全ての正方形を通る一筆書きが可能→Terの任意の分割に対し、その境界線上に必ず1つ以上の交点がある」の証明
対偶「Terのある分割に対し、その境界線上に交点がない→全ての正方形を通る一筆書きは不可能」を考える。
そのような分割に対し、ループは領域として完全に遮断されるので、ループを結合することはできない。
よって全ての正方形を通る一筆書きは不可能
以上のことから「Terの任意の分割に対し、その境界線上に必ず1つ以上の交点がある⇔全ての正方形を通る一筆書きができる」が証明された。