【数セミ】エレガントな解答をもとむ2【2016.11】 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
>>734
は、早い・・・もう見通したんですか。
心強いお言葉ですねぇ
出題1もよろしくです。
コメントを聞いてから春旅行のスケジュールを立てますw >>733 >>735
4月号 出題1は…
(1) 通分して多項式で考えるのがシュアーか?
(2) も同様。Ω条件を消したいので○○変換してみる?
(3) 因数分解できるが、対称性は自発的に破れる?
どれも当てにならぬが… >>736
出題1は微妙ですね。警戒しておこう・・ 自分を信用してないので簡単と言われた出題2に早くも手を付たのですがw、確かに簡単というか、簡単すぎるような。
穴がないかチェックしよう。。 岡本先生は2年前の赤青問題以来、丸くなってしまったのだろうか。。
あの問題は歴史に残る名作でありました >>736
> どれも当てにならぬが…
どれも解いた人にしか書けないコメントですがw
不等式スレの住人には屁の河童かもしれませんね。 >>734
> 2は気づけばなーんだという問題。(3)まで含めてB5の半分程度で行けるかな。
コレそんなに簡単ですかね・・? >>744
気づけばね。答えの式を見たら、すぐに解法が分かると思う。 さっき気がついたけど、今月から締切日必着じゃなくて消印有効になったんだな。 >>734, 745
感嘆。やっと思いつきましたよエレガントな解法を。
これを一瞬で思いつけるのは頭良すぎですよ エレガントな解答を思いつかなかった人もいるので
おそえて下さい 北か東にしか進めない格子上を(1,1)から(m+1,n)まで移動する経路数と同じでしょ? (2)は(2m+1,n)まで、(3)は(3m+1,n)までの経路数だね。 (2)は半分より右の経路を左端まで移動して、左半分の経路分を引き算する。これがf2。
(3)は3分割して同じことをやる。 (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で対応する。 >>766
f2(i) - f1(i) = f(i+m) - f(m) が 1≦i≦m で単調非減少の経路はそうですね。
非負でOKなら、部分的に減少する経路も有り得る希ガス (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) の長方形ブロック
そだね〜 >>767
f(m)は固定値でf(i+m)が単調非減少なんだから、やはり単調非減少なんじゃね? >>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が取れます。
読み違っていたらご指摘ください。
それにしてもいい問題ですねこれ。
翌月号が届くまで暇しなさそうだ。 >>768
は ブロックB1 に収まるヤング図形を数えたのでござるな。
では、L個の関数 f_1 ≦ f_2 ≦ … ≦ f_L に対しては
ブロックBに収まる3次元ヤング図形の数にならぬか?
Π[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) の直方体ブロック >>772
P.A.MacMahon:"Combinatory Analysis" Vol.2, Cambridge (1916)
にあるらしい。 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つ組の総数を求める。
シンプルで難しく、しかし美しい組み合わせ論の問題です。
組み合わせ論はエレガントな問題の宝庫ですね。
私は苦手としているのであんまり出さないでほしいのですがw
高校生以下でもチャレンジできますので題材としてはうってつけでしょう。
組み合わせ論はアイデア一発でエレガントな解答が書けることが多いです。
逆にアイデアが浮かばなければ路頭に迷いまくるという困った性質を持ちます。
(1)は重複組み合わせを考えれば終わりなので簡単です。
問題は(2)です。あるf1に対してf2が何通りあるか(*)は論文が出ています。
しかし(f1,f2)の組み合わせの総数については参考文献が見当たりません。
(*)より簡単なのだろうと思いますがエレ解レベルの数学ファンには難しいです。
なんてあたかも私がエレ解ファンの代表かのように語ってますが、
組み合わせ論は『こう解けば簡単じゃん、バカなの?』というコメントで
落ち込まされることが経験上多いので怖いですw 2018年4月号
■出題1
〔シューア不等式〕の拡張版
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) のような、△をなさない例も含む。 >>772
> では、L個の関数 f_1 ≦ f_2 ≦ … ≦ f_L に対しては
> ブロックBに収まる3次元ヤング図形の数にならぬか?
3軸の斜交格子を使って非交差経路の組を数え上げようというわけですか。
f1,f2,f3の経路のスタート、ゴールはある軸方向に1ずつ離れていると。
それは3次元ヤング図形に対応すると。 >>786
統一された手法で解けるんですね。エレガントです。
> t≧3 ⇒ f(a,b,c;t) ≦ 0,
すべてのt≧3で成り立つのは自明ですかね? >>788
tの1次式で、係数が負。
(a,b,cを固定すれば)tについて単調減少。
問題文にもあった希ガス… >>789
あのヒントというかお膳立ては必要ない気もしたんですが。
一松センセのあらゆる読者への配慮みたいなものを感じます >>789
正三角形を除き、tの係数は負の定数。
tを増大すれば、とこかで負になる。
(a,b,c)∈△ についての上限が t_2 = 3
非△ついては上限なさそう。
(a+1+1) f(a,1,1;t) = (a-1)^2 (a+4-2t)
零点 t = (a+4)/2. 数オリとエレガントな解答をもとむって、どちらの方が難しいの? エレガントな解答をもとむと大学へのの宿題となら、どちらの方が難しいのでしょうか? 近畿大学数学コンテストなんて簡単だよ
エレガントな解答をもとむが一番難しいわ 難易度:エレガントな解答をもとむ>数オリ>宿題>近畿大学数学コンテスト>学コン>東大理系数学>センター数学 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を使ったエレガントな解法を自分で見つけたかった人は多かったはず。 ■出題1
{P(x)}^2 を展開したとき、x^{奇数}の係数は偶数だから
√(2/L)以上であることを示すのかとオモタ。
■出題2
(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 >>810
リンク先のページではダメ集合Sへの言及はないですね。
ダメ集合Sの効率的な探索法は?という問いはプログラミング的に面白いかもしれない。 >>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 (チェス盤)はオイラーの時代からあったらしい… >>813
集合Sが探索効率を上げるんですかね
未解決部分があるようですが最近の研究はどうなっているのか >>813
多項式の問題すんなりイケました?
実のところそのx(1-x)の形に捕らわれて時間を食いましたわ >>815
積分を使ったので粗い評価になったようです。(エレガントかどうか?) どうもチェビシェフを使って振れ幅を最小にできるようで
ちゃんと読んでませんけど >>816
積分以外の別解法でmax≧1/f≧1/sqrtLCMと押さえられるんでしょうか?
本問のエレガント賞は積分使わなかった人かもw >>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日(消印) >>819
> なお、6月号の締切は 6月8日(消印)
消印締め切りのおかげで投函時に祈らなくてもよくなりました >>812
ご老公も大昔に出題されてますね^^
数セミ増刊「数学の問題」第(2)集、日本評論社(1978)
の No. 46
>>814
現在は、6×6の盤でも周遊可能のようです。 >>821
6×6 ナイト周遊の例(4回対称)
1 8 23 16 31 10
22 15 2 9 24 17
7 36 21 30 11 32
14 29 12 3 18 25
35 6 27 20 33 4
28 13 34 5 26 19 >>821
なんと過去に出題済みでしたか
昔の出題分かります?
今より難しかったんじゃなかろうか。
時代への迎合度を測りたい。 >>823
●46
西洋のチェスのナイト(騎士)は、四方八方に桂馬と
びをします。3×4の長方形の盤の各目に 1〜12の番号
をふります。このときつぎの2命題を証明してください:
(i) 適当な位置から出発して、つぎつ
ぎにナイトを動かしてゆき、すべての目
をただ一度だけ通ることは可能である。
(ii) しかし全部を通過して、最後の目
からふたたびナイトの飛び方で出発点に
戻ることは不可能である。
注意 (ii)はもちろんあらゆる可能性をためせば、証
明にはなりますが、もっと<エレガントな数学的な>不
可能の証明を期待します。 >>812 >>814
n×n (nは偶数)の正方形盤について
n が4で割り切れない偶数 (n≧6) のとき、4回対称な解がある。
n が4の倍数 (n≧8) のとき、2回対称な解はあるが、4回対称な解は無い。
I. J. Dejter: Ars. Combin. 16, p.285-295 (1983)
"Equivalent conditions for Euler's problem on Z_4-Hamilton cycles"
例)
I. Parberry: Discrete Applied Mathematics, 73, p.251-260 (1997)
"An efficient algorithm for the Knight's tour problem"
http://larc.unt.edu/ian/pubs/algoknight.pdf
http://larc.unt.edu/ian/research/puzzles/knightstour/ >>812 >>814
10×10 ナイト周遊の例(4回対称)
1, 92, 87, 6, 3, 74, 69, 66, 61, 76,
86, 5, 2, 97, 88, 65, 60, 75, 80, 67,
91, 100, 93, 4, 7, 70, 73, 68, 77, 62,
94, 85, 98, 89, 96, 59, 64, 79, 72, 81,
99, 90, 95, 84, 33, 8, 71, 82, 63, 78,
28, 13, 32, 21, 58, 83, 34, 45, 40, 49,
31, 22, 29, 14, 9, 46, 39, 48, 35, 44,
12, 27, 18, 23, 20, 57, 54, 43, 50, 41,
17, 30, 25, 10, 15, 38, 47, 52, 55, 36,
26, 11, 16, 19, 24, 53, 56, 37, 42, 51,
これも >>822 と同様、分かりづらい… >>822
6×6 ナイト周遊(4回対称) の別解
1, 26, 13, 24, 3, 28,
12, 23, 2, 27, 14, 17,
33, 36, 25, 16, 29, 4,
22, 11, 34, 7, 18, 15,
35, 32, 9, 20, 5, 30,
10, 21, 6, 31, 8, 19,
4つの「結び目」を除いて考えると、外周を3周するだけ… >>814
・n×n (正方形盤)
nが奇数または5以下 → 不可能。
nが偶数 (n≧6) → 可能、2回対称な解もある。
nが4で割り切れない偶数 (n≧6) → 4回対称な解もある。
n 合 計 4回対称 2回対称 非対称
------------------------------------------------------------------
4 0 0 0 0
6 1,245 5 17 1,223
8 1,658,420,855,433 0 608,233 1,658,420,247,200
10 ? 415,902 ? ?
・3×偶数 (n≦8) → 不可能。
・3×偶数 (n≧10) → 可能。n=12を除き、2回対称な解がある。
n 合 計 2回対称 非対称
------------------------------
8 0 0 0
10 6 4 2
12 44 0 44
14 396 24 372
16 3868 24 3844
18 37078 292 36786
20 362192 176 362016
・3×(4k+2) → 2回対称な解と面対称な解は同数ある。
・4×n → 不可能 … Sainte-Marie (1887)
"Knight's tour notes"
http://www.mayhematics.com/t/t.htm >>824
> 注意 (ii)はもちろんあらゆる可能性をためせば、証
> 明にはなりますが、もっと<エレガントな数学的な>不
> 可能の証明を期待します。
いいじゃないですか。エレ解らしくて。
エレファント解も用意されているのがgood.
集合S以外の解き方はぱっと浮かばず、考えさせられます
対して先月の問題はぜんぜん面白くない。
『問題文に提示されたエレガントな解答の"説明"をもとむ』という名のコーナーじゃないんだが
エレガントな"解答"を求まれたい。
>>809
> 出題1はともかく出題2は明らかにヒント過多。
> "ダメなマスの集合S"の存在をうまく隠せれば良問になっただけに残念です。
> Sを使ったエレガントな解法を自分で見つけたかった人は多かったはず。 >>822 >>827
6×6 4回対称解 の続き
(L)
1, 26, 13, 16, 3, 28,
12, 15, 2, 27, 6, 17,
25, 36, 23, 14, 29, 4,
22, 11, 32, 5, 18, 7,
35, 24, 9, 20, 33, 30,
10, 21, 34, 31, 8, 19,
これは (g) >>827 とよく似ている。
(a)
1, 26, 13, 16, 3, 28,
12, 15, 2, 27, 6, 17,
25, 36, 23, 14, 29, 4,
22, 11, 32, 5, 18, 7,
35, 24, 9, 20, 33, 30,
10, 21, 34, 31, 8, 19,
形は似ているが「結び目」でUターンするので、結局外周を1回りするだけ。
(i)
1, 8, 31, 16, 3, 10,
30, 23, 2, 9, 32, 17,
7, 36, 15, 24, 11, 4,
22, 29, 6, 33, 18, 25,
35, 14, 27, 20, 5, 12,
28, 21, 34, 13, 26, 19,
これは反転を含んでいる(4回)点で (e) >>822 に似ている。
以上が 6x6 の4回対称解 (a,e,g,i,L)
2回対称解は17種もあるらしい。 >>830
訂正スマソ
(a)
1, 14, 35, 6, 3, 28,
12, 7, 2, 27, 34, 5,
15, 36, 13, 4, 29, 26,
8, 11, 22, 31, 18, 33,
23, 16, 9, 20, 25, 30,
10, 21, 24, 17, 32, 19, >>828
> "Knight's tour notes"
> http://www.mayhematics.com/t/t.htm
マニアックだなこりゃw
芸術にも見えてくるから不思議。
ナイトツアー閉路アート 3×10 ナイト周遊
・ 2回対称解 (Bergholt) 2つ
"NSI"
4, 7, 10, 19, 16, 1, 14, 23, 28, 25,
9, 18, 5, 2, 11, 20, 29, 26, 13, 22,
6, 3, 8, 17, 30, 15, 12, 21, 24, 27,
"NSU”
6, 3, 8, 19, 16, 1, 14, 21, 24, 27,
9, 18, 5, 2, 11, 20, 29, 26, 13, 22,
4, 7, 10, 17, 30, 15, 12, 23, 28, 25,
・ 鏡面対称解 (Sulian) 2つ
"NSI"
4, 7, 10, 29, 16, 1, 14, 25, 22, 19,
9, 28, 5, 2, 11, 26, 17, 20, 13, 24,
6, 3, 8, 27, 30, 15, 12, 23, 18, 21,
"NSU"
6, 3, 8, 29, 16, 1, 14, 23, 18, 21,
9, 28, 5, 2, 11, 26, 17, 20, 13, 24,
4, 7, 10, 27, 30, 15, 12, 25, 22, 19,
(中央で180°ひねったような…)
・非対称解 2つ
>>828 の下表では 対称解(2回対称または鏡面対称) とすべきでござった。 ■ このスレッドは過去ログ倉庫に格納されています