X
トップページ⇒数学
1002コメント389KB
【数セミ】エレガントな解答をもとむ2【2016．11】 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
0720１３２人目の素数さん
垢版 |
2018/02/22(木) 13:17:42.88ID:e0oVX/cg
東大舐めすぎ
0722１３２人目の素数さん
垢版 |
2018/02/25(日) 06:21:12.27ID:gGaVEUAO
解くべき問題が無くなって暇な人に…

〔掛谷の定理〕
正係数のn次多項式
　F（x）= a_0･x^n + a_1･x^{n-1} ＋ …… + a_{n-1｝･x + a_n,
について
・a_0 > a_1 > a_2 > …… > a_{n-1｝> a_n > 0　ならば
　F（x）= 0 の解の絶対値は１より小さい。
・0 < a_0 < a_1 < a_2 < …… < a_{n-1｝< a_n　ならば
　F（x）= 0 の解の絶対値は１より大きい。
0723１３２人目の素数さん
垢版 |
2018/02/27(火) 03:14:44.71ID:M/Cc1/YM
(1)
n次方程式 F(x）= 0 の根｛r_k｝がすべて実数のとき、
　F(x）が極値・停留値をとる点b｛F '(x）= 0 の実数解｝は次をみたす。
　r_min ≦ b ≦ r_max

(2)
n次多項式 F(x）が停留値をとる点β｛F '(x）= 0 の解｝は、
　F(x）= 0 のすべての根を含む凸領域内にある。

例）　すべて単根｛α_k｝のときは
　β = Σ[k=1,n］ｔ_k α_k
　重み　t_k = |β-α_k|＾(-2)／{Σ[ｊ=1,n］｜β-α_ｊ|＾(-2)}
0724１３２人目の素数さん
垢版 |
2018/03/01(木) 16:28:38.74ID:utcJHdiE
f(x) が下に凸であるとは、a≠b、0<λ<1 に対して
　(1-λ)f(a) + λf(b) ＞ f((1-λ)a+λb)
が成り立つこととする。

〔補題〕
f(x）が 0≦x≦1 で下に凸ならば

1）　（1/n）Σ[k=1，n］f(k/(n+1)）＞｛1/(n-1)｝Σ[k=1，n-1］f(k/n),

2）　｛1/(n+1)｝Σ[k=0，n］f(k/n）＞｛1/(n+2)｝Σ[k=0，n+1］f(k/(n+1)),
0725１３２人目の素数さん
垢版 |
2018/03/02(金) 05:10:33.95ID:IyAEI4K5
f(x) が下に凸であるとは、a≠b、0<λ<1 に対して
　(1-λ)f(a) + λf(b) ＞ f((1-λ)a+λb)
が成り立つこととする。

〔Popoviciuの不等式〕
f(x) が下に凸ならば、 (a+b+c)/3 = m に対して、
f(a) + f(b) + f(c) + 3f(m) ≧ 2f((a+b)/2) + 2f((a+c)/2) + 2f((b+c)/2),

佐藤淳郎（訳）「美しい不等式の世界」 朝倉書店(2013) p.41 演習問題1.89
0726とあるエレ解常連
垢版 |
2018/03/03(土) 00:03:14.63ID:qWbxhH7e
みなさんが簡単だの受験レベルだの言うので全く手をつけてません
一身上の都合により明日1日で終わらせないといけません
これで簡単でなかったら激オコですよ
0727１３２人目の素数さん
垢版 |
2018/03/03(土) 05:56:22.65ID:hUH2ieOC
>>669-672

2017年12月号　■出題2

n=6 の解答を残しておく。

A1-A2-A3-A1
A1-B1
A2-B2
A3-B3
以上を色1で
B2-A1-B3-B1　　色2
B3-A2-B1-B2　　色3
B1-A3-B2-B3　　色4

3回（120ﾟ）対称らしい
0729とあるエレ解常連
垢版 |
2018/03/04(日) 02:58:14.77ID:FuxS60Ot
>>726
> 一身上の都合により明日1日で終わらせないといけません
> これで簡単でなかったら激オコですよ

激オコしかけましたがなんとか大丈夫でした（笑

よい週末を。
0730とあるエレ解常連
垢版 |
2018/03/10(土) 09:51:13.14ID:L1Ot5zPy
>>683
> ■出題１：レベル6〜7（常連正解率50〜70％）
> ［ノーヒントならレベル9〜10（常連正解率0〜10％）］
>
> 2n個の点からランダムにn個の区間を選ぶとき、
> すべての区間と交わる『支配区間』がk個以上できる確率を問う問題。
>
>
> ■出題２：レベル7〜8（常連正解率20〜40％）
> ［ノーヒントならレベル9〜10（常連正解率0〜5％）］
>
> 『強正則グラフ』

2問ともノーヒントでレベル9〜10という超難問だった1月号の解答がもうすぐ来ます。
待ち遠しいですね。果たして何人解けているのか。
特に出題２をノーヒントで解くのは、とあるエレ解常連レベルでは3ヶ月時間をもらっても無理です。
両問ともヒントを使ったかどうかは解き方を見ればすぐに分かります。
ヒントなしで解いた人間がいたら本スレで崇め奉りたいと思ってます。
0731１３２人目の素数さん
垢版 |
2018/03/10(土) 22:06:03.45ID:z9TqCAdc
大数3月号の宿題はどうですか
0732１３２人目の素数さん
垢版 |
2018/03/11(日) 01:18:05.30ID:WtEF6UI/
>>722
〔掛谷の定理〕
　不等式スレ９.453 459 465

>>724
　不等式スレ９.463

>>725
　〔Popoviciuの不等式〕

(i) a, b ≦ m ≦ c のとき
　f(m) + f((m+c)/2) ≧ f((a+c)/2) + f((b+c)/2),
(ii) a ≦ m ≦ b，c のとき
　f((a+m)/2) + f(m) ≧ f((a+b)/2) + f((a+c)/2),
は次から出る。

〔補題471〕
f(x) は m，nを含む区間で下に凸
m+d，n-d が m と n の中間にあるとき
　f(m) + f(n) ＞ f(m+d) + f(n-d)

　不等式スレ９.465 471

>>729
激オコしなかったんですか^^
0733とあるエレ解常連
垢版 |
2018/03/14(水) 00:23:42.30ID:sLl67O8h
4月号の出題1は一松先生、またの名を「エレガントな解答をもとむコーナーの生ける伝説」です。
ぱっと見、難易度がぜんぜん掴めません。
不等式スレの住人に斥候を頼みたいところです。

出題2は岡本吉央先生。
いつも通りエレガントな問題。安心安定のハイクオリティ。
たぶん相当な難問です。（１）、（２）、（３）までありますよ。気合入れないといかんです。
早めに取り掛かるのが吉。私のように組み合わせ論が苦手な人はなおさらです。

組み合わせ論も不等式も苦手な私は今月覚悟して取り組みます
0734１３２人目の素数さん
垢版 |
2018/03/14(水) 05:33:58.00ID:ovqCjVLT
2は気づけばなーんだという問題。(3)まで含めてB5の半分程度で行けるかな。
でも良問だと思う。
0735とあるエレ解常連
垢版 |
2018/03/14(水) 23:20:12.94ID:sLl67O8h
>>734
は、早い・・・もう見通したんですか。
心強いお言葉ですねぇ

出題1もよろしくです。
コメントを聞いてから春旅行のスケジュールを立てますｗ
0736１３２人目の素数さん
垢版 |
2018/03/15(木) 05:17:24.48ID:HCGObM3W
>>733 >>735

4月号　出題１は…
（1) 通分して多項式で考えるのがシュアーか？
（2) も同様。Ω条件を消したいので○○変換してみる？
（3) 因数分解できるが、対称性は自発的に破れる？
どれも当てにならぬが…
0738とあるエレ解常連
垢版 |
2018/03/17(土) 14:48:21.44ID:gnHvefDK
自分を信用してないので簡単と言われた出題2に早くも手を付たのですがw、確かに簡単というか、簡単すぎるような。
穴がないかチェックしよう。。
0739とあるエレ解常連
垢版 |
2018/03/17(土) 14:50:28.55ID:gnHvefDK
岡本先生は2年前の赤青問題以来、丸くなってしまったのだろうか。。
あの問題は歴史に残る名作でありました
0741とあるエレ解常連
垢版 |
2018/03/26(月) 01:41:33.59ID:sX2IDXHU
>>736
> どれも当てにならぬが…

どれも解いた人にしか書けないコメントですがｗ
不等式スレの住人には屁の河童かもしれませんね。
0744とあるエレ解常連
垢版 |
2018/04/01(日) 22:28:39.21ID:3+dpOogJ
>>734
> 2は気づけばなーんだという問題。(3)まで含めてB5の半分程度で行けるかな。

コレそんなに簡単ですかね・・？
0746１３２人目の素数さん
垢版 |
2018/04/04(水) 17:18:10.44ID:68ibS0+d
さっき気がついたけど、今月から締切日必着じゃなくて消印有効になったんだな。
0757とあるエレ解常連
垢版 |
2018/04/08(日) 11:43:58.38ID:EywXlEJ+
>>734, 745
感嘆。やっと思いつきましたよエレガントな解法を。
これを一瞬で思いつけるのは頭良すぎですよ
0759１３２人目の素数さん
垢版 |
2018/04/11(水) 00:12:32.15ID:P2CDN9E5
エレガントな解答を思いつかなかった人もいるので
おそえて下さい
0761１３２人目の素数さん
垢版 |
2018/04/11(水) 05:43:52.72ID:upSeUnLx
北か東にしか進めない格子上を(1,1)から(m+1,n)まで移動する経路数と同じでしょ？
0762１３２人目の素数さん
垢版 |
2018/04/11(水) 10:29:54.02ID:P2CDN9E5
(1)はいいから(2)(3)ぷりーず
0764１３２人目の素数さん
垢版 |
2018/04/11(水) 10:57:37.30ID:ccYYEMFW
(2)は半分より右の経路を左端まで移動して、左半分の経路分を引き算する。これがf2。
(3)は3分割して同じことをやる。
0766１３２人目の素数さん
垢版 |
2018/04/11(水) 13:46:48.14ID:vimZpIRa
(1,1)から(2m+1,n)までの経路で、(i,j)から東に進む場合にf(i)=jと定義。
1<=i<=mにおいて
f1(i)=f(i)
f2(i)=f1(i)+f(i+m)-f(m)
と置くと、f1, f2の組み合わせとf（つまり経路）が1対1で対応する。
0767１３２人目の素数さん
垢版 |
2018/04/11(水) 15:55:54.01ID:ixEOJ+I8
>>766
　
f2(i) - f1(i) = f(i+m) - f(m) が 1≦i≦m で単調非減少の経路はそうですね。

非負でOKなら、部分的に減少する経路も有り得る希ガス
0768１３２人目の素数さん
垢版 |
2018/04/11(水) 16:06:35.04ID:ixEOJ+I8
(1) は >>761 のとおり

C(m+n-1，m) = C(m+n-1，n-1)
= Π[j=1，m] Π[k=1，n-1] (j+k)/(j+k-1)
= Π[(j，k)∈B1] (j+k)/(j+k-1)
ここに、B1 = {(j，k) | 1≦j≦m，1≦k≦n-1} は m×(n-1) の長方形ブロック

そだね〜
0770とあるエレ解常連
垢版 |
2018/04/12(木) 02:58:02.43ID:RC/XWzxB
>>766
> (1,1)から(2m+1,n)までの経路で、(i,j)から東に進む場合にf(i)=jと定義。
> 1<=i<=mにおいて
> f1(i)=f(i)
> f2(i)=f1(i)+f(i+m)-f(m)
> と置くと、f1, f2の組み合わせとf（つまり経路）が1対1で対応する。

たとえばf(1)<n, f(m)=nなる経路fを取るとf2(i)=f1(i)に限定されます。
任意のiに対しf(i+m)=f(m)=nなので。
しかし実際には別のf2が取れます。
読み違っていたらご指摘ください。

それにしてもいい問題ですねこれ。
翌月号が届くまで暇しなさそうだ。
0772１３２人目の素数さん
垢版 |
2018/04/12(木) 12:34:37.16ID:TgaFEakF
>>768

は ブロックB1 に収まるヤング図形を数えたのでござるな。

では、L個の関数 f_1 ≦ f_2 ≦ … ≦ f_L に対しては
ブロックBに収まる３次元ヤング図形の数にならぬか？

Π[i=1，L] Π[j=1，m] Π[k=1，n-1] (i+j+k-1)/(i+j+k-2)
= Π[ (i，j，k) ∈ B] (i+j+k-1)/(i+j+k-2),

ここに、B =｛ (i，j，k) | 1≦i≦L，1≦j≦m，1≦k≦n-1｝は L×m×(n-1) の直方体ブロック
0785とあるエレ解常連
垢版 |
2018/04/14(土) 12:05:31.93ID:OmmA56DO
2018年4月号の講評です。
今月は良質で軽めの問題が1問、エレガントな難問が1問です。

■出題1：レベル4〜5 （常連正解率90％）

生ける伝説一松先生の出題。
変数を正としてf(a,b,c;t)≡(a^2+b^2+c^2)-t(ab+bc+ca)+9(t-1)abc/(a+b+c)が
すべてのa,b,cに対して≧0、あるいは≦0となるtの範囲を考えさせる問題。
≦0のときはa,b,cが三角形成立条件を満たすように動く。

一見して数オリの練習問題のようですが実際にそんな感じです。
必要性と十分性をきちんと押さえて議論する必要があり基礎力が問われます。
大学入学を控えた18歳がエレ解の世界へ足を踏み入れる導入問題として
4月号に似つかわしい優れた問題と言えるでしょう。


■出題2：レベル8〜？（常連正解率15％〜？）

単調非減少な関数f:{1,2,3,...,m}→{1,2,3,...,n}の総数を求める岡本先生の問題。
小問(1)は上記のとおり。(2)は任意のiでf1(i)≦f2(i)を満たす組の総数を求める。
(3)はf1(i)≦f2(i)≦f3(i)を満たす3つ組の総数を求める。

シンプルで難しく、しかし美しい組み合わせ論の問題です。
組み合わせ論はエレガントな問題の宝庫ですね。
私は苦手としているのであんまり出さないでほしいのですがｗ
高校生以下でもチャレンジできますので題材としてはうってつけでしょう。
組み合わせ論はアイデア一発でエレガントな解答が書けることが多いです。
逆にアイデアが浮かばなければ路頭に迷いまくるという困った性質を持ちます。

(1)は重複組み合わせを考えれば終わりなので簡単です。
問題は(2)です。あるf1に対してf2が何通りあるか(*)は論文が出ています。
しかし(f1,f2)の組み合わせの総数については参考文献が見当たりません。
(*)より簡単なのだろうと思いますがエレ解レベルの数学ファンには難しいです。
なんてあたかも私がエレ解ファンの代表かのように語ってますが、
組み合わせ論は『こう解けば簡単じゃん、バカなの？』というコメントで
落ち込まされることが経験上多いので怖いですｗ
0786１３２人目の素数さん
垢版 |
2018/04/15(日) 12:12:42.08ID:ZO3/JPf/
2018年4月号

■出題１

〔シューア不等式〕の拡張版
　p,q,r≧0 かつ (a,b,c) と (p,q,r) が同順または逆順のとき
　F(a,b,c) = p(a-b)(a-c) + q(b-c)(b-a) + r(c-a)(c-b) ≧ 0
をまづ示しましょう。
　bとqがそれぞれ中間にあるとして、p-q+r≧0, (a-b)(b-c)≧0,
　F(a,b,c) = p(a-b)^2 + (p-q+r)(a-b)(b-c) + r(b-c)^2 ≧ 0,

(1)
　(a+b+c) f(a,b,c；2) = a(a-b)(a-c) + b(b-c)(b-a) + c(c-a)(c-b) ≧ 0,
　t≦2　⇒　f(a,b,c；t) ≧ 0,
　t>2 に対して f(a,b,c；t) < 0 となるような (a,b,c) の例を探す。

(2)
(a,b,c)∈△ のとき
　(a+b+c) f(a,b,c；3) = -(b+c-a)(a-b)(a-c) -(c+a-b)(b-c)(b-a) -(a+b-c)(c-a)(c-b) ≦ 0,
　t≧3　⇒　f(a,b,c；t) ≦ 0,
　0<t<3 に対して f(a,b,c；t) >0 となるような (a,b,c)∈△ の例を探す。

(3)
　t_3 = (t_1 + t_2)/2 = 5/2,
　(a+b+c) f(a,b,c；5/2) = (2a-b-c)(2b-c-a)(2c-a-b)/2 = 0,
　∴ (a,b,c) は等間隔に並ぶ。
　これは (a,b,c) = (1,3,5) のような、△をなさない例も含む。
0787とあるエレ解常連
垢版 |
2018/04/15(日) 15:25:27.83ID:y2agdfqD
>>772
> では、L個の関数 f_1 ≦ f_2 ≦ … ≦ f_L に対しては
> ブロックBに収まる３次元ヤング図形の数にならぬか？

3軸の斜交格子を使って非交差経路の組を数え上げようというわけですか。
f1,f2,f3の経路のスタート、ゴールはある軸方向に1ずつ離れていると。
それは3次元ヤング図形に対応すると。
0788とあるエレ解常連
垢版 |
2018/04/15(日) 15:50:24.38ID:y2agdfqD
>>786
統一された手法で解けるんですね。エレガントです。

> t≧3　⇒　f(a,b,c；t) ≦ 0,

すべてのt≧3で成り立つのは自明ですかね？
0789１３２人目の素数さん
垢版 |
2018/04/15(日) 21:32:28.34ID:ZO3/JPf/
>>788

tの1次式で、係数が負。
（a,b,cを固定すれば）tについて単調減少。
問題文にもあった希ガス…
0790とあるエレ解常連
垢版 |
2018/04/15(日) 22:35:07.95ID:dInGck+5
>>789
あのヒントというかお膳立ては必要ない気もしたんですが。
一松センセのあらゆる読者への配慮みたいなものを感じます
0792１３２人目の素数さん
垢版 |
2018/04/16(月) 22:48:00.94ID:I9VNB52o
>>789

正三角形を除き、tの係数は負の定数。
tを増大すれば、とこかで負になる。

(a,b,c)∈△ についての上限が t_2 = 3
非△ついては上限なさそう。
(a+1+1) f(a,1,1；ｔ) = (a-1)^2 (a+4-2t)
零点 t = (a+4)/2.
0793１３２人目の素数さん
垢版 |
2018/04/20(金) 14:08:29.21ID:W4yzbmXa
数オリとエレガントな解答をもとむって、どちらの方が難しいの？
0794１３２人目の素数さん
垢版 |
2018/04/20(金) 23:58:07.64ID:W4yzbmXa
エレガントな解答をもとむと大学へのの宿題となら、どちらの方が難しいのでしょうか？
0796１３２人目の素数さん
垢版 |
2018/04/21(土) 19:41:50.90ID:LCJcAykv
近畿大学数学コンテストなんて簡単だよ
エレガントな解答をもとむが一番難しいわ
0797１３２人目の素数さん
垢版 |
2018/04/21(土) 19:55:29.52ID:LCJcAykv
難易度：エレガントな解答をもとむ>数オリ>宿題>近畿大学数学コンテスト>学コン>東大理系数学>センター数学
0809とあるエレ解常連
垢版 |
2018/05/12(土) 00:32:12.74ID:h4NJI8KX
18年5月号の講評です。

■出題1：レベル2〜3（数学好きの高校生正解率85％）

整数係数n次多項式Pの0≦x≦1における最大値Max(|P|)が
1/sqrt(LCM(1,...,2n+1))以上であることを示す問題。

2n+1はどこから出てくるのでしょうか？
このヒントでピンと来なければ超難問、ピンと来れば超易問。
常連ソルバーには物足りないでしょうが、LCMとの意外な繋がりが美しい良問。


■出題2：レベル1〜2（中学受験生正解率50％）

『チェスのナイトが矩形盤のマスを一度ずつ通り元に戻る経路（ナイトツアー）』
が存在しないことを示す問題。

(1)は『ダメなマスの集合Sが存在⇒ナイトツアーが存在しない』を示す問題。
さすがに小学生には無理か？？しかし大した論証ではないと思います。
(2)は大した試行錯誤もせず見つかります。

5月号は新入生歓迎号なのは分かりますがさすがに簡単過ぎではないかと。
出題1はともかく出題2は明らかにヒント過多。
"ダメなマスの集合S"の存在をうまく隠せれば良問になっただけに残念です。
Sを使ったエレガントな解法を自分で見つけたかった人は多かったはず。
0810１３２人目の素数さん
垢版 |
2018/05/12(土) 02:26:32.31ID:ERQyPxVg
■出題１

　{P(x)}^2 を展開したとき、x^{奇数｝の係数は偶数だから
　√(2/L）以上であることを示すのかとオモタ。

■出題２

(2)　4×n は 2列ジグザグのSが作れるので存在しない

6×6，8×8，10×10 には存在するらしい。

http://www.geocities.jp/m_hiroi/puzzle/index.html
→　パズルの解法　→　・チェスのパズル　→　騎士の周遊

ワーンスドロフの規則については

秋山 仁・中村義作 共著「ゲームにひそむ数理」森北出版 (1998/Apr) 2376円
の p.72
http://www.morikita.co.jp/books/book/117
0811とあるエレ解常連
垢版 |
2018/05/12(土) 09:53:53.76ID:h4NJI8KX
>>810
リンク先のページではダメ集合Sへの言及はないですね。
ダメ集合Sの効率的な探索法は？という問いはプログラミング的に面白いかもしれない。
0813１３２人目の素数さん
垢版 |
2018/05/13(日) 02:42:55.47ID:dQIRZ6zE
>>810

多項式P(x) の一例

・nが奇数のとき
　P(x) = {x(1-x)}^{(n-1)/2}･(2x-1),
　Max{ |P(x)| } = (1/2)^(n-1) √{(n-1)^(n-1) / (n^n)}，　x = 1/2 ± 1/(2√n),

・nが偶数（n≧4)のとき
　P(x) = {x(1-x)}^(n/2 -1)･(2x-1)^2,
　Max{ P(x) }= (1/2)^(n-3) √{(n-2)^(n-2) / (n^n)}，　x = 1/2 ± 1/√(2n),

・nが偶数(n≦4)のとき
　P(x) = {x(1-x)}^(n/2),
　Max{ P(x) } = (1/2)^n，　x = 1/2,

どれも √(2/L) よりかなり大きい…orz

分かスレ443 - 004

>>812

8×8 （チェス盤）はオイラーの時代からあったらしい…
0814とあるエレ解常連
垢版 |
2018/05/13(日) 11:07:41.37ID:3y7zv360
>>813
集合Sが探索効率を上げるんですかね
未解決部分があるようですが最近の研究はどうなっているのか
0815とあるエレ解常連
垢版 |
2018/05/13(日) 11:10:56.05ID:3y7zv360
>>813
多項式の問題すんなりイケました？
実のところそのx(1-x)の形に捕らわれて時間を食いましたわ
0817とあるエレ解常連
垢版 |
2018/05/13(日) 11:33:17.09ID:3y7zv360
どうもチェビシェフを使って振れ幅を最小にできるようで
ちゃんと読んでませんけど
0818とあるエレ解常連
垢版 |
2018/05/13(日) 11:38:39.87ID:3y7zv360
>>816
積分以外の別解法でmax≧1/f≧1/sqrtLCMと押さえられるんでしょうか？
本問のエレガント賞は積分使わなかった人かもw
0819１３２人目の素数さん
垢版 |
2018/05/13(日) 20:57:47.74ID:dQIRZ6zE
>>715-719

3月号の出題2

定義
　"number of permutations of n elements with no fixed points"
に基づいて
　d_n = (n-1)(d_{n-1} + d_{n-2}),
を出すのに手間取った。これから
　d_n - n･d_{n-1} = - (d_{n-1} - (n-1)･d_{n-2})
　= ……
　= (-1)^n (d_2 - 2･d_1)
　= (-1)^n,
これを3回使うと「エレガントな漸化式」
　d_n = n(n-1)(n-2) d_{n-3} + (-1)^n (n-1)^2,
が出る。

http://oeis.org/A000166

なお、6月号の締切は　6月8日（消印）
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況