面白い問題おしえて〜な 28問目
■ このスレッドは過去ログ倉庫に格納されています
>>398 kの小さいとこ分けるのはやったんだけどなぁ。 まぁやってみます。 ところで出題者さんに質問。 この誤差項のx^(10/21)の肩の数字はいくらでも小さく採れるんですか? だめだ、計算ミスがある。 ここまで書いてしまったが、すまんw >>400 や、今解答として用意してる計算のしかたであれば、最善のパラメーターのとり方でこの結果。 もっと和のとり方を工夫したら改善できるかもだけども >>403 そうなんですか。 むずいなぁ。 今のとこのスレの流れ的にいい線いってます? 普通に改善できた…でもパラメータ変えて誤差項の指数小さくできるかはっきりしないし問題は変えないことにする (もし小さくできたとしてもややこしくなるだけだし変えないつもりだけど) >>404 うーん、フーリエ展開から攻めるのはちょっとオススメしにくい 小数部分をとる関数 {x} に不連続点があるせいで級数が絶対収束しないから、 各フーリエ係数ごとに和をとってから全体を評価しようとするとどうしてもばかでかくなってしまう気がする フーリエ級数いじるの得意じゃないし本当にできないのかとかについては何とも言えないけど 停滞するのもあれだし類題出しときます lim_(n→∞) (1/logn)Σ_(k=1,[logn]) (n/k-[n/k]) は存在するか。 まだ暗算レベルだけど、Σ(k≦x^{1/2})({x/k}^2−{x/k}) だったら、 >>394-399 で失敗した計算が救済できて Σ(k≦x^{1/2})({x/n}^2−{x/n})=(-1/6)x^{1/2}+O(x^{1/3}) あたりのオーダーが言えそうな気がする。 また間違うかもしれないので書かないけどw >>407 もダメだった。 B(t)={t}−1/2と置くと、>>407 の場合、 ∫(x^{1/3},x^{1/2})B(t)B(x/t)dt みたいなのが出てきて、 これのxに関するオーダーが計算できないw どうやら、オイラー・マクローリンで計算すると、{x/n}の難しいところが B(t)に移転してしまい、B(t)の積分計算ができなくなって失敗するっぽい。 >>275 >>384 >>385 ・4次のとき det(A+xE) - det(A-xE) = (a+x)(b+x)(c+x)(d+x) - (a-x)(b-x)(c-x)(d-x) = 2 S_3 x + 2 tr(A) x^3, より tr(A) = {det(A+2E) -2det(A+E) +2det(A-E) -det(A-2E)}/(2・3!) ・5次のとき det(A+xE) -2det(A) + det(A-xE) = (a+x)(b+x)(c+x)(d+x)(e+x) -2abcde + (a-x)(b-x)(c-x)(d-x)(e-x) = 2 S_3 x^2 + 2 tr(A) x^4, より tr(A) = {det(A+2E) -4det(A+E) +6det(A) -4det(A-E) +det(A-2E)}/(4!) ・6次のとき det(A+xE) - det(A-xE) = (a+x)(b+x)(c+x)(d+x)(e+x)(f+x) - (a-x)(b-x)(c-x)(d-x)(e-x)(f-x) = 2 S_5 x + 2 S_3 x^3 + 2 tr(A) x^5, より tr(A) = {det(A+3E) -4det(A+2E) +5det(A+E) -5det(A-E) +4det(A-2E) -det(A-3E)}/(2・5!) ・7次のとき det(A+xE) -2det(A) + det(A-xE) = (a+x)(b+x)(c+x)(d+x)(e+x)(f+x)(g+x) -2abcdefg + (a-x)(b-x)(c-x)(d-x)(e-x)(f-x)(g-x) = 2 S_5 x^2 + 2 S_3 x^4 + 2 tr(A) x^6, より tr(A) = {det(A+3E) -6det(A+2E) +15det(A+E) -20det(A) +15det(A-E) -6det(A-2E) +det(A-3E)}/(2・6!) S_k はk次の基本対称式。 S_1 = tr(A), S_n = det(A), >>275 >>384 >>385 A, E はn次の正方行列とする。 ・nが奇数のとき tr(A) = {1/(n-1)!}Σ[k=0,n-1] (-1)^k C(n-1,k) det{A + (k-(n-1)/2)E}, ・nが偶数のとき tr(A) = {1/2(n-1)!}Σ[k=0,n] (-1)^k {C(n-1,k)-C(n-1,k-1)} det{A + (k-n/2)E}, ただし、C(n-1,n) = C(n-1,-1) = 0 和のとり方を改善してパラメータをとり直した結果、 >>380 の誤差項を O(n^(5/12)・logn) まで改善できたので一応報告 けど予定通り、問題の主張を変えるつもりはなし Σ[k≦√n] sin n/k の評価ができんorz。 >>412 手助けになればいいけど、下の定理2.1.6を使えば Σ_(k=√n) sin(n/k) = O(n^(1/3)) まで落とせそう https://spectrum.library.concordia.ca/978881/ Theorem2.1.6 (2nd derivative test) fは区間[a,b]上で二階連続的微分可能であり、c>1 であって 0<λ≦f''(t)≦cλ (for∀t∈[a,b]) が成り立っているとする。この時、 Σ_(a<k≦b) e^(2πif(k)) = O_c( (b-a)λ^(1/2) + λ^(-1/2) ).□ 具体的には m を正の整数(この場合およそ (√n)/(2π) )として、j=0,1,… に対して a_j = m・2^(-j-1), b_j = a・2^(-j) と定めて、 f(x)=N/x として各区間 [a_j,b_j] に対して定理を適用する訳なんだけど、 この場合 j の値にかかわらず c=8 で一様にとれるから、j=0,1,…,r で足し合わせても同じ implied constant で抑えられる。 あとは r の値をうまく調整すればOK >>413 sin 2πn/k はうまくいきました。 でも本丸は∫ a*cos(2πax)/x dxなんですよね〜。 こいつがO(1/a)とかならうまくいくし、数値実験てきには成立してそうなんだけどむずい。 やっぱりこりゃノーヒントじゃ無理だ。 >>378 さんヒントお願いします。 1時間に2本の列車があり、8:00 8:45 9:00 9:45 10:00 10:45 ...という風にダイヤが組まれている。 ランダムに駅に行ったときの待ち時間の期待値はいくらか? >>414 ほい (補題)h/q (q>0) は既約分数であり、k=1,2,…,q の時実数 r(k) の絶対値は E 以下であるとする。 この時、任意の実数 a について次が成り立つ: |Σ_(k=0,q-1) ({hk/q + a + r(k)} - 1/2)| ≦ 3qE + 3. (ただし特にことわらなければ {x} は x の小数部分を表すものとする) (∵)σ(k) := [q{hk/q + a}] は集合 {0,1,…,q-1} 上の全単射であるから、 ε(k) := {hk/q + a} - σ(k)/q ∈ [0,1/q) とおけば Σ_(k=0,q-1) {hk/q + a + r(k)} = Σ_(k=0,q-1) {σ(k)/q + ε(k) + r(k)} = Σ_(k=0,q-1) {(k + 1/2)/q + r'(k)}. (σ(k) を k で置き換え。ただし |r'(k)| ≦ E + 1/(2q) ) ここで、r'(k)=0 (for k=0,1,…,q-1) の時この和が q/2 に等しくなることから、 | Σ_(k=0,q-1) {(k+1/2)/q + r'(k)} - {(k+1/2)/q} | ≦ 3qE+3 を示せばよい。そのためには、区間 [k/q - E, (k+1)/q + E] が関数{x}の不連続点(つまり整数)を通過する k とそうでない k に Σ を分けて、 それぞれを評価すればよい。詳細は略(突然の飽き)□ >>294 ■@^2+CでもP1stは求められる ((n(n+1)/2)-1)^2+{4(n-1)^3+6(n-1)^2-4(n-1)-3+3(-1)^(n-1)}/48 計算知能で@^2+Cを入力すると P1st ={12n^4+28n^3-42n^2-52n-3(-1)^n+51}/48 >>418 8:00 8:30 9:00 9:30 10:00 10:30なら、1時間に2本だが最大の待ち時間が30分だぞ。 >>415 1時間に2本だから 18.75分。 最大の待ち時間は 45分。 >>416 ありがとう。 また考えてみます。 Fourier展開みたいな技使ってもダメっぽいね。 コツコツやるしかないのね…… >>415 1時間に2本だから{30 - M(60-M)/60}分。 最大の待ち時間はM分。 東京駅からのぞみ号で朝8時から9時に出発する(9時発も可)。 無作為に選んだ8時台の時間に出発ホームに到着したとすると平均の待ち時間は何分か? 以下が東京8時台発のぞみ号の時刻表である。 8:00 8:10 8:13 8:20 8:23 8:30 8:40 8:47 8:50 9:00 (0+9+8+7+6+5+4+3+2+1+0+2+1+0+6+5+4+3+2+1+0+2+1+0+6+5+4+3+2+1+0+9+8+7+6+5+4+3+2+1+0+6+5+4+3+2+1+0+2+1+0+9+8+7+6+5+4+3+2+1+0)÷61 =207÷61 =3.39344262 ≒3.4(分) 3分24秒 前>>425 >>425 面積計算して平均したら 3.95分=3分57秒になった。 http://i.imgur.com/nA0WRkX.jpg tt=c(0,10,13,20,23,30,40,47,50,60) # time table x=diff(tt) sum(x^2/2)/sum(x) http://tpcg.io/59nVsG >>425 Prelude> let tt = [0,10,13,20,23,30,40,47,50,60] Prelude> let diff = zipWith (-) (tail tt) (init tt) Prelude> sum (map (\x -> x^2/2) diff) / sum(diff) 3.95 >>426 レスありがとうございます。 筆算、乙。 0〜60分を1分ごと、0.1分ごと0.01分、0.01分ごとにして計算すると > mean(ct2wt(seq(0,60,by=1))) [1] 3.393443 > mean(ct2wt(seq(0,60,by=0.1))) [1] 3.893511 > mean(ct2wt(seq(0,60,by=0.01))) [1] 3.944343 > mean(ct2wt(seq(0,60,by=0.001))) [1] 3.949434 面積計算の値3.95分に収束するようです。 Rのソース tt=c(0,10,13,20,23,30,40,47,50,60) # time table ct2wt <- function(x){ # clock time to waiting time n=length(tt) if(x<=tt[1]){w8=tt[1]-x }else{ for(i in 1:(n-1)){ if(tt[i]<=x & x<=tt[i+1]){ w8=(tt[i+1]-x) break } }} return(w8) } ct2wt=Vectorize(ct2wt) 分単位でちょうどの時間に着いた時は 待ち時間なしの確率が1/2になるというわけだな ある駅のホームの1番線には1時間ごと、2番線には(1/2)時間ごと、3番線には(1/3)時間ごとに電車が来るようにダイヤを組みたい。 ランダムな時間に駅に着いたときの平均待ち時間を最小にするには、どのようにダイヤを組めば良いか。 ただし、何番線の電車に乗っても向かう方向や停車駅に違いは無いとする。 単純に考えて、以下ぐらいしか思いつかない 3番線 00 20 40 2番線 20/3 110/3 1番線 50 >>432 訂正 最大15分はどうしても開くのかな? 3番線 00 20 40 2番線 05 35 1番線 50 1番線 00 2番線 15 45 3番線 10 30 50 最小5分50秒 00 10 15 30 45 50 00 最大8分20秒 00 20 30 40 00 >>433-434 正解 3番線を00,20,40で固定すれば、対称性から2番線は x,30+x (0≦x≦10) のみを考えればよくて、 x をどうとっても1番線を 50 とするのが最適解(のうちの1つ)であることがわかる。 (より長い空白のど真ん中に入れた方がより平均待ち時間を削減できるから) いつもの顰蹙のプログラミング解 w8 <- function(xy,Print=FALSE){ x=xy[1];y=xy[2] if(x<0|x>20|y<0|y>30)return(Inf) tt=c(0,x,x+20,x+40,y,y+30,60) tt=sort(tt) d=diff(tt) w=sum(d^2/2)/sum(d) if(Print){ print(tt) cat(sum(d^2/2),'/',sum(d)) } return(w) } optim(par=c(0,0),w8,method='Nelder-Mead') # 最小値 > optim(par=c(0,0),w8,method='Nelder-Mead') $`par` [1] 9.999003 14.999925 $value [1] 5.833333 w8(c(10,15),P=T) > w8(c(10,15),P=T) [1] 0 10 15 30 45 50 60 350 / 60[1] 5.833333 optim(par=c(0,0),w8,method='Nelder-Mead',control=list(fnscale=-1)) # 最大値 > optim(par=c(0,0),w8,method='Nelder-Mead',control=list(fnscale=-1)) $`par` [1] 0 0 $value [1] 8.333333 w8(c(0,0),P=T) > w8(c(0,0),P=T) [1] 0 0 0 20 30 40 60 500 / 60[1] 8.333333 細かいことを言えば 1番線 03 2番線 18 48 3番線 13 33 53 でもいいはず。 これも最大値かな 1番線 00 2番線 20 50 3番線 00 20 40 >>431 4番線は1時間に4本電車が来るとしてプログラムに解かせると [[1]] [1] 0 [[2]] [1] 15 45 [[3]] [1] 10 30 50 [[4]] [1] 7.5 22.5 37.5 52.5 待ち時間の期待値は3.333333 >>440 おつ n(≧2)番線に 60*(2k-1)/2n (k=1,2,…,n) 分に来させれば良いと予想したくなるなw ファレイ数列みたいだ しかしそれだと30分に到着する番線が大量発生して非効率そうだ >>441 そんなに単純じゃないみたい。 > densha(c(15,10,7.5,6),P=T) [[1]] [1] 0 [[2]] [1] 15 45 [[3]] [1] 10 30 50 [[4]] [1] 7.5 22.5 37.5 52.5 [[5]] [1] 6 18 30 42 54 155 / 60 [1] 2.583333 よりも、こっちの方が平均待ち時間が少ない。 > densha(c(14,8,6,6),P=T) [[1]] [1] 0 [[2]] [1] 14 44 [[3]] [1] 8 28 48 [[4]] [1] 6 21 36 51 [[5]] [1] 6 18 30 42 54 150 / 60 [1] 2.5 >>442 こっちの方がもっと少なかった。 > densha(c(16,12,8,6),P=T) [[1]] [1] 0 [[2]] [1] 16 46 [[3]] [1] 12 32 52 [[4]] [1] 8 23 38 53 [[5]] [1] 6 18 30 42 54 148 / 60 [1] 2.466667 プログラムでの最適解はこんな値を返してきた。 > optim(par=30/2:5,densha) $`par` [1] 15.967750 11.935738 8.225689 5.999897 至急お願いします 異なる業種間で賃金格差が存在しているかどうかを調査するために、一部上場企業の金融業と製造業から総合職(入社5年目)の社員をそれぞれ100名ずつ無作為抽出したところ、平均賃金は金融業が600万円、製造業が570万円でした。 また、標本標準偏差はどちらも70万円でした。業種間で賃金格差が存在しているどうかを有意水準5%で検定するとき、その結果として正しいものを以下から選びなさい。 A. 金融業の方が賃金が高い B. 製造業の方が賃金が高い C. 金融業と製造業に賃金格差があるとは言えない D. いずれでもない 某テレビ局のプロデューサーX氏は製作番組の視聴率の目標を20%と想定していました。500世帯を対象に調査をしたところ、平均視聴率は15%でした。X氏の製作番組は目標視聴率20%を達成したかどうかを有意水準5%で検定します。 真の視聴率をpとするとき、帰無仮説と対立仮説、および検定結果として正しい組合せを以下から選びなさい。 A. 帰無仮説p=0.20、対立仮説p<0.20、帰無仮説を採択 B. 帰無仮説p=0.15、対立仮説p<0.15、帰無仮説を採択 C. 帰無仮説p=0.20、対立仮説p<0.20、帰無仮説を棄却 D. 帰無仮説p=0.15、対立仮説p<0.15、帰無仮説を棄却 E. いずれでもない サイコロを300回投げたところ、そのうち60回で1が出ました。このサイコロに歪みがないかを有意水準5%で検定します。 サイコロを1回投げたとき1が出る確率をpとするとき、帰無仮説と対立仮説、および検定結果として正しい組合せを以下から選びなさい。 A. 帰無仮説p=1/6、対立仮説p≠1/6、帰無仮説を棄却 B. 帰無仮説p>1/6、対立仮説p=1/6、帰無仮説を棄却 C. 帰無仮説p<1/6、対立仮説p>1/6、帰無仮説を採択 D. 帰無仮説p=1/6、対立仮説p≠1/6、帰無仮説を採択 E. いずれでもない >>444 > T.test=function(n1,n2,m1,m2,sd1,sd2){ + SE12=sqrt((1/n1+1/n2)*((n1-1)*sd1^2+(n2-1)*sd2^2)/((n1-1)+(n2-1))) + T=(m1-m2)/SE12 + 2*pt(abs(T),n1-1+n2-1,lower.tail = FALSE) + + } > T.test(100,100,600,570,70,70) [1] 0.002767864 >>444 > kinyu=scale(rnorm(100))*70+600 > seizo=scale(rnorm(100))*70+570 > t.test(kinyu,seizo,var.equal = TRUE) Two Sample t-test data: kinyu and seizo t = 3.0305, df = 198, p-value = 0.002768 alternative hypothesis: true difference in means is not equal to 0 95 percent confidence interval: 10.47802 49.52198 sample estimates: mean of x mean of y 600 570 > t.test(kinyu,seizo,var.equal = TRUE,alt='greater') Two Sample t-test data: kinyu and seizo t = 3.0305, df = 198, p-value = 0.001384 alternative hypothesis: true difference in means is greater than 0 95 percent confidence interval: 13.64024 Inf sample estimates: mean of x mean of y 600 570 答は A >>445 前半 > binom.test(0.15*500,500,0.20,alternative = 'less') Exact binomial test data: 0.15 * 500 and 500 number of successes = 75, number of trials = 500, p-value = 0.002383 alternative hypothesis: true probability of success is less than 0.2 95 percent confidence interval: 0.0000000 0.1788032 sample estimates: probability of success 0.15 答はC >>445 後半 > binom.test(60,300,1/6) Exact binomial test data: 60 and 300 number of successes = 60, number of trials = 300, p-value = 0.1216 alternative hypothesis: true probability of success is not equal to 0.1666667 95 percent confidence interval: 0.1562313 0.2498044 sample estimates: probability of success 0.2 帰無仮説は棄却できない。 帰無仮説を不採択だから、答はE >>445 447-450 この問題で答えがEなんてありえるの? >>451 キム仮説は棄却するものであって採択するものではない。 >>452 どういうことですか? 棄却されないという言い方しないと不正解だという意味? あ、ほんとだ。帰無仮説って採択しちゃいけないんですね。 y=f(x) (0≦x≦a, f(x)≦0, f(0) = f(a) = 0)であらわされる滑り台上をボールを転がす運動を考える。 ただし、摩擦、空気抵抗などは無視してボールは重力とすべり台の面からの垂直抗力のみをうけて運動するものとする。 (0,0)にボールを静かにおいて滑り台を転がせ、(a,0)まで運動させるとき、その所要時間が最小となる曲線はなにか? また東京ー大阪間の距離を400km、重力加速度を9.8m/s^2としたときの所要時間はおよそいくらか? とある数学読み物で見つけた記事より。 当方答えのみ知っております。 導出の方法など知らないのでそれは自己採点でおながいしますw 有名問題だが、地球を球体とした場合はサイクロイドにはなんないと思うぞい >>456 そこは気になったんですが元記事通りの文章で。 今は400kmは地球が球状であることは無視でおながいします。 >>380 最後の手段でズルしちゃうけど、剰余項は少なくとも O(n^(131/416+ε)) (ε>0は任意)まで改善できるはず。 ただし dirichlet divisor problem を経由するのでとてもズルイw まず、nの約数の総和をd(n)とするとき、 Dirichlet hyperbola method により、1以上の実数xに対して Σ(1≦n≦x)d(n)=2Σ(1≦n≦x^{1/2})[x/n]−[x^{1/2}]^2 が成り立つ。 Σ(1≦n≦x^{1/2})[x/n]=Σ(1≦n≦x^{1/2})(x/n)−Σ(1≦n≦x^{1/2}){x/n} なので、お目当ての Σ(1≦n≦x^{1/2}){x/n} が出てきて 2Σ(1≦n≦x^{1/2}){x/n}=2xΣ(1≦n≦x^{1/2})(1/n)−[x^{1/2}]^2−Σ(1≦n≦x)d(n) と表せる。 次に、Σ(1≦n≦x^{1/2})(1/n) に対してオイラー・マクローリンの公式 Σ(a≦n≦x)f(n) =∫(a,x)f(t)dt+(f(a)+(1−2{x})f(x))/2+B_2({x})f'(x)−B_2(0)f'(a)−∫(a,x)B_2({t})f''(t)dt (ただしaは整数でxは実数でB_2(t)=(t^2/2)−(t/2)+(1/12)) を適用して、γ=lim(x→∞)(Σ(a≦n≦x)(1/n)−log(x)) と合わせて計算すれば、 2Σ(1≦n≦x^{1/2}){x/n}=x^{1/2}+xlog(x)+(2γ−1)x+O(1)−Σ(1≦n≦x)d(n) となるはず。一方で、dirichlet divisor problem の最新の結果では Σ(1≦n≦x)d(n)=xlog(x)+(2γ−1)x+O(x^θ), infθ≦131/416 となっているので、 2Σ(1≦n≦x^{1/2}){x/n}=x^{1/2}+O(1)−O(x^θ)=x^{1/2}+O(x^θ), infθ≦131/416 となって、目標の剰余項 O(n^(131/416+ε)) (ε>0は任意)になる。 ちなみに、逆の計算もできて、 Σ(1≦n≦x^{1/2}){x/n}=(1/2)x^{1/2}+O(x^α) が成り立つなら Σ(1≦n≦x)d(n)=xlog(x)+(2γ−1)x+O(x^α) も成り立つ。よって、>>380 の剰余項はdirichlet divisor problemの剰余項と 本質的に同じものになる。そして、dirichlet divisor problemの剰余項では infθ≧1/4 が成り立つらしいので、>>380 の剰余項もそこまでが限界になる。 ぴったり infθ=1/4 が成り立つかは未解決問題らしい。 dirichlet divisor problemにおけるO(x^θ)の変遷はwikipediaに年表が載っていて、 最初にO(x^{1/2})があって、次の更新は1904年で、このときはO(x^{1/3}log x)が得られている。 一応、この時点で>>411 よりも精度が高い。該当する論文は、よく分からないけどたぶんこれ。 sur une fonction transcendante et ses applications a la sommation de quelques series sur une fonction transcendante et ses applications a la sommation de quelques series(suite) どちらも非常に長い上に、ゼータ関数を経由していて何をやっているのか全然分からん。 最初の更新がこんな高度なレベルってのが信じられんw 別の見方をすると、>>380 や>>411 ならO(x^{1/3}log x)には及ばないものの非自明な更新が 初等的に得られるということでもある。 問題(第1種情報処理技術者試験・平成元年度春期午前問17を改題) ある医院では、患者が平均10分間隔でポアソン到着にしたがって訪ねてくることがわかった。 医者は1人であり、1人の患者の診断及び処方にかかる時間は平均8分の指数分布であった。 設問1 患者が待ち始めてから、診断を受け始めるまでの「平均待ち時間」を求めなさい。 >>458 >Dirichlet hyperbola method なんかすごいのが出てきた。 こんなんがあるんだ! >>458 あかん。のっけからわからん。 Dirichlet hyperbola method って https://en.wikipedia.org/wiki/Dirichlet_hyperbola_method ですよね? このf,g,hに何をapplyしたら Σ(1≦n≦x)d(n)=2Σ(1≦n≦x^{1/2})[x/n]−[x^{1/2}]^2 になるんですか? あ、わかった。g=h=1、f(x) = d(x)だ。なるほろ。 となると今度は>>380 の出題者さんの難しい論文を引用しないでも済む方法が聞きたい。 おながいします。 >>458-461 ふぁっ!? そんなもんがあったのか…勉強になるわ、後でじっくり読もう 一応 >>380 の解答載せるけど、だいぶゴリッゴリの力ずくでそれ程有意義とも思えんけどまあ許してちょ… あとリクエストにおこたえしてガバガバながら一番最後以外の細かい係数も出してみた 実数 δ, δ', β, c を 0<δ/2≦β<δ<δ'<1, 3δ'≦1+δ, 0<c≦δ-β を満たすものとして任意に固定する。 (パラメータを最適化したら δ'=1/3, δ=1/6, β=c=1/12 となるから先に代入して読んでいっても可) n を正の整数とする。各正の整数 r≦n^(δ'-δ) に対して集合 J_r を J_r := {mは0以上の整数| r ≦ 1 + m/(n^δ) < 1+r } と定める。また、各 m∈J_r に対して集合 I_m を I_m := {kは2以上の整数| 1+m/(n^δ) ≦ n/(k(k-1)) < 1+(m+1)/(n^δ)} と定める。以降、r と m は上に示された範囲のみを動くものとする。 まずは I_m の元の個数 |I_m| を評価したい。I_m の条件式を整理すると (1/2)*(1+√(1+4n*(1+(m+1)/(n^δ))^(-1))) < k ≦ (1/2)*(1+√(1+4n*(1+m/(n^δ))^(-1))) となるから、この範囲の k の個数を考えると |I_m| ≦ 1 + √(n*(1+m/(n^δ))^(-1)) - √(n*(1+(m+1)/(n^δ))^(-1)) ≦ 1 + (√n)*(1/(n^δ))/(2*(1+m/(n^δ))^(3/2)) ≦ 1 + (1/2) * n^(1/2 - δ) * r^(-3/2) ≦ (3/2)*n^(1/2-δ)*r^(-3/2) (∵ 1/2-δ-(3/2)(δ'-δ)≧0 ) =: L_r. ディリクレのディオファントス近似定理から、各 m について |m/(n^δ) - p/q| ≦ 2/(qn^β) ((p,q)=1, 1≦q≦n^β) …(☆) を満たす整数 p,q が存在する。 また、逆に q<n^β を固定したときに(☆)を満たす p が存在するような m∈J_r の個数は、 ≦ φ(q)*(2+2(n^δ)/(qn^β)) (φはオイラーのトーシェント関数) ≦ 2(q+n^(δ-β)). また、そのような m について n/k = n/k_0 + (1+m/(n^δ))(k-k_0) + ψ~(k) (for∀k∈I_m. ただし k_0:=min(I_m)) とおくと |ψ~(k+1)-ψ~(k)|≦n^(-δ) が成り立つが、これより n/k = n/k_0 + (1+(p/q))(k-k_0) + ψ(k) (for∀k∈I_m) とおくと |ψ(k+1)-ψ(k)|≦n^(-δ)+2/(qn^β) が成り立つ。ゆえに、>>416 の補題から Σ_(k∈I_m) ({n/k}-1/2) ≦ [|I_m|/q]( 3q*(q/(n^δ) + 2/(n^β)) + 3 ) + q (∵q個の連続する整数ごとに和をとる。あぶれる項はq以下) ≦ 3*L_r*(q/(n^δ) + 3/q) + q. ここで、J_r を2つの集合 J'_r := {m∈J_r| q≦n^c ととれる }, J''_r := {m∈J_r| q≦n^c ととれない } に分割すると、 |Σ_(m∈J'_r) Σ_(k∈I_m) ({n/k}-1/2)| ({x}はxの小数部分) ≦ Σ_(q=1,[n^c]) 2(q+n^(δ-β))*(3*L_r*(q/(n^δ)+3/q)+q) ≦ Σ_(q=1,[n^c]) 4(n^(δ-β))*(12(L_r)/q + q) (∵c≦δ-β) ≦ 48*L_r*n^(δ-β)*(1+clogn) + 4n^(δ-β+2c). また、 |Σ_(m∈J''_r) Σ_(k∈I_m) ({n/k}-1/2)| ≦ Σ_(m∈J''_r) (12(L_r)/(n^c) + n^β) ≦ 12*L_r*n^(δ-c)+n^(δ+β). 以上から、 |Σ_(m∈J_r) Σ_(k∈I_m) ({n/k}-1/2)| ≦ (上二つのJ'_r,J''_rについての評価式の和). この評価式を r=1,2,…,[n^(δ'-δ)] について足し合わせれば、 Σ_(r=1,[n^(δ'-δ)]) Σ_(m∈J_r) Σ_(k∈I_m) ({n/k}-1/2) ≦ 72ζ(3/2)*n^(1/2-β)*(1+clogn) + 4n^(δ'-β+2c) + 18ζ(3/2)*n^(1/2-c) + n^(δ'+β). また、k=1,…,[√n] のうち、このΣで k の項が足されていないようなものの個数は ≦ 1+n^((1/2)(1+δ-δ')) であることがわかる。ゆえに、 |Σ_(k=1,[√n]) {k/n}-(1/2)| ≦ (上二つの評価式の和)+1. (最後の +1 は整数 k>[√n] の項で足された分) δ'=1/3, δ=1/6, β=c=1/12 と定めることにより |Σ_(k=1,[√n]) ({n/k}-1/2)|=O(n^(5/12)*logn) がわかる。□ >>468-470 乙です。 こっちは、剰余項を考えないバージョンの lim(x→∞)x^{−1/2}Σ(k≦x^{1/2}){x/k}=1/2 が一般的な形で証明できたかもしれない。使うのは>>413 で、m∈Z−{0}のときは lim(x→∞)x^{−1/2}Σ(k≦x^{1/2})e^{2πimx/k}=lim(x→∞)x^{−1/2}O(x^{1/3})=0 が成り立ち、m=0 のときは lim(x→∞)x^{−1/2}Σ(k≦x^{1/2})e^{2πimx/k}=1 が成り立つので、あとは Weyl's criterion の手法を機械的に真似すればいい。 こうすると、より一般的に、リーマン可積分な任意の f:[0,1]→R に対して lim(x→∞)x^{−1/2}Σ(k≦x^{1/2})f({x/k})=∫(0,1)f(t)dt が示せるはず。例のごとく間違ってる可能性もあるので、詳しくは書かないけどw 有名なのできっと既出だとは思いますが、すごくお気に入りなのでぜひ紹介させてください。 ドラゴンの目の色は、赤か緑のどちらかである。 ドラゴンは不死身だが、もし自分の目の色が緑だと知ってしまった場合、そのドラゴンは日付が変わると同時にトカゲに変身してしまう。 だからドラゴンたちは決して鏡を見ないし、お互いの目の色の話もしないのだ。 ところで、ある島にはドラゴンが100頭住んでいて、その目はすべて緑色である。 ここを訪れたある旅人は去り際に、見送りに来た100頭のドラゴン全員に聞こえるようにこう言った。 「この島には少なくとも一頭、緑の目のドラゴンがいる」 このあと、この島で何日後に、何が起こるだろうか。 ただしドラゴンたちは十分に聡明で、もしあるドラゴンがトカゲに変身したとき次の日にはそのことを皆が知ることになるものとし、 100頭のドラゴンは互いに顔見知りであり自身以外の99頭が緑の目をもつことを知っているものとし、 この島にドラゴンは出入りしないものとする。 不思議だなこれ 寝る。 次の日n頭中の誰もトカゲになってないなら、 どうn-1頭をとってもその中に少なくとも1頭緑目がいることになる。 適当にn-1頭が集まって「この中に少なくとも1頭緑目がいる」と宣言する。しなくても皆気付いてるけど。 寝る。 次の日集まったn-1頭中の誰もトカゲになってないなら、 その中からどうn-2頭をとってもうち少なくとも1頭は緑目がいることになる。 適当にn-2頭が集まって「この中に少なくとも1頭緑目がいる」と宣言する。しなくても皆気付いてるけど。 以下略 一方で「島には少なくとも1頭緑目がいる」という旅人の言葉は 全てのドラゴンにとって既知の事実だし、 それが全てのドラゴンにとって既知の事実だということも皆が知っているし、 それが全てのドラゴンにとって既知の事実だということも皆が知っているということも皆が知っている。 旅人の言葉は何の情報を与えてドラゴンの推論エンジンを始動したのか? >>471 の方針のもとで剰余項ありのケースを考えたら、 C_0^∞関数で近似して普通に剰余項が出たっぽい。 f:[0,1]→Rは2階微分可能で、f '' ∈L^2 が成り立つとする。 このとき、α=1/3に対して Σ(k≦x^{1/2})f({x/k})=x^{1/2}∫(0,1)f(t)dt+O(x^{(2/5)α+(3/10)}) が成り立つ。 残念ながら、O(x^{5/12}log(x))よりは精度が悪いw >>472 類題をどっかで見たようなと思ったけど、これと同じかな? こっちのほうがイメージしやすそう 100組の夫婦が暮らす村がある。 100人の夫は全員他の家の妻と不倫をしている。 この村のルールでは、妻が夫の不倫を知ったらその夜に夫を殺さなければならない。 妻は他の家の夫が不倫をしていることを必ず見抜くことができるが、 自分の夫の不倫には絶対に気がつかない。 妻たちは全員論理的な思考ができて、かつ他の妻に夫が不倫をしていることを決して言わない。 村を訪れた旅人が「少なくとも一人の夫が不倫をしている」と言った。 その後どうなるか。 見直したけど大丈夫っぽいので、>>471 の詳細を書いてみます。 剰余項つきの>>474 はまた今度。 f:[0,1]→Rに対して S_u(f)=limsup(x→∞)x^{−1/2}Σ(k≦x^{1/2})f({x/k}) S_d(f)=liminf(x→∞)x^{−1/2}Σ(k≦x^{1/2})f({x/k}) と置く。lim が実数として存在するときには S(f)=lim(x→∞)x^{−1/2}Σ(k≦x^{1/2})f({x/k}) とも置く。S(f)が存在することと、 S_u(f)=S_d(f)∈R が成り立つことは同値であり、 そのときS(f)=S_u(f)=S_d(f)∈Rが成り立つ。 fがリーマン可積分なら、S(f)が存在してS(f)=∫(0,1)f(t)dtが成り立つことを示したい。 Weyl's criterion の真似をする(f(x)が特殊な形から出発して一般化していく)。 f(x)=sin(2πkx) (k∈Z) のときは、もしk≠0なら、 >>413 により S(f)=0=∫(0,1) f(t)dt である。 また、k=0のときは S(f)=0=∫(0,1) f(t)dt である。よって、この場合は成立。 f(x)=cos(2πkx) (k∈Z) のときは、もしk≠0なら、>>413 と同じように計算して、 S(f)=0=∫(0,1) f(t)dt である。また、k=0のときは S(f)=1=∫(0,1) f(t)dt である。よって、この場合も成立。 S(f)の線形性により、有限個の sin(2πkx), cos(2πkx) (k∈Z) の R係数の線型結合で表されるg(x)に対しても、S(g)が存在してS(g)=∫(0,1)g(t)dtとなる。 次に、f:[0,1]→R が連続で f(0)=f(1) を満たすときを考える。 この場合、フーリエ展開の理論から、任意のε>0に対して、有限個の sin(2πkx), cos(2πkx) (k∈Z) のR係数の線型結合で表されるg(x)であって sup(x∈[0,1])|f(x)−g(x)|<ε を満たすものが取れる。S(g)=∫(0,1)g(t)dt により、 S_u(g)=S_d(g)=∫(0,1)g(t)dt なので、g−ε≦f≦g+ε (各点) と合わせて S_u(f)≦S_u(g+ε)=S_u(g)+ε=∫(0,1) g(t)dt+ε S_d(f)≧S_d(g−ε)=S_d(g)−ε=∫(0,1) g(t)dt−ε S_u(f)≧S_d(f) となる。また、|∫(0,1)g(t)dt−∫(0,1)f(t)dt|≦εである。よって、 ∫(0,1)f(t)dt−2ε≦S_d(f)≦S_u(f)≦∫(0,1)f(t)dt+2ε となる。 ε>0は任意だったから、この場合も成立。 次に、A⊂[0,1] に対して、1_A:[0,1]→R を 1_A(x)=1 (x∈A), 0 (x∈[0,1]−A) と定義する。 ここでは、I⊂[0,1] は開区間または閉区間または半開区間とする。f=1_I のときを考える。 任意のε>0に対して、折れ線で構成される連続関数 f_1,f_2:[0,1]→R であって f_k(0)=f_k(1) (k=1,2), f_1≦f≦f_2 (各点の意味), ∫(0,1)(f_2(t)−f_1(t))dt<ε を満たすものが簡単に構成できる。S_u(f_k)=S_d(f_k)=∫(0,1)f_k(t)dt なので、 S_u(f)≦S_u(f_2)=∫(0,1)f_2(t)dt≦∫(0,1)f_1(t)dt+ε≦∫(0,1)f(t)dt+ε S_d(f)≧S_d(f_1)=∫(0,1)f_1(t)dt≧−ε+∫(0,1)f_2(t)dt≧−ε+∫(0,1)f(t)dt S_u(f)≧S_d(f) により、−ε+∫(0,1)f(t)dt≦S_d(f)≦S_u(f)≦∫(0,1)f(t)dt+ε となる。 ε>0は任意だったから、この場合も成立。 よって、有限個の 1_I (I⊂[0,1]は開区間または閉区間または半開区間)の R係数の線型結合で表されるg(x)に対しても、S(g)が存在してS(g)=∫(0,1)g(t)dtとなる。 すなわち、任意の階段関数 g:[0,1]→R に対して、S(g)が存在してS(g)=∫(0,1)g(t)dtとなる。 最後に、f:[0,1]→R はリーマン可積分とする。リーマン積分の性質により、 任意のε>0に対して、ある階段関数 f_1,f_2:[0,1]→R が存在して、 f_1≦f≦f_2 (各点の意味), ∫(0,1)(f_2(t)−f_1(t))dt<ε が成り立つ。よって、>>479 と同じ計算で S(f)=∫(0,1)f(t)dt となる。 特にf(x)=xとして、lim(x→∞)x^{−1/2}Σ(k≦x^{1/2}){x/k}=1/2 が成り立つ。□ >>473 解説を読んでもすぐにはピンとこないよね >99日後に分かる >「少なくとも99頭のドラゴンが緑の目をしていること」はみんな知っているよ >これが「旅人がドラゴンに与えた情報」です >>475 今までに 他の家で誰も殺されていないことを全ての妻が知っている、のが前提だよね? >>480 なるほど、求める性質が成り立ってくれるとわかる関数のクラスをどんどん"扱いやすいもの"にしていくという方法か そうすると、2以上のαに対して S'(f)=lim_(x→∞) x^(1/α) Σ_(k=1,[x^(1/α)]) f(k) と定義した時に 同じ議論が成り立つかどうかも、最初の sinkx, coskx についての箇所さえチェックすればいいことになるんかな まあ、これを考えるとなると、一般の多項式についてガウス和チックなこと考えなきゃいけなくて かなり面倒になることが予想される…w ここも興味ある有志にお任せするとしようか 緑目ドラゴン3頭が島で暮らしている。 旅人が「少なくとも1頭は緑目」と言う。 ドラゴンAは考える 「我以下の2頭は緑目」 「論理的に考えて3頭中どの2頭をとっても少なくとも1頭緑目がいる」 「我とドラゴンBのうち少なくとも1頭は緑目」 「見てわかるようにドラゴンBは緑目」 「だがドラゴンBから見ると『論理的に考えて3頭中どの2頭をとっても少なくとも1頭緑目がいる』は成り立たない」 「我が赤目の場合、ドラゴンBからは緑目は1頭しか見えていないのだからな」 「とすれば論理的に考えて」 「皆が緑目であるか、」 「自分だけが赤目であるか、」 「のいずれかであるな」 おしまい。 >>484 >「我以下の2頭は緑目」 我以外、の書き間違えでした。 自分の目の色はわからないので自分と他人とでは情報に対称性がないわけです。 よって「自分から見るとAが帰結されるから他人もAと帰結するはず」とは言えない。 「少なくとも1頭緑目がいる」という既知の情報からは 「自分だけが赤目か皆が緑目のいずれかである」 という既知の事実以上の推論は不可能でした。 @ 既知の情報だから何も起こらない説 A 外部発言がなくても全員が変身する説 信じるか信じないかは、あなた次第 >>473 >適当にn-1頭が集まって「この中に少なくとも1頭緑目がいる」と宣言する。しなくても皆気付いてるけど。 この「皆気付いてるけど」が少なくとも n=3 のときは成り立たないんだよね 3匹の場合でこうかな 1日目のA: 1)我(A)が赤目だと仮定しよう。そのとき、Bは赤目(A)と緑目(C)が見えている。 Bは「a)我(B)が赤目だと仮定しよう。そのとき、Cは赤目(A,B)だけが見えている。 ならば、Cは『緑目が少なくとも一頭いるのだから、我(C)が緑目だ』と考える。 b)我(B)が緑目だと仮定しよう。そのとき、Cは赤目(A)と緑目(B)が見えている。 ならば、Cは『緑目が少なくとも一頭いることからは、我(C)が緑目だとはいえない』と考える。 a)b)から、明日になってCがトカゲになっていたら我(B)は赤目、ならなかったら我(B)は緑目だ」と考える。 2)我(A)が緑目だと仮定しよう。そのとき、Bは緑目(A,C)が見えている。 Bは「緑目が少なくとも一頭いることからは、我(B)が緑目だとはいえない」と考える。 2日目のA: Cはトカゲにならなかった。 1)我(A)が赤目だと仮定しよう。Bは「我(B)は緑目だ」と考える。 2)我(A)が緑目だと仮定しよう。Bは「我(B)は緑目だとはいえない」と考える。 1)2)から、明日になってBがトカゲになっていたら我(A)は赤目、ならなかったら我(A)は緑目だ。 3日目のA: Bはトカゲにならなかった。 我(A)は緑目だ。 >>488 対称性から2日目に結論が出るから、3日目には全員トカゲになっているな >>488 そうするとこの場合はどうなるんだろう。 島に3頭の緑目ドラゴンがいた。 ドラゴンAはある日ふと思った。 「この島には少なくとも1頭の緑目がいる」 もちろんBCも(目で見て)それ(少なくとも1頭緑目がいることを)を知っている、とAは考えている。 >>490 その場合はAの想像の中のBの想像の中のCは「緑目が少なくとも一頭いる」ことは知らない。 ABCが「緑目が少なくとも一頭いる」という知識を共有してないといけない。 >>492 1行目はわかるんだけれども、2行目、 旅人なしでも 少なくとも1頭はいるという知識は共有しているし 共有しているという知識も共有していますよね。 「あなた方の少なくとも1匹は緑目」 =「あなた以外のドラゴンがみな緑目でないなら、あなたは緑目」 「俺達の少なくとも1匹は緑目」からは後者の推論が成り立たない 「俺たちの少なくとも1頭は緑目」 =「俺以外の2頭が赤目なら俺は緑目」 形式的には全く問題なく推論が成り立つ気がするが >>496 すぐに走りだす奴がいないということは三人の帽子は順不同の白白赤か白白白。 つまり白赤が見えてるか白白が見えてる。白赤が見えてるとき人は一般に自分が赤である確率が1/3だから走るはずだ。が、あとの二人が走らないということは白白が見えてるってこった!――そう思ってみんな走った。 ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.5 2024/06/08 Walang Kapalit ★ | Donguri System Team 5ちゃんねる