【数セミ】エレガントな解答をもとむ3【2018.10】
■ このスレッドは過去ログ倉庫に格納されています
出題1、最後が無限総乗になって解けなかったけど、あれはそのままで良いのかな? 出題1の問題2は
・もしpの値が分かっていれば → p=1/2の時は普通に表裏で勝負を付け、それ以外の時は問題文の方法でやる。期待値の最小値はp=1/2の時の1回。
・pに関する情報が一切無ければ → 表裏のどちらが出やすいかは2人とも知らないので、1度のコイン投げで決めても公平である。
というわけで、いずれにせよ期待値の最小値は1。
しかし問題文をよく読むと「手元にあるコインは、どう見ても歪んでいて」とあるので、
pの値は確定している分けでは無く、逆に情報が全くないわけでは無い(どちらが
出やすいか程度は分かっている)模様。なので、この手のメタ的な方向からの
アプローチは無効だと思われる。 18年12月号の講評です。
今月は2問とも歯応えのある良問でした。
https://www.web-nippyo.jp/10317/
(すでに1月号の問題が出ている)
■出題1:レベル6以上(常連正解率75%以下)
上原隆平先生の良問。
表の出る確率pの歪んだコインを使って公平な勝負を行う。
問1は2回投げて表→裏、裏→表ならそれぞれAさん、Bさんの勝ち。
それ以外はやり直しとするルールのもと、期待値と期待値の最小値、それを与えるpを求める。
問2は問1より期待値が小さくなるルールを考える。
問1は簡単な計算問題。問2は難しい。
問1の勝敗条件をキープしつつ、ある回数を区切りとして
勝ち負けの条件を再帰的に定める方法がある。
この方法を採ると期待値は無限積となり最小値は問1の値を下回る。
>>151氏は早い段階で無限積に到達している。
以前お世話になった早解きさんでしょうか。
■出題2:完答レベル8以上(常連正解率20%以下)
奥田隆幸先生のエレガントな難問。
n個の実数a_1,a_2,...,a_nがある。
s_kを(1)a_kを-1倍、(2)a_{k-1},a_{k+1}にa_kを加える操作と定義する。
この操作を繰り返しすべて非負となったらゴールというゲーム。
問1は初期値によらずゴールできること、
問2は手順によらずゴール状態が1通りであること、
問3は左右対称形からスタートするとゴールも左右対称であることを示す。
問1はマイナスを掃き出す手順を1つ見つければよいだけ。
問2は行列群を考える方法があるが、解き切るのは難しい。
問3は問2の結果であるゴールの一意性を前提とすればゴリ押しでもなんとかいける。
つまり左右対称形でゴールできる手順を1つ見つければよい。
それは比較的簡単に見つかるが厳密な論証は簡単ではない。
エレガントに解いた方のコメントもとむ。 出題2は原題が Peter Winkler のパズル本に殆ど同じ出題があります。
Winkler, Peter. Mathematical Puzzles: A Connoisseur's Collection (p.88). Taylor & Francis - A. Kindle 版.
こっちは円形に並んでるのでややむずい。
――
Flipping the Polygon
The vertices of a polygon are labeled with numbers, the sum of which is positive. At any time, you may change the sign of a negative label, but then the new value is subtracted from both neighbors’ values so as to maintain the same sum.
(なぜか間違ってる参考図。略)
Prove that, inevitably, no matter which labels are flipped, the process will terminate after finitely many flips, with all values non-negative.
――
その問題の来歴の解説
――
Flipping the polygon
This puzzle generalizes one that appeared at the International Mathematics Olympiad in 1986 (submitted by a composer from East Germany, I am told) and subsequently termed “the Pentagon Problem.”
――
本の解答
元の数列a[k]とその級数S[k]を考える。
ただしa[0] = 0を追加しておく。
a[k]が全て0以上⇔S[k]が広義単調増大。
操作s[k]を行うとSはS[k-1]とS[k]の交換になる。
S[k]を交換していけばS[k]を広義単調増大にすることは可能で結果は一意的。
よって(1),(2)終わり。
(2)から(3)も左右対称の操作をして結果が同じになることから出る。
―― 例 縦線の右がa[k]、中がS[k]、右がその列に行った操作 ――
0 -5 3 4 -3 1 │ 0 -5 -2 2 -1 0 │ s[1]
-5 5 -2 4 -3 1 │-5 0 -2 2 -1 0 │ s[2]
-5 3 2 2 -3 1 │-5 -2 0 2 -1 0 │ s[4]
-5 3 2 -1 3 -2 │-5 -2 0 -1 2 0 │ s[3]
-5 3 1 1 2 -2 │-5 -2 -1 0 2 0 │ s[5]
-5 3 1 1 0 2 │-5 -2 -1 0 0 2 │ S[k]は広義単調増大。
(一番左はa[0]なので気にしなくて良い。) >>186
> 問2は行列群を考える方法があるが、解き切るのは難しい。
行列の方法は見通しが悪そうに見えたのですが、そんなことはなかったですね。
> ■出題2:完答レベル8以上(常連正解率20%以下)
Winkler本にある有名問題ということでレベル5〜6(常連正解率75%以上)に訂正。 >>189
Π[i=0,∞] (1 + (1/2)^{(2^i) -1}) = 3.4014709905728… 出題1の小問2
題意把握ミスかもしれないが、
第三者Cに公平に
確率2分の1→表を「H」、裏を「T」
確率2分の1→表を「T」、裏を「H」
と定めてもらう。(無論A、BさんはCの定め方を知らない。)
この決め方なら、コイントス常に
1回かつ公平(どちらも勝率が等しい)な勝負になると考えた。 >>195
なるほど。で、次にその確率1/2をどうやってこのコインで作り出すかを考えないと
→最初に戻る >>196
確かに。
「第三者に公平に」決めてもらうためのコインが必要になりますね。
堂々巡りになってしまうのか。 1月号が届きました
>>34
> ■出題1:レベル6〜7(常連正解率60〜80%)
> ※スツルムの定理不使用の場合レベル10(正解者0〜2名)
>>121
> 10月号の時弘先生の問題>>34が中高生の範囲で解けるのかどうかは気になります。スツルムの定理を前提知識として要求しているとは思えませんから。
>
> 「中高生の範囲」というのも考え始めると良く分からなくなってきますがね。スツルムの定理を理解するのに必要な知識は高校範囲の微分だけですからね。
> 一次変換だって少し前は高校でやっていたわけで。行列の知識を使わないで解くのが出題者の狙いだったとして、そのココロは私にはよく分からんですね。
時弘先生の解答編を流し読み。
スツルムの定理を知っていることが前提の問題でしたw 読者に媚びない時弘先生は今年も健在でした
10名が全問正解というのだから素晴らしい
来年も楽しみです 1月号の出題2は既知の定理の別解法を求めるもの
こういうタイプは好きではない >>194
私の方法は、
http://blog.world-mysteries.com/wp-content/uploads/2011/11/Pascal_Sierpinski.png
のようなパスカルの三角形の一番上からスタートして、表なら左下、裏なら右下に
一つずつ移動し、偶数に当たったら終了するというもの。勝ち負けは、最後の表裏で決める。
最小性の証明は書けなかったけど、こんな感じかな。
パスカルの三角形は、そこに至るまでの経路数を意味するから、コインを停止
するまでの表裏の出方の総数に等しい。(ただし、それ以前に勝負が付いた時も
その回数までコインを空投げするとする。)
各コイン投げ停止位置では、この総数のうち半数がAの勝ち、半数がBの勝ち
でないと上手く行かない(要証明)。そのため、コイン投げが停止するのは
偶数の位置である必要があり、その中では、上に書いた方法では偶数に当たった時点で
停止しているため最小の手段を実現している。
問題は(要証明)のところで、ちゃんと示すのは色々と難しそう。 >>202
おお、すばらしい。なんかこの方針で示せそう! う〜ん、示せそうだね。
答え聞くまではこれ最小性の証明つけられたやついないかもと思ってたけど、これ聞いた後だといっぱいいても不思議ないように思えてくるねww 今月の2は、各種公式をどこまで使って良いか迷うなあ。 >>209
自分の知識を使ってよいか迷う問題は十中八九悪問です。
ってまだ締め切り前でしたね、すまそ ☆★☆【神よこの者たちはもはや人間ではない悪魔であるこのような悪魔どもを一匹残らず殺してくださいお願いします】★☆★
《超悪質!盗聴盗撮・つきまとい嫌がらせ犯罪首謀者の実名と住所/死ねっ!! 悪魔井口・千明っ!!》
【要注意!! 盗聴盗撮・つきまとい嫌がらせ犯罪工作員】
◎井口・千明(東京都葛飾区青戸6−23−16)
※盗聴盗撮・嫌がらせつきまとい犯罪者のリーダー的存在/犯罪組織の一員で様々な犯罪行為に手を染めている
低学歴で醜いほどの学歴コンプレックスの塊/超変態で食糞愛好家である/醜悪で不気味な顔つきが特徴的である
【超悪質!盗聴盗撮・嫌がらせつきまとい犯罪者の実名と住所/井口・千明の子分たち】
@宇野壽倫(東京都葛飾区青戸6−23−21ハイツニュー青戸202)
※宇野壽倫は過去に生活保護を不正に受給していた犯罪者です/どんどん警察や役所に通報・密告してやってください
A色川高志(東京都葛飾区青戸6−23−21ハイツニュー青戸103)
※色川高志は現在まさに、生活保護を不正に受給している犯罪者です/どんどん警察や役所に通報・密告してやってください
【通報先】
◎葛飾区福祉事務所(西生活課)
〒124−8555
東京都葛飾区立石5−13−1
рO3−3695−1111
B清水(東京都葛飾区青戸6−23−19)
※低学歴脱糞老女:清水婆婆 ☆☆低学歴脱糞老女・清水婆婆は高学歴家系を一方的に憎悪している☆☆
清水婆婆はコンプレックスの塊でとにかく底意地が悪い/醜悪な形相で嫌がらせを楽しんでいるまさに悪魔のような老婆である
C高添・沼田(東京都葛飾区青戸6−26−6)
※犯罪首謀者井口・千明の子分/いつも逆らえずに言いなりになっている金魚のフン/親子孫一族そろって低能
D高橋(東京都葛飾区青戸6−23−23)
E長木義明(東京都葛飾区青戸6−23−20)
F若林豆腐店店主(東京都葛飾区青戸2−9−14)
G肉の津南青戸店店主(東京都葛飾区青戸6−35ー2 >>212
9日でござる。今夜もよく冷えるでござる....
今月号の2 ベクトル公式を使った解答の例
球面上に3点L,M,Nを
BOC面に垂直な向きにOL
COA面に垂直な向きにOM
AOB面に垂直な向きにON
となるようにとる。
MON面に垂直な向き ・・・・ OA
NOL面に垂直な向き ・・・・ OB
LOM面に垂直な向き ・・・・ OC
となる。(相反系)
上の定義から次が成り立つ。
OB×OC = sin(a) OL,
OC×OA = sin(b) OM,
OA×OB = sin(c) ON,
OM×ON = sinα OA,
ON×OL = sinβ OB
OL×OM = sinγ OC,
4面体O-ABCの体積をV
4面体O-LMNの体積をv
とおくと、
V = (1/6)OA・(OB×OC) = (1/6)sin(a) OA・OL,
v = (1/6)(OM×ON)・OL = (1/6)sinα OA・OL,
V/v = sin(a)/sinα,
b,β および c,γ についても同様。 >>214
それで「幾何学的な考察から導い」たと言えるかねぇ・・・・
今月の1
便宜のため、周期的に延長する。
x_{n+i} = x_i
s_{n+i} = s_i + s_n
(i=0,1,・・・・,n-1。もっと先まで伸ばしてもよい。)
f(x^(j)) = max{ min{s_(j+1)-s_j, s_(j+2)-s_j, ・・・・, s_(j+n)-s_j}, 0}
= max{ min{s_(j+1), s_(j+2), ・・・・, s_(j+n)}, s_j} - s_j
= min{s_(j+1), s_(j+2), ・・・・, s_(j+n)}, s_j} - min{s_j, s_(j+1), s_(j+2), ・・・・, s_(j+n)} (*)
n個先のsの方が大きいから、いくら追加しても min は変わらない。
∴ f(x^(j)) = σ_(j+1) - σ_j
ここに σ_k = min{s_k, s_(k+1), ・・・・, s_(2n-1), ・・・・} とおいた。
∴ (与式) = σ_n - σ_0 = s_n,
*) max{t, s_j} - s_j = t - min{s_j, t} を使った。 >>214
そんなとこですかねえ。私は外積の三重積を開く公式を使っちゃいましたが。
sinが出てきて余弦定理がダメとなると、どうしても外積が出ちゃいますね。
幾何学的にできなくも無いでしょうが、外積の公式を証明するような流れになりそう。 >>214 も V(4面体の体積) = (1/6)(3稜のスカラー三重積) を使うのでござるな。
もっと幾何学的な考察から導くなら
V(4面体の体積) = (1/3)S(底面積)h(高さ)
S(底面積) = (1/2)sin(?)
とか行きたいところでござる。 出題1は偏微分とガンマ関数使ってちょろちょろやったら解けた
... が、俺でも思いつくような解法はエレガントじゃないんだろうなあ 今月の出題のネット版、iPhoneで見ると求める式の最後(k+l)Ckが抜けているのでご注意を。 出題1は
Σ[i+k=n] Σ[j+L=m] f_1(i, j) f_2(k, L)
の形だから、級数(= 生成関数)の積を使ってゴリゴリやったら解けそうだ
... が、俺でも思いつくような解法はちっともエレガントぢゃねえんだよなぁ まだ応募期限来てないやつの話はやめとけよ。
こうやったら解けたの解けそうだだのあかんやろ。 ここそういうスレなんじゃないの?
それでも気を使って答えアップしなかったけど。 どういうスレかは誰が決めるもんでもない。
そういう問題じゃないやろ?
ここで雑誌の企画の妨害になる事してどうすんねん?
数学がどうこういう以前にそもそも人間として守らなあかん一線はあるやろ?
アホか? 19年1月号の講評:
■出題1:レベル4〜5(常連正解率95%以上)
徳重先生の良問風(?)な問題。
列x=(x_1, x_2,...,x_n)の先頭i個の部分和をs_iとする。
s_n>0のとき、xをj個ずらした列をx^(j)として、
f:x^(j)→max{min{s_{j+1},s_{j+2},...,s_j},0}
の和Σ_{j=0 to n-1} fがs_nに等しいことを示す問題。
>>215のようなエレガントなmin-max演算が出来ないと解けない、ということはない。
和を保存しつつ列を縮小する手術を考え、任意のxが非負列に変換されることを示す方針もある。
■出題2:レベル4(常連正解率〜100%)
長い問題文だがようするに球面正弦定理を示す問題。
よく知られた証明じゃつまらないので 幾何学的な考察から導け と制限が付けられている。
正弦定理だけに。(←これが言いたかっただけ) 初めて投稿してみようと思うのですが、
皆さんは証明などする際に、
論文のようにアイデアのクリティカルな部分は丁寧に書いて、ごく簡単と思われる部分は省略していますか?
それとも大学入試のように全ての場合についてしっかり議論してますか? その辺のさじ加減も証明の美しさに関わってくるし、書き手の腕の見せ所ではあるな。 >>230
問題の難易度によりけりですね。
込み入った論理展開が必要なときは相対的に自明と思われる補題は証明を省くことがあります。
一方で簡単な問題では、論文レベルでは証明を省くような自明な帰結であっても、それを書かないと解答が「自明」で終わってしまうので丁寧に書き下すことがあります。(これがめんどくさいんだよ)
余談ですが、難しいことで有名な時弘先生の出題で、先生の論文の証明の行間を埋める問題が出されたことがあります。
その問題のエレ解正解者はたったの2名。
プロのレベルは凄いもんだなぁと思いました >>231-232
非常に参考になりました
ありがとうございます エレ解よりも大学への数学の宿題のが遥かに難しいよな >>234
なんだよ素数大富豪って? 説明したまえ! 本スレの「じゃんけん」を次のように定義する
大数・宿題 は 数セミ・エレ解 に勝つ >>235
数セミ・エレ解 は 数オリ に勝つ >>237
数オリ は 大数・宿題 に勝つ 本格インド料理の KOMAL をご存知ないからコマル。
メルカード武庫川(西宮市)の1階にあります。
香港の Math. Excalibur もどうぞ。
http://www.math.ust.hk/excalibur/ ハンガリーの数学雑誌:ケマルって、難しいんですか? 兵庫のKOMALを知ってる>>246氏は常連の中の常連。
(店の常連って意味じゃないよ) >>252
そのΣのある形とない形、実際に無い形のほうが計算が簡単だと思う?
m, nが大きい場合でも明らかに簡単? 形で言えば、Σの中身に似てるけど、2項ぐらいかな。 >>254
うーん…実際に計算が簡単になってるか、という観点ではどう? >>224
9日でござる。今日もよく冷えるでござる。(インフルに注意)
■出題1
n,mを非負整数とするとき、
A(n,m) = Σ[i+k=n] Σ[j+L=m] f_1(i, j) f_2(k, L)
をより簡単な形で表わす問題。
i+k=n と j+L=m を見れば、生成関数を使う方針が浮かぶ。
G (x,y) = Σ_(n,m) A (n,m) x^n y^m
= {Σ_(i,j) f_1 (i, j) x^i y^j} {Σ_(k, L) f_2 (k, L) x^k y^L}
= g_1(x, y) g_2(x, y)
ここで g_1, g_2 は f_1, f_2 の生成関数。i,j, k,L, m,n はすべての非負整数を亘る。
本問では f_1(i,j) = (-1)^i f_2(i, j) ゆえ
g_1(x, y) = g_2(-x, y) ⇒ G(x,y) はxの偶関数。
二項公式より
g_2(x,y) = Σ_s (2s+1) {Σ[k+L=s] C[k+L,k] x^k y^L} = Σ_s (2s+1)(x+y)^s = (1+x+y)/(1-x-y)^2,
g_1(x,y) = (1-x+y)/(1+x-y)^2,
G(x,y) = g_1(x,y) g_2(x,y) = 1/[(1-y)^2 -xx] + 4y/[(1-y)^2 -xx]^2
← 等比級数の和
= Σ_n' {1/(1-y)^(2n'+2) + 4(n'+1) y/(1-y)^(2n'+4)} x^(2n')
← (一般化)二項公式
= Σ[n:偶数] Σ_m {C(n+m+1,m) + 2(n+2)C(n+m+2,m-1)} x^n y^m,
A(n,m) = C(n+m+1,m) + 2(n+2) C(n+m+2,m-1) (n:偶数)
= 0 (n:奇数) ■出題2
・問1
a = (a1, a2,・・・・, ak)
#S(a) ≦ 2^k
max{S(a)} = Σ[j=1,k] a_j
等から
2^{k-1} ≦ n < 2^k,
k[n] = 1 + [ log(n)/log(2) ]
・問2
n = 4, 2^k -1, 2^k -2 かな。 ↑いつもながらエレガントな解答ですね。
私は出題1が解けませんでした。
生成関数というものを使ったことがなく,2項展開と2項係数の公式で何とかしようとして失敗しました。 >>193
これより小さい解があったんだ!びっくりした。 例えば>>202 の図で言えば、偶数にたどり着いたら止めて最後に右下に進めばA、左下ならBの勝ちという方法が考えられるが、左右対象の位置で勝ち負け判定を入れ替えても、全体としての公平性は保たれる。
例として5段目の2つの4のいずれかにたどり着いた場合のみ勝ち負けを入れ替える。すると、4段目の3に着いた時点で、次に右下に行っても左下に行っても勝ち負けは同じになる。つまりそれ以上やる意味が無いからそこでゲームを止められる。
というように、地味に枝刈りをやっていくという方法。残念なのはこの筆者、コイン投げを途中で打ち切ってその段階の確率しか計算していないこと。まあ指数関数的に確率は減るからそれで良いかもしれんが、無限大回数までやったらどうなるかも知りたかったな。 今度からは、 >>1 と >>5 を読んでから書き込んでね >>267
同感。
すべての球にmを与えると たくさんできそうだが。
正の数値だから無理数でもいいだろうし。
「なるべく簡明にまとめた説明を工夫してください。」と言いたい。 >>269
すべての球を同じ値にするって事?
だったら四面体の頂点の4個(1つでも列とみなすとして4列)しかないんじゃない? あ、k=1の場合を考えると、2個連なってる列でも良いから、4段積みの場合でさらに9列か。 四面体の頂点って一直線上に隣接して並ぶってみなしていいのか?
例えば、3段積みなら一直線上に並ぶ球が18種類あるって意味と捉えたのだが
k=2が6種類、k=1が12種類の計18 頂点は問題の本質でないからどっちでもいいとして、問題文の意味は通ると思うけど >>259 >>260
2018-12月号出題1の解答例
(0) 2回ごとに
pp → 未定
pq → ○
qp → ●
qq → 未定
とすると、未定率は 1/2
T_0 = 4
(1) 4回ごとに
pppp → 未定
pppq → □
ppq → ■
pq → ○
qp → ●
qqp → □
qqqp → ■
qqqq → 未定
とすると、未定率は 1/8,
T_1 = 22/7 = 3.143
(2) 8回ごとに
pppp pppp → 未定
pppp pppq → △
pppp ppq → ▲
pppp pq → △
pppp qp → ▲
pppp qqp → △
pppp qqq → ▲
pppq → □
ppq → ■
pq → ○
qp → ●
qqp → □
qqqp → ■
qqqq ppp → △
qqqq ppq → ▲
qqqq pq → △
qqqq qp → ▲
qqqq qqp → △
qqqq qqqp → ▲
qqqq qqqq → 未定
とすると、未定率 1/128
T_2 = 394/127 = 3.1023622 >>274
2^k 回目に
p・・・・p q・・・・q
q・・・・q p・・・・p
の出る確率が等しいことを利用すれば、
2^k -1 回目には 全p、全q 以外はすべて決着する。
2^k 回目も同じ。 ■ このスレッドは過去ログ倉庫に格納されています