【数セミ】エレガントな解答をもとむ2【2016.11】 [無断転載禁止]©2ch.net

1132人目の素数さん2016/10/17(月) 20:05:12.65ID:wKo94p2r
過去スレ:
【数セミ】エレガントな解答をもとむ【2011.2】
http://rio2016.2ch.net/test/read.cgi/math/1295154182/

665とあるエレ解常連2017/11/25(土) 11:16:35.79ID:fXah2w3K
>>663-664
スレチですがエレ解常連の年齢層を考えるとずっぽしというw
しかも何だか観たくなります
番宣屋さんと呼ばせてもらいます

666とあるエレ解常連2017/11/25(土) 11:32:12.30ID:fXah2w3K
今月は締切が早いので注意ですよ

667132人目の素数さん2017/12/05(火) 20:29:12.67ID:E3mLmu88
■第10話【最終回】:「炎に消えた黄門様(八戸)」   12/06(水)

いよいよ最終回!
ゲストには、女優。松坂慶子さんが登場。役どころはなんと、黄門様の初恋相手!
また、劇中で松坂さんが作っている「南部姫毬」は、八戸に伝わる名産品の一つ。
平安時代に子どもたちの遊び道具として生まれた手毬を観賞用にしたもの。
糸を幾重にも巻き上げ、菱型や三角形を組み合わせた色鮮やかな模様を施している「南部毛毬」は、飾られた家の邪気を払いながら色あせていく、その家のお守り。
結婚や出産のお祝い品としても重宝されている。

最後に出演者全員で「贈ることば」を合唱?(「金八先生」1st シリーズの主題歌だったなぁ…)

http://www.bs-tbs.co.jp/mitokomon/index.html

(長い間ご愛読ありがとうございました。)

668とあるエレ解常連2017/12/06(水) 23:37:48.78ID:vkpD5gDG
2017年6月号から「問題のご感想も歓迎します」って注記されてるんですね
気付かなかった

669とあるエレ解常連2017/12/09(土) 09:20:25.61ID:p52Yk7RK
17年12月号の講評です

■出題1:レベル5(常連正解率90%)

やや易しめの良問。
隣り合う数字が連続する条件下では魔方陣が成立しないこと示す問題。
一見すると整数問題だが、グラフを考えることがエレガントに解く鍵となる。


■出題2:n=4,5はレベル2〜3(高校生正解率90%),n=6はレベル5(常連正解率90%)

n=4,5はとても易しい。問題なのはn=6でかなり悩まされた。
長時間悩んだ結果めでたく解答の道筋が立ち、
論理を整理しつつB5用紙に解答を清書していったところ
出来上がった答案は当初書くはずだった結論の逆を証明していた、という珍しい体験をした(←アホ)

670132人目の素数さん2017/12/10(日) 20:39:52.02ID:W/9Gj/R8
今月は早いでござるな。それでは…

■出題2 (と言っても蛇足だが)

・n≧3、奇数の場合の1例

単色点M(他のn-1点と同色の辺でつながる点)が1つある。
他の n-1点も、同色の辺でつながる対をなす。
M−A(2k-1)−A(2k)−M   色1
それ以外の辺はすべて違う色とする。

(多数の三角形が1点を共有するイメージ。)

・n≧8、偶数の場合の1例

上記の n-1点の例に、点Bと次の辺を追加する。
B−A1       色1
B−A3−A1    色2
B−A(k+2)−Ak  色k
B−A2−A(n-3)  色n-3
B−A4−A(n-2)  色n-2
これ以外の辺はすべて違う色とする。

671132人目の素数さん2017/12/12(火) 01:02:06.03ID:A7tAwVS8
>>670 (蛇足)の下の方は

k = 3,…,n-4 です。

我ながら、何ともセコい解だ。。。

で、本題の n=6 の方でござるが、
長時間悩んだが解答の道筋も立たず、でござった。
修行が足りぬ。。。

672とあるエレ解常連2017/12/13(水) 00:09:28.00ID:VzDBlmx4
>>671
> 長時間悩んだが解答の道筋も立たず、でござった。

n=6にエレガントな解法があるのか疑問です。
解答編を楽しみに待ちましょう。

>>670は凄いですねえ。よく一般のケースを考えようと思いましたね。
n≧8が簡単なんて想像してませんでしたよ。
n=6が特異なんですね。面白いです。

673132人目の素数さん2017/12/26(火) 04:59:12.17ID:YnF5Qwmi
問1が手がかりすら掴めん・・・
2011年8+9月号なんて手元にないよ(;´Д`)
内容知ってる人教えてもらえませんか

674132人目の素数さん2017/12/26(火) 05:15:38.50ID:WsGS/4bd
8月号と9月号かと思ったら8・9月号なんだな
https://www.nippyo.co.jp/shop/magazine/5621.html

電力不足だから8月の発売はしないことにしたのかな

675132人目の素数さん2017/12/27(水) 12:05:49.33ID:SBGZPQuO
>>674
そう。停電というよりこの頃は製紙工場が被災して、とにかく紙が足りなかった。実質9月号を飛ばしたことになる。
じゃあこの年はエレ解が11ヶ月分しか出なかったかというとそうではなくて、9月号分はネットで出題された。

676とあるエレ解常連2018/01/03(水) 22:30:31.82ID:ck/F8hfZ
>>673
> 問1が手がかりすら掴めん・・・

というコメントを読んで問2から手をつけましたが、(2)は無茶苦茶骨が折れます
これから問1を考えます。間に合うだろうか・・・

677132人目の素数さん2018/01/05(金) 07:23:13.83ID:wRuETOK7
1は3通りの方法で解いてみたが、互いに微妙に違う上に、正解とも異るという

678132人目の素数さん2018/01/05(金) 23:30:16.18ID:TIUiz4a3
>>673

数学セミナー,2011年 8/9月号,p.65-71 (2011)
岩沢宏和:「とっておきの」確率パズル
 (「確率パズルの迷宮」連載●第5回)

次の本の紹介記事

ピーター・ウィンクラー「とっておきの数学パズル」日本評論社(2011/July)
 坂井・岩沢・小副川(訳)  2592円

最後の問題27 = 本書の§4.9 = 出題1(n=500,k=1)

「同書に収められている解答は、なかなか秀逸な着想に基づき、難しい計算をいっさい使わずに、2/3が答えであることの証明を行なっている。
だが、その内容自体は、そう簡単ではなく、数ページに及ぶ長いものである。
やはりこの問題は相当に難しいようだ。」

がんばれ

679とあるエレ解常連2018/01/05(金) 23:46:53.71ID:CoqkNcgB
>>677
つまりクロスチェックには成功したと

680132人目の素数さん2018/01/05(金) 23:54:10.32ID:TIUiz4a3

681132人目の素数さん2018/01/15(月) 00:05:16.35ID:jq3xvZvh
2月号
数学基礎論の特集

「今は昔の竹内物語」に
竹内外史先生(1926/01/25〜2017/05/10)の思い出話があって、

6.辻先生が「竹の内君」と云った話(p.20)がある。

竹内端三先生(東大、1887/06/〜1945/08/07)のことだったようですが…

今の人ならきっと
竹之内脩先生(阪大・基礎工、函数解析)
と思うでしょうね。

682132人目の素数さん2018/01/15(月) 00:13:14.64ID:jq3xvZvh
>>681

「関 孝和の数学」共立出版(2008/June)
 174p.4104円
 http://www.kyoritsu-pub.co.jp/bookdetail/9784320018624
 
「函数解析」朝倉 近代数学講座7(2004/Apr)

「函数解析演習」朝倉 近代数学講座 演習編6(2008/Jan)

683とあるエレ解常連2018/01/17(水) 00:50:28.74ID:U4C1l9Ky
2018年1月号の講評です。

■出題1:レベル6〜7(常連正解率50〜70%)
[ノーヒントならレベル9〜10(常連正解率0〜10%)]

2n個の点からランダムにn個の区間を選ぶとき、
すべての区間と交わる『支配区間』がk個以上できる確率を問う問題。
親切にもヒント付きなので苦労しつつも解けた人が多いのではないでしょうか。
果たしてこの問題をノーヒントで解ける読者がいるんだろうかと思いますね。
あんな解法は100年かかっても思いつけない自信が私にはあります。
世の中には恐ろしく頭の良い人がいるものです。
良い問題、良い解法、凄い数学者、いろんな出会いのある良問でした。
エレガントな別解があるのか、解答編も楽しみです。


■出題2:レベル7〜8(常連正解率20〜40%)
[ノーヒントならレベル9〜10(常連正解率0〜5%)]

『強正則グラフ』というワードを知っている人はヒントにたどり着けたでしょう。
しかしヒント付きでもグラフの数え上げ、もっといえばuniquenessの証明は決して簡単ではないです。
そんなわけでレベルは7〜8程度と高めです。
ノーヒントなら限りなくレベル10(正解者0〜1人レベル)です。
特にn=9, n=10の一部のグラフを自力で探すのは無理ゲーではないか。
仮に探せたとしてもその唯一性を示すのがまた無理ゲー。
ヒント付きでも解答をきちんと記述するのは大変です。

一見とっつきやすそうな問題だけにノーヒントで突き進んだ人も多いと思いますが、
早めに情報収集して武装するのが吉という問題でした。
ノーヒントで解けた人は大いに自慢してよいと思います。
はっきりいってイチ数学ファンのレベルを超えていますから。
あるいは武装せずともエレガントに解けるんでしょうか?

----

2問とも
・オリジナリティがなく他所で情報を拾えてしまう
・ヒントがなければ超難問である
・ヒント付きでもそこそこの難問である
という共通項がありました。
ある意味悪問と言えなくもないですが、
両問とも我を忘れて熱中できる面白さがありました。
ゆっくり時間を取れる冬休みの宿題としては良いレベルだったと思います。

684132人目の素数さん2018/01/17(水) 03:13:28.16ID:K1wc0vuW
1月号
岩澤理論の特集 …… 代数的整数論の中心的なテーマ

(岩澤加群・セルマー群 と p進ζ関数・p進L関数 とが本質的に一致する?)

それはさて置き、出題1はのちのち、支配区間論における岩沢理論とでも呼ばれるでしょうか?

ジャステイツ氏の秀逸な着想に基づき、難しい計算を使わずに解けるらしいですが…  >>678

685とあるエレ解常連2018/01/17(水) 22:52:58.56ID:U4C1l9Ky
>>684
Justiczの論文の『秀逸な着想』は2ページにまとまってますね。
any k<nは"With slightly more care"で解けるとあります。
Justiczにとってのslightは私にとってのslightではないので困ります。

686132人目の素数さん2018/01/18(木) 00:24:15.71ID:3VMTZnuL
>>685

最後の4数(a〜d)もA(n-1),B(n-1),A(n),B(n)で表わしましょう。

本書の解は

支配区間が1つある ⇔ 最後の2つの区間(n-1とn)が「左側〜右側」

(初めのn-2の区間は無関係)というものですね。

これを slight 拡張すると、

支配区間がk個ある ⇔ 最後のk+1の区間が「左側〜右側」

(初めのn-k-1の区間は無関係)

となり、証明もほとんど同様にできそう。

・補足

定義により、A(j)とB(j)とが
「左側〜右側」 ⇔ 「右向き」あるいは「左向き」の区間が継続する。
「同じ側」 ⇔ 「右向き」と「左向き」が反転する。このとき区間1〜区間jはいずれも支配区間でなくなる。(頓死)

687132人目の素数さん2018/01/18(木) 00:31:10.14ID:3VMTZnuL
>>686 訂正

「支配区間」が(1つ以上)ある ⇔ 最後の2つの区間(n-1とn)が「左側〜右側」

「支配区間」がk個以上ある ⇔ 最後のk+1の区間(n-k〜n)が「左側〜右側」

688とあるエレ解常連2018/01/19(金) 00:56:53.35ID:keGyyLu4
>>686
> となり、証明もほとんど同様にできそう。

必要性をきっちり証明するのは自分には面倒でslight careでは済まなかったです。
細心のcareをしました。

>>687
> 「支配区間」がk個以上ある ⇔ 最後のk+1の区間(n-k〜n)が「左側〜右側」

これって正確ですか?

689132人目の素数さん2018/01/19(金) 01:53:54.91ID:4j7tlg3r
>>688

any k<n では…

なお、n-1個あるなら当然n個ありますが、これは「n-1個」と云うことにしました。

690とあるエレ解常連2018/01/20(土) 09:12:38.01ID:ViA3eIh+
2ケースあるので場合分けしなければいけないですよね。

691とあるエレ解常連2018/01/20(土) 09:51:20.82ID:fNIqamCN
先月は斥候>>673氏のコメントのおかげで早めに着手し、間に合いました。
今月はどうでしょうか?

692とあるエレ解常連2018/01/20(土) 09:53:22.69ID:fNIqamCN
斥候って「うかみ」とも読むんですね。
古代の間諜。敵の様子を探る者。「うかがい見る」の略であろう、ですって
https://kotobank.jp/word/%E6%96%A5%E5%80%99-34328

693132人目の素数さん2018/01/20(土) 14:29:54.41ID:BdHhmenA
・A(j)とB(j)が「同じ側」のとき、区間1〜区間jはいずれも支配区間でなくなる。(トン死)
・最後のk+1個の区間がすべて「左側〜右側」なら、最後のk個が支配区間になる。
ことを示せばOK

694とあるエレ解常連2018/01/20(土) 14:45:58.16ID:Ut198DTO
>>693
右側が左側より2個多いケースがあります。

695132人目の素数さん2018/01/21(日) 03:26:33.09ID:SUkk+U6n
>>694
 確かにそうですね。
 区間jが左向き B(j)> A(j)のケースでは、右側の未定数が左側より2個多く、
 次の区間の「同じ側」と「反対側」が入れ替わるので面倒ですね。
 というわけで、 「右向き」と「左向き」に戻しましょう^^

j=n-2 の例で考えると、a<b<c<d としたので
 A(n-2)< B(n-2):右向きのとき、b <{n,A(j)}< c
 A(n-2)> B(n-2):左向きのとき、a <{n,A(j)}< b
(j≦n-2)

このとき A(n-1)= b で、最後の区間nはつねに右向きになります。

・B(n-1)= a なら区間n-1 は左向き、区間nは右向き となります。向きが変わったので支配区間はありません。(頓死)

・B(n-1)= c または d なら区間n-1 〜 区間n で右向きが継続し、支配区間が(1つ以上)あります。

696132人目の素数さん2018/01/21(日) 04:32:57.87ID:SUkk+U6n
>>695 訂正スマソ

区間jが左向き B(j)< A(j)のケースでは…

697とあるエレ解常連2018/01/21(日) 10:37:00.26ID:JR12JicI
[何しゃべってるかわからん!という方はまず下の論文のp.7,8をお読みください]
https://www.maa.org/sites/default/files/images/upload_library/22/Ford/Joyce-Scheinerman881-889.pdf

>>695-696
そうですね。「右向き区間の連続」が必要十分です。
論文ではそのような書き方はされていないのでany kではちょっと悩みました。
まずここに気付けるかどうかが第一関門です。

十分性は明らかで必要性が問題ですね。
示すべきは「連続しなければ支配区間は高々k-1個となる」ことです。
これを証明できるかが第二関門です。

n-k番目から始めてn-k+a番目(0≦a≦k-1)で右向きの連続が途絶えたとすれば
[1] n-k+a 〜 n番目が支配区間となりうるのは高々k-1-a個
[2] 1 〜 n-k+a-1 番目は支配区間にならない
が成り立ちます。[1]と[2]の両方を、
■case1:左側と右側の点が同数の場合
■case2:左側よりも右側の方が2点多い場合
の2ケースで示せばOKということになります。
証明は論文の方法と同様なので"With slightly more care"なんでしょうね。

698とあるエレ解常連2018/01/21(日) 11:00:20.50ID:JR12JicI
>>697の出題は岩沢先生ですが補足にあるヒントの書き方は絶妙だなと思いました。
私のようなチキンはこの補足を読んですぐに「自力では無理」と悟りました(笑)
結果として論文を読んでもなお難しいと感じたので、ネット情報で武装したのは正解でした。
論文の方法を自力で編み出すのは私の能力の遥か遠方を飛び越えます。

>>677氏は自力で3通りの方法を試したようです。
結果が不正解だったにせよ3通りも編み出すのは凄いと思いますね。
>>677
> 1は3通りの方法で解いてみたが、互いに微妙に違う上に、正解とも異るという

3ヶ月後の解答編が楽しみです。
1)論文にあるエレガントな方法
2)論文にある積分の方法(この方針で解けるのか私は知りません)
2通り以上の解答を期待。

699132人目の素数さん2018/01/22(月) 01:15:14.15ID:EFMpeTLH
>>697

逆に辿る方が簡単?
for any k<n,
最後のk+1区間(n-k〜n)が右向き、区間n-k-1が左向きとすると
最後のk区間(n-k+1 〜 n)が支配区間で、初めのn-k区間(1〜n-k)は支配区間でない。
(区間n-k-1 と区間n-kは重ならない。)

>>687
区間j-1 と区間j が同じ向き ⇔ A(j),B(j)が反対側
区間j-1 と区間j が逆向き  ⇔ A(j),B(j)が同じ側
なので、
最後のk+1区間(n-k〜n)が同じ向き ⇔ 最後のk区間(n-k+1 〜n)でA(j)とB(j)が反対側

(区間nが右向きということを使えば、まだ改良できるけど…)

700とあるエレ解常連2018/01/22(月) 22:35:35.85ID:+Yy6qakN
>>699
なるほど・・
「向きが左(右)へ変わったら、その左向き(右向き)区間と、そこまでに連続した右(左)区間たちはすべて支配区間でない」
これは直感的に理解できますね。これを押さえれば必要条件も見通しよく書けそうです。
n個の区間を 「向きが連続した区間列」の列 と捉え、最後の区間が左向きでないことに注意すれば、必要十分条件は容易に導けそうです。

難問が易問に変わりました。
それもこれもエレガントな手法のおかげです。
組み合わせ論おそるべし。

701132人目の素数さん2018/01/24(水) 01:26:42.65ID:9ooAixL8
>700
支配区間がk個以上あるかどうかは、最後のk+1区間の向きで決まり、それより前の向きに依らない。
k+1区間のすべてが支配区間になる確率の問題に帰着するから、難しい計算を使わずに解ける。
これはnに依らない。(解決)

それはそうと、今月の問題もナニだ・・・・

702とあるエレ解常連2018/01/26(金) 00:56:37.32ID:y7mLXSVj
>>701
> それはそうと、今月の問題もナニだ・・・・

そうですかナニですか・・
出題2の問題2で手が止まってます。
出題1は問題文だけは読みましたが、難しそうなので後回しに・・

703132人目の素数さん2018/01/26(金) 03:31:06.37ID:dGgp4j0R
>>702

出題1は、n+3 を n で表わして、出てきた末項たちをまとめると、
末項 vs 総和、つまり「末項勝負」になる?

(1)の(1+x)^n はΣの隣項比から末項率が押さえられるか?
(2)の(1+x+xx)^n は準・末項がズラズラ… 一体どうするんでしょうね?

もちろん、当てにはなりませんが。

704とあるエレ解常連2018/01/28(日) 10:20:08.29ID:JN2hGa2G
>>703
> 末項 vs 総和、つまり「末項勝負」になる?

朝方に読んで吹き出しましたわ

705とあるエレ解常連2018/02/10(土) 10:57:54.92ID:puSUR9wA
2018年2月号の講評です。
今月は締め切りが9日でした。
問題の難易度が高く間に合わなかった方も多かったのでは。

■出題1:問題1はレベル6(常連正解率70〜80%)、問題2はレベル8(常連正解率20%)

徳重典英先生の出題。
n個の整数x_k∈{0,1}[{0,1,2}]の和がfloor(n/3)[floor(2n/3)]以下となる組み合わせの総数がc^n(c<2)[d^n(d<3]で押さえられるかを問う問題。
問題文はsimpleですが、simpleな問題は往々にして難しいという典型例。
良問ですが良く知られた有名問題の匂いがします。

上のレベルは正攻法で解いた場合です。
おそらくエレガントな解答が用意されています。
正攻法では知識と多少面倒な計算が必要です。
問題文には『根拠を示して答えよ』とあります。
これは裏を返せば『厳密でなくてもよい』という意味かもしれません。
正攻法で厳密な議論を展開するのはなかなか面倒です。

阿呆のコメントはひとまずこれくらいに。
ぬるぽさんか早解きさんか水戸黄門さんか、どなたかのコメントを待って議論したいと思います。


■出題2:問題1はレベル2〜3(高校生正解率80%)、問題2はレベル7〜8(常連正解率20〜30%)

丹下基生先生の出題。
凸多角形の隣接3点を使った等積変形(I-変形と名付けられている)で凸性を保ちながら正多角形にできるかを問う問題。
n角形(n≧4)では対角線を底辺とするI-変形のみが許される。
こちらも良問と言ってよいと思います。

ウォーミングアップ問題、問題1は瞬殺ですが、問題2の凸5角形のケースは簡単ではないです。
スジさえ通っていればマルがもらえるかもしれませんが、『どんな点配置でもこの変形が可能か?』を厳密に考えると結構大変です。
それを解答として記述するのもまた大変。


先月に続き、今月も本誌名物コーナー『エレガントな解答をもとむ』の醍醐味が存分に味わえる美味しい月でした。
2問とも良問なのはうれしいですね。
5chで愚問悪問排除運動を推し進めた成果が出始めているのかw

706とあるエレ解常連2018/02/10(土) 21:44:31.53ID:puSUR9wA
3月号が届いてしまった

707132人目の素数さん2018/02/13(火) 19:12:05.80ID:ZOqrSE8B
>>670

・nが奇数のとき

正n角形の任意の2頂点p,qに対して、それから等距離な頂点がちょうど1つある。
 ↓
辺と対角線を長さごとに彩色すれば、題意を満たす。

美しく、かつエレガントな結果です。(なかなか出て来ない…)

・n≧8、偶数の場合

これも おkでしたね^^(清水氏)

708132人目の素数さん2018/02/14(水) 17:03:04.49ID:/bHsoXtp
2018年3月号の講評です。
(えっ!まだ出たばかりぢゃ?)

といっても NOTE の、ですが。
(なーんだ)

■長岡京の公式

1+2+……+k = T_k
とおくと「図」から
k = T_k - T_{k-1},
kk = T_k + T_{k-1}
辺々掛けてたす。
Σ[k=1,n] k^3 = Σ[k=1,n](T_k - T_{k-1})(T_k + T_{k
-1})
= Σ[k=1,n]((T_k)^2 -(T_{k-1})^2)
=(T_n)^2,   (← T_0=0)

なんともエレガント。
クスコ副将軍の墳墓は立方体を重ねた形にしてほしい、という程でござる。

■宇都宮の不等式

単調減少な正数列 x_1 > x_2 > …… > x_n > 0 について
Σ[j=1,n](x_j)^x_{j-1}> Σ[k=1,n](x_j)^x_{j+1}
 ただし、x_0 = x_n,x_{n+1}= x_1 とする。

これも美しい不等式。
名著「不等式への招待」の著者も今や古希でござる。

709とあるエレ解常連2018/02/15(木) 00:42:18.78ID:83qwjldB
>>707
> ・n≧8、偶数の場合
>
> これも おkでしたね^^(清水氏)

そう簡単に思いつけないと思うんですけどね。
>>670で気付かれていたのはさすがの一言です。

解答編>>669
> n=4,5はとても易しい。問題なのはn=6でかなり悩まされた。
> 長時間悩んだ結果めでたく解答の道筋が立ち、
> 論理を整理しつつB5用紙に解答を清書していったところ
> 出来上がった答案は当初書くはずだった結論の逆を証明していた、という珍しい体験をした(←アホ)

と書きましたが、まったく同じことを答案にコメントした人が居たみたいですね。
私のドッペルゲンガーかと。ビックリしました。

710とあるエレ解常連2018/02/15(木) 00:54:15.67ID:83qwjldB
>>709に補足。

本誌に『苦労の時間は至福のときだったのではないでしょうか?』とありますが、
さすがにこの苦労は至福とはいえなかったですね・・w
方針がまったく定まらず、題意を満たすグラフがあるのかないのか分からず。
いよいよどうしようもなくなり非存在をシラミツブシで調べることにしたという経緯なわけで。
絵に描いたようなエレファントロードです。
オレは才能ないんだなーと悲しみを抱えつつ虱を潰してました。
そして最後には『グラフあるんかーい!』でずっこけて大団円というオチ。

711132人目の素数さん2018/02/17(土) 15:29:44.09ID:ut0k1Bb7
今月は両方解けそうだ。エレガントかどうかは別として。

712とあるエレ解常連2018/02/17(土) 16:02:19.94ID:qinAy9D+
>>711
> 今月は両方解けそうだ。エレガントかどうかは別として。

斥候ご苦労!

今月はゆったりできそうですね

713132人目の素数さん2018/02/18(日) 03:25:45.94ID:e4NqLH6n
2月号 
■出題1
問題(1)
 x_1 + x_2 + …… + x_n = k となる解(x_1,x_2,……,x_n)の個数はC[n,k]
求めるものは
 f_n = Σ(k=0,m)C(n,k),   m =[n/3]
ところで、k < n/3 のとき
 C(n,k)={(k+1)/(n-k)}C(n,k+1)<(1/2)C(n,k+1)
 < … <(1/2)^(m-k)C(n,m).

 f_n = Σ(k=0,m)C(n,k)
 < C(n,m)(1 + 1/2 + 1/4 + 1/8 + …)
 < C(n,m)* 2

〔補題〕
n≧2 のとき C(n,m)≦(4/9)c^n,
ただし、c = 3/4^(1/3)= 1.889881575

(略証)
 C(2,0)= 1 < 4^(1/3)=(4/9)c^2,
 C(3,1)= 3 =(4/9)c^3,
 C(4,1)= 4 < 9/4^(1/3)=(4/9)c^4,
これと
 C(n+3,m+1)={(n+3)(n+2)(n+1)/[(m+1)(n-m+2)(n-m+1)]}C(n,m)
 <(27/4)C(n,m)
から出る。(終)

∴ f_n < c^n,

714とあるエレ解常連2018/02/18(日) 10:45:54.76ID:2pXRmNxD
>>713
> C(n+3,m+1) = {(n+3)(n+2)(n+1)/[(m+1)(n-m+2)(n-m+1)]}C(n,m) < (27/4)C(n,m)

この漸化式で帰納法ですか。
さらっと書いてますけど思い付かんでしょうねフツーはw

微妙な差はありますが、
f_n<A x C(n,m)<B x c^n
というステップを踏むところは私と同じです
やはりこれが本筋ですね

715132人目の素数さん2018/02/20(火) 21:22:33.93ID:Sc+VCWMp
2番って漸化式からすぐに言えるんとちゃんのん?

新着レスの表示
レスを投稿する