FC2ブログ

Welcome to my blog

[答163] 円周上の9個の点を結ぶ線分で円を分割

ヤドカリ

ヤドカリ



[答163] 円周上の9個の点を結ぶ線分で円を分割


 円周上に9個の点があって、このうちの2点を結ぶ線分は全部で 92=36 本です。

 この 36 本の線分のどの3本も円の内部の同じ点で交わらないとき、

 36 本の線分は、円を幾つの部分に分けるでしょうか?


[解答1]

 右の図のように、線分(黒の線分)を1本増やすと、4個の部分が増えていますが、

 これは、増やした線分と新たにできた交点の数に等しい。

 従って、最初1個から、線分の数と円内の交点の数だけ増えるから、

 1+36+94=1+36+126=163 の部分に分けることになります。

☆ 円内の交点の数は、4点を選んで、それを頂点とする四角形の対角線の交点と考えます。



[解答2] 地道に数えるとどうなるかという uch*n*anさんの解法

 点が n 個の場合を f(n) 個とし,n-1 個の点に n 番目の点を追加する場合を考えます。

 n 番目の点と,それから反時計回りに k 番目の点とを結ぶと,

 他の直線と交わるごとに 1 個,結び終わって 1 個,分割が増えます。

 前者は要するに円の内部の交点の数で,

 1 ~ k-1 番目の点を通る直線ごとに n-1-k 個ずつで (n-1-k)(k-1) 個です。

 そこで,f(0)=1 にも注意して,
              n-1
 f(n)-f(n-1)=Σ {(n-1-k)(k-1)+1}
    n-1        k=1
  =Σ {(n-1)(k-1)-((k+1)k(k-1)- k(k-1)(k-2))/3+1}
    k=1
  =(n-1)(n-1)(n-2)/2-n(n-1)(n-2)/3+(n-1)

  =(n-1)(n-2)(n-3)/6+(n-1)
            n
 f(n)=f(0)+Σ {(k-1)(k-2)(k-3)/6+(k-1)}
    n      k=1
  =Σ {(k(k-1)(k-2)(k-3)-(k-1)(k-2)(k-3)(k-4))/24+(k-1)}+1
    k=1
  =n(n-1)(n-2)(n-3)/24+n(n-1)/2+1= n4n2 +1

 今の場合は,f(9)=126+36+1=163 です。
.

スポンサーサイト



Comments 16

There are no comments yet.
アキチャン  
No title

おはようございます。
花びらが落ちる寸前のトケイソウ?
変わったお花に見えてます (o^-^o) おもしろいです ポチ♪

スモークマン  
No title

グーテンモルゲン ^^
Aha !!♪
わたしの友人も同じように解いてました(投稿済み...Orz)...^^;
まるで夏の雲を掴むような/B29を竹槍で突き落とそうとするような...無駄なあがきをしてた...
閃きに乏しいわたしが情けなか...^^;;...Orz...

再出発  
No title

「交点の数+1だけ増える」の「+1」が「線分の本数」と直結しなかったのが最近の感覚の鈍さを物語っています。
う~ん、もっと磨かなくっちゃな~!

uch*n*an  
No title

やどかりさんには鍵コメで書きましたが,実は,算チャレ第390回に類題があります。
http://www.sansu.org/used-html/index390.html
http://kurihara.sansu.org/sansu1-3/390.html
ただし,算チャレ第390回は多角形内部の分割なので,今回の問題だと 9 少なくなります。
私はこの頃は算チャレは解いても参加はしなかったのか,正解者一覧には名前がないのですが,
手元の電子ファイルには,苦労して解いたメモが残っています。
そのときの地道な解法を元にした解法を示しておきましょう。
なお,私は全く参加していなかったのですが,過去に算チャレver.2というのがあって,
その第74問が今回の問題とほぼ同じ,あちらは 8 個の点,だそうです。
http://kurihara.sansu.org/sansu2/074.html
その意味では,有名問題なのかも知れません。

uch*n*an  
No title

地道に数える解法
点が n 個の場合を f(n) 個とし,n-1 個の点に n 番目の点を追加する場合を考えます。
n 番目の点と,それから反時計回りに k 番目の点とを結ぶと,
他の直線と交わるごとに 1 個,結び終わって 1 個,分割が増えます。
前者は要するに円の内部の交点の数で,
1 ~ k-1 番目の点を通る直線ごとに n-1-k 個ずつで (n-1-k)(k-1) 個です。
そこで,f(0) = 1 にも注意して,

uch*n*an  
No title

f(n) - f(n-1) = ∑[k=1,n-1]{(n-1-k)(k-1) + 1}
= ∑[k=1,n-1]{(n-1)(k-1) - ((k+1)k(k-1) - k(k-1)(k-2))/3 + 1}
= (n-1)(n-1)(n-2)/2 - n(n-1)(n-2)/3 + (n-1)
= (n-1)(n-2)(n-3)/6 + (n-1)
f(n) = f(0) + ∑[k=1,n]{(k-1)(k-2)(k-3)/6 + (k-1)}
= ∑[k=1,n]{(k(k-1)(k-2)(k-3) - (k-1)(k-2)(k-3)(k-4))/24 + (k-1)} + 1
= n(n-1)(n-2)(n-3)/24 + n(n-1)/2 + 1
最後は,やどかりさんの解答や計算の便宜を意識してこの形にしています。
今の場合は,f(9) = 126 + 36 + 1 = 163 です。

ヤドカリ  
No title

アキチャンさん、早速のコメントを有難う御座います。
仰る通りトケイソウです。不思議な形です。

ヤドカリ  
No title

crazy_tomboさん、コメントを有難う御座います。
この解き方が一番簡単と思います。

ヤドカリ  
No title

再出発さん、コメントを有難う御座います。
見方によって問題が簡単に解けるのが数学の醍醐味ですね。

ヤドカリ  
No title

uch*n*anさん、再度の詳しい解答と出典を有難う御座います。
私は出典については存知なかったのですが、以前、書物で見た記憶があります。
仰る通り、有名な問題なのでしょう。
この問題を通じて、直線による平面の分割が、直線と交点だけ増えることの紹介が目的です。
そして、この事を使う問題をまたいずれ形を変えて出題しようと考えています。
漸化式による方法も当然考えたのですが、貴殿が示されているように、
ΣΣを扱わなければなりません。
解答に追加しようか迷って書きませんでしたが、今、書き加えました。

スモークマン  
No title

やどかりさんへ ^^
すいません...^^;
表示が...
>f(n)-f(n-1)=� {(n-1-k)(k-1)+1}
な感じになってます...
直せますれば...お手数ですがよろしくお願いいたします m(_ _)m~v

ヤドカリ  
No title

crazy_tomboさん、Σを変えてみました。

スモークマン  
No title

>やどかりさんへ ^^v
今度はちゃんと見えてます Orz~♪
グラッチェ ^^

いっちゃん  
No title

こんばんは。
トケイソウですか?面白い形ですね。。
3Dで観ればまた、普通の形に見えたりして。♪ポチ

ヤドカリ  
No title

crazy_tomboさん、使っていたΣは環境依存文字でした。
不注意で使ってしまいました。

ヤドカリ  
No title

いっちゃん、コメントとポチを有難う御座います。
このトケイソウは、背景が遠いので、やっとピントがあった1枚です。