平面を分割する投稿者：山中和義 投稿日：2015年 6月30日(火)19時54分26秒 |
|
問題 n本の直線で平面を分割するとき、その領域の個数は最大いくつになるか。 考察 n=1のとき ① ─── ② n=2のとき ①│③ ─┼─── ②│④ n=3のとき ①│④ ─・── ── │ ＼ ／ ②│⑤ ・ ⑦ │ ／ ＼ ─・── ── ③│⑥ n=4のとき ①│⑤ ─・──────── ──────── │ ＼ ／ ②│⑥ ・ ⑩ │ ／ ＼ ─・── ── ── ─── │ ＼ ／ ＼ ／ ③│⑦ ・ ⑨ ・ ⑪ │ ／ ＼ ／ ＼ ─・── ──────── ─── ④│⑧ 横方向に平行な(n-1)本の直線をひく。これらに交わるように、縦方向に1本の直線をひく。 これによって、2n個の部分に分割される。 次に、横方向の直線どうしも互いに交わるようにして、平行を崩していく。 これは、C(n-1,2)通りある。よって、新たにC(n-1,2)個の部分が加わる。 したがって、2n+C(n-1,2)=(n^2+n+2)/2通りとなる。 （終り） 考察 n本目の線は、(n-1)本の既存の線にすべて交差するように線をひく。 ただし、既存の交点を通過しないようにする。 このとき、領域は、(既存の線の本数+1)個増える。 これより、漸化式 F[0]=1、F[n]=F[n-1]+n を得る。 F[n]=F[0]+Σ[k=1,n]{F[n]-F[n-1]}=1+n(n+1)/2=(n^2+n+2)/2 （終り） LET N=5 LET M=N-2 SET WINDOW -1,2*M+1,-M^2,4*M^2/3 !!DRAW grid CALL gcDRAWLINE(1,0,0) !1本目 Y軸 FOR K=0 TO M !2本目以降 CALL gcDRAWLINE(K,1,-K^2) NEXT K PRINT (N^2+N+2)/2 END !FV.LIB 抜粋 EXTERNAL SUB gcDRAWLINE(L,M,N) !直線Lx+My+N=0を描く IF (L=0 AND M=0) THEN PRINT "L=M=0なので、直線が成立しません。"; L;M;N ELSE ASK WINDOW x1,x2,y1,y2 IF ABS(L)>ABS(M) THEN !y=±xの傾きより大きいなら ※y軸に平行な直線を含む PLOT LINES: -(M*y1+N)/L,y1; -(M*y2+N)/L,y2 ELSE PLOT LINES: x1,-(L*x1+N)/M; x2,-(L*x2+N)/M END IF END IF END SUB ----------------------------------- 問題 n個の円で平面を分割するとき、その領域の個数は最大いくつになるか。 考察 n個の円は、互いに交差するように描いていく。 具体的には、単位円に内接する正n角形の各頂点を中心に半径2の円を描く。 1つの円では、（台の上に円板を置いていく） 重なっていない部分（外側）が1つ 重なっている部分（真ん中）がに1つ 2つの円では、 いずれの円も重なっていない部分（外側）が1つ 1つの円が重なっている部分（三日月型）が2つ 2つの円が重なっている部分（真ん中）がに1つ 3つの円では、 いずれの円も重なっていない部分（外側）が1つ 1つの円が重なっている部分（三日月型）が3つ 2つの円が重なっている部分（三日月型）が3つ 3つの円が重なっている部分（真ん中）がに1つ 4つの円では、 いずれの円も重なっていない部分（外側）が1つ 1つの円が重なっている部分（三日月型）が4つ 2つの円が重なっている部分（三日月型）が4つ 3つの円が重なっている部分（三日月型）が4つ 4つの円が重なっている部分（真ん中）がに1つ となり、n個の場合も同様である。 よって、外側+三日月型+真ん中=1+n(n-1)+1=n^2-n+2 （終り） 類題 円を1,2,3つ用いてベン図はつくれますが、4つ以上の場合は不可能です。 (終り) LET N=4 SET WINDOW -3.5,3.5,-3.5,3.5 DRAW grid FOR K=0 TO N-1 DRAW circle WITH SCALE(2)*SHIFT(COS(2*PI*K/N),SIN(2*PI*K/N)) NEXT K PRINT N^2-N+2 END 
|