解答: 2020 初級 問題5

問題5.

多角形のうち、各辺が頂点以外では交差しないものを、「シンプル・ポリゴン」といいます。(※注釈by及川:例えば、図A, Bはシンプル・ポリゴンですが、Cはシンプル・ポリゴンではありません)

シンプル・ポリゴンである多角形を考えます。多角形の2つの頂点が隣接している場合、あるいは2つの頂点を結んだ線分がその多角形の内部に存在する場合、それらの2つの点は「ビジブル」であるとします。いま、多角形の頂点の数をnとします(nは正の整数)。多角形の各頂点が、ちょうど他の4つの点と「ビジブル」の関係となるnを全て求めなさい。

(問題作成者:Morteza Saghafian)


【補足:及川】

この問題が中学1・2年対象とは・・・・・IGOの解答がまだ公表されていなくて、私には解けなかったので、H先生に解いてもらいました。以下、H先生の解説を載せます。


【解答・解説】

各頂点が、ちょうど他の4つの点と「ビジブル」の関係となるような多角形は凸五角形のみであることを示す。

まず、条件を満たす多角形の頂点数が5以上であることは明らかである。以下、頂点数が5以上の多角形について、場合分けして考える。

(※ここでいう凸五角形は、5点のうち3点が同一線上に並んでいるようなものは含まないこととします。)



(1)ある4頂点であって、4頂点が互いにビジブルであるような組が存在する場合


まず、このような4点は凸四角形をなす。


証明:もし4点が凸四角形にならないのであれば、

・4点のうち3点が同一線上に並んでいる

・4点のうち3点がなす三角形領域の内部に残る1点が存在する

のいずれかとなる。同一直線上に並んでいるのであれば、その両端は互いにビジブルでない。3点がなす三角形領域の内部に残る1点が存在するのであれば、三角形領域をなす3点のうちいずれかの2点の組は互いにビジブルでない


4点を時計回りに頂点A、頂点B、頂点C、頂点Dと名付ける。

この時、4点がなす四角形領域の内部または周上には、頂点A・頂点B・頂点C・頂点Dならびにそれらがなす辺以外の頂点および辺は存在しない。


証明:もし四角形領域の内部または周上に辺が存在するならば、線分AB、線分BC、線分CD、線分DAのうちいずれかを横切っているような辺が存在することになり、この時4頂点は互いにビジブルでない。


したがって、この多角形の辺は頂点A~頂点B~頂点C~頂点D~頂点Aというように一周している。


次に、『各頂点が、ちょうど他の4つの点と「ビジブル」の関係にある』の条件を踏まえて頂点A~頂点B間に何個の頂点が存在しうるか考えると、頂点A~頂点B間に存在する頂点は高々一つであることが示せる。


証明:頂点A~頂点B間に存在する頂点が0個の場合は、辺ABを引けばよい。

・頂点Eは頂点A~頂点B間に存在する

・頂点A・頂点B・頂点Eがなす三角形領域の内部または周上には、頂点A・頂点B・頂点Eならびにそれらがなす辺以外の頂点および辺は存在しない。


多角形の三角形分割を考えると、このような頂点Eは必ず存在する。

この時、頂点Aにとって頂点B・頂点C・頂点D・頂点Eはビジブルであり、すでに4つ以上の点とビジブルの関係にあることになる。

ここでもし、頂点Aと頂点Eが隣接していないとすれば、頂点Aに隣接する別の頂点Fが、頂点A~頂点Eの間に存在することになる。頂点Eならびに頂点Fは定義より常に頂点Aとビジブルなので、頂点Aは5つ以上の点とビジブルの関係にあることになる。これは条件に反するので、頂点Aと頂点Fは隣接している。

同様に頂点Bと頂点Eも隣接している。したがって、頂点A~頂点B間には頂点E以外の頂点は存在しない。


同様にほかの区間についても考えると、この多角形に頂点は高々8個しかないとわかる。さらに、「頂点A~頂点B間にも頂点B~頂点C間にも別の頂点が存在する」といったことは起こりえない(頂点Bからビジブルな頂点が5つ以上になってしまうため)ことを踏まえると、この多角形に頂点は高々6個しかないこともわかる。

あとは配置を試していくと凸五角形のパターンのみが条件を満たす。

(2)ある4頂点であって、4頂点が互いにビジブルであるような組が存在しない場合


ある4頂点であって、4頂点が互いにビジブルであるような組が存在しないとき、その多角形の三角形分割は一意に定まる(一意に定まらないならば互いにビジブルな4頂点がなす凸四角形がある)。


ここで、このような多角形において互いにビジブルであるような頂点のペアが何組あるかと考えると、これは多角形を三角形分割したときの辺の数に一致する。この数は、頂点数 n のとき 2n+1 となることが数学的帰納法により示せる。


一方、各頂点がちょうど他の4つの点とビジブルの関係にあるとき、互いにビジブルであるような頂点のペアが何組あるかを考えると、頂点数 n のとき n×4÷2=2n である。よって両者が一致することはなく、「ある4頂点であって、4頂点が互いにビジブルであるような組が存在しない場合」には条件を満たす多角形は存在しないことが示せた。


以上より条件を満たす多角形は凸五角形のみであり、n=5 のみが答えとなる。

セサミ数学スクール   sesami248@gmail.com    080-7049-1025