第４２６問の解答
問題［場合の数、平面図形］
 |
 |
 |
|
|
ある円周上に、１０個の点をとり、それらを結んで１０角形を作ります。（注） （注）１０個の点を結んでできる直線は１０角形の辺も含めると４５本ありますが、それらのうちどの２本を選んでも平行でなく、またどの３本を選んでも１点では交わらない（ただし、円周上を除く）ものとします。 |
|
 |
|
 |
解答例１
長野 美光さん、Taro さん、tomhさん、CRYING DOLPHINさん、アヒーのおじさんさん、姉小路さん、なかさん、小学名探偵さん、uchinyanさん、M.Hossieさん、kataさん、水田Xさん、他
まず、対角線の本数を数えてみましょう。以下では、一般的に凸n角形として考えます。
一つの頂点について対角線を引けるのは、自分とその両隣を除く(n-3)個あります。
従って、全部でn(n-3)本引けますが、各対角線について両端の頂点で重複して数えていることになります。
よって、実際の本数は、この半分の
Ｎ＝1/2×n(n-3)本
となります。従って、対角線２本を選ぶのは、全部で
NC2＝1/2×N(N-1)＝1/8×n(n-3)(n2-3n-2)通り
となります。題意より、どの対角線２本をとっても平行ではないので、必ず交点１個をもちます。
また、３本の対角線は１点では交わらないので、これらの頂点は全て異なるので、
交点数合計＝1/8×n(n-3)(n2-3n-2)個
となります。（本問では、５９５個）
さて、対角線の交点がn角形のどこにできるかで分類してみましょう。
n角形の内側になる場合（第３９０問参照）
凸n角形の対角線の交点は、多角形の４個の頂点を選ぶとそれに対して１個の交点が対応します。
従って、
交点数＝nC4＝1/24×n(n-1)(n-2)(n-3)
と求まります。（本問では、２１０個）
n角形の辺上になる場合（いずれかの頂点と一致する）
この場合、対角線の交点は、いずれかの頂点と一致します。
各頂点を固定し、これが対角線の交点になる場合を考えてみましょう。
この場合、交点はこの頂点を通る(n-3)本の対角線から２本選ぶn-3C2個となります。従って、
交点数＝n-3C2×n＝1/2n(n-3)(n-4)個
となります。（本問では、２１０個）
n角形の外側になる場合（求める本数）
全体の交点数から、１．内側、２．辺上の交点数を除いて求めます。
交点数＝1/8×n(n-3)(n2-3n-2)−1/24×n(n-1)(n-2)(n-3)−1/2(n-3)(n-4)n
＝1/12×n(n-3)(n-4)(n-5)個
となります。（本問では、５９５−２１０−２１０＝１７５個）従って、本問では、n＝10として、
外側の交点数＝1/12×10×７×６×５＝１７５個
と求まります。答： １７５個
以上
解答例２
mhayashiさん、uchinyanさん、スモークマンさん、他
解答例１では、n角形の内側にある交点数を、頂点４個を選んで求めました。
今度は、頂点４個を選ぶと外側に交点が２個できることに着目してみます。
頂点４個を選んで外側にできる交点
頂点４個を選ぶと１個の凸四角形ができます。
このとき、隣り合わない２個ずつの頂点を結ぶと内側に１個交点ができます。
今度は、隣り合う２個ずつの頂点を選ぶと（選び方は２通り）外側に１個ずつ、
合計２個の交点ができます。従って、
交点数＝nC4×２＝1/12×n(n-1)(n-2)(n-3)個
となります。（本問では、４２０個）
２辺で外側にできる交点
辺を１本選ぶと、自分とその両隣を除く(n-3)本の辺とで交点が外側にできる。
従って、n(n-3)個の交点ができるが、２辺の選び方で重複して数えていることになるので、
交点数＝1/2×n(n-3)個
となります。（本問では、３５個）
１辺と対角線で外側にできる交点
１辺を固定して考えます。
最初の１辺に含まれる２頂点以外の(n-2)個の頂点から２個を選ぶと、もう一方の対角線が選べます。
ただし、このうち２頂点がn角形の辺となる場合の(n-３)通りは除く必要がありますので、
n-2C2−(n-3)＝1/2×(n-3)(n-4)個
の頂点ができます。従って、１辺はn個あるので、
交点数＝1/2×(n-3)(n-4)n個
となります。 （本問では、２１０個）従って、
求める交点数＝（１）−（２）−（３）＝1/12×n(n-3)(n-4)(n-5)個
となります。（本問では、４２０−３５−２１０＝１７５個）
解答例３
辻。さん、DrKさん、小学名探偵さん、nemuさん、みかんさん、エルクさん、N.Nishiさん、 他
ここでは、１０角形に限定し考えることにします。
１頂点を固定し、そこから時計回りに頂点をA0、A1、・・・、A9とします。
A0と結んで対角線となる頂点は、A2、・・・、A8の７個になります。
それぞれの場合に分けて、これより右側に対角線が何本引けるかを数えていきます。
A2の場合
A3A5、A3A6、・・・、A3A9 ・・・ ５本
A4A6、A4A7、A4A8、A4A9 ・・・ ４本
A5A7、A5A8、A4A9 ・・・ ３本
A6A8、A6A9 ・・・ ２本
A7A9 ・・・ １本
交点数＝５＋４＋３＋２＋１＝１５個A3の場合
A4A6、A4A7、A4A8、A4A9 ・・・ ４本
A5A7、A5A8、A4A9 ・・・ ３本
A6A8、A6A9 ・・・ ２本
A7A9 ・・・ １本
交点数＝４＋３＋２＋１＝１０個A4の場合
A5A7、A5A8、A4A9 ・・・ ３本
A6A8、A6A9 ・・・ ２本
A7A9 ・・・ １本
交点数＝３＋２＋１＝６個A5の場合
A6A8、A6A9 ・・・ ２本
A7A9 ・・・ １本
交点数＝２＋１＝３個A6の場合
A7A9 ・・・ １本
交点数＝１個A7、A8場合 ・・・ 右側に対角線は引けない
よって、
合計＝１５＋１０＋６＋３＋１＝３５個
となります。頂点は１０個あるので、交点数は全部で３５×２＝３５０個となりますが、
２つの対角線について交点を重複して数えているので、
実際の交点数＝３５０×1/2＝１７５個
となります。
解答例４
Toru Fukatsuさん、uchinyanさん、ほげさん、 他
解答例３では力業で数えましたが、もう少しスマートに数えられないでしょうか。
下図のように、一つの頂点Aを固定して、残りの頂点から３個選んでB、C、Dと、ABとCDの交点が１個外側にできます。
残りの頂点は(n-1)個ありますが、ABおよびCDが多角形の対角線となるためには、
BはAの右隣であってはならず、またDはCの右隣であってはいけません。従って、アバウトに考えると残りの頂点は(n-3)個から３個選ぶとしてもよさそうです。 ・・・ （１）
すると、この場合の数はn-3C3通りあるので、あとは解答例３と同様にして、
交点数＝n-3C3×n×1/2＝1/12×n(n-3)(n-4)(n-5)個
と求まります。（１）のところをもう少し厳密にするには、下記のように考えるといいでしょう。
すなわち、Aとその両隣の点を除く(n-3)個の頂点から３個選んで、順にB、C、Dとします。（この選び方は、n-3C3通り）
このときDの右隣の頂点をD'とすると、DはAの左隣の頂点ではないので、D'はAよりは左側にある頂点となります。
こうすると、ABおよびCD'の間には別の頂点が存在するので、それぞれn角形の対角線となります。今度は、ABとCD'がn角形の対角線としましょう。
ABの間には別の頂点が存在するので、BはAの右隣の頂点ではありません。
また、CDの間には別の頂点が存在しますから、DをD'の左隣の頂点とすると、D'はCよりは右側にある頂点となります。
従って、B、C、Dは、Aと両隣の点を除く３つの頂点となります。上記の対応は１対１となるので、
ABとCD'がn角形の対角線となる場合の数
＝Aとその両隣の点を除く(n-3)個の頂点から３個選ぶ選び方
＝n-3C3通り
となります。以下、同様。
（（１）の別解）
ABの距離（BがAより何番目の頂点かを数えたもの）をｘ、BCの距離をｙ、CDの距離をｚ、DAの距離をｗとします。
ｘ、ｙ、ｚ、ｗは
ｘ＋ｙ＋ｚ＋ｗ＝n（ただし、ｘ≧2、y≧1、z≧2、w≧1） ・・・ （２）
を満たす整数となります。逆に（２）を満たすｘ、ｙ、ｚ、ｗに対して、Aから順にB、C、Dを決めていけば、
ABとCDはn角形の対角線となり、ABとCDの交点はn角形の外側にできます。従って、（２）を満たす整数解の個数を数えればいいことになります。
ここでは、（２）の替わりにX=x-1、Y=y-1、Z=z-1、W=w-1と置き換えて
Ｘ＋Ｙ＋Ｚ＋W＝n-6（ただし、X≧0、Y≧0、Z≧0、W≧0） ・・・ （３）
を考えてみましょう。この個数は、上記左図のように、(n-6)+3=(n-3)個の枠から３個選んで、それぞれに仕切を置く場合の数として求めることができます。仕切と仕切の間にある碁石の個数の和は(n-3)となり、碁石の個数は０以上となるからです。
従って、この場合の数は、n-3C3通りとなります。
