『マッチ棒の一筆書き』解答
◆愛知県 Y.M.Ojisan さんからの解答。
【問題１】 １８本
【問題２】 ３１本
【問題３】 ３８本
【課題】
ｎが偶数のとき ｎ２＋２
ｎが奇数のとき ｎ２＋ｎ＋１
上記式の本数の解は一般に、下図のように渦巻状にマッチを置いてゆけば得られる。
よって問題は課題解答が最大値であることを証明することである。
| 偶数 |
奇数 |
 |
 |
＜偶数＞
マッチは同方向に２本連続で置くことができないので、
従って、最大でｎ２＋ｎ本まで置ける可能性があるところまで絞られる。
さて、横２段ずつ端から切り出して考える。（下図）
このときｎ２＋ｎを最大限実現するには、２段を端から切り出しているので、縦２本の位置のどちらかはマッチを置かなければならない。
即ち、中央の１列の交点は総て縦置きのマッチの頭が存在する。
ところがｎは偶数なのでその頭数は奇数であり、全部を横置きのマッチで連結できない。
即ち、縦置きマッチをｎ＋１本置くことができるのは、一筆書きの端点があるときだけである。
これは各々の２段ごとに独立に言えることである。
同様に、縦２段ずつ切り出した横置きの場合の各２段に関しても言える。
よって最大マッチの数は、
ｎ（２段あたりの縦（or横）置きマッチ数）×ｎ（縦２段横２段合計ｎ組）＋２（端点用）＝ｎ２＋２である。
＜奇数＞
| ２本連続できないので 一列を見たとき最大 |
ｎ＋１
２ |
しか置けない。 |
従って、最大ｎ２＋２ｎ＋１まで置ける可能性がある。
しかしその置き方は一通りであって下図左の状態であり、一筆書きが成立しない。
この状態を解消するには、少なくとも縦または横の端から２列づつの組の総ての組の一方から１本減らしてずらさなければならず、
| 全部で |
ｎ＋１
２ |
本削減しなければならない（下図中央参照）。 |
さもないと、下図右のように小ループができる。
このとき、削減後の横（ないし縦）置きの本数は
ｎ２＋２ｎ＋１
２ |
− |
ｎ＋１
２ |
＝ | ｎ２＋ｎ
２ |
であるが、 |
マッチは縦横交互に置いてゆくことから、縦置きの本数は多くても横置きの本数＋１である。
よって 最大 ｎ２＋ｎ＋１ 本である。
| ｎ２＋２ｎ＋１ |
（ｎ２＋２ｎ＋１）−（ｎ＋１）／２ |
縦横両方に一組づつでも残すと |
 |
 |
 |
『マッチ棒の一筆書き』へ
数学の部屋へもどる