◆ 17. 田村稔 さん

神奈川県には，観光協会が 1979 年に制定した「かながわの景勝 50 選」で選ばれた風光明媚な場所が 50 ヶ所あります。そこには「かながわの景勝 50 選」であることを示す石碑が立っています。みのるさんは，その石碑全部と写真を撮ることに挑戦中です。 ある日，みのるさんは地図上で，まだ行っていない場所 (赤点) どうしを，辺が交わらないように結んで，できるだけ多くの三角形を作りました。すると，すべての三角形に一つずつすでに行った場所 (青点) が入り，さらにできた図形の外側にも一つだけ行った場所 (青点) がありました (図は行った場所が 6 ヶ所，行ってない場所が 6 ヶ所の場合の例です)。 みのるさんがすでに行った場所は最大何ヶ所でしょうか？ (注) この問題での景勝の場所は実際の場所とは関係ありません。景勝の配置によっては行った場所の数は異なりますが，その中で最大の数を解答してください。 (かながわの景勝 50 選)

▼ 解説 三角形を一つ作るには，頂点が 3 個必要である。ここに頂点を一つ追加して，できるだけ三角形の数を増やすには，三角形の内部 (a) または外部から 3 頂点に線が結べる位置 (b) に頂点を追加すればよい。このとき，どちらの場合も三角形が 2 個増える。その結果，外周は三角形になり，その内部は三角形で仕切られる (下図)。 外周が n 角形 (n＞3) の場合，頂点を外部に一つ追加すると，三角形は最大で (n−1) 個増える。また，n 角形は簡単な変形を繰り返すことにより，外周を三角形にすることができる。このとき，三角形は (n−3) 個増える (下図)。 よって，ある頂点数において，外周が三角形の場合の三角形の最大数を x とすると，外周が n 角形の場合の三角形の最大数は x−(n−3) である。ここに頂点を一つ追加すると，三角形は最大で (n−1) 個増え，三角形の最大数は x−(n−3)＋(n−1)＝x＋2 となる。 また，外周が三角形の場合は頂点を一つ追加すると，三角形は最大で 2 個増え，三角形の最大数は x＋2 となる。したがって，外周が三角形の場合を考えれば十分である。 頂点を一つ増やすごとに，三角形の最大数は 2 ずつ増えるので，頂点の数と三角形の最大数の関係は次のようになる。 頂点 3 4 5 ・・・ 17 18 19 ・・・ 三角形 1 3 5 ・・・ 29 31 33 ・・・ 題意より，頂点の数と三角形の最大数の和が 49 であればよい。上表から，そのときの頂点の数は 18 であり，これはまだ行ってない場所の数である。 したがって，すでに行った場所は 50−18＝32 ヶ所となる。