面白い問題おしえて～な 28問目

面白い問題おしえて～な 28問目 at MATH

[前50を表示]
350:１３２人目の素数さん
18/11/17 16:09:42.72 A1Nd7rYy.net
>>328
aについてしか解いてくれてないけど。
虚数解混じってるし。
全部実数になる解あるの？

351:１３２人目の素数さん
18/11/17 16:11:44.94 KDdXvc30.net
>>329
More rootってあるだろ、これ以上はスレチになるからこことは違うところで調べてくれ

352:１３２人目の素数さん
18/11/17 16:11:55.46 A1Nd7rYy.net
あ、いや、ごめんなさい。
実数解ひとつあれば全部実数になる解は自動的にあるな。
あれ？>>320どこ間違ってるんだろう。
パソコンないとこうも手詰まりになるもんだな。

353:１３２人目の素数さん
18/11/17 16:15:18.14 knKRx/Qn.net
>>331
> a^2d=a(4-bc), bc^2=c(4-ad)より
> a^2d+bc^2=4(a+c)-(ad+bc)=-16/3-4
a^2d+bc^2=4(a+c)-ac(b+d)
計算見直すだけだろ

354:１３２人目の素数さん
18/11/17 16:20:26.22 A1Nd7rYy.net
あ、わかった。
お騒がせしました。

355:１３２人目の素数さん
18/11/17 16:22:25.07 UVEx0ybP.net
Wolfram 先生に
factorize x^4-(8/3)x^3-2x^2+8x+1
ってお願いして irreducible factorization 出してもらえば普通に a,b,c,d 構成できるんじゃないの
あと >>320 だけど
a^2d+bc^2=4(a+c)-(ad+bc)=-16/3-4
は計算間違いで本当は
a^2d+bc^2=4(a+c)-(abc+acd)
になって特に何が言える訳でもないと思うよ

356:１３２人目の素数さん
18/11/17 16:25:04.30 js5kwOKA.net
まだやってたのか、NG入れてあぼーんしてたから気づかなんだわ。
数学板の常連は意外と面倒見がいいんだな。

357:１３２人目の素数さん
18/11/17 16:30:49.85 UVEx0ybP.net
解決してた　すまん
未解決だけど投稿します
各項の係数の絶対値が1以下であるような整数係数多項式 f(x)≠0 であって、x^4+x^3+3x^2+x+1 で割り切れるようなものは存在するか。

358:１３２人目の素数さん
18/11/17 16:31:38.43 A1Nd7rYy.net
>>334
ありがとう。
後で気づいた。
お騒がせしました。

359:１３２人目の素数さん
18/11/17 16:41:11.53 pHGjVcYj.net
m種類の文字をm^n個並べた円順列で、連続するn文字の並びがすべて異なるものは常に存在するか？
例：文字0,1の円順列[00011101]中の3文字の並びは 000,001,011,111,110,101,010,100 で、すべて異なる。

360:１３２人目の素数さん
18/11/17 18:50:57.91 A1Nd7rYy.net
じゃトレースがらみで
Aをn次正方行列とするとき、行列Bを
B[i j] =tr(A^(i+j))
で定められるn次正方行列とする。
この時
Aの固有値が全て異なることと det(B)≠0 である事は必要十分である事を示せ。

361:１３２人目の素数さん
18/11/17 18:56:20.25 A1Nd7rYy.net
>>339
訂正
B[i j] = tr(A^(i+j-2))
です。

362:１３２人目の素数さん
18/11/17 19:39:06.00 pHGjVcYj.net
>>339,340
tr(A^i)はAの固有値のi乗の総和なので、行列BはAの固有値のヴァンデルモンド行列とその転置との積。
したがってBの行列式は差積の2乗つまり判別式。

363:１３２人目の素数さん
18/11/17 19:53:18.73 A1Nd7rYy.net
>>341
素晴らしい！
正解です。簡単すぎてすまソ

364:１３２人目の素数さん
18/11/17 23:22:11.01 laGp565a.net
京大理学部特色入試
お暇な方はどうぞ
URLﾘﾝｸ(i.imgur.com)
URLﾘﾝｸ(i.imgur.com)
URLﾘﾝｸ(i.imgur.com)
URLﾘﾝｸ(i.imgur.com)

365:１３２人目の素数さん
18/11/18 01:04:20.36 ZJOO9Eig.net
>>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にできる。

366:１３２人目の素数さん
18/11/18 01:42:47.40 ZJOO9Eig.net
訂正
×まず左上の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成分減る。

367:１３２人目の素数さん
18/11/18 02:05:20.86 ZJOO9Eig.net
あ、いらん訂正した。>>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通りは全て→で結ばれていて自由に挿げ替えられる。

368:１３２人目の素数さん
18/11/18 02:36:13.22 ZJOO9Eig.net
>>346
スレ汚しすまん。まだ間違ってる。
挿げ替えのアルゴリズムは >>344では不十分。
以外に訂正。
とりあえず、全ブロックの→を挿げ替えで同一成分にする。
これで十分。
もしこれで2成分以上あったとする。
しかし元のグラフは連結なので2成分X YとXの通過する点とＹの通過する点を結ぶ→がみつかる。
実際異なる連結成分を結ぶパスで長さ最小のパスを取ればそれは→である。
たとえばm=5, n=5で
X: …→02432→30243→…
Y: …→02431→10243→…
の02432と10243の様な組みである。
そしてこの部分は同一ブロックに属する。
しかし同一ブロックの→は全て同一連結成分になる様に取っているのでそれらが異なる連結成分に属するのは矛盾。

369:１３２人目の素数さん
18/11/18 03:56:43.71 ENzLbcND.net
>>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)
URLﾘﾝｸ(suseum.jp)

370:１３２人目の素数さん
18/11/18 16:54:39.76 ENzLbcND.net
>>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

371:１３２人目の素数さん
18/11/19 00:15:59.14 eL1RQpps.net
>>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,

372:１３２人目の素数さん
18/11/19 07:45:15.59 5ARxnQrn.net
問題 : ４リットルと３リットルの容器を使って２リットルの水を測るにはどうすればいい？
これが最短手順でいい？
[(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3),(2,0)]

373:１３２人目の素数さん
18/11/19 08:21:43.58 uVfWyczI.net
[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2)] は禁止？

374:１３２人目の素数さん
18/11/19 11:25:42.32 eL1RQpps.net
>>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,
分かスレ４４８-819,827

375:１３２人目の素数さん
18/11/19 12:26:19.49 ofBQh0Xr.net
>>352
お見事！

376:１３２人目の素数さん
18/11/19 17:31:06.43 ofBQh0Xr.net
10Lの容器いっぱいに油が入っています。7Lの容器と3Lの容器を使って、この油を5Lずつに分けます。どのような分け方がありますか。
URLﾘﾝｸ(katekyo.mynavi.jp)
何でグラフで解けるんだろ？

377:イナ
18/11/19 18:19:06.42 /GTUzlHS.net
>>355満タン(10)(７)(３)の三つの容器をこの並びで置き、
初め(10)(０)(０)入っているのを移していく
→(３)(７)(０)
→(３)(４)(３)
→(６)(４)(０)
→(６)(１)(３)
→(９)(０)(１)
→(２)(７)(１)
→(２)(５)(３)
→(５)(５)(０)
８回で二分できた。

378:１３２人目の素数さん
18/11/19 18:46:32.29 TVJAPYv0.net
>>344-347
だいたい考えてた解答と一緒です。
自分のは、1234→2341→3412→4123→1234のようなサイクルをつないでいくやり方でした。
探索なしで生成する方法はないんでしょうかね？

379:イナ
18/11/19 18:46:44.45 /GTUzlHS.net
前>>356両手ありで空にしたとこにすぐ入れるのをノーカンにするなら７回だけど、 (10)(０)(０) →(３)(７)(０) →(３)(４)(３) →(６)(４)(０)省略可 →(６)(１)(３) →(９)(１)(０)省略可 →(９)(０)(１) →(２)(７)(１) →(２)(５)(３) →(５)(５)(０) 片手だと９回か。

381:１３２人目の素数さん
18/11/19 23:43:46.25 eL1RQpps.net
>>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,

382:１３２人目の素数さん
18/11/19 23:55:14.32 yvqX1603.net
>>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となる

383:１３２人目の素数さん
18/11/19 23:55:39.30 vaYg27wd.net
>>357
え？自作問題なんですか？
よくこんなの思いつきましたね！すっげ！
とりあえず >>344-347みたいな解答できた後、明示的な解が作れないか考えたけど出来ずorz。
普段ならパソコンに探索させてやってみるんですが、今パソコン壊れててそれもできず。
少なくともm=2とかに限定すれば出来て不思議なさそうなんですけどねぇ？

384:１３２人目の素数さん
18/11/20 01:41:08.34 bRya54dl.net
>>355
こうなると人間技では無理だな。
100Lの容器いっぱいに油が入っています。51Lの容器と49Lの容器を使って、この油を50Lずつに分けます。どのような分け方がありますか。

385:１３２人目の素数さん
18/11/20 12:20:49.85 cFR1wwH3.net
>>362
１００ステップでできた。
URLﾘﾝｸ(tpcg.io)

386:１３２人目の素数さん
18/11/20 19:24:29.46 U5ObGMnl.net
>>361
いや、以前に問題だけなにかで知ったやつ。
いま探したけど、けっこう有名っぽい。生成コードも載ってるし。
URLﾘﾝｸ(en.wikipedia.org)
URLﾘﾝｸ(en.wikipedia.org)
なんか見たことある名前だと思ったら De Bruijn notationの人だった。

387:１３２人目の素数さん
18/11/20 20:29:08.33 2b66cHGf.net
無限にも一般化できそうねこれ　既に解答あるかどうか知ってる訳じゃないけど
n を正の整数とする時、関数 f:Z→Z であって、F:Z→Z^n;F(x)=(f(x+1),f(x+2),…,f(x+n)) が全単射になるものは常に存在するか？

388:１３２人目の素数さん
18/11/20 20:41:37.58 2b66cHGf.net
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)) )
が全単射になるものは常に存在するか？

389:１３２人目の素数さん
18/11/21 01:28:51.54 e25FOlfs.net
とりあえず >>364 のページには ”こうすりゃできる” というのが載ってはいるが、なぜそれで出来るサッパリわがんね。
試しにm=n=3で手計算でやってみると
aaabaacabbabcacbaccbbbcbccc
……できてる……すっげ！

390:１３２人目の素数さん
18/11/21 15:11:01.60 klg9AAWq.net
18: [] 2018/11/21(水) 02:38:57.162 ID:QyQDf8nQ0
これ頼む
URLﾘﾝｸ(i.imgur.com)

391:１３２人目の素数さん
18/11/21 16:43:13.37 Ul7BezYU.net
ブルゾンちえみ

392:１３２人目の素数さん
18/11/21 16:50:09.62 LdWYnCJ+.net
>>368
刺身にタンポポの花を乗せるような単調作業は、このスレにはふさわしくない。

393:１３２人目の素数さん
18/11/21 18:12:12.71 yvDuGGse.net
>>368
くそつまらん問題だな

394:１３２人目の素数さん
18/11/21 18:57:16.48 vRlJnRg/.net
>>365
文字が整数ではなく自然数だったら、つまりf:N→N,

395: F:N→N^nだったら、 n=2の場合、0 01 1 0212 2 031323 3 0414… n=3の場合、0 001011 1 002012022102112122 2 003013… のようにすればよさそうだけど、n≧4の場合はどうすればいいんだろう？

396:１３２人目の素数さん
18/11/21 19:24:25.67 e25FOlfs.net
>>368
計算機でやれば一瞬……打ち込むのに1時間程かかるwww

397:１３２人目の素数さん
18/11/22 01:16:02.37 x/Au2Ugh.net
>>368
直木三十五

398:１３２人目の素数さん
18/11/22 01:47:18.64 x/Au2Ugh.net
>>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)

399:１３２人目の素数さん
18/11/22 07:33:32.61 LiApVatG.net
>>375
やはり比で解く問題だったか

400:１３２人目の素数さん
18/11/23 01:34:48.76 4a5jgypk.net
>>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となる。
……やっと証明わかった。
こんな構成法絶対思いつかん。

401:１３２人目の素数さん
18/11/23 18:46:55.67 imnUH0Gw.net
実数 x に対して [x] を x の整数部分と定める。この時、次の値を求めよ：
lim_(n→∞) (1/√n)Σ_(k=1,[√n])(n/k-[n/k])

402:１３２人目の素数さん
18/11/23 21:38:04.43 v31SUiKG.net
>>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

403:１３２人目の素数さん
18/11/23 22:23:27.31 afoQoOE+.net
じゃあ問題変えよか
次を示せ：
Σ_(k=1,[√n]) n/k-[n/k] = (1/2)√n + O(n^(10/21))

404:１３２人目の素数さん
18/11/23 23:06:09.28 K/FSQatd.net
>>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

405:１３２人目の素数さん
18/11/23 23:47:54.50 afoQoOE+.net
>>381
誤差項の係数まで出してるわけじゃないから計算一つ一つ追ってくのはしんどくてすぐできそうにないけど、>>380 の右辺を
(√n)･(1/2 + O(n^(-1/42)))
と変形できて、n にそのまま 10^11 入れて n^(-1/42) 計算しても 0.547 くらいになるから、
むしろ >>381 の数値の 1/2 との近さは"良すぎる"くらいだね　言い換えれば >>380 の評価がガバガバすぎるってことなんだけど

406:１３２人目の素数さん
18/11/23 23:51:14.65 K/FSQatd.net
>>382
らじゃ。むずかしそう……

407:１３２人目の素数さん
18/11/24 00:57:22.81 R0eGczxp.net
>>275
> 3次正方行列Aについて、tr(A) を det(Aと単位行列Eの式) の式で表せ。（detの中身は複数種類でも可）
これどうやるんですか？

408:１３２人目の素数さん
18/11/24 01:23:19.32 lLG6RWzh.net
>>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)
でいける

409:１３２人目の素数さん
18/11/24 01:41:19.61 R0eGczxp.net
>>385
なるほど！ありがとうございます。

410:１３２人目の素数さん
18/11/24 07:43:35.23 QwiE/Y/T.net
>>382
これもしかしてL関数とか使う？

411:１３２人目の素数さん
18/11/24 10:55:38.86 9xCWeV16.net
>>387
想定してる解答ではそういう複素解析的な技術は使ってないよ
使えるのかどうかはわからないけど、n>n' として n' の時の和が n の時の和の部分和になってる訳じゃないから
今までと同じような方法で臨むのは難しそうな気がする

412:１３２人目の素数さん
18/11/24 12:56:55.99 464U4GYy.net
>>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)の評価ネットで探してもありそでなさそで……
これむずい。気長にやります。

413:１３２人目の素数さん
18/11/24 13:09:45.85 HscCLQgZ.net
{x}＝x－[x]と定義して、
Σ(1≦k≦x^{1/2}){x/k}＝(1/2)x^{1/2}＋O(x^{1/3})
が示せた(計算ミスがなければ)。方針は >>389なんだけど、
L関数ではなく、普通にフェイェール核を使う。
あとはオイラー・マクローリン。

414:１３２人目の素数さん
18/11/24 13:16:03.61 464U4GYy.net
>>390
おお、すごい！解答おながいします。

415:１３２人目の素数さん
18/11/24 13:19:27.31 HscCLQgZ.net
すまん、フェイェール核じゃなくてディリクレ核だった。

416:１３２人目の素数さん
18/11/24 13:30:52.39 464U4GYy.net
私も >>389訂正。L(ξ, 1)じゃなくてL(1,ξ)ね。
あとwolframで確かめてみたら
x - [x] - 1/2 = -1/πΣ[i] sin(2πix)/iですね。
URLﾘﾝｸ(www.wolframalpha.com)(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) d

417:x (ただし a = 2πn/k) の項が出てきて評価ができなかった。 Dirichlet の不連続因子っての使うのかなとも思ったんだけど眠くなってやめた。積分苦手 orz。

418:１３２人目の素数さん
18/11/24 14:01:12.00 HscCLQgZ.net
計算が面倒くさすぎるので、使う道具だけ書いておきます。間違ってたらスマン。
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

419:１３２人目の素数さん
18/11/24 14:12:41.48 HscCLQgZ.net
定義　命題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.

420:１３２人目の素数さん
18/11/24 14:18:51.97 HscCLQgZ.net
定理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 で置き換える。

421:１３２人目の素数さん
18/11/24 14:21:47.97 HscCLQgZ.net
定理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.

422:１３２人目の素数さん
18/11/24 14:32:22.84 HscCLQgZ.net
Σ(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)
と分解する。

423:１３２人目の素数さん
18/11/24 14:39:30.16 HscCLQgZ.net
おーっと、計算ミスしてるっぽい箇所を発見。。。

424:１３２人目の素数さん
18/11/24 14:42:15.81 UbXGWPhk.net
>>398
kの小さいとこ分けるのはやったんだけどなぁ。
まぁやってみます。
ところで出題者さんに質問。
この誤差項のx^(10/21)の肩の数字はいくらでも小さく採れるんですか？

425:１３２人目の素数さん
18/11/24 14:44:32.75 HscCLQgZ.net
だめだ、計算ミスがある。
ここまで書いてしまったが、すまんｗ

426:１３２人目の素数さん
18/11/24 15:29:53.61 R0eGczxp.net
>>401
君の使命を果たすんだ！

427:１３２人目の素数さん
18/11/24 15:35:04.80 qzNDTVhe.net
>>400
や、今解答として用意してる計算のしかたであれば、最善のパラメーターのとり方でこの結果。
もっと和のとり方を工夫したら改善できるかもだけども

428:１３２人目の素数さん
18/11/24 16:06:23.59 1kbxmjW3.net
>>403
そうなんですか。
むずいなぁ。
今のとこのスレの流れ的にいい線いってます？

429:１３２人目の素数さん
18/11/24 16:48:54.13 qzNDTVhe.net
普通に改善できた…でもパラメータ変えて誤差項の指数小さくできるかはっきりしないし問題は変えないことにする
（もし小さくできたとしてもややこしくなるだけだし変えないつもりだけど）
>>404
うーん、フーリエ展開から攻めるのはちょっとオススメしにくい
小数部分をとる関数 {x} に不連続点があるせいで級数が絶対収束しないから、
各フーリエ係数ごとに和をとってから全体を評価しようとするとどうしてもばかでかくなってしまう気がする
フーリエ級数いじるの得意じゃないし本当にできないのかとかについては何とも言えないけど

430:１３２人目の素数さん
18/11/24 16:55:34.93 qzNDTVhe.net
停滞するのもあれだし類題出しときます
lim_(n→∞) (1/logn)Σ_(k=1,[logn]) (n/k-[n/k])
は存在するか。

431:１３２人目の素数さん
18/11/24 17:17:24.06 HscCLQgZ.net
まだ暗算レベルだけど、Σ(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})
あたりのオーダーが言えそうな気がする。
また間違うかもしれないので書かないけどｗ

432:１３２人目の素数さん
18/11/24 19:35:26.74 HscCLQgZ.net
>>407もダメだった。
B(t)＝{t}－1/2と置くと、>>407の場合、
∫(x^{1/3},x^{1/2})B(t)B(x/t)dt みたいなのが出てきて、
これのxに関するオーダーが計算できないｗ
どうやら、オイラー・マクローリンで計算すると、{x/n}の難しいところが
B(t)に移転してしまい、B(t)の積分計算ができなくなって失敗するっぽい。

433:１３２人目の素数さん
18/11/25 02:09:19.35 AuW29Ma5.net
>>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),

434:１３２人目の素数さん
18/11/25 02:25:52.63 AuW29Ma5.net
>>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

435:１３２人目の素数さん
18/11/25 02:42:24.60 XzUMGiUk.net
和のとり方を改善してパラメータをとり直した結果、
>>380 の誤差項を O(n^(5/12)･logn) まで改善できたので一応報告
けど予定通り、問題の主張を変えるつもりはなし

436:１３２人目の素数さん
18/11/25 06:01:42.98 f8nTJKnO.net
Σ[k≦√n] sin n/k の評価ができんorz。

437:１３２人目の素数さん
18/11/25 14:43:15.35 4bOKPxfm.net
>>412
手助けになればいいけど、下の定理2.1.6を使えば Σ_(k=√n) sin(n/k) = O(n^(1/3)) まで落とせそう
URLﾘﾝｸ(spectrum.library.concordia.ca)
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

438:１３２人目の素数さん
18/11/25 18:39:02.79 9eLajdTN.net
>>413
sin 2πn/k はうまくいきました。
でも本丸は∫ a*cos(2πax)/x dxなんですよね～。
こいつがO(1/a)とかならうまくいくし、数値実験てきには成立してそうなんだけどむずい。
やっぱりこりゃノーヒントじゃ無理だ。
>>378さんヒントお願いします。

439:１３２人目の素数さん
18/11/25 21:03:53.65 0+5Uplew.net
１時間に２本の列車があり、8：00　8:45 9:00 9:45　10：00 10:45 ...という風にダイヤが組まれている。
ランダムに駅に行ったときの待ち時間の期待値はいくらか？

440:１３２人目の素数さん
18/11/25 21:07:15.08 MRMVN18u.net
>>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 に Σ を分けて、
それぞれを評価すればよい。詳細は略（突然の飽き）□

441:１３２人目の素数さん
18/11/25 22:00:17.82 UuPttQIq.net
>>294
■①^2+④でも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+④を入力すると
P1st =｛12n^4+28n^3-42n^2-52n-3(-1)^n+51｝/48

442:１３２人目の素数さん
18/11/25 22:26:05.78 pUh+e9hX.net
>>415
1時間に2本だから30分。

443:１３２人目の素数さん
18/11/25 22:30:55.48 0+5Uplew.net
>>418
8：00　8:30 9:00 9:30　10：00 10:30なら、1時間に2本だが最大の待ち時間が30分だぞ。

444:１３２人目の素数さん
18/11/25 22:43:08.35 AuW29Ma5.net
>>415
1時間に2本だから 18.75分。
最大の待ち時間は 45分。

445:１３２人目の素数さん
18/11/25 22:52:10.23 pUh+e9hX.net
あ、失礼。15分。

446:１３２人目の素数さん
18/11/25 23:03:00.46 0+5Uplew.net
>>420
正解。
これの平均値を求めるだけ。
URLﾘﾝｸ(i.imgur.com)

447:１３２人目の素数さん
18/11/26 00:47:04.32 BZQrI/i+.net
>>416
ありがとう。
また考えてみます。
Fourier展開みたいな技使ってもダメっぽいね。
コツコツやるしかないのね……

448:１３２人目の素数さん
18/11/26 01:17:52.33 JAq6ovHt.net
>>415
1時間に2本だから｛30 - M(60-M)/60｝分。
最大の待ち時間はM分。

449:１３２人目の素数さん
18/11/26 01:22:34.01 zUO0KBha.net
東京駅からのぞみ号で朝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

450:イナ
18/11/26 03:00:27.06 s06YIHN9.net
(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

451:１３２人目の素数さん
18/11/26 07:15:29.27 zUO0KBha.net
>>425
面積計算して平均したら
3.95分＝3分57秒になった。
URLﾘﾝｸ(i.imgur.com)

tt=c(0,10,13,20,23,30,40,47,50,60) # time table
x=diff(tt)
sum(x^2/2)/sum(x)
URLﾘﾝｸ(tpcg.io)

452:１３２人目の素数さん
18/11/26 07:29:11.92 zUO0KBha.net
>>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

453:１３２人目の素数さん
18/11/26 08:20:42.11 zUO0KBha.net
>>426
レスありがとうございます。
筆算、乙。
０～６０分を１分ごと、０．１分ごと０．０１分、０．０１分ごとにして計算すると
> 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)

454:１３２人目の素数さん
18/11/26 15:12:05.01 kjzRc5OI.net
分単位でちょうどの時間に着いた時は
待ち時間なしの確率が1/2になるというわけだな

455:１３２人目の素数さん
18/11/26 15:40:21.97 cCOlyEA2.net
ある駅のホームの1番線には1時間ごと、2番線には(1/2)時間ごと、3番線には(1/3)時間ごとに電車が来るようにダイヤを組みたい。
ランダムな時間に駅に着いたときの平均待ち時間を最小にするには、どのようにダイヤを組めば良いか。
ただし、何番線の電車に乗っても向かう方向や停車駅に違いは無いとする。

456:１３２人目の素数さん
18/11/26 16:20:05.15 kjzRc5OI.net
単純に考えて、以下ぐらいしか思いつかない
３番線　00　20　40
２番線　20/3　110/3
１番線　50　

457:１３２人目の素数さん
18/11/26 16:27:19.74 kjzRc5OI.net
>>432　訂正
最大15分はどうしても開くのかな？
３番線　00　20　40
２番線　05　35
１番線　50　

458:１３２人目の素数さん
18/11/26 16:37:26.72 kjzRc5OI.net
１番線　00
２番線　15　45
３番線　10　30　50

459:１３２人目の素数さん
18/11/26 17:05:53.16 kjzRc5OI.net
最小5分50秒　00　10　15　30　45　50　00
最大8分20秒　00　20　30　40　00

460:１３２人目の素数さん
18/11/26 17:53:39.06 yzjtacP4.net
>>433-434
正解
３番線を00,20,40で固定すれば、対称性から２番線は x,30+x (0≦x≦10) のみを考えればよくて、
x をどうとっても１番線を 50 とするのが最適解（のうちの１つ）であることがわかる。
（より長い空白のど真ん中に入れた方がより平均待ち時間を削減できるから）

461:１３２人目の素数さん
18/11/26 18:17:18.85 mGDYWVbl.net
いつもの顰蹙のプログラミング解
w8 <- function(xy,Print

462:=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

次ページ