・ 英語の試験もなかなか Ｓ．Ｈ氏
平成１９年度大学入試センター試験の英語の問題に、面白い問題が出ているということ
を、当ＨＰがいつもお世話になっている加俊さんから教えていただいた。
（当ＨＰ掲示板「出会いの泉」（平成１９年２月５日付け））
今年のセンター入試の英語の問題に、面白そうな数学のゲームみたいなのがありました。
二人が交互に行うゲームです。用意するものは、紙と鉛筆のみ。
（１） 始めにいくつかの点を書く。（最初は、３つ、４つのときから考えた方がよい。）
（２） それらのうちの一つから線を引き始め自分または他の線と交わらないように適当な
点と結ぶ。このとき、点は元の点でもよい。
ただし、一つの点から出る線は三本以下とする。
（３） 引いた線上に一つ点を付ける。つまり、このとき新たに作った点は、すでに二本の
線に結ばれていることになる。
（４） （２）～（３）を繰り返し、線が引けなくなったら終了。
かなり長い勝負になりそうですが、必勝法はあるのでしょうか？？
英語の試験も「なかなかやる～！」と思いながら、この問いかけに興味を持ったので、少し
考えてみた。ここでは、最後に線を引いた人を、このゲームの勝者とする。
３個の点がある場合
左図のように、８本の線を引けば、後手が勝つことになるわけ
だが、線の引き方はもっと別な場合もあるので、事は、そう単純
にはいかないようだ。
当ＨＰがいつもお世話になっている、らすかるさんによれば、下図のように先手が最初の
１手で他の１点を内部に、残りの１点を外部にあるように自分自身を線で結ぶと先手必勝
になるそうである。なぜならば、後手の可能性は、
など、いろいろな場合があるが、後手がどのような線を引いても最後の１本を先手が必ず
引けるからである。（上図の続きを是非楽しんで欲しいと思う！）
したがって、３個の点の場合は、
自分自身に戻る線を、他の１点を内部に、残りの点を外部にあるように引く
ことが、先手必勝形に持ち込む最良の方法である。先手必勝形を見つけるには、線の本数
が奇数になる最小のパターンを見つければいいようだ。このことは加俊さんが指摘している。
当ＨＰがいつもお世話になっている未菜実さんからの情報によると、このゲームは、スプラ
ウト（Ｓｐｒｏｕｔｓ）ゲームというようで、次の本が詳しいそうである。
マーチンガードナー 著 一松 信 訳 数学カーニバルⅠ （紀伊国屋書店） 11p～20p
このゲームの発案者は、コンウェイとパターソン（１９６０年代後半）とのことである。
未菜実さんによれば、必勝法は、点の個数が １～６個までは分かっているとのことで、
| 点の個数 |
１ |
２ |
３ |
４ |
５ |
６ |
| 必勝者 |
後手 |
後手 |
先手 |
先手 |
先手 |
後手 |
となるそうである。因みに、６個の点の場合の証明は、４９ページにも及ぶらしい！
（参考） 未菜実さんからの情報によると、証明は当時、ケンブリッジの数学科のデニス・
Ｐ・モリソン（Denis P.Mollison)によるもので、コンウェイが１０シリングの賭金を出
したのに対して、証明を提出した、となっていて、文献として残っているかどうか
は不明だそうである。
（追記） 平成１９年２月１４日付け
らすかるさんのご奮闘により、７個の点の場合が解決されました。
「後手必勝」とのことです。（８０時間！かかったそうです．．．スゴイ。）
らすかるさん、お疲れ様でした！ （追記終）
実際に、必勝手順を考察してみよう。
１個の点の場合、後手が必勝であることは明らかだろう。
２個の点の場合、後手が必勝であることはそれほど明らかではない。
もし先手が、
ときたら、後手は、
と応対すればよい。このとき、先手がどう線を結んでも後手は必ず勝てる線の引き方がある
ので、後手必勝である。
もし先手が、
ときたら、後手は、
と応対すればよい。このとき、先手がどう線を結んでも後手は必ず勝てる線の引き方がある
ので、後手必勝である。
もし先手が、
ときたら、後手は、
と応対すればよい。このとき、先手がどう線を結んでも後手は必ず勝てる線の引き方がある
ので、後手必勝である。
３個の点の場合、先手が必勝であることは比較的容易に確かめられた。しかし、２個の
点での検証からも分かるように、後手必勝を示すのはかなり難しそうだ。
未菜実さんからの情報でも、６個の点の場合、後手必勝を証明するのに、４９ページも必
要とのことであるが、２個の場合の経験から予想できる数字である！
４個の点の場合、５個の点の場合も、一応、下図のように線の引き方の一つを書いては
みたものの、ゲームなのでそのようにはすんなりいかないのが玉に瑕．．．。
| ４個の点がある場合 |
|
５個の点がある場合 |
 |
|
 |
両者とも先手必勝ということなので、初手に先手がどういう対応をし、後手の対応に対して
先手がどう答えるのかを考えればいいわけだが、気が遠くなりそうな雰囲気である。
（追記） 平成１９年２月１４日付け
らすかるさんのご奮闘により、４個、５個の点の場合について、先手が初手
に取るべき手が明らかとなった。
４個の点の場合は、
５個の点の場合は、
（コメント） この後どう応手するのか、楽しみが増えましたね！ （追記終）
（コメント） この問題を原文で英語の先生に見てもらったところ、大変驚かれていました。私
も、まさか英語の問題に数学の問題があるとは思いませんでした。でも、たいそう
な英文を読ませておいて、設問のレベルの低さには驚きました。あれでは英文を
正確に読まなくても正解が書けてしまいますね！配点が１２点分あるのに．．．。
これは、受験生に点をやるための問題なのですかね？
面白い問題をお教えいただいた加俊さんに感謝いたします。
（追記） 未菜実さんからの情報によると、
Ｎ個の点に対して、線が引ける最大本数は、３Ｎ－１である
ことが、コンウェイによって証明されているそうである。（２月７日付け）
ということは、次の手順で線を引く場合に最大本数が与えられるのだろうか？
（１） トポロジー的に、Ｎ個の点は、正Ｎ角形の頂点としてよい。隣り合う頂点を結んで辺と
する。 ・・・・ このとき、Ｎ本の線が引かれる。
（２） 各辺の中点と隣り合う頂点の一つを結ぶ。 ・・・・ このとき、Ｎ本の線が引かれる。
（３） このときできるＮ個の点から２点を選んで結ぶ。
・・・・ このとき、Ｎが偶数なら、Ｎ/２本の線が引かれる。
・・・・ このとき、Ｎが奇数なら、（Ｎ－１）/２本の線が引かれる。
（４） Ｎが偶数のとき、Ｎ/２個の点について、（３）の操作を行う。
Ｎが奇数のとき、（Ｎ－１）/２＋１個の点について、（３）の操作を行う。
以上の操作を繰り返すことにより、任意のＮ個の点について、描かれる線分の本数が求
められる。（最後の２点を結んだ時点で終了！）
例 Ｎ＝３ のとき
線の本数＝３＋３＋（３－１）/２＋（１＋１）/２＝８
例 Ｎ＝４ のとき
線の本数＝４＋４＋４/２＋２/２＝１１
例 Ｎ＝５ のとき
線の本数＝５＋５＋（５－１）/２＋｛（２＋１）－１｝/２＋（１＋１）/２＝１４
例 Ｎ＝６ のとき
線の本数＝６＋６＋６/２＋（３－１）/２＋（１＋１）/２＝１７
上記の計算は、ガウス記号を用いれば、もっとすっきりするだろう。
上記の（１）～（４）の手順で、（１）（２）は必然で、２Ｎ本の線が引かれる。
（３）（４）によって出来る点は、もはやあと１点としか結ぶことができず、また、２つの点から
同じ性質をもつ点を１つ生成しているので、できる線の本数は、
［Ｎ/２］＋［（Ｎ－［Ｎ/２］）/２］＋・・・・・＝Ｎ－１
である。以上から、Ｎ個の点に対して、結ばれる線の本数は、
Ｎ＋Ｎ＋Ｎ－１ ＝ ３Ｎ－1
となる。
先手・後手が勝負を終わらせまいと互いに譲歩しつつ線を引いた場合の最大本数が、
（点の個数）×（１点から出る線の最大数）－１
の形をしている点がとても興味深い。
ところで、
Ｎ個の点があるとき、引くことが出来る線の最大本数は、３Ｎ－１本
ということを、らすかるさんは、「ほとんど自明！」（Ｈ１９．２．７）と仰っている。
らすかるさんが使っている文言をちょっと修正させていただいて、一応検証しておこう。
Ｎ個の点があるとする。１個の点から３本まで線が引けるので、１個の点には３つの接合
部があると考えられる。よって、Ｎ個の点全体では、接合部の合計は、３Ｎ個ある。
点と点（自分自身を含む）を線で結ぶということは、３Ｎ個の接合部から２つを選んで結ぶ
ということである。この際、新たに１点が生じ、接合部が１個だけ増える。
このことから、線を１本引くことにより、接合部の個数は、２減１増なので、結局、１個だけ
減少する。
したがって、接合部の個数が３Ｎ個から１個になるまで、線を引くことが可能で、よって、
引くことが出来る線の最大本数は、３Ｎ－１本である。
らすかるさんによれば、
「閉領域によって孤立箇所が出来ると、３Ｎ－１
本より減り、ここがゲームになっている。
閉領域で孤立箇所が出来ないように隣接点ば
かり繋いでいけば、必ず ３Ｎ－１ 本になる。」
（左図は、Ｎ＝５ で、線の本数が、１４本の場合）
上記では、線を引くことが出来る最大本数が「３Ｎ－１本」ということであったが、らすかる
さんは、「３Ｎ－１本」が必ず可能であることを次のように証明された。（Ｈ１９年２月８日付け）
最初に適当な点Ａを選び、１本目の線はＡからＡのループとし、中間点をＢとする。２本目
の線は、ＡとＢを上記ループの外側で結び、中間点をＣとする。これで、点Ａと繋がっている
図形から出せる線は残り１本（Ｃから）だけとなり、他の新しい点を使わないと線が引けない
状態になる。（以上の線はすべて閉領域に他の点を含まないようにＡの近傍で引く）
次に新しい点Ｄを選び、１本目の線はＣとＤを結び、中間点をＥとする。２本目はＤとＥを結
び、中間点をＦとする。３本目はＤとＦを、閉ループＤ－Ｅ－Ｆ－Ｄの外側で結び、中間点をＧ
とする。これで点Ａと繋がっている図形から出せる線は残り１本（Ｇから）だけとなり、他の新
しい点を使わないと線が引けない状態になる。（以上の線も、他の点を閉領域内に含まない
ようにＣからＤを結んだ線の近傍で引く）
この操作を繰り返すと、Ａの近傍－Ｄの近傍－３つ目の新しい点の近傍－…と数珠繋ぎの
図形が出来るが、他の新しい点を閉領域に閉じ込めることがないので、残りの新しい点が
使用出来なくなることはない。
よって、点Ａを使って、２本、次に新しい点を使うたびに3本多く線が引けるので、３Ｎ－１本
の線を引くことが可能である。
らすかるさんの証明に対して、当ＨＰがいつもお世話になっている加俊さんは、
Ｎ個の点があるとき、引くことが出来る線の最大本数は、３Ｎ－１本
ということを、次のように不等式を用いて証明された。（平成１９年２月８日付け）
最初の点の個数が、Ｎ 個のときに引ける線の最大本数を、Ｆ(Ｎ) と表す。
明らかに、Ｎ＝１ のとき、 Ｆ(１)＝２ である。
次に Ｎ≧２ とする。Ｎ個の各点において、自分自身と線で結び、さらに、そのとき出来る
点と自分自身をループの外部で結ぶ。このとき、あと１本しか線が引けない点が１個できる。
これらの点は全部でＮ個ある。このうち２個を選んで線で結び、このとき出来る点と残りの
Ｎ－２個の点から１個選んだ点を結ぶ。
この操作を続けると、全部でＮ－１本の線を引くことが出来る。
よって、 Ｆ(Ｎ)≧２Ｎ＋Ｎ－１≧３Ｎ－１
ところで、１本の点からは、３本の線以下しか引けず、１本線を引く毎に、点から出せる線の
総数が１減っていくことから、 Ｆ(Ｎ)≦３Ｎ－１
したがって、 Ｆ(Ｎ)＝３Ｎ－１ である。
（コメント） やっと、追いついたかな．．．？
当ＨＰがいつもお世話になっているＨＮ「ＦＮ」さんからの問題提起です。
（平成２２年１１月１９日付け）
上記では、最初の点が Ｎ 個であるとして、次のことが示されている。
引ける線の数、即ち、勝負がつくまでの手数は、３Ｎ－１ 以下である。
（実際に、３Ｎ－１本の線が引けるケースがある！）
従って、勝負がつくまでの手数の最大値は、３Ｎ－１であることは証明されています。
では、
勝負がつくまでの手数の最小値、即ち、引ける線の数の最小値
はどうなるでしょうか？
攻略法さんの考察によれば、答えは「２Ｎ」とのことである。（平成２２年１１月２４日付け）
考 察（証明ではありません！）
最初の点を、Ａ、Ｂ、Ｃ、・・・ とし、追加される点を順に、１、２、３、・・・ とする。
N＝３ の場合
ABC12345678
0手:00000000000
1手:20020000000
2手:22022000000
3手:33022200000
4手:33222220000
5手:33332222000
6手:33333322200 ←
7手:33333333220 ← ここで先手が必勝？
8手:33333333332 ←
のように各点の線の本数が決まる。図示すれば下図となる。
Ａ、Ｂ、Ｃ、・・・、１、２、３、・・・ の順になるべく早く「引けなくする（値を３にする）」ように埋
めていく。
６手目で終了するには、線の本数が「2」の点が３つあるが、それらが２つ以上の閉路で区
切られ、別々の３つの領域に配置されていればよい。
同じ領域に「2」以下の点が２つ以上あれば、それらを結ぶことができる。
閉路を構成するのは、「3」の点列である。最少数は２個となる。
点が一列に並んでいるとすると、 {3,2,3, 3,2,3, 3,2,3} とすればよい。
具体的には、２つの閉路 A-1、3-C-5 で区切られた３つの領域 ※括弧数字が「2」の点
┌───┐┌───┐ ┌───┐
A─(2)─1 B─(4) 3─C─(6)─5
└───┘└─┘ └─────┘
手順： A-A、A-1、B-C、B-B、C-3、C-5 の順に線を引いていく。
３つの閉路 A-1、B-3、C-5 で区切られた４つの領域
┌───┐┌───┐┌───┐
A─(2)─1 B─(4)─3 C─(6)─5
└───┘└───┘└───┘
手順：A-A、A-1、B-B、B-3、 C-C、C-5 の順に線を引いていく。
がその一例である。
閉路を構成する条件は、3の個数をN(3)、2の個数をN(2)とすると、N(3)≧2N(2) の場合
は可能である。
７手目で終了するには、{…, 3,2,3, …, 3,2,3, …} ※…の部分には残りの「3」が入る
とすればよい。
Ｎ＝１ の場合
A12
0手:000
1手:220
2手:332 ← 後手
Ｎ＝２ の場合
AB12345
0手:0000000
1手:2020000
2手:2222000
3手:3322200
4手:3333220 ← ここで後手必勝？
5手:3333332 ←
Ｎ＝４ の場合
ABCD123456789ab
0手:000000000000000
1手:200020000000000
2手:220022000000000
3手:330022200000000
4手:332022220000000
5手:332222222000000
6手:333322222200000
7手:333333222220000
8手:333333332222000 ←
9手:333333333322200 ← ここで先手が必勝？
10手:333333333333220 ←
11手:333333333333332 ←
Ｎ＝５ の場合
ABCDE123456789abcde
0手:0000000000000000000
1手:2000020000000000000
2手:2200022000000000000
3手:3300022200000000000
4手:3320022220000000000
5手:3322022222000000000
6手:3333022222200000000
7手:3333222222220000000
8手:3333332222222000000
9手:3333333322222200000
10手:3333333333222220000 ←
11手:3333333333332222000 ← ここで先手が必勝？
12手:3333333333333322200 ←
13手:3333333333333333220 ←
14手:3333333333333333332 ←
ＦＮさんからのコメントです。（平成２年１１月２４日付け）
問題の答えが「２Ｎ」とのことですが、正解だと思います。２Ｎ以上であることと、２Ｎ以下で
あることを示せばいいわけですが、２Ｎ以下であることは、実際に、２Ｎ手で終わるケースを
作ればいいわけで、攻略法さんの次の手順をそのまま一般化すればＯＫです。
３つの閉路 A-1、B-3、C-5 で区切られた４つの領域
┌───┐┌───┐┌───┐
A─(2)─1 B─(4)─3 C─(6)─5
└───┘└───┘└───┘
手順：A-A、A-1、B-B、B-3、 C-C、C-5 の順に線を引いていく。
あとは、２Ｎ以上であることの証明ですが．．．。攻略法さんの記号 N(3) と
N(2) の関係か
ら出そうです。終局した時点でN(3)≧2N(2)が成り立っていることとかを使えば．．．。
