�������裴�������ʬ�β�����

Taro
「４つの部分」・・・・う〜〜〜ん
疲れのせいで一瞬自分で数え間違えたかとも思いました(汗)
じたく・・・帰宅直後　　 5月19日（木） 0:09:29　　 　　25070
トトロ＠Ｎ
しまった。急がば回れでした。
樹形図を途中まで書いて60×4＝240
兵庫県明石市　　 5月19日（木） 0:09:53　　 MAIL:h-sakai@zb3.so-net.ne.jp 　　25071
吉川マサル
またまた京ぽんからです…。

私は漸化式っぽい解法を想定してました。
　　 5月19日（木） 0:10:30　　 　　25072
数楽者
使わない色があってもいいかどうか不明だったので、
解答を２通送りました。
横浜　　 5月19日（木） 0:10:57　　 MAIL:iida@ae.keio.ac.jp 　　25073
ひろぼうず
４つの部分を４色？
しかも白でぬる？
何か深い意味でも・・・
かなり焦りました
　　 5月19日（木） 0:11:44　　 　　25075
呑ちゃん
#25070
ホントで酒ね。４つになってま酒。
お疲れで酒か。お元気出して下さいね。
え？酔っ払いはいらんてか？こりゃまた失礼致しました。
それでは、ごめんやしておくれやしてごめんやっしゃ〜！
酔っ払い天国　　 5月19日（木） 0:13:30　　 MAIL:hopes@mba.ocn.ne.jp HomePage:HOPES　　25076
DrK
パーツごとの組み合わせだったのですね。
私は単純に順列だけを考えました。
4色の場合は、2箇所塗る色を1つ選ぶので4通り
それ以外は、3つの部分に対して塗る組み合わせが3×2=6通り
4×6=24
3色の場合は、3箇所に同じ色を塗る場合は、2箇所が隣り合うため不可。　
よって、2箇所を2色ということになる。この場合は、交互に2色が隣り合うことになる。
4色から3色を選ぶ通りは4通り
3色から2色を選ぶのは3通り
2色の並び方は2通り
よって4×3×2=24
24+24=48
が答えといいたくなるところであるが、
これは5等分のときのみで、
実際は大きさが異なるため、それぞれ別のものとして考える
48×5=240
が答え
今は楽園かな?違うな。　　 5月19日（木） 0:13:33　　 MAIL:satoka@star.odn.ne.jp 　　25077
ミキティ
認証で入りました。意味が分からない……。
210通りじゃないのかな？
　　 5月19日（木） 0:14:17　　 HomePage:みきこむ　　25078
みかん
今回の問題、条件があいまいではないでしょうか。

・辺で接するところは色を変えなければならないのか。
→塗り分け問題では別の色にするのが常識ですが、問題文のどこにも
　明記されていない
・４色すべて使う必要があるのか
→まあ、示されている例が３色ですから「使わない色があってもいい」
　ということなのでしょう。が、きちんと問題文に書いて欲しい…
・「白で塗る」と「まったく塗らない」は同一視していいのか
→普通「白で塗る」というのは考えないのではないでしょうか。
　　 5月19日（木） 0:23:52　　 　　25079
ミキティ
> ・辺で接するところは色を変えなければならないのか。
注意書きの「ア〜オの各部分は区別するものとします。」が該当？

> ・４色すべて使う必要があるのか
例示で緑を使っていないのでＯｋ？

だと思います。しかし、プログラムでも数えても210通り。
どう違うんだろう？

＜一覧は不要になったので、00:30 に消去＞
　　 5月19日（木） 0:30:59　　 HomePage:みきこむ　　25080
ミキティ
５つ全部塗るんかい（
ならば、240通りで間違いないと思います。
　　 5月19日（木） 0:26:46　　 HomePage:みきこむ　　25081
吉川　マサル
　ただいま帰宅いたしました。（とりあえず４つの部分→５つの部分に訂正させて頂きました）

　問題文に不備があり、申し訳ありませんでした。以下、現時点での見解です。

・辺で接するところは色を変えなければならないのか。

　えと、「塗り分ける」という言葉の意味に含まれていると思っていました。隣どうしで（アならば、イまたはオの部分）では同じ色を使ってしまうと、「塗り分ける」ということにならないかなと...。すみません。（実は１度※部分に書いたのですが、「不要かな」と思って消してしまいました...）

・４色すべて使う必要は？

　皆様ご指摘の通りですが、その必要はありません。一応、例でそれを示したつもりでした。やはり文章で記すべきでした。
PowerBook G4　　 5月19日（木） 0:29:30　　 MAIL:masaru-y@san　su.org HomePage:算チャレ　　25082
ひろぼうず
『塗り分ける』＝『隣り合う部分は違う色で塗る』
というのは、小学生の間では暗黙の了解になってるみたいです。
でも、説明がほしかったです。
さあ、今からうまい方法でも考えます。
　　 5月19日（木） 0:29:52　　 　　25083
みかん
結局「４か所を〜」は誤記と判断すべきなのでしょうか。

「区別される５か所を、同じ色が隣り合わないように、４色以内で塗る」
と解釈すれば、４色の場合が１２０通り、３色の場合も１２０通りが出てくる
と思います。

（#25080　ミキティさん）
>> ・辺で接するところは色を変えなければならないのか。
>注意書きの「ア〜オの各部分は区別するものとします。」が該当？
これは「円順列は適用しない」ということを表しているだけで、「同じ色が
接してはいけない」とは取れないでしょう。

>> ・４色すべて使う必要があるのか
>例示で緑を使っていないのでＯｋ？
例示が３色だからＯＫ、と考えてもいいけれど…。「ちょうど４色で」と
していないから３色でもいい、と考えるのは算数の範囲ではちょっとつらい。
　　 5月19日（木） 0:33:30　　 　　25084
tomh
場合分けで数えました。

[1] ア / イ(≠ア) / オ(≠ア, ≠イ) / ウ(≠イ, ≠オ) / エ(≠ウ, ≠オ)
　　4x3x2x2x2 = 96.

[2] ア / イ(≠ア) / オ(≠ア, ≠イ) / ウ(＝オ) / エ(≠オ)
　　4x3x2x1x3 = 72.

[3] ア / イ(≠ア) / オ(＝イ) / ウ(≠イ) / エ(≠ウ, ≠オ)
　　4x3x1x3x2 = 72.

96+72+72 = 240通り.
新潟市　　 5月19日（木） 0:37:15　　 MAIL:tomh@yahoo.co.jp HomePage:H to M　　25085
アヒーのおじさん
色分け問題では隣接する場所は異なる色にするのが常識だったのですか（滝汗）
「なんで1024じゃないんだ！？」と真剣に悩んでた人間がここに1人（苦笑）
9点円の中心　　 5月19日（木） 0:38:59　　 HomePage:正体不明　　25086
ひろぼうず
ア、イ、ウ、エ、オの順に塗るとして、
４×３×３×３×３＝３２４
【アとオが同色】４×３×３×３＝１０８
【アとオとエが同色】４×３×３＝３６
【アとオとエが同色】４×３＝１２
【アとオとエとウが同色】４×３＝１２
３２４−１０８＋３６−１２＝２４０通り
初めて考えた解法です。（さらに発展させて考えます）
　　 5月19日（木） 0:39:39　　 　　25087
吉川　マサル
#25084
> 結局「４か所を〜」は誤記と判断すべきなのでしょうか。

　えと、出題者本人としては完全な「誤記」です。が、「４ヶ所を...」のままだとすると、「５つの中の４ヶ所を選んで、最大４色の色を使って塗り分ける」という解釈になる気がします。だとすると、５×４×３×３×３＝５４０通り、とかになる気がするのですが...。
PowerBook G4　　 5月19日（木） 0:41:56　　 MAIL:masaru-y@san　su.org HomePage:算チャレ　　25088
ミキティ
>>25084
私は「ア〜オの各部分は区別するものとします。」を
「各部分が区別できるよう、違う色で塗りなさい。」と
解釈していました。(^^;;

「円順列は適用しない」ですか、なるほどねぇ。

なお、256通り、1024通りも当然解答しました（
　　 5月19日（木） 0:42:17　　 HomePage:みきこむ　　25089
ひとくん
自分では足し算方式でしましたが、やはりひろぼうずさんの様な引き算方式に惹かれますね。
4×3×3×3×3＝324から、「隣あった2か所がダブる場合」を引きます。
84通りですが、よく考えてみるとこれは、「円を4色に分割した場合の塗り方」に他なりません。（←ダブるところを1か所と考える）
　　 5月19日（木） 0:47:54　　 MAIL:h-wada@cream.plala.or.jp 　　25090
アヒーのおじさん
最終的にはこんな回答になりました（＾＾；

5箇所にたいして4色なので、必ず最低1色は2回つかう色が出てきます
まず5箇所のうちから同じ色で塗る2箇所をとなりあわないように選ぶと
5C2-5＝5通り　だから5×4×3×3×2＝360通り
ただしこれは同じ2色を2回ずつつかう場合を重ねて数えているので
同じ色を1回だけつかう：5×4×3×2×1＝5！=120
を引いて2で割ってからまた足しました（＾＾；　(360-120)÷2+120＝240

ありゃりゃなんか面倒臭いことしてるなこりゃ（苦笑）
9点円の中心　　 5月19日（木） 0:48:33　　 HomePage:正体不明　　25091
吉川　マサル
問題文に追記をほどこしました。m(__)m

　ちなみに私の想定した解法は、円をｎ個の分割したときの塗り分け方をAnとして、

Ａ1＋Ａ2＝　１６
Ａ2＋Ａ3＝　３６
Ａ3＋Ａ4＝１０８
Ａ4＋Ａ5＝３２４

という解き方でした。
PowerBook G4　　 5月19日（木） 0:49:58　　 MAIL:masaru-y@san　su.org HomePage:算チャレ　　25092
ひとくん
自分では足し算方式でしましたが、やはりひろぼうずさんの様な引き算方式に惹かれますね。
4×3×3×3×3＝324から、「隣あった2か所がダブる場合」を引きます。
84通りですが、よく考えてみるとこれは、「円を4色に分割した場合の塗り方」に他なりません。（←ダブるところを1か所と考える）
　　 5月19日（木） 0:50:39　　 MAIL:h-wada@cream.plala.or.jp 　　25093
ミキティ
>>25088
５つの中の４か所を選び、最大４色の色を使って塗り分ける。
ただし、白と「地の色」は別物と見なす。
→　540通り。

５つの中の４か所を選び、最大４色の色を使って塗り分ける。
ただし、白と「地の色」は同一視する。
→　210通り。
※　白＆「地の色」が２か所以上となる場合はありえます。

５つの中の４か所を選び、最大４色の色を使って塗り分ける。
ただし、白と「地の色」は同一視し、かつ１か所に限る。
→　120通り。
※　つまり、白を使わずに塗ると同じ意味になりますが。(^^;;
　　 5月19日（木） 1:40:58　　 HomePage:みきこむ　　25094
むらかみ
４色で塗るとき
・アとウが同色
・アとエが同色
・イとエが同色
・イとオが同色
・ウとオが同色
よって、4*3*2*1*5=120通り

３色で塗るとき
・ア以外を２色で塗る（イとエ、ウとオがそれぞれ同色）
・イ以外を２色で塗る（アとエ、ウとオがそれぞれ同色）
・ウ以外を２色で塗る（アとエ、イとオがそれぞれ同色）
・エ以外を２色で塗る（アとウ、イとオがそれぞれ同色）
・オ以外を２色で塗る（アとウ、イとエがそれぞれ同色）
よって、4*3*2*5=120通り

120+120＝240通りと解きました
　　 5月19日（木） 1:01:26　　 MAIL:ryoiti@sansu.org 　　25095
はなう
ここんとこ立て込んで手ご無沙汰してました☆

普通に足しました。
4×3×（1×3×2+2×(1×3＋2×2））＝240
強引に足すのが好きなので☆

漸化式はステキですね☆
とーきょ　　 5月19日（木） 1:04:41　　 HomePage:http://hanau.daa.jp/blog2/　　25096
ゴンとも
今回の問題はア,イ,ウ,エ,オと文字が振ってあるので回転して
同じ等考えなくてよいであまり紛らわしくなかったです。
以下自分なりの解答です。
先ず、題意の図でア,オ,エが同じで
イ,ウが同じであるとして考えると
ピンクをP,水色をB,緑をG,白をWとし,
塗り分けるので隣の色は異なるとして
(ア,オ,エ)がバラバラで真ん中がPのものは
(ア,オ,エ)=(B,P,G)　(イ,ウ)=(P,B),(P,W),(G,P),(G,B),(G,W),(W,P),(W,B)
(ア,オ,エ)=(G,P,B)　(イ,ウ)=(P,G),(P,W),(B,P),(B,G),(B,W),(W,P),(W,G)
(ア,オ,エ)=(B,P,W)　(イ,ウ)=(P,B),(P,G),(G,P),(G,B),(W,P),(W,B),(W,G)
(ア,オ,エ)=(W,P,B)　(イ,ウ)=(P,G),(P,W),(B,P),(B,G),(B,W),(G,P),(G,W)
(ア,オ,エ)=(G,P,W)　(イ,ウ)=(P,B),(P,G),(B,P),(B,G),(W,P),(W,B),(W,G)
(ア,オ,エ)=(W,P,G)　(イ,ウ)=(P,B),(P,W),(B,P),(B,W),(G,P),(G,B),(G,W)
で42通り
あと真ん中がB,G,Wも同じ通り数で42*4=168通り・・・・・・��
(ア,オ,エ)がア=エのときでア=エ=Pのものは
(ア,オ,エ)=(P,B,P)　(イ,ウ)=(B,G),(G,B),(B,W),(W,B),(G,W),(W,G) B,G,W
(ア,オ,エ)=(P,G,P)　(イ,ウ)=(B,G),(G,B),(B,W),(W,B),(G,W),(W,G) B,G,W
(ア,オ,エ)=(P,W,P)　(イ,ウ)=(B,G),(G,B),(B,W),(W,B),(G,W),(W,G) B,G,W
で18通り
あとア=エがB,G,Wも同じ通り数で18*4=72通り
これと�，鯊�して72+168=240通り・・・・・・(答え)
場合の数等は私なんかは通り数だけでなく事象を
すべて書き出したいんで今回もそんな解法でした。
(しかし事象が同形の場合は書き出しません。)では。
豊川市　　 5月19日（木） 1:08:40　　 MAIL:fttnm528@ybb.ne.jp 　　25097
みかん
（#25092）
注を加筆したあとの問題文なら、よくある塗り分け問題と捉えられます。
ただ、「白で塗る」というのは違和感あり。別に「赤・青・黄・緑の４色」
でもいいじゃないかと（もちろんこれにも「地の色は白である」という思い
込みが入っていますが）。
　　 5月19日（木） 1:09:10　　 　　25098
ゴンとも
なんか自分だけ問題文の図で(ア,オ,エ)グループ(イ,ウ)グループ
に分けてるみたいな気が・・・
また塗り分けるというのは隣同士でなく絵の具5色を使用して
違うバリエーションのものができれば
たとえ隣の色が同じでも塗りわけたと解釈してしまうんですけど・・・。
きっと真夜中でおかしいんでしょう思考方法が。では。
豊川市　　 5月19日（木） 1:51:04　　 MAIL:fttnm528@ybb.ne.jp 　　25099
ゴンとも
今、上の図のように、とある問題文の図でア,イ,ウ,エ,オの扇形の角度を測ると
ア=49度,イ=98度,ウ=98度,エ=65度,オ=50度
くらいでア=オはともかくエはだいぶ違いました。
(やはり真夜中で眠いので同じと見えたと思います。)
あと解法としては5なら3,2として分けるので
(4,1とすると面倒)
#25097 で
>題意の図でア,オ,エが同じで
>イ,ウが同じであるとして考えると
同じとして考えなくとも同じです。
豊川市　　 5月19日（木） 2:13:18　　 MAIL:fttnm528@ybb.ne.jp 　　25100
小学名探偵
閉じた配列では、
n>=2のとき、
O(n)=3^n+(-1)^n+3
O(5)=243-3=240 になるようです。
　　 5月19日（木） 8:38:01　　 　　25101
kasama
おはようございます(*^_^*)。

public class Question451 {
　private static int count = 0;
　public static void main(String[] args) {
　　paint(0, new int[5]);
　　System.out.println(count);
　}
　private static final void paint(int n, int[] colors) {
　　if (n >= colors.length) {
　　　for (int i = 0; i < colors.length; ++i) if (colors[i%colors.length] == colors[(i+1)%colors.length]) return;
　　　++count;
　　　return;
　　}
　　for (int i = 1; i <= 4; ++i) {
　　　colors[n] = i;
　　　paint(n+1, colors);
　　}
　}
}
出先　　 5月19日（木） 9:17:57　　 　　25102
小学名探偵
訂正
閉じた配列では、
n>=2のとき、
O(n)=3^n+(-1)^n*3
O(5)=243-3=240 になるようです
　　 5月19日（木） 11:09:36　　 　　25103
吉川　マサル
えと、ちょっと前の話題になりますが...。

最初の問題の書きこみ（#25021）
uchiyanさんの解説（#25061）
Toru Fukatsuさんの補足（#25065）

　この問題ですが、私は全然違う解法を用いました。（もちろんヒントがあったからなんですが）間違ってる部分があればご指摘頂ければ幸いです。

nを整数、mを自然数とし（m,nは互いに素）、cos πx=n/mとおく。（cosで議論して良い理由はuchiyamaさんの説明と同じ）

m≧3を満たすmが存在すると仮定すると、

cos 2πx=2n^2/m^2-1
　　　　=(2n^2-m^2)/m^2

m,nは互いに素だから、mが奇数のとき、m^2と2n^2-m^2は互いに素で、右辺の分母はm^2であり、m≦m^2である。

　　　　　　　　　　 mが偶数のとき、右辺の分母はm^2/2であり、m≦m^2/2

よって、m≧3であれば、cos 2^a・xπはすべて有理数で、全て異なる。

ところでp,qを互いに素な整数、kを自然数とするとき、

cos k(q/p)π=cos (2t/p)π　　 　（←qk = 2t　とおく）
　　　　　　=cos (ps+r)/p・2π　（←2tをpで割った商をs、余りをrとおく）
　　　　　　=cos (r/p)・2π

となるが、rは高々p-1通りであるので、矛盾。

よって、m=1,2

（以下略）
PowerBook G4　　 5月19日（木） 13:10:34　　 MAIL:masaru-y@san　su.org HomePage:算チャレ　　25104
uchinyan
はい、こんにちは。
今回は、まずは、地道に解いて、漸化式でもできそうだったので、それも考えてみました。

(解法1)
地道な方法です。
まず、明らかに、塗る色は、3色か4色でないとダメです。
・3色の場合
3色を選ぶのに 4 通り、アを選ぶのに 3 通り、イを選ぶのに 2 通り、は、すぐに分かります。問題はウとオの塗り方です。
同じ色の場合は、アともイとも違う色を塗ることになり 1 * 1 通りで、このとき、エが 2 通り。
異なる色の場合は、エは 1 通りで、オがイと同じ場合は、ウは 2 通り、オがイと違う場合は、ウは 1 通りです。
そこで、4 * 3 * 2 * (1 * 1 * 2 + (1 * 2 * 1 + 1 * 1 * 1)) = 120 通りになります。
・4色の場合
アを選ぶのに 4 通り、イを選ぶのに 3 通り、は、すぐに分かります。ウとオの塗り方がやはり問題になります。
同じ色の場合は、アともイとも違う色を塗ることになり 2 * 1 通りですが、このとき、エは、4色を使うという条件から 1 通りです。
異なる色の場合は、オがイと同じ場合は、やはり4色を使うという条件からウは 2 通りになり、エが 1 通りで、1 * 2 * 1 通り、
オがイと違う場合は、ウがアと同じときには、やはり4色を使う条件からエが 1 通りで 2 * 1 * 1 通り、
ウがアと違うときには、エが 2 通りで 2 * 1 * 2 通りになります。
そこで、4 * 3 * (2 * 1 * 1 + (1 * 2 * 1 + 2 * 1 * 1 + 2 * 1 * 2)) = 120 通りになります。
以上ですべてなので、120 + 120 = 240 通り。

(解法2)
漸化式を考えます。
一般に、円を、区別する n 個の区画に分けて 4 色で塗り分ける場合の数を a(n) とします。
すると、a(n) は、
n-1 の場合の区画を分ける線のところを切り開いて新たな区画を追加するか、
n-2 の場合の区画の一つの中を二つに切り開いて新たな区画を追加するか、
のいずれかになります。
このとき、どの部分を切り開くかは、対称性により区別する必要はありません。
(要するに、「ア、イ、ウ、エ」に「オ」を追加する場合、「ア、イ、ウ、エ、オ」と「ア、イ、ウ、オ、エ」とは、
単に文字の付け方の差しかなく、二つの区画は同じものです。)
線のところを切り開く場合には両側の色は異なるので 2 通りの、
区画の中を切り開く場合には両側の色は同じなので 3 通りの色の区画を追加できます。
そこで、次の漸化式が成立します。
a(n) = 2 * a(n-1) + 3 * a(n-2)
ただし、初期条件が微妙で、n = 1, 2, 3 の場合は、区画の追加が一部しか成立せず、
a(1) = 4, a(2) = 3 * a(1) = 12, a(3) = 2 * a(2) = 24
となります。したがって、先ほどの漸化式は、n >= 4 で成立します。これから、
a(4) = 2 * a(3) + 3 * a(2) = 2 * 24 + 3 * 12 = 48 + 36 = 84
a(5) = 2 * a(4) + 3 * a(3) = 2 * 84 + 3 * 24 = 168 + 72 = 240
となり、240 通りになります。
なお、高校レベル？(多分、普通の高校生にはちょっと難しいかも．．．)ですが、n >= 4 で、
a(n) + a(n-1) = 3 * (a(n-1) + a(n-2)) = ... = 3^(n-3) * (a(3) + a(2)) = 4 * 3^(n-1)
a(n) - (-1) * a(n-1) = 4 * 3^(n-1)
(-1)^n * a(n) - (-1)^(n-1) * a(n-1) = 4 * (-1)^n * 3^(n-1)
より、漸化式は解けて、
a(n) = 3^n + (-1)^n * 3, n >= 4
となります。これと、a(1), a(2), a(3) とを比較すると、
a(1) = 4, a(n) = a(n) = 3^n + (-1)^n * 3, n >= 2
が、一般解になります。
ネコの住む家　　 5月19日（木） 14:44:49　　 MAIL:uchi@sco.bekkoame.ne.jp 　　25105
uchinyan
一応、掲示板読みました。
#25095のむらかみさん、#25087のひろぼうずさんの解法、見事ですね。勉強になりました。
なお、最初考えて失敗した解法を見直したら、正解にたどり着きました！
#25087のひろぼうずさんの解法にちょっと似ていますが、発想は大分違います。
ご参考までに書いておきます。

(解法3)
円に色を塗るのではなく、5 個の区画に順番に 1 〜 5 の番号をつけ、その番号を書いた札を四つの異なる色を塗った箱に入れると考えます。
箱に入っている番号の区画にその箱の色を塗れば、題意を満たします。この求める場合の数を、a(5) 通りとします。
もし、隣り合う区画に同じ色を塗ってもいい、つまり、1, 2 のように連続する二つの番号、ただし、5 は、4, 5 だけでなく 5, 1 も考えて、が、
同じ箱に入っていてもいいとすると、4^5 通りですが、隣り合う場合を除く必要があります。
隣り合う場合は、隣り合う番号を書いた札を輪ゴムでくくったものを考えればいいです。このとき、
・一つが隣り合う場合：札は 4 枚になり、札の作り方は 5 通り、箱への入れ方は a(4) 通りで、5 * a(4) 通りを引きます。
・二つが隣り合う場合：札は 3 枚になり、札の作り方は 5 + 5 = 10 通り、箱への入れ方は a(3) 通りで、10 * a(3) 通りを引きます。
・三つが隣り合う場合：札は 2 枚になり、札の作り方は 5 + 5 = 10 通り、箱への入れ方は a(2) 通りで、10 * a(2) 通りを引きます。
・四つが隣り合う場合：札は 1 枚になり、札の作り方は 1 通り、箱への入れ方は a(1) 通りで、1 * a(1) 通りを引きます。
結局、
a(5) = 4^5 - 5 * a(4) - 10 * a(3) - 10 * a(2) - a(1)
同様のことを、a(1) 〜 a(4) に考えると、
a(1) = 4^1 = 4
a(2) = 4^2 - 1 * a(1) = 12
a(3) = 4^3 - 3 * a(2) - a(1) = 24
a(4) = 4^4 - 4 * a(3) - 6 * a(2) - a(1) = 84
a(5) = 4^5 - 5 * a(4) - 10 * a(3) - 10 * a(2) - a(1) = 240
で、240 通り。
一般化もできそうですが、#25105の(解法2)でやってしまったので、省略します。
ネコの住む家　　 5月19日（木） 22:13:03　　 MAIL:uchi@sco.bekkoame.ne.jp 　　25106
あする
今回のは簡単でした
解き方
まず、並び方を考えます
例えば、赤をウに塗るとすると、もう１つの赤をアかオに塗ることになります。すると、横に並んだ４つの四角に、赤が両端にこないように塗るのと同じになります。
よって、（４−２）＊３＊２＊１＝１２通りの並び方があります。
次に色の選び方を考えます
４つの色で、５つの部分に塗るので、必ず１つは２回使います。
二回使う色を考えればいいですから、色は４通りの選び方があります。
位置は、１マスずつずらせば違う位置になればいいので、５通りあります。
よって、１２＊４＊５＝２４０通りとなります。
　　 5月19日（木） 16:34:41　　 　　25107
uchinyan
#25104：マサルさん、解法、ありがとうございます。
細かい点がちょっと気になったのですが、ロジックは正しいようです。
気になった点：
＞m,nは互いに素だから、mが奇数のとき、m^2と2n^2-m^2は互いに素で、右辺の分母はm^2であり、m≦m^2である。
偶数の場合もそうですが、「≦」の等号は意味があるのでしょうか？
もちろん、あり得ないのですが、等号がいえたとすると、以下の議論が微妙になります。
「<」でいいのでは？
＞cos k(q/p)π=cos (2t/p)π　　 　（←qk = 2t　とおく）
＞　　　　　　=cos (ps+r)/p・2π　（←2tをpで割った商をs、余りをrとおく）
ここの等式が変です (^^;
2t = 2 * (ps+r) で、t = ps+r のようです。
この場合、kq が偶数でないと、t は整数にならず、商、余りが、意味がなくなります。
多分、今の場合、「cos 2^a・xπ」に対して考えるので、k は偶数としてよく、問題は生じないとは思います。
＞となるが、rは高々p-1通りであるので、矛盾。
高々 p 通り？　cos(2π) は除いて考えているのですね、きっと。

実は、私は、4通りの方法を模索していました。
一つ目は、掲示板に書いた方法、
二つ目は、正多角形の外接円の半径と辺の比が有理数になる場合の検討、
三つ目は、ax = sin(πx), ただし、a は有理数、の場合の有理数解の検討、
四つ目は、マサルさんのように、三角関数の公式から、無限個の有理数が出現し、三角関数の周期性と矛盾するという方向、
です。
一つ目で解けたので、取り敢えず満足してしまいましたが、例の
「cos(π/n) が有理数」<=> 「cos(πm/n) が有理数」
は、四つ目の方向を模索していたときの副産物です。
四つ目の方向は、マサルさんの解法でスッキリしました。
なお、二つ目の方向は、
「正多角形の外接円の半径とその正多角形の一辺との比が有理数となるのは正六角形だけ。」
という興味深い命題とこの問題が関係が深いことを意味します。何か、算数っぽくできそうな気がするのですが．．．
また、三つ目の ax = sin(πx) の有理数解は、0 <= x <= 1/2 に限定すると、a が 2 又は 3 に限られる、というやはり興味深い結果に等価です。
いずれにせよ、面白い問題をありがとうございました。
あ、もちろん、算チャレ問題も、いつも面白いですぅ ^^/

ネコの住む家　　 5月19日（木） 17:46:33　　 MAIL:uchi@sco.bekkoame.ne.jp 　　25108
kobayashi
３色で塗る場合　４色から３色を選ぶ組み合わせは４通り　３色で５箇所を塗るのだから赤で２箇所　緑で２箇所　黄で１箇所のように塗る箇所の数の組み合わせは（２，２，１）よってそのうちのひとつを求めて３倍すればいい　隣合わない２箇所の選び方は５通りでその各々に対して隣合わない２箇所を選ぶ方法は２通り　よってある特定の３色で塗り分ける方法は５×２＝１０通りを３倍した３０通り　特定の３色の選び方は４通りあるので３色で塗る方法は３０×４＝１２０通り　　次に４色で塗る場合　４色のうちひとつだけを２回使い他は１回ずつなのである特定の色を２回使う場合を求めて４倍すればいい　ある特定の色を２回使う方法は、５箇所から隣合わない２箇所を同じ色で塗る方法×残りの３箇所を残りの異なる３色で塗る方法なので５×６＝３０通り　よって４色で塗る方法は３０×４＝１２０通り　塗り分け方は合計して１２０＋１２０＝２４０通り
　　 5月19日（木） 21:14:18　　 　　25109
uchinyan
(少し追加)
(解法4)
#25106の(解法3)の置き換えをイメージした方が分かりやすいですが．．．
アは 4 通り、イは 3 通りで、
・ウがアと同じ色の場合は、ウは 1 通り、エは 3 通り、オは 2 通り。
・ウがアと異なる色の場合は、ウは 2 通りで、
・・エがアと同じ場合は、エは 1 通りで、オは 3 通り。
・・エがアと異なる場合は、エは 2 通りで、オは 2 通り。
結局、4 * 3 * (1 * 3 * 2 + 2 * (1 * 3 + 2 * 2)) = 4 * 3 * 20 = 240 通り。
これは、#25105の(解法1)の修正版ですが、#25105の(解法2)のように、一般化が容易です。
#25106の(解法3)の置き換えで考えます。なお、n >= 4 とします。
今回の題意の場合の数を a(n)、一般に、n が 1 と異なる箱に入る場合の数を b(n)、n が 1 と同じ箱に入る場合の数を c(n)、とします。
すると、明らかに、
a(n) = b(n)
b(n) = 2 * b(n-1) + 3 * c(n-1)
c(n) = b(n-1)
これから、
a(n) = 2 * a(n-1) + 3 * a(n-2)
となり、#25105の(解法2)の漸化式が導けます。
なお、#25087のひろぼうずさんの解法は、
a(n) + a(n-1) = b(n) + c(n) = 3 * (b(n-1) + c(n-1)) = ... = 3^(n-3) * (b(3) + c(3)) = 3^(n-3) * (a(3) + a(2)) = 4 * 3^(n-1)
が、a(1) = 4, a(2) = 12, a(3) = 24 より、n >= 3 で成立することと、a(2) = 4 * 3 から
a(5) = 4 * 3^4 - a(4) = 4 * 3^4 - (4 * 3^3 - a(3))
= 4 * 3^4 - 4 * 3^3 + a(3) = 4 * 3^4 - 4 * 3^3 + 4 * 3^2 - a(2)
= 4 * 3^4 - 4 * 3^3 + 4 * 3^2 - 4 * 3
ですね。これは、きれいだなぁ。
ネコの住む家　　 5月20日（金） 11:49:52　　 MAIL:uchi@sco.bekkoame.ne.jp 　　25110
吉川　マサル
#25108
>偶数の場合もそうですが、「≦」の等号は意味があるのでしょうか？

　ゴメンナサイ、意味ないです。m(__)m

>＞cos k(q/p)π=cos (2t/p)π　　 　（←qk = 2t　とおく）
>＞　　　　　　=cos (ps+r)/p・2π　（←2tをpで割った商をs、余りをrとおく）
>ここの等式が変です (^^;

　あ、ホントですね。ミスです。

>＞となるが、rは高々p-1通りであるので、矛盾。
>高々 p 通り？　cos(2π) は除いて考えているのですね、きっと。

　pとqは互いに素だから....とか考えてましたが、k=pの場合もあるんでした。orz

　ちなみにこの解法ですが、「倍角の公式で無限に存在することになって、その後は背理法」っていうヒントがあったので解けましたが、そうではければ解けた自信はあまりないかな...。(^^;;
PowerBook G4　　 5月19日（木） 22:17:44　　 MAIL:masaru-y@san　su.org HomePage:算チャレ　　25111
スモークマン
場合わけしてやっと入れました・・・
そうことは簡単ではなかったのですね。

ところで、これも有名？

500円玉しか持っていないn人と1000円札しか
持っていないn人の合計2n人が勝手な順番に輪
をつくってならんでいる。受付は各人から500円
を徴収する。
このとき、つり銭をもっていない受付はある適当な
人から（時計まわりに）集金を開始すれば、つり銭
が不足することがないようにできることを示せ。
　　 5月19日（木） 23:31:23　　 MAIL:kennji72001@yahoo.co.jp 　　25112
吉川マサル
カタラン数ですよね。これも過去門にあります...。
　　 5月20日（金） 0:13:33　　 　　25113
b4kumatyan
アをピンクとして固定して、イは、アと違う３通り。ウは、イと違う３通り、としてオまで考えると、
まず、３＊３＊３＊３＝８１通り。
オがピンクになってダメなケースは２１通り。
よって、アがピンクのとき、題意を満たすのは
８１−２１＝６０通り。

アが他の色についても同様だから
６０＊４＝２４０通り。

泥臭いやり方だった・・・
　　 5月20日（金） 0:35:07　　 　　25114
万打無
　私は配色パターン数を調べて、それに色を当てはめる形で考えました。
　（アイウエオ）に色A,B,C,Dを当てはめる。
　交換した場合同じになる場合は除く。例えば（アイウ）にて(ABA)と(BAB)は同じとする。
　配色パターンを考えるとき、アをAに固定しイ,オをBB,BCと考えると簡単である。

　１色、２色で塗る場合は不可。

　３色の場合(ABCAB)(ABACB)(ABABC)(ABCBC)(ABCAC)の５通り。
　色の選び方が4通り。色の振り分け方が3！＝6通りなので、4×6×5=120通りあることになる。

　４色の場合(ABCDB)(ABDAC)(ABDBC)(ABADC)(ABCDC)の５通り。
　色の選び方が1通り。色の振り分け方が4！＝12通りなので、1×12×5=120通りあることになる。

　よって全部の組み合わせは合わせて240通りあることになる。
　　 5月20日（金） 7:54:15　　 　　25115
小学名探偵
色分け
開いた配列の場合の数L(n)= 4*3^(n-1)
閉じた配列の場合の数O(n)
両者の関係は、
n = 1,2のとき、L(n)= O(n)
n >2 のとき、L(n)= O(n)+O(n-1)

したがって、k>=1 のとき、
O(2k)= Σ{i= 1 to k}L(2i)- Σ{i= 1 to k-1}L(2i+1)
L(x)に値を代入して、O(2k)= 3^2k+3
O(2k+1)= Σ{i= 1 to k}L(2i+1)-Σ{i= 1 to k}L(2i)
（たとえば、O(5)=L(5)-L(4)+L(3)-L(2)です）
L(x)に値を代入して、O(2k+1)= 3^(2k+1)-3

また、O(n)の漸化式は、
L(n)= O(n)+O(n-1)と
L(n)=3L(n-1)から、
n>=4のとき、
O(n)+O(n-1)=3O(n-1)+3O(n-2)
よって、
O(n)=2O(n-1)+3O(n-2)
　　 5月20日（金） 8:20:24　　 　　25116
uchinyan
#25116：私の#25105の(解法2)、#25110の(解法4)辺りと同じですね。
特に、L(n) = b(n) + c(n), O(n) = a(n) ですね。
ネコの住む家　　 5月20日（金） 11:40:51　　 MAIL:uchi@sco.bekkoame.ne.jp 　　25117
uchinyan
#25112：
数学的帰納法で証明できますね。
いかにも数学オリンピックという感じの問題ですが、違うのかな？
#25113：
算チャレの過去問にあるのですか。さすがですねぇ。
ネコの住む家　　 5月20日（金） 13:08:30　　 MAIL:uchi@sco.bekkoame.ne.jp 　　25118
吉川　マサル
#25118
　あ、過去問と言ってもさすがにそのままではありませんけど、まぁ趣旨は似たようなものだったかと。
PowerBook G4　　 5月20日（金） 13:33:20　　 MAIL:masaru-y@san　su.org HomePage:算チャレ　　25119
uchinyan
#25117：済みません、言葉足らずでした。何故か修正ができない．．．
＞#25116：私の#25105の(解法2)、#25110の(解法4)辺りと同じですね。
＞特に、L(n) = b(n) + c(n), O(n) = a(n) ですね。
#25116を読み返してみて、L(n)の使い方がうまいなぁ、と感心しました。
特に、O(n)、私の a(n)、を直接に求めるよりもL(n)経由で求める方が容易です。
O(n)が、L(n)の交代級数で表されるのも自然ですし。
勉強になりました。
ネコの住む家　　 5月20日（金） 14:38:17　　 MAIL:uchi@sco.bekkoame.ne.jp 　　25120
スモークマン
#25118
実際にどこからお金を徴収すればいいかの見つけ方も分かるでしょうか？
金光　　 5月20日（金） 16:01:26　　 MAIL:kennji72001@yahoo.co.jp 　　25121
ハラギャーテイ
プログラムでできました。
京都へ来ています。
北九州　　 5月20日（金） 17:04:41　　 HomePage:信号処理に挑戦　　25123
uchinyan
#25121：どうかなー (^^;　帰納的に可能なのかな？　
一応、私の考えた証明を書いておきますが、私の証明では、残念ながら、ちょっと無理のような気がしますね。
(#25112のお金を集める問題の証明)
n = 1 は、500円玉を持っている人から始めればいいので、明らか。
n-1 以下で、正しいと仮定します。
500円玉を持っている人を適当に一人選んでその人から開始するとします。その人を 1 と番号をつけておきます。
もし、これで最後までうまくいけば、問題なしです。
うまくいかなかった場合、1000円札を持っていておつりが払えなくなる最初の人を k+1 番目の人とします。
すると、1 〜 k では受付さんの持っている500円玉は 0 個以上で、k でちょうど 0 個になっています。
このとき、1 〜 k の人は、500円玉を持っている人と1000円札を持っている人とが同数です。
そうでないと、k でちょうど 0 個になりません。
そこで、k >= 2 で、この 1 〜 k の人を除いた残りの人、k+1, ..., 2n-1, 2n は、2n 人より少なく、
500円玉を持っている人と1000円札を持っている人とが同数になっています。
したがって、残りの人に帰納法の仮定が適用できて、残りの人には、必ず、受付さんの徴収は成功します。
この場合の開始する人を A とします。
すると、k+1 の一つ前、2n か A (A が 2n の場合)、では、受付さんの500円玉は 1 個以上です。
さて、1 〜 k の人を戻して 2n 人の場合、この A から新たに徴収を開始します。
すると、A 〜 2n までは除いた場合と同じで問題なく、1 〜 k はそもそも問題なく、
k+1 の番でも受付さんは 1 個以上の500円玉を持っているので問題なく、後は、除いた場合と同じで問題なく、すべてうまくいきます。
(証明終)
この証明では、うまくいかなかった場合、及びその 1 〜 k の特定ができそうにないので、開始する人を特定するのは無理そうですね。
他のうまい証明があればいいのですが．．．
ネコの住む家　　 5月20日（金） 17:31:21　　 MAIL:uchi@sco.bekkoame.ne.jp 　　25124
スモークマン
#25124：uchinyanさん、ありがとうございます。
これからゆっくり読ませていただきま〜す。
金光　　 5月20日（金） 19:23:51　　 MAIL:kennji72001@yahoo.co.jp 　　25125
鉄道アニマル（マジで）中１
久々のカキコです。
まず、４色をどのような配分で塗るかは、（２，１，１，１）（２，２，１，０）の２通り。
（２，１，１，１）の場合
配分２の塗り方は、（アウ）（アエ）（イエ）（イオ）（ウオ）の５通り。
あとの配分１の塗り方は、配分２の余りに塗ればいいので、３！＝６通り
配分２のところに、色を４ついれられるので、５＊６＊４＝１２０通り
（２，２，１，０）の場合
まず、配分１の入れ方は５通り。
ここで、残り４つの枠は、一列に並んでいることに気づく。
よって、隣り合わないように２色を塗るためには、（左端，右から２番目）（右端，左から２番目）の２通り。
配分の仕方は、配分１に４通り。配分０に残りの３通り。よって、４＊３＝１２通り。５＊２＊１２＝１２０通り
この２つを合わせて、１２０＋１２０＝２４０通り。

さとすぺ�蠅猟鏤劼任后�（マジで）　　 5月20日（金） 21:44:16　　 　　25126
姉小路
�顱烹蛙�塗りの場合
１回しか使わない色の選び方は、4通り。
また、１回しか使わない色を塗る場所の選び方は5通り。
２回使う色の選び方は、3C2=3通り。
また、その他の部分の色の塗り方は2通りなので、
4*5*3*2=120通り

�髻烹歓�塗りの場合
２回使う色の選び方は4通り。
２回使う色の配分の仕方は5通り。
残りの部分の色の塗り方は3*2*1=6通りなので、
4*5*6=120通り

以上より、120+120=240通り

です。皆様と同じ解法ですね(^^;
算数の街　　 5月20日（金） 21:58:43　　 MAIL:pctakada@mail.goo.ne.jp HomePage:高田の呟き　　25127
LEN
#25112
500円所有者＝”+1”，
1000円所有者＝”-1”，
輪の任意の開始位置をi=0とおき（f(0)=0)、そこから時計回りに進むとき、
所有者に遭うごとに、iを1インクリメントし、
500円所有者ならば、f(i)=f(i-1)+1,
1000円所有者ならば、f(i)=f(i-1)-1とする。
開始位置に戻ると、f(2n)=0=f(0)になる。
上の関数f(i)は、iの初期値0と終値間2nにおいて、最大値と最小値をもつ。

よって、f(i)が最小になる位置から始めれば、
釣り銭が不足することはありません。

反時計回りに進むときは、時計回りのときにf(i)が最大になる位置で
f*(i)が最小になります。
f*(i)：開始位置をi=2nとおき(f*(2n)=0)、そこから反時計回りに進むとき、
　　　所有者に遭うごとに、iを1デクリメントし、
　　　500円所有者ならば、f*(i)=f*(i-1)+1,
　　　1000円所有者ならば、f*(i)=f*(i-1)-1とする。
このとき、f(i)+f*(i)=0
　　 5月21日（土） 3:25:24　　 　　25128
uchinyan
#25128：
LENさん、興味深く読ませて頂きました。お見事です。
スモークマンさん、この解法ならば、徴収を開始する人を特定できそうです。その意味で、私の解法より優れていると思います。
ただ、ちょっと細かい点を補足しておいた方がいいかもしれません。

＞#25112
＞500円所有者＝”+1”，
＞1000円所有者＝”-1”，
＞輪の任意の開始位置をi=0とおき（f(0)=0)、そこから時計回りに進むとき、
＞所有者に遭うごとに、iを1インクリメントし、
ここらは、i を、受付さんが徴収を開始した後の状態、と考えた方がいいように思います。
i = 0 は、徴収を開始する前の状態、いわゆる初期状態ですね、i = k は、k 番目の人から徴収した後の状態、です。
＞500円所有者ならば、f(i)=f(i-1)+1,
＞1000円所有者ならば、f(i)=f(i-1)-1とする。
＞開始位置に戻ると、f(2n)=0=f(0)になる。
「開始位置に戻ると」は、「徴収をし終わった状態では」、ということです。
＞上の関数f(i)は、iの初期値0と終値間2nにおいて、最大値と最小値をもつ。
これは、f(i) が有限個の整数の集合なので、明らか。
＞よって、f(i)が最小になる位置から始めれば、
正確には、「f(i)が最小になる状態の次の人から始めれば、」かな。
要するに、f(m) = 最小値 として、m+1 から開始する、ということです。
＞釣り銭が不足することはありません。
すべての i に対して f(i) >= 最小値 = f(m)、なので、g(i) = f(i+m) - f(m) とすれば、g(0) = 0 で、g(i) >= 0 です。
なお、時計回りか反時計回りかは、問題の本質とは関係ないですね。

徴収を開始する人を特定するには、与えられた実際の並びに対して、f(i) を計算して最小値を求めればいいわけです。
最小値を与える i が一意でない場合もありますが、その場合にはそのどれをとっても OK です。
ただし、f(i) の取り方に、取り敢えずどの人から開始するかの任意性があります。
しかしこの任意性は、f(0) = 0 の与え方のズレだけなので、グラフ的にいうと軸方向の平行移動だけなので、座標の入れ方の任意性に過ぎず、
どの f を用いても、最小値の特定は同じで、それに対応する人の特定も、座標のズレを考慮すれば、同じです。
要は、a が500玉を持っていることを [a,+] と書くとして、[a,+], [b,-], [c,-], [d,+], [e,-], [f,+] となっていたとして、
a から始めると、f(i) は、0 (= f(0)), 1, 0, -1, 0, -1, 0 なので、最小値を与えるのは i = 3 or 5 ですが、これは、c 又は e で、
b から始めると、f(i) は、0 (= f(0)), -1, -2, -1, -2, -1, 0 なので、最小値を与えるのは i = 2 or 4 ですが、これは、やはり、c 又は e です。
つまり、どちらで計算しても、開始する人は、d 又は f に特定できます。
これでうまくいくのでは？
ネコの住む家　　 5月21日（土） 11:50:41　　 MAIL:uchi@sco.bekkoame.ne.jp 　　25129
スモークマン
#25129,#25128:
LENさん、uchinyanさん、解法ありがとうございます。
わたしは数式が苦手ですぐ理解できなくて・・・
直感的に、500円-1000円の連続になるところを次々に消して行くと、最後に1組だけ500-1000の鎖が残るので、その残った500円の人から集めたらいけそうに思うのですが？いかがでしょうか？
みなさんと同じことを言ってるだけかも・・・
金光　　 5月21日（土） 12:51:38　　 MAIL:kennji72001@yahoo.co.jp 　　25130
uchinyan
#25130：
＞直感的に、500円-1000円の連続になるところを次々に消して行くと、最後に1組だけ500-1000の鎖が残るので、
＞その残った500円の人から集めたらいけそうに思うのですが？いかがでしょうか？
お、確かにそうだな．．．うーむ、そうですね、確かに正しそう、これは参った (^^;
＞みなさんと同じことを言ってるだけかも・・・
その可能性はありますが、何よりも簡明で優れていると思います。
なお、LENさんの解法では、可能な人を「一度にすべて」特定できる点が優れていると思います。
もちろん、スモークマンさんの方法でも可能ですが、消し方をいろいろ試さないとならないと思います。
いずれにせよ、私の解法が一番ダメですね．．．
うーむ、まだまだ修行が足りません．．．目から鱗ですぅ ^^/
ネコの住む家　　 5月21日（土） 13:28:31　　 MAIL:uchi@sco.bekkoame.ne.jp 　　25131
成藤
４色をそれぞれ１，２，３，４とすると，アを１、イを２で塗った場合、もう１色使った場合は１０通り，もう２色使った場合も１０通りで計２０通り。　　　　　　アとイの組み合わせは　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　１と２，１と３，１と４，　　　　　　　　　　　　　　　　　　　　　　　　　２と１，２と３，２と４，　　　　　　　　　　　　　　　　　　　　　　　　　３と１，３と２，３と４，　　　　　　　　　　　　　　　　　　　　　　　　　４と１，４と２，４と３の１２通りなので，　　　　　　　　　　　　２０×１２＝２４０通り　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　しらみつぶしに泥臭くやって，やっととけました。
　　 5月21日（土） 13:18:01　　 　　25132
スモークマン
#25129,#25128:
LENさん、uchinyanさん、解法ありがとうございます。
わたしは数式が苦手ですぐ理解できなくて・・・
直感的に、500円-1000円の連続になるところを次々に消して行くと、最後に1組だけ500-1000の鎖が残るので、その残った500円の人から集めたらいけそうに思うのですが？いかがでしょうか？
みなさんと同じことを言ってるだけかも・・・
金光　　 5月21日（土） 13:39:12　　 MAIL:kennji72001@yahoo.co.jp 　　25133
吉川　マサル
【どーでも良いお知らせですが】

　算チャレの各所に貼ってあった広告（クリック数に応じてお金が入るやつ）を撤廃してみました。さほどお金になるわけではないし、何よりもそれによってこのページが重くなっているのが気になりまして。（まぁ、算チャレは巷のページの中ではかなり軽い方だとは思いますが）

# あ、WILLCOMの紹介とかしてますが、これはお金はもらってない「勝手に広告」ですので。(^^;;
PowerBook G4　　 5月21日（土） 23:03:24　　 MAIL:masaru-y@san　su.org HomePage:算チャレ　　25134
uchinyan
今回の問題、もう一つ、解法を思いつきました。(解法3)や、ひろぼうずさんの解法にちょっと似ていますが、かなり違います。

(解法5)
隣り合った部分の色を違える塗り分けを最初は無視して数え、後から引いていきます。
塗り分けを無視すれば、4^5 通りです。
これから、アとイ、ウとエのように、隣り合った部分が同じ色になるものを引きます。
これは、隣り合った部分の境を選んでその境をとってしまったものを考えればいいので、5C1 * 4^4 通り。
しかし、アとイとウのように三つ隣り合ったものを引き過ぎたので、これを足します。
これは、同様に考えて、境を二つ選べばいいので、5C2 * 4^3 通り。
さらに、四つ隣り合ったものが復活してしまったので、これを引きます。
これは、境を三つ選べばいいので、5C3 * 4^2 通り。
最後に、五つの部分が一つになった場合を引き過ぎているので、これを足します。
これは、円で閉じることより、今までとちょっと違って、境を四つ選んだ場合、5C4 * 4 通り、を足しただけでは足し過ぎで、
境を五つ選んだ場合、5C5 * 4 通りを引かないとダメです。
最後の部分がミソです。結局、
4^5 - 5C1 * 4^4 + 5C2 * 4^3 - 5C3 * 4^2 + 5C4 * 4 - 5C5 * 4
= 4^5 - 5C1 * 4^4 + 5C2 * 4^3 - 5C3 * 4^2 + 5C4 * 4 - 1 - 3
= (4 - 1)^5 - 3 = 3^5 - 3
= 240 通り
になります。
この一般化は、非常に容易です。明らかに、
a(n) = 4^n - C(n,1) * 4^(n-1) + C(n,2) * 4^(n-2) - C(n,3) * 4^(n-3) + ...
+ (-1)^(n-2) * C(n,n-2) * 4^2 + (-1)^(n-1) * C(n,n-1) * 4 + (-1)^n * C(n,n) * 4
= (4 - 1)^n - (-1)^n + (-1)^n * 4
= 3^n + (-1)^n * 3
に、なります。
ネコの住む家　　 5月22日（日） 22:38:59　　 MAIL:uchi@sco.bekkoame.ne.jp 　　25135
N.Nishi
地道にパターンを数えました。
　　 5月24日（火） 5:48:44　　 　　25136

過去問題一覧へ戻る