面白い問題おしえて〜な 28問目
■ このスレッドは過去ログ倉庫に格納されています
じゃトレースがらみで
Aをn次正方行列とするとき、行列Bを
B[i j] =tr(A^(i+j))
で定められるn次正方行列とする。
この時
Aの固有値が全て異なることと det(B)≠0 である事は必要十分である事を示せ。 >>339
訂正
B[i j] = tr(A^(i+j-2))
です。 >>339,340
tr(A^i)はAの固有値のi乗の総和なので、行列BはAの固有値のヴァンデルモンド行列とその転置との積。
したがってBの行列式は差積の2乗つまり判別式。 >>341
素晴らしい!
正解です。簡単すぎてすまソ >>338
m=3、n=2の場合で考える。
別のケースでもいけるけど記述がうるさくなるので。
0〜m^n-1の整数を頂点とし[x/m] ≡ y (mod m^n/m)の時xからyに→を描いて向き付きのグラフGを作る。
このグラフが全ての点をちょうど一回づつ通る向き付きのループを持つ事を示せば良い。
隣接行列をfromが横方向、toが縦方向に来るようにとる。
また、見やすいようにfromは最下位桁以外が一致するものを固めてならべ、toは最上位桁以外が固まるように並べる。
今の場合なら例えば以下のようになる。
. 00 01 02 10 11 12 20 21 22
00 1 1 1
10 1 1 1
20 1 1 1
01 1 1 1
11 1 1 1
21 1 1 1
02 1 1 1
12 1 1 1
22 1 1 1
このなかの1から1をm^n個選びその表す部分グラフが連結成分数が1の向き付きループになるものを見つければ良い。
各行、各列からちょうど一個づつ選べば向き付きループの有限和にはなる。
例えば対角線上の1を全て選べば良い。しかしそれだと連結成分が複数出てくるので繋げていく。
まず左上のm×mを必要なだけ挿げ替えてそのブロックにあるループが成分一個になるようにする。
上の例なら
. 00 01 02 10 11 12 20 21 22
00 ○
10 ○
20 ○
01 ○
11 *
21 △
02 ○
12 △
22 ※
となる。
この時点で00→20→02→10→01→00、11→11、12→21→12、22→22の4成分。
ここで右上のブロックを占有するループの中の→のtoは最下位桁以外を無視して0〜m^n/m-1までの全ての数がでるから各ブロックを少なくとも1回づつ通過する。
よって先の様な挿げ替えを再び行って成分数を1にできる。 訂正
×まず左上のm×mを必要なだけ挿げ替えて
○ まず左上の(m^n/m)×(m^n/m)を必要なだけ挿げ替えて
訂正ついでにも少し補足。
挿げ替えとはA→B、C→DをA→D、C→Bと→を選び直す事。
この作業を何回か繰り返せば同じブロックに属する→は全て同一成分に出来る。
今の例なら
A→B→‥→A、C→D→‥→Cという2成分が
A→D→‥→C→B→‥→Aとつながって1成分減る。 あ、いらん訂正した。>>344であってます。
>>345は無かったことに。
同一ブロックに入るのはたとえばm=3, n=5ならたとえば
fromが02430,02431,02432,02433,02434,
toが. 00243,10243,20243,30243,40243
であるm×m個。
このfromがm個、toがm個のm×m通りは全て→で結ばれていて自由に挿げ替えられる。 >>346
スレ汚しすまん。まだ間違ってる。
挿げ替えのアルゴリズムは>>344では不十分。
以外に訂正。
とりあえず、全ブロックの→を挿げ替えで同一成分にする。
これで十分。
もしこれで2成分以上あったとする。
しかし元のグラフは連結なので2成分X YとXの通過する点とYの通過する点を結ぶ→がみつかる。
実際異なる連結成分を結ぶパスで長さ最小のパスを取ればそれは→である。
たとえばm=5, n=5で
X: …→02432→30243→…
Y: …→02431→10243→…
の02432と10243の様な組みである。
そしてこの部分は同一ブロックに属する。
しかし同一ブロックの→は全て同一連結成分になる様に取っているのでそれらが異なる連結成分に属するのは矛盾。 >>343
[1] (20点)
aを2以上の整数とし、有理数bを b = 1 + 1/a により定める。自然数nに対して、
S_n = Σ[k=1,n] k^(1/a),
とおく。ただし、k^(1/a) とはa乗するとkになる正の実数のことである。
以下の設問に答えよ。
(1) lim[n→∞] S_n / n^b = 1/b を示せ。
(2) lim[n→∞] (S_n - (n^b)/b)= ∞ を示せ。
[4] (20点)
nを自然数とする。整数kに関する次の条件(C),(D)を考える。
(C) 0≦k<n.
(D) k/n ≦ 1/m < (k+1)/n を満たす自然数mが存在する。
条件(C),(D)を満たす整数kの個数を T_n とする。以下の設問に答えよ。
(1) T_50 を求めよ。
(2) 次の極限値を求めよ。
lim[n→∞]log(T_n)/log(n)
http://suseum.jp/gq/question/2951 >>321
x - 2/3 = X,
とおくと
f(x) = x^4 -(8/3)x^3 -2x^2 +8x +1
= X^4 -(14/3)X^2 +(80/27)X +(131/27)
= (X^2 +f)^2 -(14/3 +2f)(X-g)^2,
となり、2次因子に分解する。
2(14/3 +2f)g = (80/27),
ff -(14/3 +2f)gg = (131/27),
より
f^3 +(7/3)f^2 -(131/27)f -(9053/729) = 0,
g^3 -(2/5)g^2 +(7/3)g -(10/27) = 0,
f = (-7 +6(13+2√11)^{1/3} +6(13-2√11)^{1/3})/9 = 2.256314207884
g = (2 +3(4+25√11)^{1/3} -3(-4+25√11)^{1/3})/15 = 0.161393818172 >>349 (続き)
f(x) = (x^2+2ax+b) (x^2+2cx+d)
とする。
x^2 +2ax +b = X^2 +2√(7/6 +f/2)・(X-g) +f,
判別式 a^2 -b = (7/6 +f/2) -f +2g√(7/6 +f/2)
= (7/6 -f/2) +20/[27√(7/6 +f/2)]
= 0.5274900867207
x^2 +2cx +d = X^2 -2√(7/6 +f/2)・(X-g) +f,
判別式 c^2 -d = (7/6 +f/2) -f -2g√(7/6 +f/2)
= (7/6 -f/2) -20/[27√(7/6 +f/2)]
= -0.4504709612713
(a^2 -b)(c^2 -d) = (7/6 -f/2)^2 -(80/27)^2/(7/6 +f/2)
= -(4/3)[10 - (13+2√11)^{2/3} - (13-2√11)^{2/3}]
= -0.237618966426144
< 0, 問題 : 4 リットルと 3 リットルの容器を使って 2 リットルの水を測るにはどうすればいい?
これが最短手順でいい?
[(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3),(2,0)] [(0,0),(0,3),(3,0),(3,3),(4,2),(0,2)] は禁止? >>350 訂正
(a^2 -b)(c^2 -d) = (7/6 -f/2)^2 - (20/27)^2/(7/6 +f/2)
= (1/3)[10 - (13+2√11)^{2/3} - (13-2√11)^{2/3}]
= -0.237618966426144
< 0,
分かスレ448-819,827 10Lの容器いっぱいに油が入っています。7Lの容器と3Lの容器を使って、この油を5Lずつに分けます。どのような分け方がありますか。
https://katekyo.mynavi.jp/juken/know-how/7993
何でグラフで解けるんだろ? >>355満タン(10)(7)(3)の三つの容器をこの並びで置き、
初め(10)(0)(0)入っているのを移していく
→(3)(7)(0)
→(3)(4)(3)
→(6)(4)(0)
→(6)(1)(3)
→(9)(0)(1)
→(2)(7)(1)
→(2)(5)(3)
→(5)(5)(0)
8回で二分できた。 >>344-347
だいたい考えてた解答と一緒です。
自分のは、1234→2341→3412→4123→1234のようなサイクルをつないでいくやり方でした。
探索なしで生成する方法はないんでしょうかね? 前>>356両手ありで空にしたとこにすぐ入れるのをノーカンにするなら7回だけど、
(10)(0)(0)
→(3)(7)(0)
→(3)(4)(3)
→(6)(4)(0)省略可
→(6)(1)(3)
→(9)(1)(0)省略可
→(9)(0)(1)
→(2)(7)(1)
→(2)(5)(3)
→(5)(5)(0)
片手だと9回か。 >>350 >>353
(a^2 -b)(c^2 -d) = (7/6 -f/2)^2 - (20/27)^2/(7/6 +f/2)
= (1/3) [(13+2√11)^{1/3} - (13-2√11)^{1/3}]^2
= -0.237618966426144
< 0, >>359
■式を展開してゆくと
(a^2-b)(c^2-d)<0
a^2c^2-a^2d-c^2b+bd<0
a^2c^2-(a^2d+c^2b)+bd<0
a^2c^2-(a+c)(ad+bc)+ac(b+d)+bd<0
ac(ac+b+d)-(a+c)(ad+bc)+bd<0
ac(b+4ac+d)-3a^2c^2-(a+c)(ad+bc)+bd<0
a+c=-4/3, b+4ac+d=-2, ad+bc=4, bd=1
は作ることができたが
最終的に9a^2c^2+6ac-19>0となる >>357
え?自作問題なんですか?
よくこんなの思いつきましたね!すっげ!
とりあえず>>344-347みたいな解答できた後、明示的な解が作れないか考えたけど出来ずorz。
普段ならパソコンに探索させてやってみるんですが、今パソコン壊れててそれもできず。
少なくともm=2とかに限定すれば出来て不思議なさそうなんですけどねぇ? >>355
こうなると人間技では無理だな。
100Lの容器いっぱいに油が入っています。51Lの容器と49Lの容器を使って、この油を50Lずつに分けます。どのような分け方がありますか。 無限にも一般化できそうねこれ 既に解答あるかどうか知ってる訳じゃないけど
n を正の整数とする時、関数 f:Z→Z であって、F:Z→Z^n;F(x)=(f(x+1),f(x+2),…,f(x+n)) が全単射になるものは常に存在するか? De Bruijn torus みたいに多次元への一般化も考えられてるみたいだし、更にこんな一般化もできる ごっちゃごちゃやけど
m, n_1, n_2,…, n_m を正の整数とし、N=n_1*n_2*…*n_m とおく。この時、関数 f:Z^m→Z であって
F:Z^m→Z^N; F(x) = ( f(x+(1,1,…,1)), f(x+(1,1,…,2)), …, f(x+(n_1,n_2,…,n_m)) )
が全単射になるものは常に存在するか? とりあえず>>364 のページには ”こうすりゃできる” というのが載ってはいるが、なぜそれで出来るサッパリわがんね。
試しにm=n=3で手計算でやってみると
aaabaacabbabcacbaccbbbcbccc
……できてる……すっげ! 18: [] 2018/11/21(水) 02:38:57.162 ID:QyQDf8nQ0
これ頼む
https://i.imgur.com/AE4TWZ7.jpg >>368
刺身にタンポポの花を乗せるような単調作業は、このスレにはふさわしくない。 >>365
文字が整数ではなく自然数だったら、つまりf:N→N, F:N→N^nだったら、
n=2の場合、0 01 1 0212 2 031323 3 0414…
n=3の場合、0 001011 1 002012022102112122 2 003013…
のようにすればよさそうだけど、n≧4の場合はどうすればいいんだろう? >>368
計算機でやれば一瞬……打ち込むのに1時間程かかるwww >>374
左上から
横7cm → 縦5cm → 横4cm → 横8cm → 縦9cm → 横5cm,
下3段の縦の比
右端から 4:4:8 → 4:4:9 → 8:9 → 8:4:5 →→ 7:7:5:4:5
横の比 20:35:21:(5cm) >>363のwikiに載ってる方法
0 ≦ x ≦ m^n-1をみたす整数を(必要なら上位を0で埋めて)m進数n桁表示で表示したとき、その最上位以外をひとつずつ上位に移し、最高位を最下位に移す写像を f とする。
このとき f は0 ≦ x ≦ m^n-1をみたす整数の全体 S の置換を与える。
この置換を互いに可換な循環置換の積 f = g[1]g[2]…g[t] で表す。
ただしg[i] = (n[i1]…n[ij]) n[i1]が最小限と表示するときワードw[i] = n[i1]…n[ij]は辞書式順序で昇順であるとする。
n[11]n[12]…をすべてつなげたワードをwとする。
そのワードの各文字をm^(n-1)で割った商で置き換えたワードがde Bruijn sequenceとなる。
--例--
m=3、n=2のとき。
f = (0) (1 3) (2 6) (4) (5 7) (8)
であるから
w = 0 1 3 2 6 4 5 7 8
であり各文字を3^1で割った商に置き換えて
001021222
はde Bruijn sequenceとなる。
……やっと証明わかった。
こんな構成法絶対思いつかん。 実数 x に対して [x] を x の整数部分と定める。この時、次の値を求めよ:
lim_(n→∞) (1/√n)Σ_(k=1,[√n])(n/k-[n/k]) >>378
収束するん?
全然収束してる感ないけど?
*Main> let f n = (/(sqrt n)) $ sum [n/k - (fromInteger $ truncate $ n/k) |k<-[1..(sqrt n)]]
*Main> mapM_ print [f x | x<-[10000..10010]]
0.39775176396203077
0.42960405947242447
0.4414551710047714
0.4733020995001393
0.46515384320018427
0.4370114006470376
0.4688537799785083
0.5106894801475358
0.4425649747743292
0.4843978105580605
0.37630141203414064 じゃあ問題変えよか
次を示せ:
Σ_(k=1,[√n]) n/k-[n/k] = (1/2)√n + O(n^(10/21)) >>380
>>378より主張が強くなってるけどホントに成立するん?
相当収束遅いんかな?
100000000000でもまだ0.01ぐらいの誤差あるけど。
この辺までくると計算誤差かもしれないけど。
もってる R(n)/n^(10/21) の上からの評価値と矛盾してない?
収束してても不思議ない感くらいはあるんだけど。
*Main> mapM_ print [f x | x<-[100000000000..100000000010]]
0.49838288499722044
0.4983868107954477
0.4983780874456663
0.4984167982310302
0.49843969769390706
0.4984309743244439
0.4984601983048952
0.4984957468592659
0.4984870234930951
0.49847830012017674
0.4984695768000378 >>381
誤差項の係数まで出してるわけじゃないから計算一つ一つ追ってくのはしんどくてすぐできそうにないけど、>>380 の右辺を
(√n)・(1/2 + O(n^(-1/42)))
と変形できて、n にそのまま 10^11 入れて n^(-1/42) 計算しても 0.547 くらいになるから、
むしろ >>381 の数値の 1/2 との近さは"良すぎる"くらいだね 言い換えれば >>380 の評価がガバガバすぎるってことなんだけど >>275
> 3次正方行列Aについて、tr(A) を det(Aと単位行列Eの式) の式で表せ。(detの中身は複数種類でも可)
これどうやるんですか? >>384
A の固有値を a,b,c とおくと
det(A+E) + det(A-E) - 2det(A)
= (a+1)(b+1)(c+1) + (a-1)(b-1)(c-1) - 2abc
= 2(a+b+c) = 2tr(A)
でいける >>387
想定してる解答ではそういう複素解析的な技術は使ってないよ
使えるのかどうかはわからないけど、n>n' として n' の時の和が n の時の和の部分和になってる訳じゃないから
今までと同じような方法で臨むのは難しそうな気がする >>388
違うのか…
Σ_(k=1,[√n]) (n/k-[n/k] - 1/2) = O(n^(10/21))
を示せば十分で
x - [x] - 1/2 = -2/πΣ[i] sin(2πix)/i
を使って
Σ_(k=1,[√n]) (n/k-[n/k] - 1/2) = -2/πΣ[k] Σ[i] sin (2πi n/k) / i
で
Σ[i] sin (2πi n/k) / i = Σ [ξ] <sin (2πi n/k), ξ(i)> L(ξ, 1)
でL(ξ,1)を評価するのかなと。
でもこのL(ξ,1)の評価ネットで探してもありそでなさそで……
これむずい。気長にやります。 {x}=x−[x]と定義して、
Σ(1≦k≦x^{1/2}){x/k}=(1/2)x^{1/2}+O(x^{1/3})
が示せた(計算ミスがなければ)。方針は>>389なんだけど、
L関数ではなく、普通にフェイェール核を使う。
あとはオイラー・マクローリン。 すまん、フェイェール核じゃなくてディリクレ核だった。 私も>>389訂正。L(ξ, 1)じゃなくてL(1,ξ)ね。
あとwolframで確かめてみたら
x - [x] - 1/2 = -1/πΣ[i] sin(2πix)/iですね。
https://www.wolframalpha.com/input/?i=plot+-1%2Fpi*(sin(1+x)%2F1%2Bsin(2+x)%2F2%2B+sin(3+x)%2F3%2Bsin(4+x)%2F4%2Bsin(5+x)%2F5%2Bsin(6+x)%2F6%2Bsin(7+x)%2F7%2Bsin(8+x)%2F8%2Bsin(9+x)%2F9%2Bsin(10+x)%2F10)
これ気合で i:1〜10 足したけどもっと賢く入力できないのかな?
ここからオイラーマクローリンで行こうとおもったんだけど
∫[1,∞] a cos (ax)x (x - [x] - 1/2) dx (ただし a = 2πn/k)
の項が出てきて評価ができなかった。
Dirichlet の不連続因子っての使うのかなとも思ったんだけど眠くなってやめた。
積分苦手 orz。 計算が面倒くさすぎるので、使う道具だけ書いておきます。間違ってたらスマン。
m≧0に対して、D_m:R→R を D_m(x)=(sin mπx)/sin πx (x∈R−Z), m (x∈Z) と定義する。
また、f_m=D_{2m+1} (m≧0) と定義する。
基本的な性質の一覧。
D_0(x)=0, D_1(x)=1, D_m(1±x)=D_m(x)=D_m(−x) (x∈R, m≧1)
f_0(x)=1, f_m(1±x)=f_m(x)=f_m(−x) (x∈R, m≧1)
m≧1に対して∫(0,1/2)f_m(t)dt=∫(1/2,1)f_m(t)dt=1/2
m≧1, x∈R に対して Σ(n=1〜m) cos2πnx = −1/2+f_m(x)/2
m≧1, x∈R に対して {x}−1/2=−Σ(n=1〜m) (sin 2πnx)/(πn)+∫(1/2,{x})f_m(t)dt 定義 命題Pに対して、[[P]] ∈ {0,1} を次のように定義する。
[[P]]=0 (Pが偽のとき), 1 (Pが真のとき).
定理1 x∈R に対して lim(m→∞)∫(1/2,{x})D_m(t)dt = −[[x∈Z]]/2.
特に、x∈R に対して lim(m→∞)∫(1/2,{x})f_m(t)dt = −[[x∈Z]]/2.
特に、x∈R に対して Σ(n=1〜∞) (sin 2πnx)/(πn) = 1/2−{x}−[[x∈Z]]/2. 定理2 g:[0,1/2]→Rは[0,1/2]上でルベーグ積分可能であり、g(+0)が存在するとする。このとき、
Clim(m→∞)∫(0,1/2)f_m(t)g(t)dt=g(+0)/2.
ただし、実数列 {a_m}_m に対して Clim(m→∞)a_m=lim(m→∞)(a_1+a_2+…+a_m)/m と定義する。
定理3 a<bとする。g:[a,b]→Rは[a,b]上でルベーグ積分可能であり、n∈[a,b]∩Zのとき、
g(x)はx=nにおいて片側極限が必ず存在するとする。このとき、
Clim(m→∞)∫(a,b)f_m(t)g(t)dt=Σ(n∈[a,b]∩Z) (g(n−0)+g(n+0))/2.
ただし、a∈Z のときは、(g(a−0)+g(a+0))/2 の部分を g(a+0)/2 で置き換える。
また、b∈Z のときは、(g(b−0)+g(b+0))/2 の部分を g(b−0)/2 で置き換える。 定理4(オイラー・マクローリンの公式) a∈Z, b∈R, a<b とする。
f:[a,b]→C はC^1級とする。このとき、任意の実数 x∈[a,b] に対して
Σ(a≦k≦x)f(k)=∫(a,x)f(t)dt+(f(a)+(1−2{x})f(x))/2+∫(a,x)f'(t)({t}−1/2)dt.
定理5(オイラー・マクローリンの公式) a, b∈R, a<b とする。
f:[a,b]→C はC^1級とする。このとき、任意の実数 x∈[a,b] に対して
Σ(a<k≦x)f(k)=∫(a,x)f(t)dt+((1−2{x})f(x)−(1−2{a})f(a))/2+∫(a,x)f'(t)({t}−1/2)dt. Σ(1≦k≦x^{1/2}){x/k}=(1/2)x^{1/2}+O(x^{1/3}) の証明を大雑把に。
x>1として、Σ(1≦k≦x^{1/2}){x/k}=Σ(1≦k≦x^{1/3}){x/k}+Σ(x^{1/3}<k≦x^{1/2}){x/k}
と分解して、まず Σ(1≦k≦x^{1/3}){x/k}=O(x^{1/3}). 次に、m≧1を任意に取って
Σ(x^{1/3}<k≦x^{1/2}){x/k}
=Σ(x^{1/3}<k≦x^{1/2})(1/2−Σ(n=1〜m) (sin 2πnx/k)/(πn)+∫(1/2,{x/k})f_m(t)dt)
=([x^{1/2}]−[x^{1/3}])/2−Σ(n=1〜m)(1/(πn))Σ(x^{1/3}<k≦x^{1/2}) sin 2πnx/k
+Σ(x^{1/3}<k≦x^{1/2})∫(1/2,{x/k})f_m(t)dt (1)
と分解する。 >>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
でもいいはず。 ■ このスレッドは過去ログ倉庫に格納されています