FC2ブログ

Welcome to my blog

[答540] 7つの角の和

ヤドカリ

ヤドカリ



[答540] 7つの角の和


 図0のように、A,B,C,D,E,F,G,A の順につなぐと凸七角形になるような、

 同一平面上の7点 A,B,C,D,E,F,G があります。

 図0~図3のような、7つのどの点も他の2点と線分で結ばれている図は全部で 465個できます。

 ( https://okayadokary.blog.fc2.com/blog-entry-1354.html を参照)

 この 465個の図において、劣角を ∠A,∠B,∠C,∠D,∠E,∠F,∠G とするとき、

(1) 図3において、∠A+∠B+∠C+∠D+∠E+∠F+∠G=?

(2) ∠A+∠B+∠C+∠D+∠E+∠F+∠G が図3の場合と等しくなるのは図3を含めて何個?

 ただし、図1,図2のように、和が定まらないものについては除外します。


[解答]

(1) DEを結ぶと ∠C+∠F=∠CED+∠FDE になるので、

 7つの角の和は 五角形ABDEGの内角の和と等しく、540゚ です。

 右端の図のように、左回りで全部の線分を通ってもとに戻る道順を考えれば、

 方向を変える青色で示された角度は2周分だから、

 赤の角の和は、7・180゚-2・360゚=540゚ としても求められます。

(2) 図3,図4,図5,図6は回転した形を考えると7個ずつ、図7の場合が1個、

 図8,図9のように三角形と四角形に分かれるものが 73=35 個、

 よって、7・4+1+35=64 個です。


[参考] たけちゃんさんのコメントより

 n点(n≧5)に対し,角の和が 180゚・(n-4) の問題に一般化してみます.

 まず,すべての点がループを作る場合の数Nを考察します.

 1つの頂点をOと名付け,そこから反時計回りに 1,2,……,n-1 と点に名前を付けます.

 すべての点のループで条件を満たすのは,

 向きの変化が常に同じ回り方(左回りとしてよい)で,その合計が 720゚ のとき.

 これは,Oから出発して,いくつかの頂点を1周目として左回りに順にたどり,

 残りの頂点を2周目として順にたどる経路である.

 ただし,常に左回りより,次の条件を満たす.

  (ⅰ) 1周目の頂点は2つ以上 (1周目の最後以外の頂点で左回りを保証)

  (ⅱ) 2周目の頂点は2つ以上 (2周目の最初以外の頂点で左回りを保証)

  (ⅲ) 1周目の最初の頂点は2周目の最後の頂点より前 (頂点Oで左回りを保証)

  (ⅳ) 2周目の最初の頂点は1周目の最後の2つの頂点より前 (1周目の最後の頂点で左回りを保証)

  (ⅴ) 2周目の最初の2つの頂点は1周目の最後の頂点より前 (2周目の最初の頂点で左回りを保証)

 全体集合 U={1,2,……,n-1}に対し,Uの部分集合Aを1周目にたどる点全体の集合とする.

 Uの部分集合の総数 2n-1 から除外される部分集合Aは,

  ・(ⅰ),(ⅱ)の条件から,n-10n-11n-1n-2n-1n-1=2n 通り

  ・(ⅲ)の条件から,k=2 ~ k=n-3 として A={x|k<x} の n-4 通り

  ・(ⅳ),(ⅴ)の条件から,Aの要素数 k=2 ~ k=n-3 に対し,

   A={x|x<k}∪{m} (m=k ~ m=n-1) の n-k 通りと

   A={x|x<m}∪{x|m<x≦k+1} (m=1 ~ m=k-1) の k-1 通り

   となり,合計 (n-4)(n-1) 通り

 だけなので,N=2n-1-2n-(n-4)-(n-4)(n-1)=2n-1-n2+2n.

 次に,全体で1つのループを作る場合以外を考えます.

 2つのループに分かれ,それぞれが(凸)多角形を作る場合,すなわち

 {O,1,2,……,n-1} を要素数がともに3以上の2つに分割する仕方なので,場合の数は,

 (2nn0n1n2nn-2nn-1nn)/2=2n-1-n2/2-n/2-1

 まとめると,一般化した問題に対する場合の数は, 2n-3n2/2+3n/2-1 です.

 具体的には,n=5,6,7,8,9 に対して順に,場合の数は 1,18,64,171,403 となります.

.

スポンサーサイト



Comments 25

There are no comments yet.
ヤドカリ  
No title

スモークマンさん、コメントを有難うございます。
私は、「もれなく調べてくれれば」と思って出題しましたが、
たけちゃんさんからのコメントで、奥の深さを知った次第です。
意図しないまま、大変な問題を作ったものだと驚いています。

ヤドカリ  
No title

さっちゃんこさん、コメントとナイス!を有難うございます。
福寿草は本当に春が間近に来ていることを感じさせる花です。
「春」という言葉が、気持ちが「張る」から来ている説がありますが、
福寿草を見るとうなづける説です。

ヤドカリ  
No title

Nemoさん、コメントを有難うございます。
みなさん、この問題に真剣に取り組んで頂き、
非常に嬉しくコメントを読ませて頂いています。

たけちゃん  
No title

tsuyoshik1942さんのプログラムは「(仮称)十進BASIC」ですね.
触発されて,口直しのプログラムを組んでみました.
使ったことのない命令をいっぱい使い,
けっこう技巧的なこともしていますが,
実行すると,私はちょっと楽しかったです.
なお,「Q=9」は,5から9の別の値にしても動作します.
(Q=9用なので,Qが小さいと,形がゆがみますが...)

コピペ用に,少し長いですが,全部投稿します.
十進BASICが使える環境の方は,実行してみてください.
(ただし,本当に口直しになるかどうかは保証できませんが.)

たけちゃん  
No title

OPTION ANGLE DEGREES
OPTION ARITHMETIC COMPLEX
DIM P(9),ANS(1000),Z(9)
LET Q=9
SET WINDOW -5,5,-5,5
REM 9個は,虚部がすべて異なり,凸9角形をなし,虚部実部とも±5まで
LET P(1)=COMPLEX(0,4)
LET P(2)=COMPLEX(-2,3.1)
LET P(3)=COMPLEX(-3.2,1.1)
LET P(4)=COMPLEX(-3,-1.3)
LET P(5)=COMPLEX(-1.4,-3)
LET P(6)=COMPLEX(1,-3.5)
LET P(7)=COMPLEX(3.4,-1)
LET P(8)=COMPLEX(3.6,1)
LET P(9)=COMPLEX(2.5,3)
MAT PLOT POINTS,LIMIT Q:P
MAT PLOT LINES,LIMIT Q:P
PLOT LINES:P(Q);P(1)
LET C=0

たけちゃん  
No title

FOR I=0 TO FACT(Q-1)-1
LET X=I
FOR J=1 TO Q
LET Z(J)=P(J)
NEXT J
FOR J=Q-1 TO 1 STEP -1
LET Y=MOD(X,J)+1
LET W=Z(J)
LET Z(J)=Z(Y)
LET Z(Y)=W
LET X=INT(X/J)
NEXT J
IF IM(Z(Q-1))>IM(Z(1)) THEN
LET S=ABS(ARG((Z(Q)-Z(1))/(Z(2)-Z(1))))
LET S=S+ABS(ARG((Z(Q-1)-Z(Q))/(Z(1)-Z(Q))))
FOR J=2 TO Q-1
LET S=S+ABS(ARG((Z(J-1)-Z(J))/(Z(J+1)-Z(J))))
NEXT J

たけちゃん  
No title

IF ROUND(S,1)=(Q-4)*180 THEN
LET C=C+1
LET ANS(C)=I
END IF
END IF
NEXT I
PRINT C;"個の解がみつかりました"
PAUSE
CLEAR
FOR I=1 TO C
LET X=ANS(I)
FOR J=1 TO Q
LET Z(J)=P(J)/5+COMPLEX(MOD(I+4,5)*2-4,-MOD(INT((I-1)/5),5)*2+4)
NEXT J
FOR J=Q-1 TO 1 STEP -1
LET Y=MOD(X,J)+1
LET W=Z(J)
LET Z(J)=Z(Y)
LET Z(Y)=W
LET X=INT(X/J)
NEXT J

たけちゃん  
No title

MAT PLOT LINES,LIMIT Q:Z
PLOT LINES:Z(Q);Z(1)
IF MOD(I,25)=0 THEN
PAUSE
CLEAR
END IF
NEXT I
END

ヤドカリ  
No title

たけちゃんさん、プログラムを有難う御座いました。
私には猫に小判ですが、十進BASICをご存知の方には参考になると思います。

tsuyoshik1942  
No title

>たけちゃんさん

プログラムの披露ありがとうございます。早速トライさせていただきました。
やはりすごいですね!自分も図を描く構想は持っていたのですが、その技術がありませんでした。また、再帰部分、複素数の活用、MAT、その他多くが未消化です、勉強させていただきます。
なお、十進Basicが古いため、最初は動きませんでした。updata後正常に動作しました。

uch*n*an  
No title

たけちゃんさん,やどかりさん
解説,解答解説の修正,ありがとうございました。ようやく納得できました。

昨日納得できなかった理由は,規則
> () 2周目の最初の頂点は1周目の最後から2つ目の頂点より前
の意味を取り違えていたためでした。
「1周目の最後から2つ目の頂点」が分かりづらく,
1周目の最後を a とすると,a-2 の頂点,の意味だとばかり思っていました。
そうではなくて,1周目の頂点の中の後から2番目,最後の一つ前,の意味なんですね。
後の A の不適な集合の記述を見て,「なぁ~んだ,そうか。」と思いました (^^;
それならば,論理は明解で,必要十分も明らかですね。
こんな思い違いをしたのは,私が思い違いをしたものに似た規則を得ていたからで,
この場合は十分性は保証できないので「おかしいなぁ。」と思ってあのコメントになりました。
申し訳ない。

ただ,無用の誤解を与えないよう,可能ならば,表現を少し変える方がいいかも知れません。
例えば,
「1周目にたどる頂点の中の最後から2番目(最後の一つ前)の頂点」
とか。ご検討ください。

uch*n*an  
No title

tsuyoshik1942さん,たけちゃんさん
プログラムの提示をありがとうございます。勉強になります。時間をみて試してみますね。

たけちゃん  
No title

>十進Basicが古いため、最初は動きませんでした。
あわててヘルプを調べましたが,
どの機能がひっかかったのかは特定できませんでした.
すみませんが,「最新版で実行してください」ということで...

なお,右回りが発生して角の和が不定なのに,
たまたま和が条件に合ってしまう可能性はあるかもしれません.

このことの懸念が増すので推奨はできませんが,
「IF ROUND(S,1)=(Q-4)*180 THEN」

「IF ROUND(S,1)=(Q-6)*180 THEN」
に書き換えると,「3周」する解を出力します.
Q=8でのこのときの出力も見てもらいたいです.

ヤドカリ  
No title

tsuyoshik1942さん、コメントを有難う御座います。
詳細は分からないものの、私もたけちゃんさんの長いプログラムには驚きました。
多分、たくさんの工夫が散りばめられていることと思います。

なお、コメントが未承認というのは、このブログでは初めてですが、、
私は悪質なコメントを避けるために、コメントチェッカーを使用し、
フィルタリングを強設定にしているからだと思います。
最後の「○○しております」がまずいのではないかと思います。

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
解答をまとめていて自分なりに理解すると、
説明の中に他の解釈ができる部分があることを見落としてしまいます。

> 無用の誤解を与えないよう,…,表現を少し変える方がいいかも…
()が2行になると見づらくなるので、
文字数が同程度になるように()()を書き変えました。

ヤドカリ  
No title

たけちゃんさん、度々のコメントを有難う御座います。
貴殿の考察により、私はまとめる段階で勉強になりました。
皆さんは、解答説明のこの記事で勉強になったようです。
ほとんど貴殿のコメントを並べたようなまとめ方になりましたが、
まとめた甲斐はありました。

tsuyoshik1942  
No title

>Nemoさん

関心を寄せていただき、ありがとうございます。
たけちゃんさんの高度なプログラムに比し、大きく見劣りしますが、その分、自分のそれは、プログラムの組み立てが読みやすいのではないかと思います。

たけちゃんさん
8角形の180度、その他も走らせました。きれいですね!
知らないことが多く、まだまだ読み解けておりませんが、じっくり楽しませていただきます。

ヤドカリ  
No title

tsuyoshik1942さん、コメントを有難う御座いました。

uch*n*an  
No title

やどかりさん
解答解説の修正,ありがとうございます。これならば分かりやすいです。

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
最初からこのように書けば誤解がなかったと思いますが、
最初はそこまで気がつきませんでした。

たけちゃん  
消滅コメントが残念

例えば[問題1305]の記事には22個のコメントが付いているので,
コメント数の上限が20ということではないようですが,
自動で移行した場合,コメント数の上限が20となるのでしょうか.

本記事は,もともと50個のコメントがついていたのですが,
20個になっていますね.
仕方ないことだと思いますが,残念ではあります.

ヤドカリ
ヤドカリ  
Re: 消滅コメントが残念

たけちゃんさん、コメントを有難うございます。
こんなにコメントが消えているとは思いませんでした。
Yahoo!の移行ツールを使うとコメントは消えるそうですので、
これでもましだと思います。

ヤドカリ
ヤドカリ  
Re: 消滅コメントが残念

消滅コメントをコピペしました。

解答図の図7を見つけ、自信があったのですが、図8,9の35個が完全に欠落していました。
「少なくとも35個以上」のヒントに助けられました。
「参考」の考察はすごいですね!中身は追いきれないのですが、
結果の「1,18,64,171,403」は自分なりの手法で確認させていただきました。
2013/2/13(水) 午前 11:59[ tsuyoshik1942 ]

この問題は,(1)は易しいけれど,(2)はとても難しく,
しかもヒント「540」が(2)では使えない点でも厳しい問題でした.
この問題自体に対しては,私の考察はかえってめんどうかもしれませんが,
一般化した方が正体が見える気もして提示しました.
採り上げていただき,ありがとうございました.
(単なる書き写しでなく,分かりやすく書き直していただいているのも感謝です.)
細かいことですが,
「・(ⅲ)の条件から,Aの要素数 k=2 ~ k=n-3 で
A={x|k<x} の n-4 通り」
は,場合の数は正しいですが,kはAの要素数ではないと思います.
また,
「・(ⅳ),(ⅴ)の条件から,Aの要素数 k=2 ~ k=n-3 に対し,
(中略)
A={x|x<m}∪{x|m<x≦k} (m=1 ~ m=k-1) の k-1 通り」
は,
A={x|x<m}∪{x|m<x≦k+1} (m=1 ~ m=k-1) の k-1 通り」
が正しいと思います.
(これについては,私の投稿の誤りです.すみません.)
2013/2/13(水) 午後 2:00[ たけちゃん ]

この問題は,(1)は,まぁ,少なくともこのサイトの常連さんには簡単だと思いますが,
(2)は,難しく,私も結局は一つずつ数えることになりました。
ただ...
[参考]のたけちゃんさんの解答ですが,実は,私も同じことを考えていて,
幾つかの図を描いて,記述されている規則が必要なことは分かっていましたが,
それで尽きているのか,つまり,十分か,がよく分からず,
確認のためには一つずつ調べるしかないのかな,と思っておりました。
この解答ではそこらが書かれていませんが,どうなんでしょうか?
必要性は,幾つか図を描いて示せばいいと思いますが,
十分性は,明らか,又は簡単に示せるのでしょうか?
なお,規則の必要十分性が確認できたとしてのその後の計算は,
これから時間をみて調べてみますが,現時点でもよく分からないところがあります。
まず,
>1周目にたどる点全体の部分集合をAする.
この意味がよく分からないのですが,
A は U の部分集合で,A = {1周目にたどる点全体}。
でしょうか。それとも,
B = {1周目にたどる点全体} で,A は B の部分集合。
でしょうか。
また,
>・(ⅲ)の条件から,Aの要素数 k=2 ~ k=n-3 で A={x|k<x} の n-4 通り
n - 4 通り,は正しいですが,説明がよく分からず。
A の要素数が k なんですか? でも,「A = 」の式の集合の要素数は n-1-k では?
多分,k は2周目の最後ではないのかな。
その後も似たような記述なので,さすがに読む気が失せました (^^;
もっとも,二つに分かれる場合は,明らかに正しいです。
2013/2/13(水) 午後 2:31[ uch*n*an ]


グーテンターク ^^
これはお手上げでした...^^;
該当図もすべて見つけられなくて...
5=4+1+1+1=3+2+2 しかないと思ってました...
それでも抜けてましたが...4+3,1+1+1+1+1+1+1 も当てはまることには頭回りませんでした ^^;;
パズルチックで面白かったですが...たけちゃんさんのように理屈でも攻めれるのには驚き☆...熟読玩味...^^;...Orz~
2013/2/13(水) 午後 2:32[ スモークマン ]

規則の十分性ですが,
(i)が成り立つとき,1周目の,最後以外の頂点で左回り,
(ii)が成り立つとき,2周目の,最初以外の頂点で左回り,
(iii)が成り立つとき,頂点Oで左回り,
(iv)が成り立つとき,1周目の最後の頂点で左回り,
(v)が成り立つとき,2周目の最初の頂点で左回り
なので大丈夫だと思います.
また,「1周目にたどる点全体の部分集合をAする.」

「A は U の部分集合で,A = {1周目にたどる点全体}。」
です.
2013/2/13(水) 午後 2:50[ たけちゃん ]

>規則の十分性ですが,
>...
>なので大丈夫だと思います.
おっしゃりたいことは分かるつもりですが,
でも,点の位置関係,正7角形とは限らない,とか,n が大きくなると,
次の点,特に,1周目の最後から2周目の最初,に移るときに,
中心角が 180°を超えることもあるので,
一見逆回り,右回り,になるように見える場合もあり,本当に大丈夫なのかな。
まぁ,左回りで2周は確かなので大丈夫なんでしょうけれど。
もっとも,tsuyoshik1942さんのご確認によれば,正しいことは間違いなさそうですね。
2013/2/13(水) 午後 6:10[ uch*n*an ]


uch*n*anさんには,私の考察に期待するとまで言っていただき,
大変ありがたかったので,何とか納得してもらいたいなあと思っています.
しつこいようで申し訳ありませんが...
この考察では,「左回り」との用語は,
はじめの1周目,2周目で「順にたどる」と言っている部分を除いてすべて,
「左に向きを変える」という意味です.
(はじめの部分を,点の定義に合わせて「反時計回り」と
しておく方がよかったかもしれません.)
反時計回りの1周目,2周目の途中は当然すべて左回りであり,
それ以外の頂点で左回りとなれば,
「すべての頂点で向きの変化が常に同じ回り方」
との要件を満たすことになると思います.
2013/2/13(水) 午後 7:19[ たけちゃん ]

自分の手法はPCの腕力を頼ったプログラムです。
工夫もテクニックもなく恥ずかしいのですが、記します(一部略)
OPTION ANGLE DEGREES
FUNCTION DO(x1,x2,x3,y1,y2,y3)
LET l1=SQR((x1-x2)^2+(y1-y2)^2)
LET l2=SQR((x3-x2)^2+(y3-y2)^2)
LET l3=SQR((x3-x1)^2+(y3-y1)^2)
LET DO=ACOS((l1^2+l2^2-l3^2)/(2*l1*l2))
END FUNCTION
DIM kx(9)
DIM ky(9)
LET kx(1)=2.5
LET ky(1)=5
.
.(点1から点9の座標を任意に入力、凸9角形に留意)
LET kx(9)=3.9
LET ky(9)=5.1
s1=1
FOR s2=2 TO 9
FOR s3=2 TO 9
IF s3=s2 THEN GOTO 600
.
.(s4~s8省略)
FOR s9=2 TO 9
IF s9=s2 OR ..省略.OR s9=s8 THEN GOTO 50
LET kakudo=0
LET ka1=DO(kx(1),kx(s2),kx(s3),ky(1),ky(s2),ky(s3))
.(ka1~ka9省略)
LET kakudo=ROUND((ka1+......ka8+ka9),1)
IF kakudo=900 THEN
count=count+1
PRINT count;kakudo;s2....;s9
END IF
50 NEXT S9
.(NEXTs8~s3省略)
700 NEXT S2
END
386個(逆周りも数えて)が10秒ほどではじき出されました。
2013/2/13(水) 午後 7:45[ tsuyoshik1942 ]

>たけちゃんさん
似たような考えで分類しようとしましたが、時間が無くて結局あきらめてしまいました^^;
いつも素早く的確な解答されていて、すごいなぁと拝見しています。
tsuyoshik1942さん
プログラムで解くのも素敵ですね!色んなアプローチがあって面白いです。
これはどういう言語なのですか?
BASICっぽい感じがしますが・・。
2013/2/13(水) 午後 9:48[ Nemo ]

たけちゃん  

コメントのコピペをありがとうございました.
お疲れさまでした.

ヤドカリ
ヤドカリ  
Re: タイトルなし

たけちゃんさん、コメントをありがとうございます。
fc2のツールを使うと鍵コメント以外は全部再生されているものと
思っていましたが、そうではなかったようです。
記事が更新できなくなる8月まで Yahoo! ブログをそのままに
しておこうと思っていますので、
何かお気づきのことがあれば教えて頂ければ嬉しいです。
私は、リンクを書き換えるので精一杯でした。