FC2ブログ

Welcome to my blog

[答1311] 交わらない対角線

ヤドカリ

ヤドカリ

P7100380.jpg



[答1311] 交わらない対角線


 凸23角形の対角線は何本? そのうちの交わらない2本の選び方は何通り?

 「交わらない」は、凸23角形の内部または頂点で交わらないことを意味します。


[解答1]

 一般化して凸n角形で考えます。

 対角線は1つの頂点において (n-3)本あり、頂点はn個、同じ対角線を2回数えるので、

 n(n-3)/2 本です。

 そのうちの2本の選び方は、

 n(n-3)/22={n(n-3)/2}{n(n-3)/2-1}/2=n(n-3)(n2-3n-2)/8 通り、

 頂点で交わる2本の選び方は、

 n・n-32=n(n-3)(n-4)/2 通り、

 内部で交わる2本の選び方は、頂点4個に対して1通りあるので、

 n4=n(n-1)(n-2)(n-3)/24 通りだから、

 交わらない2本の選び方は、

 n(n-3)(n2-3n-2)/8-n(n-3)(n-4)/2-n(n-1)(n-2)(n-3)/24

 =n(n-3){3(n2-3n-2)-12(n-4)-(n-1)(n-2)}/24

 =n(n-3)(3n2-9n-6-12n+48-n2+3n-2)/24

 =n(n-3)(2n2-18n+40)/24=n(n-3)(n2-9n+20)/12

 =n(n-3)(n-4)(n-5)/12 通りです。

 n=23 のとき、23(23-3)/2=230 本 、23(23-3)(23-4)(23-5)/12=13110 通りです。


[解答2]

 一般化して凸n角形で考えます。

 2つの頂点を結ぶと 辺か対角線なので、対角線は

 n2-n=n(n-1)/2-n=n(n-3)/2 本です。

 頂点のうち4つを左回りにA,B,C,Dをとり、対角線AB,CDが交わらないものとします。

 Aの決め方が n通り、Aから左回りに凸n角形の頂点に1からnまでの番号をつけると、

 B,C,Dは3からnまでの中から3つを C,Dが隣り合わないようにとることになります。

 3から n-1 の中から3つを選び、

 小さい2つの番号を B,C とし、最大の番号に1を加えたものを D にすれば条件を満たします。

 ただし、2本の選び方は同じものを2回ずつ数えることになるので、

 n・n-33/2=n(n-3)(n-4)(n-5)/12 通りです。

 n=23 のとき、23(23-3)/2=230 本 、23(23-3)(23-4)(23-5)/12=13110 通りです。

.
スポンサーサイト



Comments 2

There are no comments yet.
スモークマン  
グーテンターク ^^

[解答2]のアプローチは斬新でシンプルね☆
ちなみに...これって、正n角形を異なる頂点を通るk本の対角線で(k+1)分割する場合の数に使えますね...当たり前ですけど...^^;v

ヤドカリ
ヤドカリ  
Re: グーテンターク ^^

スモークマンさん、コメントを有難うございます。
解けてももう少しいい方法はないかと考えて、
そんな方法が存在したら嬉しいでね。