��裴��ʬ�β��

い

ちばん！　　って、嘘

　　 7月1日（木） 0:06:03　　　　23171

あ〜く＠ぴかぴかの（略

開始数分後に解法が分かるも何故か「(10,[5])-5*(6,[5])=222」
なぞという式をたててしまい、このためさらに数分合っている考え方を
色々といじくって、やっと書き間違いに気づきました・・・（[5]→[4]に）

考え方としては五角形は対角線と辺の合計が10本なのでここから4本選ぶと(10,4)
で、あとは一つの頂点から出ている四本の線分を除いた6本から4本選ぶ場合の数が(6,4)なので、
求める場合の数は(10,4)-5*(,6,4)=135

※（〜、〜）は２項係数です。

未完成の蜜柑星　　 7月1日（木） 0:20:59　　 MAIL:ishizaki@qa.so-net.ne.jp 　　23172

ｎ厨

ぇ何？

　　 7月1日（木） 0:21:06　　　　23173

ｎ厨

なんかおかしい。

　　 7月1日（木） 0:23:01　　　　23174

あ〜く＠ぴかぴかの（略

遅ればせながら進作さん、誕生日おめでとうございます。

マサルさんは今日（７／１）が誕生日なのでしょうか？それとも昨日（６／３０）が誕生日だったのでしょうか？
何はともあれ、三十数歳（ぇ）のお誕生日、おめでとう御座いますm(_ _)m

未完成の蜜柑星　　 7月1日（木） 0:24:21　　 MAIL:ishizaki@qa.so-net.ne.jp 　　23175

吉川　マサル

#23172
　想定した解き方はまさにこれとおんなじなんですが、しかし「１２５通り」という解答がやたらと多い（それも大物の方に...）のが非常に気になっています。う〜む、大丈夫なんだろうか...。

#27175
　えと、６／３０でした。３４歳になりました。(^^;;

MacOS X　　 7月1日（木） 0:27:34　　 MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ　　23176

CRYING DOLPHIN

125になるかは未検証でしたが、#23712さんの解き方を見て、
135より少なくなるという結論が出ました。
反例は少々お待ちを。

１年ピカチュウ組　　 7月1日（木） 0:32:52　　 HomePage:算数の限界ってどのくらい？　　23177

あ〜く＠ぴかぴかの（略

#23178 (マサルさん）
A島〜E島まであるとすると、以下のような橋のかけ方もオッケーなのでしょうか？
A-B B-C C-A D-E
これが駄目なら130通りのような気も・・・

未完成の蜜柑星　　 7月1日（木） 0:34:36　　 MAIL:ishizaki@qa.so-net.ne.jp 　　23178

吉川　マサル

し、しまった...。３角形＋線分の場合があった...。

２週連続のミスになってしまいました...。m(__)m

MacOS X　　 7月1日（木） 0:35:01　　 MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ　　23179

CRYING DOLPHIN

たとえばこんなの
http://ha3.seikyou.ne.jp/home/okabayashi/toi408qqq.GIF

１年ピカチュウ組　　 7月1日（木） 0:35:20　　 HomePage:算数の限界ってどのくらい？　　23180

あ〜く＠ぴかぴかの（略

125通りのようですね（＾＾；）

結局はいつも通り間違っていたわけですか・・・場合の数は難しい・・・

未完成の蜜柑星　　 7月1日（木） 0:36:19　　 MAIL:ishizaki@qa.so-net.ne.jp 　　23181

Taro

135−5C2=125　になるのかな？

じたくぅ　　 7月1日（木） 0:36:41　　 MAIL:tarox@nifty.com 　　23182

まるケン

橋の架かり方は以下の３通りと思います。

Ａ　ひとつの島から他の４つの島へ放射状に橋を架ける
Ｂ　ひとつの島から他の３つの島へ放射状に橋を架け、最後の
　　島へはその３つのうちのどれかから架ける
Ｃ　一筆書きのように島を結ぶ

それぞれの架け方を調べると、
Ａはどの島を中心にするかで５通り
Ｂは中心の島の選び方が５通り、最後の島の選び方が４通り、
最後の島を３つの島のどれと結ぶかで３通り、全部かけて６０通り
Ｃは５×４×３×２通りを逆順も考えて２で割って６０通り

答え：１２５通り

また、ＮＧな架け方を探してみました。

Ａ　４つの島で四角形を形成する
Ｂ　３つの島で三角形を形成し、そのどれかともうひとつの島を結ぶ
Ｃ　３つの島で三角形を形成し、残りの２つを結ぶ

Ａはどの島を仲間はずれにするかで５通り
Ｂは三角形の作り方が１０通り、どの島を結ぶかで２通り、三角形の
どの島と結ぶかで３通り、かけて６０通り。
Ｃは三角形を作れば残りの二つは決定するので１０通り。

合計、７５通り
１０本から４本を選ぶ選び方
１０×９×８×７÷（１×２×３×４）＝２１０からＮＧを引いて、

２１０−７５＝１３５

答え：１３５通り

としたいところですが、４つの島をループにするのに３通りの
結び方があるので、Ａのケースは１５通り。

よって、ＮＧは１５＋６０＋１０＝８５通り。

結局答えは１２５通りでは？

　　 7月1日（木） 0:39:26　　 MAIL:take4310@mobile.email.ne.jp HomePage:まるケンの部屋　　23183

tomh

#23172のような考え方をしたけど、
やっぱり変な気がする…
125通りが正しいのでは?

ところで、前回の答えで認証できるようになっていませんか、マサルさん?

新潟市　　 7月1日（木） 0:39:26　　 MAIL:tomh@yahoo.co.jp 　　23184

n厨

＞結局はいつも通り間違っていたわけですか
ぇｗ

　　 7月1日（木） 0:39:56　　　　23185

圭太

#23183　おいらも同じ考えでしたが。。＾＾；

米所〜♪　　 7月1日（木） 0:40:46　　 HomePage:圭太の研究所＠いれこみくん！＆役満縛り〜♪　　23187

あ〜く＠ぴかぴかの（略

#23185
＞結局はいつも通り間違っていたわけですか
いやいや、場合の数は苦手な範疇なのでいつも間違いまくっているからこう書いただけです。

未完成の蜜柑星　　 7月1日（木） 0:42:34　　 MAIL:ishizaki@qa.so-net.ne.jp 　　23188

呑

もっとお馬鹿な質問してい〜い？
やっぱりや〜めた。
＃23183のまるけんさんの解き方をもう一度考えま酒。

酔っぱらい天国　　 7月1日（木） 0:44:48　　 MAIL:hopes@mba.ocn.ne.jp HomePage:ＨＯＰＥＳ　　23189

ｎ厨

＞あ〜くさん
あ〜くさんに向けて書いたつもりではないですｙo
　
やはりこうなｒｙ

　　 7月1日（木） 0:47:19　　　　23190

吉川　マサル

　順位表の訂正をいたしました。m(__)m

MacOS X　　 7月1日（木） 0:49:10　　 MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ　　23191

なか

ここにこれないので、こんなメイルを出して寝るところでした。
よかった、よかった。

１．どの島にも橋が２本以内の場合　５！÷２＝６０とおり
２．３本かかる島がある場合
　３本かかる島の選び方　５とおり
　２本かかる島の選び方　４とおり
　その先につながる島の選び方　３とおり、で、５＊４＊３＝６０とおり
３．４本かかる島がある場合
　４本かかる島の選び方そのものなので　５とおり

全部で　６０＋６０＋５＝１２５とおり
# 一部訂正済み（３とおりの意味）

品川　　 7月1日（木） 1:05:15　　 MAIL:naka@sansu.org HomePage:naka's Home Page　　23192

tomh

#23183の通りで
パターンは以下のものですね。

○―○―○―○―○
60通り

○
｜
○―○―○
｜
○
60通り

　　○
　　｜
○―○―○
　　｜
　　○
5通り

新潟市　　 7月1日（木） 0:55:05　　 MAIL:tomh@yahoo.co.jp 　　23193

DrK

今気がつきました。
何てことはないのに！
私の場合、直線しか頭にありませんでした。60を送っても全くだめ。何故かなと考えて寝ようとしたその瞬間、枝分かれは？と思ってみると、枝分かれでも4つの橋で5つの島が結べることに気づきました。後は#23183、#23192、#23193などに書いてある通りですね。
頭に浮かんだイメージは#23193と同じかな？

今は楽園かな?違うな。　　 7月1日（木） 1:12:57　　 MAIL:satoka@star.odn.ne.jp 　　23194

DrK

#23165経友会の進作さんは66歳で吉川　マサルさんは34歳、その差32年丁度なので、日数の差は11688日ということになります。進作さんの奥さんは28日が誕生日で63歳ということなので、差は1094日。
7月1日現在、進作さんは24108日、奥さんは23014日、マサルさんは12420日ということになります。
日数を計算するようになったのは1983年11月3日、それ以来、どこに行ってもこの芸当を披露したのですが・・・
最近は余りやらなくなったかな。でも未だに箇所全員の生年月日を覚えられるけど。

今は楽園かな?違うな。　　 7月1日（木） 1:26:39　　 MAIL:satoka@star.odn.ne.jp 　　23195

DrK

今は楽園かな?違うな。　　 7月1日（木） 1:30:32　　 MAIL:satoka@star.odn.ne.jp 　　23196

DrK

今は楽園かな?違うな。　　 7月1日（木） 1:34:52　　 MAIL:satoka@star.odn.ne.jp 　　23197

DrK

あれ、同じものが3回も書き込まれている！
更新を押したらこうなってしまいました。

今は楽園かな?違うな。　　 7月1日（木） 1:35:54　　 MAIL:satoka@star.odn.ne.jp 　　23198

トトロ＠Ｎ

#23193
全く同じ解き方です。
125でダメだったので風呂に入って出直し。もう一度考えてもやっぱり125。
掲示板に適当に5刻みで数字を入れましたが、あきらめてました。
今覗いたら何と私が１位とは。実は125は3つ目の答えでした。

兵庫県明石市　　 7月1日（木） 1:46:45　　 MAIL:h-sakai@zb3.so-net.ne.jp 　　23199

BossF

(5C2)C4-{5x(4C2)C4+5C2}
全体＜(5C2)C4＞から4-1に分かれたもの＜5x{(4C2)C4}＞と3-2に分かれたもの＜5Ｃ2＞をひきました。
でも、幅が島の間隔ほどもある巨大な橋や、Ｙ字orＸ字型などの変則形の橋を許したらどうなるか・・・・謎です

(^^　　 7月1日（木） 4:10:50　　 MAIL:fv2f-ftk@asahi-net.or.jp HomePage:ＢｏｓｓＦ’Ｓ　Ｔｏｙ　Ｂｏｘ　　23201

小西孝一

対角線付き５角形の辺を４つ選ぶのから、ＮＧの対角線付き４角形から４つ
と、三角形と線の場合を引きました。
10Ｃ4-5*6Ｃ4-5Ｃ3=210-75-10=125
ずっと、寝ぼけて５＊１５＝４５と計算して間違えてました・・・

九州の山奥　　 7月1日（木） 5:04:14　　 MAIL:nikotan@fat.coara.or.jp 　　23202

始受験勉強君

3パターンの橋のかけ方を考えて、最初は85通りとか変な答えになったのですが、途
中でよくよく考えてみると「125通り」ということが分かりました。でも答えを送ったのにも関わらず、正解者順位表に載らない上、正解者掲示板にも入れない。
そして朝、順位表をみると約60人も正解者がいる。もうこりゃだめだとか思ってい
たら、なんと19位に自分の名前が載っている。まあこんな感じで今正解者掲示板に
入りました。
ではさようなら。

算数大好き人間(後は数学)　　 7月1日（木） 6:32:27　　 MAIL:oirarion@dk.pdx.ne.jp 　　23203

ちこりん

１直線の場合（１）、１つの島に行く時だけ脇にそれる場合（２）、１つの島から４つの橋が出てる場合（３）の３パターンでそれぞれの場合の数を求めました。
（１）・・・５つの島の並べ方だから、５！／２＝６０通り
（２）・・・分岐する２つの島以外の３つの島の並べ方だから５Ｐ３＝６０通り
（３）・・・真ん中の島の選び方だけで決まるので、５通り。
よって、６０＋６０＋５＝１２５通り

鹿児島県鹿児島市の桜島のよく見える場所　　 7月1日（木） 6:54:10　　　　23205

ハラギャーテイ

おはようございます。

勘働きで入れました。

北九州　　 7月1日（木） 7:16:20　　 HomePage:ハラギャーテイの制御工学にチャレンジ　　23206

まるケン

おはようございます。

島の数がｎの時の一般解を考えてみました。どうやら、ｎ＾（ｎ−２）になりそうです。
例のサイトではA000272「Number of labeled trees on n nodes」と紹介されています。

　　 7月1日（木） 9:18:57　　 MAIL:take4310@mobile.email.ne.jp HomePage:まるケンの部屋　　23207

kasama

おはようございます。
ちこりんさん(#23205)と同じやり方と思います。

出先　　 7月1日（木） 9:44:35　　　　23208

ISAMU

10C4-5*6C4=135 かな？

　　 7月1日（木） 10:02:17　　　　23209

おかひで博士

ｔｏｍｈさん（#23193）と同じやり方でした
一般項でも考えやすそうですね

ｔｏｍｈさんのような図は、化学で炭素がいくつか並んだ化合物を考えるときによく出てきたのを思い出します

　　 7月1日（木） 10:15:01　　　　23210

M.Hossie

こんばんにゃ。ぼくも最初１３５通りだと思ってしまいました。結局は３つのトポロジーでそれぞれ何通りあるか計算しました。

＞化学で炭素がいくつか並んだ化合物
　有機化学で一番最初に扱うアルカン alkane の異性体 isomer ですね。異性体の構造式とその沸点や融点などの物性とどう関連が有るかなど学習したものであります。懐かしいですね。

都内某所　　 7月1日（木） 12:48:37　　　　23211

ゴンとも

毎回、1日寝るともう素晴らしい解法が今回でいうとグラフ理論でいう木に
元ずく解法がでなにも書くことないです。起きてはいたものの違うサイト
の問題を解いて力つきました。今回の問題に関係ないですけど
算数の玉手箱というサイトの管理人さんがマニアが集まる映画館
の人とは。数学スリラー映画のπをそこで見たのを昨日はDVDで見てました
(半分)。これからはまともなこと書けるようにがんばります。では。

愛知県豊川市　　 7月1日（木） 13:11:01　　 MAIL:ｆｔｔnm528@ybb.ne.jp 　　23212

ドンガバチョ

コッホン、みなっさん！このわたくしドンガバチョが市長になったなら五つの島に４つの橋をかけてどの島にも自由にいけるようにして差し上げます。つきましては何通りのかけ方があるかハカセくんのお知恵を拝借したいのでありま〜す。ブハ、ブハ、ブハ。

　　 7月1日（木） 13:13:26　　　　23213

長野　美光

なんか、久しぶりの参加のような気が．．．
ただ今、天津にいます。（って、いつもって言われそう）
ホテルからのアクセスでは、遅くて、図付きのは不安です。

てんしん　　 7月1日（木） 13:54:19　　 HomePage:ヨッシーの八方美人　　23214

uchinyan

こんにちは。今回は少し苦労しました。皆さん、すごいですね。

最初見たときは、簡単そうだったのですが、頭の中で考えているうちに図形というかグラフがこんがらがってきて、
地道に、島の数、点の数、が、n=2から積み上げてみよう、と思いました。

基本的に、皆さんも書いていますが、島を点、橋を線で表し、対象となるグラフを考えます。また、グラフを、
(グラフの中の点の総数; 線が1本出ている点の数, 線が2本出ている点の数, 線が3本出ている点の数, ...)
で書くことにします。ただし、点が二つの場合の(2;2,0,0,0,...)など、明らかに後ろに0が並ぶ場合には、
(2;2)と書くことにします。
また、このグラフの個数を、f(2;2)などと書くことにします。また、グラフの総数をf(2)などと書きます。

以下、少し長くなります。ご容赦を。

* n=2 の場合
(2;2)だけで、f(2) = f(2;2) = 1通りです。

* n=3 の場合
三つの点のうち、二つを選んでそれにn=2の場合を適用し、三つ目の点をそれにつなげることを考えます。
こうしてできるグラフは、(3;2,1)だけです。これを、
(2;2) -> (3;2,1)
と書きます。このとき、点の総数が一つ増え、線が1本出ている点をつなげることになるので、
線が1本出ている点が、元のグラフから一つ減り、新たに一つ増え、線が2本出ている点が一つ増えます。
この規則性は重要です。
グラフの個数は、二つの点を選ぶのに3通り、n=2がf(2;2)通り、つなげるのに2通り、ですが、出来上がったグラフは、
「−−○」の付け方で2通りの重複があることに注意します。この重複の数は、線が1本出ている点の数に対応します。
したがって、
f(3;2,1) = 3 * f(2;2) * 2 * 1/2 = 3
なので、
f(3) = f(3;2,1) = 3通り
です。

* n=4 の場合
同様に、n=3のグラフに1点を追加することを考えます。
1本線が出ている点に追加する場合は2通りあって、1本線が出ている点は一つ減り一つ増えて変化なし、
2本線が出ている点は一つ増えます。これを次のように書きます。
(3;2,1) -> (4;2,2) * 2
2本線が出ている点に追加する場合は1通りで、今度は、1本線が出ている点が一つ増え、2本線が出ている点が一つ減り、
3本線が出ている点が一つ増えるので、
(3;2,1) -> (4;3,0,1) * 1
これだけです。
したがって、
f(4;2,2) = 4 * f(3;2,1) * 2 * 1/2 = 12
1/2をかけるのを忘れずに！
f(4;3,0,1) = 4 * f(3;2,1) * 1 * 1/3 = 4
今度は、f(4;3,0,1)なので、線が1本出ている点の数は3で、1/3になります。
結局、
f(4) = f(4;2,2) + f(4;3,0,1) = 16通り

* n=5 の場合
同様に計算します。
(4;2,2) -> (5;2,3) * 2 or (5;3,1,1) * 2
(4;3,0,1) -> (5;3,1,1) * 3 or (5;4,0,0,1) * 1
(5;3,1,1)が二箇所から違う重みで現れることに注意です。
したがって、
f(5;2,3) = 5 * f(4;2,2) * 2 * 1/2 = 60
f(5;3,1,1) = 5 * (f(4;2,2) * 2 + f(4;3,0,1) * 3) * 1/3 = 60
f(5;4,0,0,1) = 5 * f(4;3,0,1) * 1 * 1/4 = 5
よって、
f(5) = 60 + 60 + 5 = 125通り
これが今回の答えです。

ここまでくると、グラフが、(5;2,3), (5;3,1,1), (5;4,0,0,1)しかないことが分かるので、
皆さんのような解法も可能です。

なお、以上の計算は、更に続けることが可能です。

* n=6 の場合
(5;2,3) -> (6;2,4) * 2 or (6;3,2,1) * 3
(5;3,1,1) -> (6;3,2,1) * 3 or (6;4,0,2) * 1 or (6;4,1,0,1) * 1
(5;4,0,0,1) -> (6;4,1,0,1) * 4 or (6;5,0,0,0,1) * 1
f(6;2,4) = 6 * f(5;2,3) * 2 * 1/2 = 360
f(6;3,2,1) = 6 * (f(5;2,3) * 3 + f(5;3,1,1) * 3) * 1/3 = 720
f(6;4,0,2) = 6 * f(5;3,1,1) * 1 * 1/4 = 90
f(6;4,1,0,1) = 6 * (f(5;3,1,1) * 1 + f(5;4,0,0,1) * 4) * 1/4 = 120
f(6;5,0,0,0,1) = 6 * f(5;4,0,0,1) * 1/5 = 6
f(6) = 360 + 720 + 90 + 120 + 6 = 1296通り

* n=7 の場合
(6;2,4) -> (7;2,5) * 2 or (7;3,3,1) * 4
(6;3,2,1) -> (7;3,3,1) * 3 or (7;4,1,2) * 2 or (7;4,2,0,1) * 1
(6;4,0,2) -> (7;4,1,2) * 4 or (7;5,0,1,1) * 2
(6;4,1,0,1) -> (7;4,2,0,1) * 4 or (7;5,0,1,1) * 1 or (7;5,1,0,0,1) * 1
(6;5,0,0,0,1) -> (7;5,1,0,0,1) * 5 or (7;6,0,0,0,0,1) * 1
f(7;2,5) = 7 * f(6;2,4) * 2 * 1/2 = 2520
f(7;3,3,1) = 7 * (f(6;2,4) * 4 + f(6;3,2,1) * 3) * 1/3 = 8400
f(7;4,1,2) = 7 * (f(6;3,2,1) * 2 + f(6;4,0,2) * 4) * 1/4 = 3150
f(7;4,2,0,1) = 7 * (f(6;3,2,1) * 1 + f(6;4,1,0,1) * 4) * 1/4 = 2100
f(7;5,0,1,1) = 7 * (f(6;4,0,2) * 2 + f(6;4,1,0,1) * 1) * 1/5 = 420
f(7;5,1,0,0,1) = 7 * (f(6;4,1,0,1) * 1 + f(6;5,0,0,0,1) * 5) * 1/5 = 210
f(7;6,0,0,0,0,1) = 7 * f(6;5,0,0,0,1) * 1 * 1/6 = 7
f(7) = 2520 + 8400 + 3150 + 2100 + 420 + 210 + 7 = 16807通り

．．．

お気づきかどうか．．．
f(2) = 1 = 2^0 = 2^(2-2)
f(3) = 3 = 3^1 = 3^(3-2)
f(4) = 16 = 4^2 = 4^(4-2)
f(5) = 125 = 5^3 = 5^(5-2)
f(6) = 1296 = 6^4 = 6^(6-2)
f(7) = 16807 = 7^5 = 7^(7-2)
...

恐らく、一般に、
f(n) = n^(n-2)
です :-)

証明できるかなぁ。上記の方法では、ちょっと難しいか。

P.S.
上記の関係を発見してニンマリだったのですが、まるケンさんの#23207にご指摘がありました。
有名な問題なのですね。きっと。

　　 7月1日（木） 17:18:37　　　　23215

ちこりん

なんか、飽和炭化水素の炭素の結合の仕方を思い出した。
個々の炭素は区別しないからちょっと様子が違うけど・・・。

鹿児島県鹿児島市の桜島のよく見える場所　　 7月1日（木） 18:52:50　　　　23216

なか

先週ネタ、失礼。
「上位ｋ桁がｋで割り切れ、各桁が異なるｒ桁のｒ進数」という問題。

#23166 uchinyan さんが、２８進数まで調べたというご報告がありました。
C で確認してみました。２８進数までuchinyan さんと同じ結果が得られました。
そして、４０進数までいってももはや解はみつかりません。

「０」を最終桁用に残しておき、奇偶交互に並べるという条件下では、
４０進数でわずか３１桁までしか並べることができず、解はますます遠のくばかりです。
きっと、１４進数が最大です。ね。

<base 2> 1 0
----- base 2 max 2 -----
<base 4> 1 2 3 0
<base 4> 3 2 1 0
----- base 4 max 4 -----
<base 6> 1 4 3 2 5 0
<base 6> 5 4 3 2 1 0
----- base 6 max 6 -----
<base 8> 3 2 5 4 1 6 7 0
<base 8> 5 2 3 4 7 6 1 0
<base 8> 5 6 7 4 3 2 1 0
----- base 8 max 8 -----
<base 10> 3 8 1 6 5 4 7 2 9 0
----- base 10 max 10 -----
----- base 12 max 8 -----
<base 14> 9 12 3 10 5 4 7 6 11 8 1 2 13 0
----- base 14 max 14 -----
----- base 16 max 12 -----
----- base 18 max 14 -----
----- base 20 max 16 -----
----- base 22 max 18 -----
----- base 24 max 18 -----
----- base 26 max 22 -----
----- base 28 max 22 -----
----- base 30 max 24 -----
----- base 32 max 26 -----
----- base 34 max 29 -----
----- base 36 max 28 -----
----- base 38 max 31 -----
----- base 40 max 31 -----

北海道　　 7月1日（木） 20:42:50　　 MAIL:naka@sansu.org HomePage:naka's Home Page　　23217

uchinyan

#23215
先週ネタのご報告、ありがとうございます。
やはり、解は見つかりませんか。
ただ、こだ割り数の場合と違って、コンピュータで計算しただけでは、14進数を超えたら解がないという証明にはならず、
本当にそうなのか、には、数学的な証明が必要ですね。
うーむ、スッキリ証明できないのかな。
まぁ、できたからといって、どうということはないのでしょうが。
今週の一般解の n^(n-2) といい、宿題が残ってしまった感じがしています．．．

　　 7月1日（木） 21:57:00　　　　23218

uchinyan

#23218への訂正。
参照先の#23215は、#23217の間違いです。済みません。

　　 7月1日（木） 21:59:07　　　　23219

経友会の進作

　なまじ家内の誕生月日が6月28日という二つの完全数だったものだから、
つまらない投稿をしました。そうしたらマサル先生と僕が同じ日だなんて。
一部の皆さんからエールを頂き有難うございました。ところが今回の問題
はこの爺さんには大変。皆さんが書かれているようなことを試行錯誤の上
やっと入ることが出来ました。気持は若いですが頭の方の衰えはもはや、
どうしようもなくなりました。まぁそれでも頑張りますわ。

京都府木津町　　 7月2日（金） 7:16:04　　 MAIL:tanioka-s@ams.odn.ne.jp 　　23220

ちこりん

#23220
そういう数字いいですねぇ。
うちの誕生日なんて９月２７日で、たいした数字じゃないです。
素因数分解しても３しか出てこないし・・・。
#23218
今回のn^(n-2)は帰納法で証明できないのでしょうか？
前回のあれは証明なんてどこから手を付ければいいかわからない・・・

鹿児島県鹿児島市の桜島のよく見える場所　　 7月2日（金） 12:30:55　　　　23221

uchinyan

こんにちは。

今回(408回)の問題の一般解 n^(n-2) の証明ができたようなので、ご参考までに紹介しておきます。
また、長くなります。ご容赦を。

証明だけを読むと、何でこんなことを考えるのかちょっと分かりにくい箇所もあると思います。
そこで、具体的な証明を始める前に、まず、証明に至った考えの流れを示します。

* 考え方の経緯

ちこりんさんが#23221にご指摘のように、結果が予想できているので、数学的帰納法を使うのが自然です。
しかし、前回の私の方法(#23215)では、具体的なグラフの形状に注目しているので、n を増やすと新たなf(n;...)が
増えていってしまい漸化式がうまく作れません。そこで、他の方法を模索しました。

グラフを特徴付けるものとして、ある点に集まった線の本数があります。
そこで、グラフの一点Aを固定し、そこから出ている線の本数を考えます。n=5 では、1本、2本、3本、4本の場合があります。
これは、点Aを掴んでグラフを持ち上げたときにできる形状に注目していることに対応します。
今回の問題(点の個数 = 線の本数 + 1)では、ループはありえないので、結局、木構造のグラフを対象にしていることになります。
(このことは、本当は証明が必要でしょうが、ループは、点の個数 = 線の本数であることから明らかなので省略します。)
したがって、一点Aを固定するというのは、木構造グラフの根(ルート)を固定していることに対応します。
すぐに分かりますが、この方法ならば、各線の先につなげるグラフの個数は残りの点の個数の関数で書けます。
ただ、線が2本以上は、残りの点をどの線とつなげるかで、場合分けが発生します。これは必ずしも簡単ではないのですが、
地道に考えれば計算できて、n点のグラフの総数をf(n)とすると、結局、次のような式が導けます。

f(n) = ��(m=1,n-1) { (n-1)C(m) ��(p1+p2+...+pm=n-m-1) {(n-m-1)!/p1!p2!...pm! * f(p1 + 1)f(p2 + 1)...f(pm + 1)} }

ここで、��(p1+p2+...+pm=n-m-1) は、和が n-m-1 になるような0以上のm個の整数に関して和をとることを意味します。
また、f(1)=1 とします。

この式の右辺のf(..)の引数はnより小さいので、右辺に帰納法の仮定を適用して計算すれば、原理的には、証明が可能です。
しかし、この式はそれなりに美しいのですが、複雑であるので、(多分できると思いますが、)うまい計算が思いつきませんでした．．．
そこで、さらに方向転換をします。

計算が難しいのは、点Aから出ている線の先の状況をまじめに計算したからで、これすらも漸化式にできないか、
と考えました。すなわち、上のf(n)の2番目の�瑤慮紊�g(m,n-m-1)(= g(m,n-1-m))とおいてしまって、つまり、

f(n) = ��(m=1,n-1) { (n-1)C(m) * g(m,n-m-1) }

として、g(p,q)の漸化式を新たに考えます。
このとき、g(p,q)は、他のどの点ともつながれていない孤立点を含むグラフも許している点に注意する必要があります。
最初、これは問題ではないかと思ったのですが、この式の意味を考えると納得できます。
すなわち、この式は、点Aからm本出ている線をそれらの線を切るように分割し、点Aを含まない側のグラフの個数を
g(m,n-m-1)とすることを意味します。こうした分割からは、孤立点が出現してもおかしくありません。
後で示す証明は、この方針で行いました。後の証明で見るように、この孤立点の存在が、問題を簡単にします。

これと並行して、グラフの個数の母関数とでもいうべきものも、考えていました。
今、点Aにk本線が集まるグラフの個数をx^kの係数とするようなxの関数をf(n,x)とします。つまり、

f(n,x) = ��(k=1,n-1) (点Aにk本の線が集まるグラフの個数) * x^k

何でこんなものを考えていたかというと、二項係数の計算で (1+x)^n を使用することがよくありますが、
それを真似しようとしたわけです。明らかに、

f(n) = f(n,1)

です。n=2,3,4,5ぐらいの具体的な値で計算してみると、

f(n,x) = x * (x + (n-1))^(n-2)

になりそうな予想がつきます。
残念ながらこれを直接に証明する方法は思いついていないのですが、この予想は、後の証明で一部参考にします。

* 一般解が n^(n-2) となる証明

n点を与えた場合の題意を満たすグラフの総数をf(n)とします。
グラフの一点Aを固定し、その点に集まる線の本数に注目します。
本数がm本の場合、それらの線を切って、点Aを含まない側のグラフの個数を考えます。これは、
g(p,q)を、p個の点で外とつながり、q個の点は外とつながっていないグラフの個数とすると、g(m,n-1-m)と書けます。
一方、m本の線のAとは異なる側のm個の点を選ぶのに (n-1)C(m) 必要なので、

f(n) = ��(m=1,n-1) (n-1)C(m) * g(m,n-1-m)

このとき、g(m,n-1-m)には、他の点とはつながれていない孤立点を含むグラフも許されことに注意します。
次に、g(p,q)について考えます。このグラフ自体、p個の点が、q個の点からなる部分グラフとr個の点でつながっているので、
r個の点を選ぶのに (q)C(r) 通り、r個の点をp個の点と孤立点を許してつなぐのに p^r 通り、部分グラフの個数がg(r,q-r)個、
だから、

g(p,q) = ��(r=1,q) (q)C(r) * p^r * g(r,q-r)

(p個の点に孤立点を許したことで、p個の点をr個の点とつなぐつなぎ方が非常に簡単になっていることに注意。)
ただし、明らかに、g(p,0) = 1 です。(この場合、p個の孤立点があるだけになります。)
f(n)の式と比べると、次が分かります。

f(n) = g(1,n-1)

後は、gについての漸化式を解けばよいのですが、直接に解くのは簡単ではなさそうです。
しかし、二項係数の出現などに注意して、次を利用することを考えます。
(ここで、母関数 f(n,x) も頭におきながら次式を導いています。)

(p+q)^(q-1) = ��(r=0,q-1) (q-1)C(r) * p^r * q^(q-1-r)
p * (p+q)^(q-1) = ��(r=0,q-1) (q-1)C(r) * p^(r+1) * q^(q-1-r) = ... = ��(r=1,q) (q)C(r) * p^r * r * q^(q-r-1)
(r -> r-1 とし、(q-1)C(r-1) = r/q * (q)C(r) を使っています。)

なので、

g(p,q) = p * (p+q)^(q-1)

が解となり、g(p,0) = 1 も満たすという条件から、これに一意に決定します。
これより、

f(n) = g(1,n-1) = n^(n-2)

となります。

これで、一応、証明はできました。
また、式の意味より、

f(n,x) = g(x,n-1) = x * (x + (n-1))^(n-2)

もいえます。

　　 7月4日（日） 15:46:54　　　　23222

uchinyan

#23222への補足。明らかですが、念のため。

g(p,q)におけるp個の点は、今回の題意からすると、互いにつながることはできません。
これは、もしつながっていたら、p個の点は外部のグラフとつながり、外部のグラフは結局は点Aとつながっているので、点Aを通してループができてしまうからです。
今回のグラフがループを含まないことは、先にも注意したとおり、すぐに分かります。
具体的には、2次元版のオイラーの公式(点の個数 - 線の本数 + ループの個数 = 1)を使ってもいいし、点の個数の帰納法でもいいし、背理法でもOK。
結局、グラフが木構造になることを使って、根からの枝の深さ(段数？レベル？)による漸化式を作っていることになっています。

　　 7月5日（月） 12:15:15　　　　23223

姉小路

最初は、５角形の対角線と辺（合計１０）から４選べばいいじゃないですか、と勢いに乗って此処に来てみましたが、はねられました。
そして、三角形や四角形を作っては行けないと気付いたのですが……。
その後、いろいろあって結局、
５つの島ＡＢＣＤＥのうちのＡから何本橋を架けるかと場合分けして解いたわけです。

算数の街　　 7月7日（水） 23:17:08　　 MAIL:pctakada@mail.goo.ne.jp HomePage:高田の呟き　　23224

過去問題一覧へ戻る

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

��裴��ʬ�β��