【数セミ】エレガントな解答をもとむ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/

783◆2VB8wsVUoo 2018/04/13(金) 18:18:47.29ID:uddKuSDq

784とあるエレ解常連2018/04/14(土) 11:11:10.88ID:OmmA56DO
気が進まないけど講評書くかな

785とあるエレ解常連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つ組の総数を求める。

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

(1)は重複組み合わせを考えれば終わりなので簡単です。
問題は(2)です。あるf1に対してf2が何通りあるか(*)は論文が出ています。
しかし(f1,f2)の組み合わせの総数については参考文献が見当たりません。
(*)より簡単なのだろうと思いますがエレ解レベルの数学ファンには難しいです。
なんてあたかも私がエレ解ファンの代表かのように語ってますが、
組み合わせ論は『こう解けば簡単じゃん、バカなの?』というコメントで
落ち込まされることが経験上多いので怖いですw

786132人目の素数さん2018/04/15(日) 12:12:42.08ID:ZO3/JPf/
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) のような、△をなさない例も含む。

787とあるエレ解常連2018/04/15(日) 15:25:27.83ID:y2agdfqD
>>772
> では、L個の関数 f_1 ≦ f_2 ≦ … ≦ f_L に対しては
> ブロックBに収まる3次元ヤング図形の数にならぬか?

3軸の斜交格子を使って非交差経路の組を数え上げようというわけですか。
f1,f2,f3の経路のスタート、ゴールはある軸方向に1ずつ離れていると。
それは3次元ヤング図形に対応すると。

788とあるエレ解常連2018/04/15(日) 15:50:24.38ID:y2agdfqD
>>786
統一された手法で解けるんですね。エレガントです。

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

すべてのt≧3で成り立つのは自明ですかね?

789132人目の素数さん2018/04/15(日) 21:32:28.34ID:ZO3/JPf/
>>788

tの1次式で、係数が負。
(a,b,cを固定すれば)tについて単調減少。
問題文にもあった希ガス…

790とあるエレ解常連2018/04/15(日) 22:35:07.95ID:dInGck+5
>>789
あのヒントというかお膳立ては必要ない気もしたんですが。
一松センセのあらゆる読者への配慮みたいなものを感じます

791とあるエレ解常連2018/04/15(日) 22:40:25.26ID:dInGck+5
今月号はなんとなく簡単な予感がす。

792132人目の素数さん2018/04/16(月) 22:48:00.94ID:I9VNB52o
>>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.

793132人目の素数さん2018/04/20(金) 14:08:29.21ID:W4yzbmXa
数オリとエレガントな解答をもとむって、どちらの方が難しいの?

794132人目の素数さん2018/04/20(金) 23:58:07.64ID:W4yzbmXa
エレガントな解答をもとむと大学へのの宿題となら、どちらの方が難しいのでしょうか?

795132人目の素数さん2018/04/21(土) 09:16:13.39ID:I5oMZRza
もちろん、近畿大学の数学コンテストです。

796132人目の素数さん2018/04/21(土) 19:41:50.90ID:LCJcAykv
近畿大学数学コンテストなんて簡単だよ
エレガントな解答をもとむが一番難しいわ

797132人目の素数さん2018/04/21(土) 19:55:29.52ID:LCJcAykv
難易度:エレガントな解答をもとむ>数オリ>宿題>近畿大学数学コンテスト>学コン>東大理系数学>センター数学

798132人目の素数さん2018/04/21(土) 21:00:47.89ID:zpKOfNof
これは酷い

799◆2VB8wsVUoo 2018/04/23(月) 15:54:09.29ID:HBynUzNE

800◆2VB8wsVUoo 2018/04/23(月) 15:54:28.43ID:HBynUzNE

801◆2VB8wsVUoo 2018/04/23(月) 15:54:47.69ID:HBynUzNE

802◆2VB8wsVUoo 2018/04/23(月) 15:55:08.36ID:HBynUzNE

803◆2VB8wsVUoo 2018/04/23(月) 15:55:30.56ID:HBynUzNE

804◆2VB8wsVUoo 2018/04/23(月) 15:55:52.39ID:HBynUzNE

805◆2VB8wsVUoo 2018/04/23(月) 15:56:12.51ID:HBynUzNE

806◆2VB8wsVUoo 2018/04/23(月) 15:56:35.72ID:HBynUzNE

807◆2VB8wsVUoo 2018/04/23(月) 15:57:01.49ID:HBynUzNE

808◆2VB8wsVUoo 2018/04/23(月) 15:57:25.51ID:HBynUzNE

809とあるエレ解常連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を使ったエレガントな解法を自分で見つけたかった人は多かったはず。

810132人目の素数さん2018/05/12(土) 02:26:32.31ID:ERQyPxVg
■出題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

811とあるエレ解常連2018/05/12(土) 09:53:53.76ID:h4NJI8KX
>>810
リンク先のページではダメ集合Sへの言及はないですね。
ダメ集合Sの効率的な探索法は?という問いはプログラミング的に面白いかもしれない。

812とあるエレ解常連2018/05/13(日) 01:34:09.74ID:vWLY3HuW
>>810
ナイトツアーは有名問題なんですね

813132人目の素数さん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 (チェス盤)はオイラーの時代からあったらしい…

814とあるエレ解常連2018/05/13(日) 11:07:41.37ID:3y7zv360
>>813
集合Sが探索効率を上げるんですかね
未解決部分があるようですが最近の研究はどうなっているのか

815とあるエレ解常連2018/05/13(日) 11:10:56.05ID:3y7zv360
>>813
多項式の問題すんなりイケました?
実のところそのx(1-x)の形に捕らわれて時間を食いましたわ

816132人目の素数さん2018/05/13(日) 11:25:33.25ID:dQIRZ6zE
>>815
 積分を使ったので粗い評価になったようです。(エレガントかどうか?)

817とあるエレ解常連2018/05/13(日) 11:33:17.09ID:3y7zv360
どうもチェビシェフを使って振れ幅を最小にできるようで
ちゃんと読んでませんけど

818とあるエレ解常連2018/05/13(日) 11:38:39.87ID:3y7zv360
>>816
積分以外の別解法でmax≧1/f≧1/sqrtLCMと押さえられるんでしょうか?
本問のエレガント賞は積分使わなかった人かもw

819132人目の素数さん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日(消印)

820とあるエレ解常連2018/05/14(月) 23:03:48.51ID:EjCwyYuo
>>819
> なお、6月号の締切は 6月8日(消印)

消印締め切りのおかげで投函時に祈らなくてもよくなりました

821132人目の素数さん2018/05/16(水) 02:49:28.54ID:iriy4b81
>>812

ご老公も大昔に出題されてますね^^

数セミ増刊「数学の問題」第(2)集、日本評論社(1978)
の No. 46

>>814

現在は、6×6の盤でも周遊可能のようです。

822132人目の素数さん2018/05/16(水) 15:20:17.92ID:iriy4b81
>>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

823とあるエレ解常連2018/05/16(水) 20:40:24.04ID:peJi7xrg
>>821
なんと過去に出題済みでしたか
昔の出題分かります?
今より難しかったんじゃなかろうか。
時代への迎合度を測りたい。

824132人目の素数さん2018/05/17(木) 01:07:01.50ID:FDCSht5h
>>823

●46
 西洋のチェスのナイト(騎士)は、四方八方に桂馬と
びをします。3×4の長方形の盤の各目に 1〜12の番号
をふります。このときつぎの2命題を証明してください:

(i) 適当な位置から出発して、つぎつ
ぎにナイトを動かしてゆき、すべての目
をただ一度だけ通ることは可能である。

(ii) しかし全部を通過して、最後の目
からふたたびナイトの飛び方で出発点に
戻ることは不可能である。

注意 (ii)はもちろんあらゆる可能性をためせば、証
明にはなりますが、もっと<エレガントな数学的な>不
可能の証明を期待します。

825132人目の素数さん2018/05/17(木) 05:53:49.67ID:FDCSht5h
>>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/

826132人目の素数さん2018/05/17(木) 14:55:49.51ID:FDCSht5h
>>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 と同様、分かりづらい…

827132人目の素数さん2018/05/17(木) 16:14:58.24ID:FDCSht5h
>>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周するだけ…

828132人目の素数さん2018/05/17(木) 17:56:56.89ID:FDCSht5h
>>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

829とあるエレ解常連2018/05/17(木) 23:53:00.15ID:5HviOqXJ
>>824
> 注意 (ii)はもちろんあらゆる可能性をためせば、証
> 明にはなりますが、もっと<エレガントな数学的な>不
> 可能の証明を期待します。

いいじゃないですか。エレ解らしくて。
エレファント解も用意されているのがgood.
集合S以外の解き方はぱっと浮かばず、考えさせられます

対して先月の問題はぜんぜん面白くない。
『問題文に提示されたエレガントな解答の"説明"をもとむ』という名のコーナーじゃないんだが
エレガントな"解答"を求まれたい。

>>809
> 出題1はともかく出題2は明らかにヒント過多。
> "ダメなマスの集合S"の存在をうまく隠せれば良問になっただけに残念です。
> Sを使ったエレガントな解法を自分で見つけたかった人は多かったはず。

830132人目の素数さん2018/05/18(金) 03:17:36.06ID:539vwTx6
>>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種もあるらしい。

831132人目の素数さん2018/05/18(金) 03:32:54.15ID:539vwTx6
>>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,

832とあるエレ解常連2018/05/19(土) 10:41:11.33ID:Q9nxl5kt
>>828
> "Knight's tour notes"
> http://www.mayhematics.com/t/t.htm

マニアックだなこりゃw
芸術にも見えてくるから不思議。
ナイトツアー閉路アート

833132人目の素数さん2018/05/20(日) 02:23:00.20ID:1IiDnvUy
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回対称または鏡面対称) とすべきでござった。

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