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

面白い問題おしえて～ ..

95:１３２人目の素数さん
18/11/05 22:38:47.29 Pcec+Aw3.net
どかーん！
(⌒⌒⌒)
　｜｜
／￣￣￣￣￣＼
|　・　Ｕ　　　　　　|
| |ι　　　　　　　|つ
Ｕ｜｜￣￣｜｜
　　￣　　　　　￣
呼んだ？

96:１３２人目の素数さん
18/11/05 22:53:10.54 wfCkOOVj.net
>>90
81の計算は、当選確率1/6^6のクジを995回引いたときの当選回数の期待値に等しい。
84の計算は、当選確率1/6^6のクジを995回引いたとき、少なくとも一回当たりくじを引く確率に等しい。
「目的の出目が六回続けて出る」という事が達成される確率が1/6^6。
普通のクジなら、外れを引くとクジ一個分を無駄にする。
しかし、この問題の場合は、いわば途中まで成功していた分のクジも無駄になることになる。
一回の失敗で、無駄になるクジの数が１枚の場合もあれば、複数の場合もある。
チャレンジできる回数が995回固定ということはない。
さらに、失敗したとしても、もし、１を引いていたら、新たなチャレンジの第一歩を
踏み出していたことになるが、それ以外の目で失敗したら、第０歩から
スタートすることになる。単純に「失敗」と言っても、内容が異なることもある。
本来はこのような機微に関わる問題で、厳密な値は、シンプルな式では表せない。
87や86は、6^1000通りある全てのパターンを想定している。

97:１３２人目の素数さん
18/11/05 22:59:51.87 hlCe+j6H.net
チャレンジできる回数が995回固定されないかも
ちょうど1000回使い切ることもありうる

98:１３２人目の素数さん
18/11/05 23:21:44.43 1RAsBANL.net
>>92
解説ありがとうございました。
＞失敗したとしても、もし、１を引いていたら、新たなチャレンジの第一歩を踏み出していたことになる
この理解が私には欠けていました。

99:１３２人目の素数さん
18/11/06 02:48:39.54 jOazYBXJ.net
P1st Q1st even
[1,] 0 0 1
[2,] 4 5 6
[3,] 26 27 13
[4,] 84 83 23
[5,] 203 197 35
[6,] 413 398 50
[7,] 751 722 67
[8,] 1259 1210 87
[9,] 1986 1910 109
[10,] 2986 2875 134
完全追尾型多項式が完成しました
宝の個数を２で固定します
P1st =｛12n^4+28n^3-42n^2-52n-3(-1)^n+51｝/48
Q1st =｛12n^4+20n^3-18n^2-20n-3(-1)^n+3｝/48
■Wolframに入力すると既約分数表示になるので御注意
P1st／Q1st
=｛8(n-1)｛(n-2)n-6｝/｛2n(n+2)(6n^2-2n-5)-3(-1)^n+3｝｝+1

100:１３２人目の素数さん
18/11/06 03:09:24.93 FZJllfOU.net
>>85
任されたんぢゃ、生姜ねぇ…
線形漸化式は
　p[n] = p[n-1] - p[n-6] /(6^6),
特性多項式は
　t^6 - t^5 + (1/6)^6
= (t-α) (t-β) {tt -2

101:Re(γ_1) t + |γ_1|^2} {tt -2 Re(γ_2) t + |γ_2|^2}, 特性根は α = 0.9999785642321302281427595561300279367871 　　= 1 - (1/6)^6 - 5･(1/6)^12 - 40･(1/6)^18 - … β = 0.11947305512892524659941083415872186721 γ_1 = |γ_1| e^(i θ_1) 　|γ_1| = 0.117113316705063892011642575051190099053 　θ_1 = 2.5253513177722176449 γ_2 = |γ_2| e^(ｉ θ_2) 　|γ_2| = 0.11436934616195511830934529716995273057 　θ_2 = 1.279751470687185368 p[n] = 1.00000000689325α^(n-5) + c_0 β^n + c_1 |γ_1|^n cos(n θ_1+ d_1) + c_2 |γ_2|^n cos(n θ_2 + d_2) 　　　= 1.00000000689325α^(n-5)　　　　　　　　(n>>1) 　　 ∵　0．114 < |β|，|γ_1|，|γ_2| < 0．120　なので 1 - p[1000] = 1 - 1.00000000689325α^995 = 0.021102960211842 1.00000000689325 = 1 + 15 (1/6)^12 + …

102:１３２人目の素数さん
18/11/06 03:39:44.90 FZJllfOU.net
>>84
いったん「123456」が完成すると次の5回はデッド・タイムになるわけか。
GM計数管（放射線測定器）の分解時間、不感時間みたいなものかな？

103:１３２人目の素数さん
18/11/06 05:08:26.34 FZJllfOU.net
>>44
BD、CD が半整数でいいなら、もう一つ解があるらしい…

104:１３２人目の素数さん
18/11/06 05:12:24.35 DN0vL5hu.net
haskell先生の答え
*Main> let ps = map (!!6) $ iterate (¥x->(tail x) ++ [x!!5 + 6%(6^6) - (sum $ take 6 x)/6^6]) $ [1%1,1%1,1%1,1%1,1%1,0,0,0,0,0,0]
*Main> fromRational $ ps !! 999
2.110296021184187e-2

105:１３２人目の素数さん
18/11/06 05:17:27.31 Er8xgC3V.net
>>98
あった
*Main> [(x,y)| x<-[4.0,4.5..10.0],y<-[1.0,1.5..7.0],y*(x^2+(3.5)^2-7^2)== -x*(y^2+(3.5)^2-4^2)]
[(4.5,4.5),(6.0,2.0)]

106:１３２人目の素数さん
18/11/06 05:50:54.52 FZJllfOU.net
>>86
g[n] の漸化式は
g[n] - g[n-1] = (1/6)f[n-1] = (1/6)^2 e[n-2] = (1/6)^3 d[n-3] = (1/6)^4 c[n-4] = (1/6)^5 b[n-5]
　　= (1/6)^6 (1-g[n-6])
となります。したがって　p[n] = 1 - g[n]　の漸化式は
　p[n] = p[n-1] - (1/6)^6 p[n-6],
これは >>85 と同じです。
Memo．
　a[n] = p[n] - (1/6)p[n-1] - (1/6)^2 p[n-2] - (1/6)^3 p[n-3] - (1/6)^4 p[n-4] - (1/6)^5 p[n-5],
　b[n] = (1/6) p[n-1],
　c[n] = (1/6)^2 p[n-2],
　d[n] = (1/6)^3 p[n-3],
　e[n] = (1/6)^4 p[n-4],
　f[n] = (1/6)^5 p[n-5],
　g[n] = 1 - p[n],

107:１３２人目の素数さん
18/11/06 06:21:01.93 L5OqW8l+.net
Haskell 先生に聞いてみました。
Prelude Data.List Data.Ratio> let ps = map head $ iterate (¥x->(tail x) ++ [x!!5 - 1%(6^6) * x!!0]) [1%1,1%1,1%1,1%1,1%1,1%1-1%(6^6)]
Prelude Data.List Data.Ratio> fromRational $ 1%1 - (ps !! 999)
2.110296021184187e-2
確かにこっちの方がいいね。

108:１３２人目の素数さん
18/11/06 08:00:46.22 9NNsjRpE.net
>>102
こんな短いコードで算出できるとは驚きです。
計算原理がさっぱりわかりません。
個々のコマンドはなんとかわかります。
1-1/(6^6）は何の数値でしょうか？

109:１３２人目の素数さん
18/11/06 08:04:21.77 9NNsjRpE.net
>>103
>96の線形漸化式の配列化？

110:１３２人目の素数さん
18/11/06 08:57:44.56 9NNsjRpE.net
>>102
ようやくコードの意味が理解できたのでRに移植。
実数計算なので誤差がでます。
f = function(N){
p=numeric()
p[1]=p[2]=p[3]=p[4]=p[5]=p[6]=1
for(n in 7:(N+1)){
p[n]=p[n-1]-p[n-6]/(6^6)
}
1-p[N+1]
}
> f(1000)
[1] 0.02110296

111:１３２人目の素数さん
18/11/06 09:04:09.41 9NNsjRpE.net
>>105
表示桁を増やしてみた。
> options(digits=22)
> f(1000)
[1] 0.0211029602118424364221

112:１３２人目の素数さん
18/11/06 12:59:18.08 poLu8oO

113:g.net

114:１３２人目の素数さん
18/11/06 15:40:04.34 cDO4b4Dm.net
コインを１０００回投げた。連続して表がでる確率が最も高いのは何回連続するときか？

115:１３２人目の素数さん
18/11/06 17:36:12.86 /OX7Wfwz.net
0<|2x^2-y^3|<100√|y|
を満たす整数の組(x,y)が無限に存在することを示せ

116:１３２人目の素数さん
18/11/06 17:39:00.56 FZJllfOU.net
まとめ（？）
ε = 1/(6^6)　とおく。
・「123456]を２つ以上含む場合を無視　 >>81
　1 - p[n] ≒ (n-5)ε
・複数あり、相関を無視　　 >>84
　1 - p[n] = 1 - (1-ε)^{n-5} = (n-5)ε - (1/2)(n-5)(n-6)ε^2 + (1/6)(n-5)(n-6)(n-7)ε^3 - …
・複数あり、相関あり　　 >>96
　α = 1 -ε -5ε^2 -40ε^3 -385ε^4 -4095ε^5 - …
　1 - p[n] = 1 - (1 + 15ε^2 + …)α^{n-5} = (n-5)ε - (1/2)(n-10)(n-11)ε^2 + …
Python？ Haskell？
プログラムの作れないオジサンは Excel で1000行使ってますよ。。。

117:１３２人目の素数さん
18/11/06 19:13:07.74 0/M2gc6l.net
>>108
日本語の微妙なニュアンスは、それで合ってるの？
100回のコイントスで連続表の最大回数は
5回がもっとも起こりやすく確率は26%　らしいけど

118:１３２人目の素数さん
18/11/06 19:32:20.35 3z562f7u.net
>>108
1000回コインを振って、11連以上、10連以上、．．．、7連以上の表が出る確率はそれぞれ、
0.215431673
0.385449752
0.624240992
0.861144809
0.981783332
なので、最大連続数が、10連、9連、8連、7連となる確率は、それぞれ、
0.170018079
0.23879124
0.236903817
0.120638523
8連と9連がほぼ等しいが、9連となる確率が最も高い。
参考
ｽﾚﾘﾝｸ(math板:462番)-465

119:１３２人目の素数さん
18/11/06 20:00:33.66 cDO4b4Dm.net
>>112
１００回で５
１０００回で９
１００００回で１２
１０万回で１５
１０００万回で１８になった。

120:１３２人目の素数さん
18/11/06 20:04:45.57 cDO4b4Dm.net
>>113
Rのスクリプトはここに置いた。
ｽﾚﾘﾝｸ(hosp板:54番)
有理数表示したかったのでPythonに移植
ここで実行可能
# URLﾘﾝｸ(tpcg.io)

サイコロを１万回ふったときに５回以上　及び、丁度５回１の目が続く確率を算出。数字を変えて実行も可能。

121:１３２人目の素数さん
18/11/06 20:07:29.69 FZJllfOU.net
a = 2^(1/6) は無理数だから、ディリクレの定理より
　|p/q - a| < 1/q^2
（「ディオファントス近似」とかいうらしい。）
x = q^3，y = pp とおくと
0 < | 2xx - y^3 | = | 2q^6 - p^6 | < ?
う～む、近似が足りぬ…

122:１３２人目の素数さん
18/11/06 20:14:11.95 FZJllfOU.net
>>115
では、ニュートン・ラフソン法を使おう。
　f(x) = (x^6 -2) / x^(5/2),
として
　x ' = x - f(x) / f '(x) = x - 2x(x^6 -2)/(7x^6 +10) = x(5x^6 +14)/(7x^6 +10),
を繰り返す。このとき
　x '- a = (x-a)^3 * (5x^4 +8ax^3 +9aaxx +8aaax +5a^4)/(7x^6 +10)
∴　| x '- a | < C |x-a|^3,
さて…

123:１３２人目の素数さん
18/11/06 20:32:32.09 cDO4b4Dm.net
>>113
１００万回で１８の間違い。
ちなみに１０００万回で２２回（確率は0.2474）だった。

124:１３２人目の素数さん
18/11/06 20:39:21.84 cDO4b4Dm.net
>>117
URLﾘﾝｸ(www.tutorialspoint.com)
だとタイムアウトしたので、オフラインで算出してみた。
Just 22
4456779119136417/18014398509481984
= 0.2474009396866937

125:１３２人目の素数さん
18/11/06 22:06:22.80 0/M2gc6l.net
ある道路では、30分以内に車が通る確率は99.9%である。
では、10分以内に車が通る確率は？

126:１３２人目の素数さん
18/11/06 22:18:24.46 JyIr9Vjq.net
>>119
1-(1-0.999)^(1/3)
=0.9

127:１３２人目の素数さん
18/11/06 23:36:10.05 08uZxk9P.net
>>115
それを満たすp q が無限にあったとしてもそれらが平方数、立方数になってくれてる保証なんかないでしょ？

128:１３２人目の素数さん
18/11/07 00:32:00.28 p6NUZQ5G.net
>>105
分数表示したいのでPythonに移植した。
from fractions import Fraction
def dice126(N):
P=list()
for n in range(6):
P.append(1)
P.append(1-1/(6**6))
for n in range(7,N+1):
P.append(P[n-1]-P[n-6]/(6**6))
return(1-P[N])
def dice123456(N):
print(Fraction(dice126(N)))
print(" = " + str(dice126(N)))
dice123456(1000)

129:１３２人目の素数さん
18/11/07 00:44:06.23 5PMwby1T.net
>>116 （補足）
　a = 2^(1/6) として
　0 < (5x^4 +8ax^3 +9aaxx +8aaax +5a^4)/(7x^6 +10) ≦ C,
　C = 2.706458005831039532180100595416
　等号成立は x = 0.903918268122918428596803223653869

130:１３２人目の素数さん
18/11/07 02:28:28.15 Lk/NCQ39.net
>>81
((1-(5/6)^6)^6)/4

131:１３２人目の素数さん
18/11/07 04:43:16.35 5PMwby1T.net
>>96 (補足)
　p[0] = p[1] = p[2] = p[3] = p[4] = p[5] = 1
より
　p[n] = 1.00000000689307114563713652919α^(n-5) + c_0 β^n + ……
　　= (1 + 15ε^2 + 220ε^3 + 320ε^4 +…)α^(n-5) + c_0 β^n + ……
　c_0 = -0.02813048468
　c_1 = 0.03983999218
　d_1 = -0.51407117920
　c_2 = -0.05049060128
　d_2 = 1.43835771780

132:１３２人目の素数さん
18/11/07 09:16:36.43 5PMwby1T.net
>>110 (補足)
ε = 1/(6^6)　とする。
p[n] ≒ (1 +15ε^2 +220ε^3+ 3060ε^4 + …) α^(n-5)
　　= (1 +15ε^2 +220ε^3+ 3060ε^4 + …)(1 -ε -5ε^2 -40ε^3 -385ε^4 -4095ε^5 -…)^(n-5)
　　= 1 -(n-5)ε +(1/2!)(n-10)(n-11)ε^2 -(1/3!)(n-15)(n-16)(n-17)ε^3 +(1/4!)(n-20)(n-21)(n-22)(n-23)ε^4 - …

133:１３２人目の素数さん
18/11/07 17:50:14.73 fQSBmb6Q.net
今んとこ解かれてないのは >>26 >>36 >>42 >>43 >>79 >>109 かね
真ん中二つはリンク先に答えあるみたいだしあれだけども

134:１３２人目の素数さん
18/11/07 19:51:09.21 5PMwby1T.net
>>110 (補足)
ε = 1/(6^6)　とする。
α = 1 -ε -5ε^2 -40ε^3 -385ε^4 -4095ε^5 -46376ε^6 -548340ε^7 - …
p[n] = Σ[k=0,∞] Ｃ[n-1-5k，k] (-ε)^k,

135:１３２人目の素数さん
18/11/07 21:09:24.11 p6NUZQ5G.net
某シリツ

136:医大の裏口入学調査委員会が裏口入学は高々10%と報告したとする。その結果の検証に100人を調査したら4人続けて裏口入学生であった、という。この検証から裏口入学率が10%であるか否かを有意水準1%で検定せよ。

137:１３２人目の素数さん
18/11/07 21:51:21.02 mEYJ0uIZ.net
>>129
＞その結果の検証に100人を調査したら4人続けて裏口入学生であった、という。
これは100件の検証結果の中に
・1度だけ4連続裏口入学があった
・複数回4連続裏口入学があった
・1度だけ4以上連続裏口入学があった
・複数回4以上連続裏口入学があった
のどれを意味していますか？

138:１３２人目の素数さん
18/11/07 22:38:16.40 p6NUZQ5G.net
>>130
情報がないとして全ての場合を含む、
１回以上、4以上の連続裏口入学があった場合を考える。
４連続が１回でもいいし、
４連続が２回の後に５連続が１回でもいいとする。
想定したのは
表のでる確率が0.1のコインを100回投げて表が4回以上連続する確率が1%未満かという問題。

139:１３２人目の素数さん
18/11/07 23:02:36.60 PN+gm2kl.net
>>131
４回以上連続することが複数回あっても構わないとする。

140:１３２人目の素数さん
18/11/08 02:09:05.40 45SX77TX.net
>>128 (訂正)
　p[n] = Σ(k=0, [n/5]) C[n-5k, k] (-ε)^k,
でした。　...orz >>126 は ok

141:１３２人目の素数さん
18/11/08 02:34:17.78 45SX77TX.net
>>109 >>116
(x, y) = (q^3, pp) とおくと、求めるものは
0 < | 2q^6 - p^6 | < 100･p,
を満たす整数 (p, q)
そこで 2^(1/6) = a の近似分数の列 p/q = t を次の漸化式で定める。
　t ' = t - 2 t (t^6 - 2)/(7 t^6 + 10) = t (5 t^6 + 14)/(7 t^6 + 10),
(p,q) の漸化式は
　p ' = p (5p^6 + 14q^6),
　q ' = q (7p^6 + 10q^6),
(p,q) = (1,1) のときは成立するが
(p,q) = (19, 17) のときは　2xx -y^3 = 2･17^6 - 19^6 = 1229257 > 100*19
(p,q) = (10889952049, 9701846569)　のときは　2xx -y^3 = 2q^6 - p^6 = 2.31865949E+54 > 100･p
(p,q) = (217953260587942275546675683149407795232019596416934847340158868299331811, 194174280472305108606358058802927185430436427469916728412097502845028473)
のときも絶望的でござる。

142:１３２人目の素数さん
18/11/08 02:59:04.34 45SX77TX.net
>>76
　Macedonia の人の解答と同じらしいです。

143:１３２人目の素数さん
18/11/08 04:07:51.53 pDHe6HSd.net
>>134
てかその方針そのものが無理なんじゃないの？
もし
>0 < | 2q^6 - p^6 | < 100･p,
>を満たす整数 (p, q)
が無限にあったら
0 < 2q^6 - p^6 < 100p 又は -100p < 2q^6 - p^6 < 0
になるけど前者なら t = 100p/q^6、b=(p/q)^(-5/6)とおいて
p/q < 2^(1/6) < (p^6/q^6 + 100/q^6)^(1/6) = p/q + tb/6 - 5tb/72 (bt) + 55tb/1296 (bt)^2 + ……
だけど誤差項がO(q^(-5))なので
＞この系は、トゥエ・ジーゲル・ロスの定理が、代数的数の有理数での近似の下界は 2 を超えて 2 + ε への改善はできないという意味で、最良であることを示している。
に矛盾してしまう。
URLﾘﾝｸ(ja.wikipedia.org)
後者でも同様。

144:１３２人目の素数さん
18/11/09 05:17:13.44 pvdoV3Z4.net
>>110 >>126 >>128
ε = 1/(6^6) とする。
p[n] = (1 +15ε^2 +220ε^3 +3060ε^4 +42504ε^5 +593775ε^6 +8347680ε^7 + … )α^(n-5)
α は　t^6 - t^5 +ε = 0 の根
α = 1 -ε -5ε^2 -40ε^3 -385ε^4 -4095ε^5 -46376ε^6 -548340ε^7 -6690585ε^8 - …

145:１３２人目の素数さん
18/11/09 07:40:

146:24.37 ID:pvdoV3Z4.net

147:１３２人目の素数さん
18/11/09 14:55:14.01 ds1M8gYh.net
>>79
分からないけど、｛a_n｝の母関数の関数等式ができたので一応書いとく
f(x)=Σ[n≧1] a_nx^n
g(x)=Σ[n≧1] a_(2n-1)x^(2n-1)
h1(x)=Σ[n≧1] a_(3n-2)x^(3n-2)
h2(x)=Σ[n≧1] a_(3n-1)x^(3n-1)
h3(x)=Σ[n≧1] a_(3n)x^(3n)
とおく。これらは区間 (-1,1) 上で絶対収束する。
まず明らかに
　h1(x)+h2(x)+h3(x)=f(x)　…①
　(f(x)-f(-x))/2=g(x)　…②
さらに漸化式より
　xh1(x^2)=g(x^3)　…③
　h2(x^2)=xg(x^3)　…④
　h3(x)=-f(x^3)　…⑤
①に x^2 を代入して x 倍
　xh1(x^2)+xh2(x^2)+xh3(x^2)=xf(x^2)
③④⑤より
　g(x^3)+x^2g(x^3)-xf(x^6)=xf(x^2)
②より
　(1+x^2)(f(x^3)-f(-x^3))/2-xf(x^6)=xf(x^2)
整理して
　(1+x^2)(f(x^3)-f(-x^3))=2x(f(x^2)+f(x^6))
うーん…

148:１３２人目の素数さん
18/11/09 16:11:31.59 u44VxTes.net
>>79はデタラメ詰将棋君の香りがする。
ホントに解けるのかどうかかなり疑問ww

149:１３２人目の素数さん
18/11/09 17:20:59.61 UXVKU4RE.net
デタラメ詰将棋君ってなんだよ？説明したまえ

150:１３２人目の素数さん
18/11/09 19:33:26.08 ak/GsOoT.net
しらんの？わかスレでこれ答えでんやろって適当な問題連発してるやつ。
とくに彼がだしてる確率系は殆どとけない。
(というか持ってる答えあるなら出してくれといって出したことないのでそう推定している。)
>>79はいかにも彼が好きそうな形。
本人解けたつもりで出してるだけの可能性あり。

151:１３２人目の素数さん
18/11/09 21:24:51.59 EXq8jHLE.net
でたらめ予定調和君

152:１３２人目の素数さん
18/11/09 22:58:54.45 5AnUTlVm.net
コインを１００回投げて表が連続した最大数が５のとき、表がでる確率の９５％信頼区間を求めよ。
近似解計算で
lower upper
0.2487456 0.6386493
になったけど、自信がない。

153:１３２人目の素数さん
18/11/10 01:10:06.43 TW6tyhOr.net
>>138
>t^6 - t^5 +ε = 0 の根は
>
>α = 1 - Σ[k=1,∞] c(5, k) ε^k,
これどうやって証明するんですか？
Link先にも載ってないですけど？

154:１３２人目の素数さん
18/11/10 01:27:10.71 TW6tyhOr.net
あ、わかった。
G.f.: inverse series of y*(1-y)^5.
これだ。

155:１３２人目の素数さん
18/11/10 02:17:14.74 BjsJwiKs.net
>>79は関数等式が作れたので満足ということにしよう
 >>26
これも分からないけど考えたことを書いてみる。
区間 [0,√2] で関数の値を決めれば、
等式 f(x+√2)=(f(x)+f(x+1))/2 を満たすように実数全体に一意に拡張することができる。
したがって、[0,√2] 上で定数であることを示すことが必要かつ十分。
[0,√2] 上で定数でないと仮定して、有界でないことを導く感じかなあ。
x を大きくすると平均化されて収束しそうなので、逆に x を -∞ の方に持ってくと有界でなくなりそう。

156:１３２人目の素数さん
18/11/10 02:54:00.82 0LaPCkg7.net
>>89
Henry Mancini - Baby Elephant Walk
URLﾘﾝｸ(www.youtube.com)

157:１３２人目の素数さん
18/11/10 03:12:05.12 P9RJEHjc.net
諦め早いなあ　じゃヒント

158: >>79 S(n) = Σ_(k=1,n) a_(2k-1) とおくと S(3n) = Σ_(k=1,n) a_(6k-5) + a_(6k-3) + a_(6k-1) = Σ_(k=1,n) a_(4k-3) - a_(2k-1) + a_(4k-1) = S(2n) - S(n)

159:１３２人目の素数さん
18/11/10 03:46:00.82 P9RJEHjc.net
ちなみに言っとくと
 >>142 人違いです　書き込んだことあるのはこの面白スレだけなので
あとついでにもう一問
整数 N に対し、rad(N) を N の互いに異なる素因数の積と定める。
正の整数 n に対して (1+√2)^n を展開した時の √2 の係数を a_n とおくと、
n を奇数の中から適切に選んで rad(a_n)/a_n を任意に小さくできることを示せ。

160:１３２人目の素数さん
18/11/10 05:01:41.49 QJPqV+Y8.net
ヒントあってもムズい。
存在すれば０までは簡単だけど。

161:１３２人目の素数さん
18/11/10 05:09:34.22 0LaPCkg7.net
>>150
a_n = {(1+√2)^n - (1-√2)^n} / (2√2),
{(1+√2)^m + (1-√2)^m}/2 は自然数。
∴　a_{pq} は a_p および a_q で割り切れる。
さて、どうするか？

162:１３２人目の素数さん
18/11/10 05:35:01.43 EuCYu9xA.net
>>150
こっちの方はできたかな？
RをQ[√2]の整数環とする。
p≡3.5 (mod 8)である素数をとる。
x^2 - 2 = 0は mod p で解を持たないからQ/Zのpの拡大次数は2でpRはRの素イデアル。
とくにa+b√2∈p^iR ⇔ a∈p^iZ かつ b∈p^iZ である。
ここで n をR/p^2Rの乗法群の位数とするとき(1+√2)^n ≡ 1 (mod p^2R)であるからa≡1 (mod p^2) かつ b≡0 (mod p^2)である。
とくにこのとき rad b ≦ b/p であるから rad b / b ≦ 1/p となる。
p≡3.5 (mod 8)である素数は無数にあるから主張は示された。

163:１３２人目の素数さん
18/11/10 05:45:34.35 EuCYu9xA.net
あれ？素数取り直す必要ないか。
R/3^iRの乗法群の位数をnとすれば(1+√2)^n = a + b√2 とおくとき同様にしてb ≡ 0 (mod 3^i)だから
b / rad b ≦ 1/3^(i-1)でいいのか。

164:１３２人目の素数さん
18/11/10 05:57:33.06 P9RJEHjc.net
>>153
その n が奇数になる保証はあるかい？

165:１３２人目の素数さん
18/11/10 05:59:55.44 EuCYu9xA.net
ありゃ？とすると代数的整数論のテクニック使う必要すらないや。
(1+√2)^(8・3^(i-1)) = a[i] + b[i]√2 とおいて a[i] ≡ 1 (mod 3^i)、b[i] ≡ 0 (mod 3^i) を帰納法で示せばいいだけだ。

166:１３２人目の素数さん
18/11/10 06:01:19.90 EuCYu9xA.net
あ、奇数っていう制限もあるのか。

167:１３２人目の素数さん
18/11/10 06:03:33.77 0LaPCkg7.net
>>152
n = (2^r) -1 のとき　a_n は 2n-1 で割り切れるらしい。
といっても平方因子じゃないが…
a_7 = 13^2,
a_15 = 5^2･29･269,

168:１３２人目の素数さん
18/11/10 06:31:54.82 EuCYu9xA.net
>>155
とりあえず代数的整数論つかえば n が奇数もクリアできた。
p ≡ 3、5 (mod 8)にとっておけば p^2 ≡ 9 (mod 16)なのでRの乗法群の位数は16で割り切れない。
とくに 1+√2 + pR がある数の8乗であれば1+√2 + pRの位数は奇数である。
よって方程式 x^8 - (1+√2) が R/pRで完全分解する素数pをとればよい。
そのような素数はチェボタレフ密度定理により無限にある。

169:１３２人目の素数さん
18/11/10 06:33:49.21 EuCYu9xA.net
かいたあとに気づく。orz。これも初等的にいける。けど、もういいや。これで。

170:１３２人目の素数さん
18/11/10 06:36:20.52 0LaPCkg7.net
>>158
　と思ったが、間違えたようだ。ｽﾏｿ

171:１３２人目の素数さん
18/11/10 07:34:42.59 0LaPCkg7.net
>>158
どうやれば平方因子が（無限に）出てくるか、という問題らしいけど、サパーリです。

172:１３２人目の素数さん
18/11/10 11:22:16.94 QJ6NJqU7.net
コインを１００回投げて表が連続した最大数が５のとき、
表がでる確率の期待値と最頻値および９５％信頼区間を求めよ。

173:１３２人目の素数さん
18/11/10 12:31:29.30 8Fs/tUZA.net
>>159
それは題意とは別のことの証明みたい
nを奇数に制限した時に数列 a_n に素因数が無限に出現することの証明　これもこれですごいんだけど

174:１３２人目の素数さん
18/11/10 13:53:36.51 mkbHRdk3.net
>>155
初等的に。
(1+√2)^n = a[n] + b[n]√2 (a[n],b[n]∈Z) として b[3・5^i] ≡ 0 (mod 5^(i+1))をしめす。
i=0のとき(1+√2)^3 = 7+5√2より成立。
i=kで成立するとしてi=k+1のとき
b[3・5^(i+1)] = 5a[3・5^i]^4 b[3・5^i] + 10a[3・5^i]^2 b[3・5^i]^3 + b[3・5^i]^5
だから成立。
これを用いて
rad b[3・5^i]/b[3・5^i] ≦ 1/5^i。

175:１３２人目の素数さん
18/11/10 18:49:11.34 zIdKF+X8.net
>>149
もうちょいおながいします。

176:１３２人目の素数さん
18/11/10 19:05:10.64 0LaPCkg7.net
>>150 >>165
n=3･5^i　のとき
　a_n = {(1+√2)^n - (1-√2)^n}/(2√2) ≡ 0,　　(mod 5^(i+1))
(略証)
iについての帰納法で
i=0、n=3 のとき
　a_3 = {(1+√2)^3 - (1-√2)^3}/(2√2) = 5 ≡ 0,　　(mod 5)
m で成立するとして n=5m のとき
a_{5m} / a_m = {(1+√2)^(5m) - (1-√2)^(5m)} / {(1+√2)^m - (1-√2)^m}
= {(1+√2)^(4m) + (1-√2)^(4m)} + (-1)^m･{(1+√2)^(2m) + (1-√2)^(2m)} +1
= {64(a_m)^2 + 32(-1)^m}^2 +2} + (-1)^m･{8(a_m)^2 + 2(-1)^m} +1
= 64(a_m)^4 + 40(-1)^m･(a_m)^2 + 5
≡ 0　(mod 5),　　　　　(← a_m≡0)
だから n=5m でも成立。
ここで
(1+√2)^(2m) + (1-√2)^(2m) = {(1+√2)^m - (1-√2)^m}^2 + 2(-1)^m
　= 8(a_m)^2 + 2(-1)^m,
(1+√2)^(4m) + (1-√2)^(4m) = {(1+√2)^(2m) + (1-√2)^(2m)}^2 - 2
　= {8(a_m)^2 + 2(-1)^m}^2 - 2
　= 64(a_m)^2 + 32(-1)^m (a_m)^2 + 2,
を使った。

177:１３２人目の素数さん
18/11/10 22:23:10.80 P9RJEHjc.net
>>165 >>167
正解　実は自分もこのくらい初等的な証明の存在は投稿してから気づいた
 >>166
しょうがないなあ
 >>149 の続き
a_n の絶対値は全て１であるから n>m の時
|S(n)-S(m)| = |Σ_(k=m+1,n) a_(2k-1)|
≦ Σ_(k=m+1,n) |a_(2k-1)|
= n-m.
したがって、一般の n,m≧1 について
|S(n)-S(m)| ≦ |n-m|
が成り立つ。これと >>149 の式を組み合わせると…？

178:１３２人目の素数さん
18/11/11 00:03:41.56 6OpEPnNJ.net
>>168
|S(3n)|≦nですか？
答え0と予想してるんですけど？
1/3?

179:１３２人目の素数さん
18/11/11 00:17:10.76 6OpEPnNJ.net
あ、いや、なるほど！わかったかも！
でも偶数項もなんとかせねば！

180:１３２人目の素数さん
18/11/11 00:23:46.00 6OpEPnNJ.net
気のせいだった。ムズイ

181:１３２人目の素数さん
18/11/11 02:26:17.27 sLf3laj9.net
>>167 のようにおくと
a_{5m} = 64(a_m)^5 + 40(-1)^m･(a_m)^3 + 5 a_m,
(略証)
mについての帰納法による。
m=1 のとき
　a_1 = 1，a_5 = 29 だから成立。
m 以下で成立すれば…
a_{m+1} - a_{m-1} = 2a_m = 2a,
a_{m+1}a_{m-1} = (a_m)^2 + (-1)^m = aa + (-1)^m,
から
a_{m+1}^3 - a_{m-1}^3 = 2a[(2a)^2 +3{aa+(-1)^m}] = 14a^3 +6(-1)^m a,
a_{m+1}^5 - a_{m-1}^5 = 2a[(2a)^4 +5(4aa){aa+(-1)^m} +5{aa+(-1)^m}^2] = 82a^5 +60(-1)^m a^3 +10a,
が出る。また、
64(a_{m+1})^5 + 40(-1)^{m+1}･(a_{m+1})^3 + 5a_{m+1} - a_{5(m-1)}
　= 64(a_{m+1}^5 - a_{m-1}^5) - 40(-1)^m･(a_{m+1}^3 - a_{m-1}^3) + 5(a_{m+1} - a_{m-1})
　= 64{82a^5 + 60(-1)^m･a^3 + 10a} - 40{14(-1)^m a^3 + 6a} ＋ 10a
　= 82{64a^5 + 40(-1)^m･a^3 + 5a}
　= 82 a_{5m},　　　(← 帰納法の仮定)
以上により
a_{5(m+1)} = 82a_{5m} + a_{5(m-1)} = 64(a_{m+1})^5 + 40(-1)^{m+1}･(a_{m+1})^3 + 5a_{m+1},
∴　m+1 でも成立する。

182:１３２人目の素数さん
18/11/11 03:18:51.59 /I0SuFdi.net
>>149
できたかも。
まず >>149を一般化して
S[3N] = S[2N] - S[N]
S[3N-1] = S[2N-1] - S[N]
S[3N+1] = S[2N+1] - S[N]
さらにT[N] = Σ[n≦2N, n:evev] a[n]とおいて
T[3N] = S[2N] - T[N]

183:。 T[3N+1] = S[2N+1] - T[N]。 T[3N-1] = S[2N-1] - T[N]。まず|S[N]|、|T[N]| ≦ N^(3/4)(log (3*N)))^2を示す。 f(x) = x^(3/4)(log (x+1))^2とおくときx≧1において多分 f(3x)≦f(2x) + f(x)、 f(3x+1)≦f(2x+1) + f(x)、 f(3x-1)≦f(2x-1) + f(x) である。(∵パソコンでグラフ描いてみた) よって成立。よって lim[n→∞](S[N]+T[N])/N = 0 である。

184:１３２人目の素数さん
18/11/11 04:37:04.53 WkH7Bxld.net
>>173
あれ？なんかおかしい気がする。
ひとまず撤回。

185:１３２人目の素数さん
18/11/11 04:40:28.26 3J0JXQFX.net
今わかった。はっきりおかしい。orz。>>173無視してください。

186:１３２人目の素数さん
18/11/11 05:41:25.27 /oKi5paQ.net
>>26が一応できたけど、証明が長くなった。
もし模範解答が短いなら書くだけ損なので、あまり書きたくないｗ

187:１３２人目の素数さん
18/11/11 05:44:17.33 /oKi5paQ.net
>>79は2種類の証明ができて、lim_(n→∞) (1/n)Σ_(k=1,n)a_k＝0 が証明できた。
1つ目の方法は、正の実数xに対して S(x)＝Σ(1≦k≦x) a(2k－1) と置いてから、
>>149の類似品を作って、それを展開しまくってたくさんのS(x)の和にしたあとに、
その和を適当に区切ってからそれぞれ評価して、
limsup_x S(x)/x と liminf_x S(x)/x を考える方法。
簡単だけど計算がごちゃごちゃしてて、8レスくらいになった。
計算ミスしてる可能性もある。
2つ目の方法は、>>149の類似品を使いながら、素数定理の簡単な証明
URLﾘﾝｸ(people.mpim-bonn.mpg.de)
と同じやり方を使う方法。実はこっちの方が先にできた。これは7レスくらい。

188:１３２人目の素数さん
18/11/11 10:17:49.16 6OpEPnNJ.net
>>177
おお、素晴らしい。あげてくださりませ。

189:１３２人目の素数さん
18/11/11 10:22:49.91 6OpEPnNJ.net
そうなんだよね～
ディリクレ級数はまず真っ先に思いつくのはつくんだけど、母関数と違って関数等式作れなくてs=1近傍での振る舞いが確定できなかった。
どうやったんですか？
関数等式作れました？

190:１３２人目の素数さん
18/11/11 13:14:33.63 FVh8W5vn.net
>>177
んーなんかできてるっぽいね　やや略式ではあるけど一応答え載せときます
（これからも答え複雑になりそうな時はこんくらい省いても問題ないんじゃないかな　まあでもこれは個人の感覚か）
>>149 を使って、例えば
S(9n) = S(6n)-S(3n) = S(6n)-S(2n)+S(n) = S(4n)-2S(2n)+S(n)
のように、S(3N) を S(2N)-S(N) に置き換える操作を繰り返していく時、各辺を
Σ_(c∈C) σ(c)S(cn) (Cは正整数の有限集合、各cに対してσ(c)は整数)
とおいた時の Σ_(c∈C) |σ(c)c| の値は操作により増加しないことがわかる。
（このことは、操作を適用する項だけに着目して、その項の操作前後の変化を考えればわかる）
（上の例では 9 ≧ 6+3 ≧ 6+2+1 ≧ 4+2*2+1）
したがって、a>b>0 かつaとbの偶奇が一致しない時
S((3^a)n) = S((2^a)n) - S((3^b)n) + (それ以外)
と展開することができることから、limsup |S(n)/n|=μ とおくと >>168 から
(3^a)μ ≦ |2^a-3^b| + limsup((それ以外)/n)
≦|2^a-3^b| + (3^a-2^a-3^b)μ.
よって、μ ≦ |2^a-3^b|/(2^a+3^b).
ディリクレのディオファントス近似定理より
|mlog_3(2) - (1/2)log_3(2) - m'| (m,m'は十分大きい正の整数) は任意に小さくすることができるので、
a=2m-1, b=2m' とおけば a

191:,b は条件を満たし、|2^a-3^b| も (2^a+3^b) と比べて任意に小さくなる。ゆえに、μ=0. さらに >>173 の T(n) について limsup|T(n)/n|=ν とおくと、 3ν = limsup|T(3n)/n| ≦ limsup|S(2n)/n| + limsup|T(n)/n| = ν から、ν=0.　以上より、示された。

192:１３２人目の素数さん
18/11/11 14:15:47.83 FVh8W5vn.net
よければ >>177 の手法ももうちょい詳しく聞いてみたいな
ここからはやや余談。コラッツの問題は
f(n)=n/2 (if 2|n), 3n+1 (otherwise)
とおいた時 f の合成による値の挙動を問う問題でご存知の通りまだ未解決なんだけど、
kを正の整数として『（１に到達するまでの操作の回数）mod k』で自然数を分類した時に何か言えないか？
を考えることができるのではと思い、感触をつかむためまず手始めに
g(n)=n/3 (if 3|n), 2n+1に最も近い3の倍数 (otherwize)
とした時にできる同類の問題を考えてみた、というのが >>79 の問題。
どんな自然数もgの合成でいずれ1に到達することは簡単にわかるけど、
それでもこの問題の（思いつく限り簡単な）解は >>180 のようにやや込み入ったものになっていて、以外、という印象。
本来のコラッツ数列で同類の問題を考えた時にどうなるかは、少なくとも自分には未解決です
あと実は >>26 は >>79 の解からも着想を得てできた問題で、要は
「動き方が制限されている関数（実→実関数の連続性、整数→整数関数のリプシッツ連続性、等）に
非有理的な”漸化式”（f(x),f(x+1),f(x+√2)間、S(n),S(2n),S(3n)間、等）を設けた時の挙動」
を問う問題を他にも作ってみたい、という感じでできたものでした　まあ解法は若干違うものになったんだけど…
>>26 の想定解は >>180 と同じぐらいかそれ以下の分量なんだけど、
他の方法も見てみたいし、もしお時間あれば概略だけでも是非書いてみてくださいな

193:１３２人目の素数さん
18/11/11 14:18:07.45 FVh8W5vn.net
以外、じゃねえ、意外

194:１３２人目の素数さん
18/11/11 14:23:27.97 FVh8W5vn.net
連投すまん。
g(n)=n/3 (if 3|n), 2nに最も近い3の倍数 (otherwise)
でした

195:１３２人目の素数さん
18/11/11 14:33:02.52 /oKi5paQ.net
>>79の解答。
正の実数xに対して S(x)＝Σ(1≦k≦x) a(2k－1) と置く。
ただし、0＜x＜1のときは S(x)＝0 と定義する。
η(x)＝S(3x)－S(2x)＋S(x) (x＞0)
と置くと、>>149と同じような計算をして、η(x)は有界であることが示せる。
α＝limsup_(x→∞)S(x)/x, β＝liminf_(x→∞)S(x)/x と置くと、
－1≦β≦α≦1 である。α＝β＝0 を示したい。
S(3x)＝S(2x)－S(x)＋η(x) をxで割ってlimsup_xを取ると、
3α≦2α－β となるので、α＋β≦0 となる。また、liminf_xを取ると
3β≧2β－α となるので、α＋β≧0 となる。よって、α＋β＝0 となる。
β≦αにより0＝α＋β≦2αとなるので、0≦αとなる。

196:１３２人目の素数さん
18/11/11 14:36:34.89 /oKi5paQ.net
次に、S(3x)＝S(2x)－S(x)＋η(x) において、x＞0をx/3＞0で置き換えると
S(x)＝S((2/3)x)－S(x/3)＋η(x/3) となるので、n≧1とx＞0に対して、帰納的に
S(x)＝S((2/3)^n x)－Σ(k＝0～n－1)S((2/3)^k x/3)＋Σ(k＝0～n－1)η((2/3)^k x/3)
が成り立つ。特にx＞1のとき、n_x＝[log_{3/2}x]＋1と置けば、
0 ＜ (2/3)^{n_x} x ＜ 1 となるので、S((2/3)^{n_x} x)＝0 であり、
S(x)＝－Σ(k＝0～n_x－1)S((2/3)^k x/3)＋Σ(k＝0～n_x－1)η((2/3)^k x/3)
となる。この式では、Σの部分は n_x－1 までの和なので、
x に依存して和の項数が増えることに注意。

197:１３２人目の素数さん
18/11/11 14:40:11.70 /oKi5paQ.net
ηが有界であることから、x のオーダーとして
Σ(k＝0～n_x－1)η((2/3)^k x/3)＝O(n_x)＝O([log_{3/2}x]＋1)＝O(log x) (x→∞)
である。よって、
S(x)＝－Σ(k＝0～n_x－1)S((2/3)^k x/3)＋O(log x)
である。次に、s(x)＝S(x)/x (x＞0) と置く。－1≦s(x)≦1である。上の式をxで割って
s(x)＝－Σ(k＝0～n_x－1) (2/3)^k (1/3) s((2/3)^k x/3)＋o(1)
となる(o(1)の部分は、こだわるならO((log x)/x)と書いた方が精密だが、ここではo(1)で十分)。
ここで、δ＞1を任意に取って固定する。Σの部分を
Σ(k＝0～n_x－1) ＝ Σ(k：(2/3)^k x/3＜δ)＋Σ(k：(2/3)^k x/3≧δ)
と分解する。

198:１３２人目の素数さん
18/11/11 14:42:57.29 /oKi5paQ.net
Σ(k：(2/3)^k x/3＜δ) (2/3)^k (1/3) s((2/3)^k x/3)
≧Σ(k：(2/3)^k x/3＜δ) (2/3)^k (1/3)(－1)
＝Σ(log_{3/2}(x/(3δ))＜k≦n_x－1) (2/3)^k (1/3)(－1)
≧Σ([log_{3/2}(x/(3δ))]＜k) (2/3)^k (1/3)(－1)
＝(－1/3)(2/3)^{ 1＋[log_{3/2}(x/(3δ))] } * 1/(1－2/3)
＝o(1)
である。

199:１３２人目の素数さん
18/11/11 14:45:18.55 /oKi5paQ.net
また、
Σ(k：(2/3)^k x/3≧δ) (2/3)^k (1/3) s((2/3)^k x/3)
≧Σ(k：(2/3)^k x/3≧δ) (2/3)^k (1/3) inf(t≧δ)s(t)
＝Σ(1≦k≦log_{3/2}(x/(3δ))) (2/3)^k (1/3) inf(t≧δ)s(t)
＝Σ(1≦k≦[log_{3/2}(x/(3δ))]) (2/3)^k (1/3) inf(t≧δ)s(t)
＝(1/3)(2/3)(1－(2/3)^{ [log_{3/2}(x/(3δ))] })/(1－2/3) * inf(t≧δ)s(t)
＝(1/3)(2/3)(1－o(1))/(1－2/3) * inf(t≧δ)s(t)
＝(2/3)(1-o(1)) * inf(t≧δ)s(t)
＝(2/3)inf(t≧δ)s(t)－(2/3)o(1)inf(t≧δ)s(t)
＝(2/3)inf(t≧δ)s(t)＋o(1)
である。

200:１３２人目の素数さん
18/11/11 14:48:06.02 /oKi5paQ.net
これらの不等式を
s(x)＝－Σ(k＝0～n_x－1) (2/3)^k (1/3) s((2/3)^k x/3)＋o(1)
と合わせて、
s(x) ≦ o(1)－(2/3)inf(t≧δ)s(t)
となるので、limsup_x を取って α≦－(2/3)inf(t≧δ)s(t) となる。
δ＞1は任意だから、δ→∞として、α≦－(2/3)β となる。
よって、3α＋2β≦0 となるので、α＋β＝0によりα≦0となる。
一方でα≧0だったから、α＝0となる。よって、β＝0となる。
よって、lim(x→∞) S(x)/x＝0 である。

次ページ