- 1 名前：１３２人目の素数さん mailto:sageteoff [2015/05/22(金) 09:38:35.72 ID:wNOlCA2c.net]
- 過去ログ
www3.tokai.or.jp/meta/gokudo-/omoshi-log/
まとめwiki
www6.atwiki.jp/omoshiro2ch/
1 cheese.2ch.net/test/read.cgi/math/970737952/
2 natto.2ch.net/test/read.cgi/math/1004839697/
3 science.2ch.net/test/read.cgi/math/1026218280/
4 science.2ch.net/test/read.cgi/math/1044116042/
5 science.2ch.net/test/read.cgi/math/1049561373/
6 science.2ch.net/test/read.cgi/math/1057551605/
7 science2.2ch.net/test/read.cgi/math/1064941085/
8 science3.2ch.net/test/read.cgi/math/1074751156/
9 science3.2ch.net/test/read.cgi/math/1093676103/
10 science4.2ch.net/test/read.cgi/math/1117474512/
11 science4.2ch.net/test/read.cgi/math/1134352879/
12 science6.2ch.net/test/read.cgi/math/1157580000/
13 science6.2ch.net/test/read.cgi/math/1183680000/
14 science6.2ch.net/test/read.cgi/math/1209732803/
15 science6.2ch.net/test/read.cgi/math/1231110000/
16 science6.2ch.net/test/read.cgi/math/1254690000/
17 kamome.2ch.net/test/read.cgi/math/1284253640/
18 kamome.2ch.net/test/read.cgi/math/1307923546/
19 uni.2ch.net/test/read.cgi/math/1320246777/
20 wc2014.2ch.net/test/read.cgi/math/1356149858/
- 152 名前：１３２人目の素数さん [2015/06/15(月) 22:59:41.61 ID:w9Nq94Ln.net]
- 7×7のマス目のいくつかのマスの中心に、以下の条件を満たすようにゴマを1つ置く。
条件：置かれたゴマのうちのどれか4つを頂点とする長方形で、その辺がマス目の辺に平行なものができてはならない。
最大でいくつゴマを置くことができるか。
- 153 名前：１３２人目の素数さん mailto:sage [2015/06/15(月) 23:11:35.53 ID:O9+dQNu/.net]
- なんか日本語おかしいよ
- 154 名前：１３２人目の素数さん mailto:sage [2015/06/16(火) 00:24:40.43 ID:fqscTCpW.net]
- >>137
最初地道にやった結果と、
wikipediaの「バーンサイドの補題」を参考にしてやった結果が一致したから
合ってるかな
1493通り
- 155 名前：１３２人目の素数さん mailto:sage [2015/06/16(火) 00:43:12.01 ID:fqscTCpW.net]
- >>150
7列からどの２列を選んで重ねても、ゴマのあるマスが２箇所以上重なることがない
という条件なので、多分21個。
例：
(1,1)(1,2)(1,3)
(2,1)(2,4)(2,5)
(3,1)(3,6)(3,7)
(4,2)(4,4)(4,6)
(5,2)(5,5)(5,7)
(6,3)(6,4)(6,7)
(7,3)(7,5)(7,6)
- 156 名前：１３２人目の素数さん mailto:sage [2015/06/16(火) 01:14:16.63 ID:H1/I840P.net]
- >>152
俺も地道に計算して1493通りになったんだけど、ネットで見つけた問題の模範解答は違っていた…
どう思う？
www.y-sapix.com/articles/19267/
- 157 名前：１３２人目の素数さん mailto:sage [2015/06/16(火) 03:30:19.03 ID:fqscTCpW.net]
- >>154
そのsapixの解答は、明らかに間違ってるな。
(C)以外の(A)の場合と、(D)以外の(B)の場合において、上下反転をダブルカウントしてる。
実際は、(A)も(B)も
(90-3!)/2+3で45通りなので
45*2+(2896-45*2)/2=1493
が正解。
そりゃ「優秀賞に値する答案はいただけませんでした」になるわな（苦笑）
その間違った模範解答をエスパーするのは無理。
sapix大丈夫？
- 158 名前：１３２人目の素数さん mailto:sage [2015/06/16(火) 03:36:36.67 ID:fqscTCpW.net]
- （それ、最終回の問題だったのか…とんだ有終の美だな…）
- 159 名前：１３２人目の素数さん mailto:sage [2015/06/16(火) 03:57:44.00 ID:H1/I840P.net]
- やはり間違っていたようですね。安心した。
2007年頃に塾のバイトしていたときに、m色n個ずつの円順列や数珠順列を
(m、n)=(2、4)、(3、3)、(3、4)の場合を出題した
- 160 名前：ことがあったんだけど、
当時の解答の手書きメモと、最近ネットで見かけたsapixの解答が違っていて>>137に書いた次第。
ちなみに私の解法は黒玉の連続する個数で５通りに場合分けして、エレガントとは程遠い解法でしたが…。 [] - [ここ壊れてます]
- 161 名前：１３２人目の素数さん mailto:sage [2015/06/16(火) 05:24:18.29 ID:goQtvF3x.net]
- プログラムでカウントさせたところ、1493通りでした。
ちなみに、色を入れ替えて一致するものも同一視すると297通り
- 162 名前：１３２人目の素数さん mailto:sage [2015/06/16(火) 06:06:45.29 ID:H1/I840P.net]
- >>158
ありがとうございます。プログラムは ご自分で作られたのですか？
模範解答と答えが違うとき、まず自分を疑ってしまいがちですが、こんなこともあるのですね。
- 163 名前：１３２人目の素数さん mailto:sage [2015/06/16(火) 08:49:30.12 ID:deTZhkJL.net]
- >>159
こんな感じのもので確かめました。
ttp://codepad.org/DmPnExwI
- 164 名前：１３２人目の素数さん [2015/06/16(火) 13:35:34.98 ID:TmgIPwFn.net]
- 誰か>>18 >>40 >>66の解き方教えて
- 165 名前：１３２人目の素数さん mailto:sage [2015/06/16(火) 21:57:51.55 ID:LTpWN3vT.net]
- >>66 (1)は解けた
(50k^2+20k+2)^2+1=5(10k^2+6k+1)(50k^2+10k+1)
よりn=50k^2+20k+2(k≧1)のときn!はn^2+1で割り切れる
(2)は素数pが4n-1型のとき、((p-1)/2)!≡±1 (mod p) になることまでは分かったが…
- 166 名前：１３２人目の素数さん mailto:sage [2015/06/17(水) 01:20:30.74 ID:QCqizCQx.net]
- >>155-157
あまり責めないでやれ。
SAPIXというと、ある年代以降の生まれの人には
絶大な信用があるが、
要するに代ゼミだよと言えば、ある年代以前の人なら
多くを期待すべき相手でないことが解る。
M&Aは、ブランド名のロンダリングでもある。
- 167 名前：１３２人目の素数さん [2015/06/18(木) 09:44:50.83 ID:XPs4xt6p.net]
- 2015個の連続する正の整数からなる列であって, ちょうど155個の素数を含むようなものが存在することを示せ
- 168 名前：１３２人目の素数さん mailto:sage [2015/06/18(木) 11:26:36.76 ID:pAuqikyi.net]
- >>164
nからn+2014までの自然数のうち素数の個数をf(n)とおくと、
f(1)=305であり、
素数定理などから、明らかにf(N)<155となるNが存在する。
ここで、任意の自然数nについて、
f(n+1)-f(n)は、1,0,-1のいずれかなので、
f(n)=155，1<n<Nを満たすnが存在する。
定義域が整数である場合の中間値の定理のようなものですな。
本当はf(N)<155となるNの具体例を示したかったのだが、
いきなりf(500000)=155となることを見つけてしまったので^^;
- 169 名前：１３２人目の素数さん mailto:sage [2015/06/18(木) 19:54:40.67 ID:/w4mTADd.net]
- >>165
f(N)<155となるNの存在をいうだけなら素数定理を持ちださなくても
あきらかにf(2016!+2)=0だよね
- 170 名前：１３２人目の素数さん mailto:sage [2015/06/19(金) 18:55:13.73 ID:n/Pn+0sj.net]
- >>40は上手くいきそうでいかない
「六角形」の辺を適当に結んで平行云々でパスカルの逆、って流れだと
いまいち綺麗にできない（場合分けが下手？）
数式に持ち込んでもごちゃごちゃ
前提条件が妙に強いからサクッとできるのだろうが
- 171 名前：１３２人目の素数さん [2015/06/21(日) 14:51:11.58 ID:eRDPXgWJ.net]
- >>66 (2)
まず, 条件を満たすnを具体的に構成する方法を示す.
kを3以上の奇数とする. k!+1は奇数なのでp|(k!+1)である奇素数pが存在する.
k!+1は1,2,...,kで割り切れず, またk,pはともに奇数なのでp-1>k
ここで, ウィルソンの定理より(p-1)!≡-1(mod p)なので,
-1≡(p-1)!
≡k!*(k+1)*...*(p-1)
≡(-1)*(k+1)*...*(p-1)
≡(-1)^(p-k)*(p-k-1)!
≡(p-k-1)! (∵p-kは偶数)
よ�
- 172 名前：ﾁてp|((p-k-1)!+1)
k+(p-k-1)=p-1<pより, kかp-k-1の一方はp/2より小さい.
その小さい方をnとすれば, p|(n!+1)かつ2n<pが成り立つので, このnは条件を満たす.
次に条件を満たすnが無限個存在することを示す.
条件を満たすnとして n_1,n_2,...,n_m が与えられたとき, そのいずれとも異なるn_(m+1)が存在して条件を満たすことを示せばよい.
(n_1)!+1,(n_2)!+1,...,(n_m)!+1の素因数全体の集合をPとする.
Pの元のいずれよりも大きな3以上の奇数kをとり, 上記の構成法に従ってp,nを定める.
このときp>kよりp∉Pなので, nはn_1,n_2,...,n_mのいずれとも異なる.
よってn=n_(m+1)とすればよい. 以上より示された. [] - [ここ壊れてます]
- 173 名前：１３２人目の素数さん [2015/06/21(日) 14:59:56.59 ID:eRDPXgWJ.net]
- 正の整数からなる集合Aは次の条件(i),(ii),(iii)を全て満たす：
条件(i)：Aは3個以上の元を持つ
条件(ii)：a∈Aかつ d|a (d>0)ならばd∈A
条件(iii)：a, b∈Aかつ1<a<bならば1+ab∈A
このとき, Aは全ての正の整数を含むことを示せ.
- 174 名前：１３２人目の素数さん mailto:sage [2015/06/22(月) 20:30:45.44 ID:pYzkOfH1.net]
- >>169
条件より1<a<bなるa,bが存在して1,a,b,ab+1∈A
a,b,ab+1のうち少なくとも1つは偶数なので2∈A
よって2b+1,2(2b+1)+1∈A
b,2b+1,2(2b+1)+1のうち少なくとも1つは
3の倍数であるかまたは6で割った余りが2
前者の場合3∈A
後者の場合6k+2∈Aとして
3k+1∈A
2(3k+1)+1=3(2k+1)∈A
よって3∈A
ここまでで1,2,3∈Aが示せたので4,5∈Aもいえる
ここでn(≧5)以下の正整数が全てAに属すると仮定する
nが偶数のとき2<n/2∈Aよりn+1∈A
nが奇数のとき2<(n+1)/2∈Aよりn+2∈A
よってn(n+2)+1=(n+1)^2∈Aよりn+1∈A
以上よりAは全ての正整数を含む
- 175 名前：１３２人目の素数さん mailto:sage [2015/06/22(月) 21:01:14.59 ID:pYzkOfH1.net]
- >>170
抜けがあったので訂正
＞b,2b+1,2(2b+1)+1のうち少なくとも1つは
＞3の倍数であるかまたは6で割った余りが2
b≡5(mod 6)の場合これは成り立たないが
このときはb(2b+1)+1≡2(mod 6)がAに属するので
「後者の場合」に帰着する
- 176 名前：１３２人目の素数さん mailto:sage [2015/06/22(月) 21:16:09.10 ID:pYzkOfH1.net]
- ＞よって2b+1,2(2b+1)+1∈A
＞b,2b+1,2(2b+1)+1のうち少なくとも1つは
よって2b+1,b(2b+1)+1∈A
b,2b+1,b(2b+1)+1のうち少なくとも1つは
とすればいいだけだった…
- 177 名前：１３２人目の素数さん mailto:sage [2015/06/23(火) 05:42:15.74 ID:bZvTLbCC.net]
- >>169の条件(iii)を改変したバージョンも解けたので問題として出しておく
正の整数からなる集合Aは次の条件(i),(ii),(iii)を全て満たす：
条件(i)：Aは3個以上の元を持つ
条件(ii)：a∈Aかつ d|a (d>0)ならばd∈A
条件(iii)：a, b∈Aかつ1<a<bならばab-1∈A
このとき, Aは全ての正の整数を含むことを示せ.
- 178 名前：１３２人目の素数さん mailto:sage [2015/06/23(火) 23:32:20.59 ID:rY+w350S.net]
- どことなくコラッツの問題に似てるから
実は解くのが難しいとかそういう話なのかと思ったら
解けるのか
- 179 名前：１３２人目の素数さん mailto:sage [2015/06/25(木) 21:00:57.54 ID:35Y69c7I.net]
- 表裏の出る確率が均等でないコインが1枚ある。
これを繰り返し投げて出た結果によって、確率1/2の試行を実現したい。
投げる回数の期待値を最小にするにはどうすればいいか。
- 180 名前：１３２人目の素数さん mailto:sage [2015/06/25(木) 22:22:23.83 ID:2yBiznPm.net]
- 右手か左手に表裏の出る確率が均等でないコインを隠し、選んで貰う
- 181 名前：１３２人目の素数さん mailto:sage [2015/06/26(金) 10:13:21.94 ID:5yy/K2nU.net]
- >>175
最初「期待値」の意味がわからなかったけど、例えばこういうことかな。（これが期待値最小かどうかはおいといて）
判定結果は○／×で表すものとします。
偶数回目のみにチェックポイントを設け、以下の判定を行う。
そこまでに投げた回数をN=2^n*a（aは奇数、nは正の整数）とする。
次の判定を、決着がつかない限り、k=1からnまで順に繰り返す。
・N回目とN-2^(k-1)回目のコインの表裏が異なる場合、N回目は表なら○、裏なら×で決着。そうでない場合は決着せず。
有限回数で必ず決着する手段が存在しない以上、「ある条件を満たせば決着」という手法を考え
その条件に至るまでの回数の期待値ってのが問題になるわけね
- 182 名前：１３２人目の素数さん mailto:sage [2015/06/26(金) 10:42:50.12 ID:5yy/K2nU.net]
- さっきの >>177 の判定の意味がわかりにくいので補足。
基本となる手法は以下
偶数回目のみチェックする。
直前の２回が「裏表」なら○、「表裏」なら×で決着
それ以外は、その回では決着せず
この手法では、決着せずに試行を繰り返さないといけないケースは
２回ずつまとめてみると「表表」もしくは「裏裏」のパターンのみをくりかえす場合。
その決着しないケースをなるべく救済するために、今度は4の倍数回にチェックポイントを設け
直前４回が「裏裏表表」なら○、「表表裏裏」なら×とする。
この手法を追加しても、決着せずに試行を繰り返さないといけないケースは
４回ずつまとめてみると「表表表表」もしくは「裏裏裏裏」のパターンのみをくりかえす場合。
それををなるべく救済するため、8の倍数回にチェックポイントを設け
直前８回が「裏裏裏裏表表表表」なら○、「表表表表裏裏裏裏」なら×とする。
（以下略）
というのをまとめた結果。
- 183 名前：１３２人目の素数さん mailto:sage [2015/06/26(金) 12:09:01.54 ID:IIy/cicI.net]
- 1/2を期待できる方法（小道具を使うが、１回で完了）
コインの表を偶数、裏を奇数に対応づけ、コインを振り、止まった瞬間に時計の秒針を見て
偶数か奇数かをチェック。コインの偶奇と一致するかどうかで判定
ほぼ1/2を期待できる方法
でやすい面を表、でづらい面を裏と表すこととし、表のでる確率をpとする
コインを繰り返し振り、n回目の裏がでたのが、偶数回目だったか、奇数回目だったかで判定
確率pに対応して、下のようなｎを採用すれば、最大誤差1%程度になる。
0.99<p<1 なら、n=1で十分。
初めて裏がでるのが偶数回目となる確率＝p(1-p)+p^3(1-p)+...=p/(1+p)
初めて裏がでるのが奇数回目となる確率＝(1-p)+p^2(1-p)+...=1/(1+p)
0.8<p<0.99 なら、n=2辺りを用いる
二回目の裏がでるのが偶数回目となる確率＝(1-p)^2+C[3,1]p^2(1-p)^2+...=(1+p^2)/(1+p)^2
二回目の裏がでるのが奇数回目となる確率＝2p/(1+p)^2
0.6<p<0.8 なら、n=3辺り
３回目の裏がでるのが偶数回目となる確率＝3p(1-p)^3+C[5,2]p^3(1-p)^3+...=(3p+p^3)/(1+p)^3
３回目の裏がでるのが奇数回目となる確率＝(3p^2+1)/(1+p)^3
0.5<p<0.6 なら、n=4
４回目の裏がでるのが偶数回目となる確率＝(1-p)^4+C[5,3]p^2(1-p)^4+...=(p^4+6p^2+1)/(1+p)^4
４回目の裏がでるのが奇数回目となる確率＝(4p^3+4p)/(1+p)^3
- 184 名前：１３２人目の素数さん mailto:sage [2015/06/26(金) 12:13:45.71 ID:ya3KuOPO.net]
- あ、最後の行、ミスってる
×：４回目の裏がでるのが奇数回目となる確率＝(4p^3+4p)/(1+p)^3
○：４回目の裏がでるのが奇数回目となる確率＝(4p^3+4p)/(1+p)^4
ごらんのように、パスカルの三角形が登場してます。
- 185 名前：１３２人目の素数さん mailto:sage [2015/06/26(金) 12:44:04.27 ID:/ysslOVn.net]
- コイン以外のところから、確率1/2の事象を引っ張ってくるのは出題者の意図とはたぶん違うんじゃないかね。
それだったら、コインいらないし……。
- 186 名前：１３２人目の素数さん mailto:sage [2015/06/26(金) 20:46:11.23 ID:h7iWFEKI.net]
- >>175
ちょっと考えた
pが既知かつ近似解で良い場合
中心極限定理で適当にやればp=0,1以外はどうにでもなる
pが既知かつ厳密解が欲しい場合
初めて表が出るまでの回数をNとしてNが特定の回数だった場合を
新たに「表」として定義する
N=nの確率はp*(1-p)^(n-1)となるので適当に組み合わせれば
p=0,1以外なら任意の精度で「表」の確率が定義できそう
pが未知の場合
ベイズ的には初回は必ず1/2
と言うのは冗談だがpを推定してから上記の場合に持ち込むのかな
- 187 名前：１３２人目の素数さん mailto:sage [2015/06/26(金) 20:53:56.32 ID:h7iWFEKI.net]
- >>182に補足
元のお題は最小回数の作り方だから
pが既知かつ厳密解が欲しい場合については
N回投げて各出目の確率の和が1/2になる
組み合わせが見つかったらそれが最小のN
- 188 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 00:30:06.71 ID:/+u9NzxP.net]
- >>175 は、確率は未知という設定じゃないとつまんないので、自分はそっちで考える。
確率は未知であっても、確実に1/2の確率を実現できる方法を考えて、
回数の期待値は、未知だけど実際には存在する確率pの関数として表す。
「期待値最小」ということを厳密にどう判定するかは難しいが、
まずはよりよい関数となる手法を考え、もしかしたら
「pが未知でも成り立つ手法の中では、どんなpに対しても最小の期待値を持つ」手法が
存在するのかもしれない。
ちなみに、>>178 の「基本となる手法」で期待値を計算すると1/(p(1-p))となる。
（p=1/2で最小値4をとる）
>>177 の手法ではそれよりもどんなpにおいても小さい値になるのは明らかだが、
うまい計算方法が見つからなくて困ってる。
- 189 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 03:03:16.58 ID:/+u9NzxP.net]
- >>177 の期待値
f(p) = Π[n=0,∞](1+p^(2^n)+(1-p)^(2^n))
となるようだ。
>>178 の「基本となる手法」の期待値
g(p) = 1/(p(1-p))
と比較すると、こんな感じ。
p g(p) f(p)
0.1 11.111 10.585
0.2 6.250 5.698
0.3 4.762 4.186
0.4 4.167 3.574
0.5 4.000 3.401
- 190 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 03:30:28.63 ID:/+u9NzxP.net]
- pが未知なら、>>177が最強な気がしてきた。
誰か証明もしくは反証よろしく
- 191 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 09:14:57.33 ID:S/MSoatr.net]
- >>177の判定原理は表と裏の回数が等しい試行を組にして
「表」「裏」と名づけていると見ることができる
ゆえに>>178が最短の判定方法となっていることが証明できる
- 192 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 12:56:11.26 ID:AqwryHTX.net]
- 177(178)の方法において、どの出方はAが勝ちか、どの出方はBが勝ちか決めてみることにする。
その決め方は複数(多数)候補があるけれど、いいやりかたを選べば、
(177(178)の方法を使ったときに)ある場面において、表がでても裏が出てもAが勝ち(あるいはBが勝ち)
という場面を作り出すことができそう。
そういう場面が出来たなら、そこは実はコインを投げる必要がないということになる。
そして期待値は下がる。
となりそうな気がする。
- 193 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 14:30:27.03 ID:/+u9NzxP.net]
- >>188
なるほど。>>177 のルールのままだと、最後が表なら○と決めているので
最後まで決着しないけど、判定の部分のルールをたとえば
・N回目とN-2^(k-1)回目のコインの表裏が異なる場合、
kが奇数ならば、N回目は表なら○、裏なら×で決着。
kが偶数ならば、N回目は表なら×、裏なら○で決着。
としておけば、
表表裏
となった時点で、４回目は表でも裏でも○になるから
追加ルールとして
・その後のコインの表裏によらず、○か×かが確定した時点で、コインは投げない
というのを入れとくと、さらに回数の期待値は減るわけですね。
ううむ、最強からはほど遠かったか。
- 194 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 14:33:16.85 ID:/+u9NzxP.net]
- （さすがに、>>189 のルールでの期待値の計算はあきらめた）
- 195 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 14:50:27.11 ID:/+u9NzxP.net]
- >>188-190
よく考えたら、チェックポイントの２手以上前に○×が確定することは
ありえない（最後の２回が表裏と裏表で必ず○×が異なる）ので、
>>177のルール変更を
・N回目とN-2^(k-1)回目のコインの表裏が異なる場合、
N-1回目が表なら○、裏なら×で決着。
とでもしておくと、元のルールで表でも裏でも決着するケースでは
確実に１手減らすことができますね。
この方向性での改善としてはこれが最良かな。
- 196 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 16:41:16.45 ID:imKgYOrh.net]
- n次元空間にn+1個の頂点があり、全ての面が正三角形となる超立体の体積をエレガントに求めよ。
- 197 名前：１３２人目の素数さん [2015/06/27(土) 19:40:48.41 ID:n9T/LEaD.net]
- f(n)=2n^2+29と定める.
f(0),f)1),f(2),f(3)はいずれも素数であることが分かっている.
このとき,f(4),f(5),...,f(28)も全て素数であることを示せ.
ただし, 各fの値を実際に求めたり, 素数で順に割ったりしてはならない.
- 198 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 19:41:47.15 ID:iChne//v.net]
- >>175
これ、極端に考えればp=1.0でも題意を満たす必要があるんじゃ？
- 199 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 20:29:05.21 ID:iv70QRnH.net]
- p=1.0の場合はどのみち不可能なんだから期待値は∞ってことで問題なくね？
- 200 名前：１３２人目の素数さん [2015/06/27(土) 21:37:06.11 ID:1W0Ez/9a.net]
- (1)
自然数nに対して
(Σ[k=1..n],1/k)=P(n)/Q(n)
をみたす実数係数の多項式P(x),Q(x)は存在しないことを示せ
(2)
数列a(n)を
a(1)=2,a(n+1)=(1/(a(1)*a(2)*a(3)*....a(n)))-1
として定義する。
この時、nが偶然ならば、数列a(n)は定数数列であることを示し、その値を求めよ
- 201 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 21:43:26.06 ID:/+u9NzxP.net]
- >>192
1辺が1のn次元の正単体のn次元の体積をV(n)，中心から各頂点までの距離をR(n)とする。
V(1)=1，R(1)=1/2
n+1次元空間内に1辺1のn次元の正単体X(n)を配し、X(n)の各頂点から距離1となる点Aをとると、
AとX(n)はn+1次元の正単体X(n+1)を構成する。
AからX(n)におろした垂線の足をM、X(n+1)の中心をO、X(n)の1つの頂点をBとすると、
OA=OB=R(n+1)、MB=R(n)であり、
X(n+1)の各頂点に重さ1の質点を置いた時の重心がOであることからOA:OM=n+1:1となり、
OM=R(n+1)/(n+1)
OB^2-OM^2=MB^2（三平方の定理）より、整理すると(n(n+2)/(n+1)^2)(R(n+1))^2=(R(n))^2
∴ ((n+2)/(n+1))(R(n+1))^2=((n+1)/n)(R(n))^2=…=(2/1)(R(1))^2=1/2
∴ (R(n))^2=n/(2(n+1))
AM=((n+2)/(n+1))R(n+1)より、
V(n+1)=(1/(n+1))・AM・V(n)=((n+2)/(n+1)^2)R(n+1)V(n)
(V(n+1))^2=((n+2)^2/(n+1)^4)((n+1)/(2(n+2)))(V(n))^2=((n+2)/(2(n+1)^3))(V(n))^2
n≧2において
(V(n))^2=Π[k=1,n-1]((k+2)/(2(k+1)^3))
=((n+2)!/2)/(2^(n-1)・(n!)^3)=(n+1)/(2^n・(n!)^2)
∴ V(n)=(1/n!)√((n+1)/2^n)
n次元の錐体の体積が (1/n)・底面積・高さ であることは断りなく使った。
エレガント、ではない。
- 202 名前：１３２人目の素数さん [2015/06/27(土) 21:45:05.79 ID:1W0Ez/9a.net]
- (3)
面積および外接円の半径が全て整数であるような三角形は無数に存在することを示せ。
ただし相似な三角形は除く。
- 203 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 21:48:38.69 ID:/+u9NzxP.net]
- （数式を、カッコ多用ではなくちゃんと紙に書けば、そんなにゴチャゴチャはしてないんだよ…）
- 204 名前：１３２人目の素数さん mailto:sage [2015/06/27(土) 21:52:29.64 ID:/+u9NzxP.net]
- >>198
辺の長さは整数じゃなくていいのか？
- 205 名前：１３２人目の素数さん [2015/06/27(土) 21:58:42.68 ID:1W0Ez/9a.net]
- >>200
どちらでも構わない
- 206 名前：１３２人目の素数さん mailto:sage [2015/06/29(月) 04:10:45.50 ID:jBA8xQxN.net]
- >>196
(1) そのようなP(x),Q(x)が存在するとして矛盾を導く。
lim[n→∞](1/log n)Σ[k=1..n],1/k＝1であるから、
lim[n→∞](1/log n)(P(n)/Q(n))＝1 でなければならないが、
P(x)とQ(x)の最高次数に注目して計算すると矛盾することが分かる。■
(2) nが偶数なら a(n)＝－1/2, nが3以上の奇数なら a(n)＝－2が
成り立つことが数学的帰納法で証明できる。■
- 207 名前：１３２人目の素数さん mailto:sage [2015/06/29(月) 04:31:16.19 ID:jBA8xQxN.net]
- >>198
そのような三角形の無限列であって、互いに相似でないものが
構成できることを証明しようかと思ったが、別にその必要はなかった。
(3) 面積と外接円の半径が整数であるような三角形の集合をMと置く。
M上の二項関係～を以下のように定義する。
a,b∈Mに対して、a～b ⇔ aとbは相似.
このとき、～はM上の同値関係となることが分かる。
a∈Mの同値類を[a]と書くことにする。同値類の集合M/～は
M/～＝{ [a]｜a∈M }と表せる。このM/～が無限集合であることを
示せばよい。以下の補題を使う(証明は後回しにする)。
補題：任意の正整数nに対して、次を満たすA⊂Mが存在する。
・Aはn元集合.
・Aの任意の異なる2元は相似でない.
この補題により、各nに対して対応するA⊂Mを取れば、次が成り立つ。
・{ [a]｜a∈A }⊂M/～.
・{ [a]｜a∈A }はn元集合.
従って、M/～は少なくともn個の元を含む。nは任意だから、
M/～は無限集合である。最後に、上の補題を証明する。
- 208 名前：１３２人目の素数さん mailto:sage [2015/06/29(月) 04:43:55.79 ID:jBA8xQxN.net]
- 補題の証明：半径がnの円S
- 209 名前：を用意し、S上の3点A,B,Cを、三角形ABCが正三角形であるように取る。
円Sにおける弧BCは2つあるが、その中で短い方の弧をL1とする。L1から両端点B,Cを除いたものをL2とする。
L2上の点Pを任意に取ると、三角形APBについて、次が成り立つことが分かる。
(i) ∠PAB ＜ 60°＜∠PBA.
(ii) ∠APB＝60°.
(iii) APBの面積をs(P)と置くと、0＜s(P)＜(3√3/4)n^2 が成り立つ.
(iv) P→Bのときs(P)→0であり、P→Cのときs(P)→(3√3/4)n^2 である.
さて、s(P)はP∈L2に関して連続関数であるから、(iii)と(iv)にも注意して、中間値の定理から、
任意のλ∈(0, (3√3/4)n^2) に対して、s(P)＝λを満たすようなP∈L2が存在する。
特に、λが正整数のときを考える。(3√3/4)n^2＞nであるから、λとしては
少なくとも1,2,…,nまでが選べる。対応するPをP_1,…,P_n とする。
三角形AP_iBをa_iと置けば、a_iの面積は i であり、a_iの外接円の半径はnである。
従って、a_i∈Mである。A＝{ a_1,…,a_n } と置けば、このAが題意を満たす。
実際、Aがn元集合であることは明らか。Aの任意の異なる2元が相似でないことは、
a_iの3頂点の角度に注目すればすぐに従う(具体的には(i),(ii)を使う)。■ [] - [ここ壊れてます]
- 210 名前：１３２人目の素数さん mailto:sage [2015/06/30(火) 20:34:38.25 ID:H5GoaVHE.net]
- >>198
3辺の長さを
4n+2, 4n^2*4n, 4n^2+4n+2
とすれば、面積は4n(n+1)(2n+1), 外接円の半径は2n^2+2n+1
- 211 名前：１３２人目の素数さん mailto:sage [2015/06/30(火) 22:09:05.54 ID:M1LX+grn.net]
- >>198
0より大きく1未満の任意の有理数 t を持ってきて、それを t=b/a と表したとき
(つまり、aとbは互いに素で、0<b<aの整数)
a^2-b^2,2ab,a^2+b^2
の3数は、原始ピタゴラス三角形の3辺を成す。その二倍形
2(a^2-b^2),4ab,2(a^2+b^2)
は、>>198の条件を満たす。
なお、205の例(4n^2*4nは4n^2+4nの誤植と思われる)は、ここに挙げたもので
a=b+1 としたものにあたる
- 212 名前：１３２人目の素数さん mailto:sage [2015/07/01(水) 01:01:33.17 ID:rdTrEG2D.net]
- >>205-206
その答えは、おととい
「高校生が自作問題を世に問うスレ」
の ≫584 に書いといたのと、同じものだな。
- 213 名前：１３２人目の素数さん [2015/07/03(金) 23:23:02.20 ID:rGXRJhyh.net]
- 一次独立な２つのベクトルx↑、y↑について
|x↑|≦|x↑+y↑|が成り立っているならば
任意の実数a≧1に対して |x↑+y↑|≦|x↑+a*y↑|となることを示せ。
- 214 名前：１３２人目の素数さん mailto:sage [2015/07/03(金) 23:43:12.41 ID:hJIQsZ5a.net]
- 最近話題のルーローの三角形形の掃除機ロボットを見て思いついた問題。
直径１の正方形の内部で、直径１のルーローの三角形が滑らかに回転するとき、
ルーローの三角形が通過する領域の面積を求めよ。
- 215 名前：１３２人目の素数さん mailto:sage [2015/07/04(土) 13:02:24.94 ID:fKcIqKgn.net]
- わりときれいな値になるんだな。
それに検索してみると、この動き自体がなかなかおもしろい。
- 216 名前：１３２人目の素数さん mailto:sage [2015/07/04(土) 13:20:18.83 ID:ZDm2eXaJ.net]
- 内部に入らない。
- 217 名前：209 mailto:sage [2015/07/04(土) 21:29:26.26 ID:TU5VZOTE.net]
- ちなみに俺は解けなかったぜ
- 218 名前：209 mailto:sage [2015/07/04(土) 23:13:12.35 ID:TU5VZOTE.net]
- 解けたかも
2√3+Π/6-3=0.9877…
あってる？
- 219 名前：１３２人目の素数さん mailto:sage [2015/07/05(日) 00:09:18.45 ID:yb6nmQkj.net]
- >>213
πが大文字なのを除けば、同じ答えになった。
- 220 名前：１３２人目の素数さん mailto:sage [2015/07/05(日) 00:26:02.25 ID:xGfPr6DD.net]
- たぶんそれであってる
mathworld.wolfram.com/ReuleauxTriangle.html
https://en.wikipedia.org/wiki/Reuleaux_triangle
ddincrement.blog.shinobi.jp/amoo_o/4 👀
Rock54: Caution(BBR-MD5:18e3ad85d511352dc19ab55963b20571)
- 221 名前：209 mailto:sage [2015/07/05(日) 09:16:02.23 ID:38VAmmOq.net]
- おお、スッキリした。
正三角形の頂点の軌跡を求めて解いたけど、
頂点以外の部分がこの領域からはみ出ないことを示すのは、
（直感的には明らかだけど）まじめに証明するのは結構大変な気がする。
- 222 名前：１３２人目の素数さん mailto:sage [2015/07/05(日) 19:10:04.37 ID:xGfPr6DD.net]
- たしかに証明しろって言われたら
えっ・・・ってなる
- 223 名前：１３２人目の素数さん mailto:sage [2015/07/05(日) 22:24:37.43 ID:KtOLXaqd.net]
- >>169の条件(iii)を
「a, b∈Aかつ1<a<bならばa^2+b^2∈A」
に置き換えた場合を考えてみたんだけど、
「4n+3型の素因数をもたない正整数は全てAに属する」
ということが言えそうなのに、惜しくも証明ができない。
Aに必ず含まれるような正整数からなる集合をSとすると
1,2,5∈S
a,b∈Sならばab∈S
が証明できるので、
4n+1型の素数がすべてSに属することを示せればいいんだけど。
とりあえず200以下の4n+1型素数についてはSに属することが確認できた。
あとは誰かに任せた。
- 224 名前：１３２人目の素数さん mailto:sage [2015/07/05(日) 23:32:25.53 ID:xGfPr6DD.net]
- コラッツの問題に似てるから
実は超難問みたいな地雷を踏みそうでこわい
- 225 名前：１３２人目の素数さん [2015/07/08(水) 16:40:03.46 ID:dTJ+Tbfl.net]
- eを自然対数の底とする.
正の整数nに対して, 関数f_n(x), およびF_n(x)を
f_n(x)=x^n(1-x)^n/(n!), F_n(x)=∑[k=0~2n](-1)^k f_n{k}(x) と定める.
(ただし, f_n{k}(x)はf_n(x)の第k次導関数を表す)
(1) 任意のnに対して, ∫[0 to 1]e^x f_n(x) dx=eF_n(1)-F_n(0) が成り立つことを示せ.
(2) eは無理数であることを示せ.
- 226 名前：１３２人目の素数さん [2015/07/09(木) 07:56:40.26 ID:cP+R7nhb.net]
- >>218 ちょっと考えてみたけど、
pを4n+1型の素数とすると
平方剰余の相互法則から、1≦k≦p-1 に対して
n^2 + k^2 = 0 (mod p) となる nが存在する
このnをn(k)とおくと、各kに対してn(k)は２つある
また、aとbが異なるとき、a+b=p なら n(a)=n(b)
それ以外のとき、n(a)とn(b)は全て異なる
n(n(k))=k,p-k が成り立つ
よって、n(k)をうまく選べば、 k → n(k) は
{1,2,・・・,p-1} から {1,2,・・・,p-1} への全単射となる
仮に、各pに対して、{1,2,・・・,p-1} のうち(p+3)/2個以上の数がAに含まれる・・・（※）
が証明できれば、鳩の巣原理より、あるkが存在して、
k,n(k)≠1 かつ kとn(k)が両方Aに含まれる
この時、n(k)^2 + k^2 ∈A となり、 p|n(k)^2 + k^2 より p∈A が示せる
(※)の証明はわかりません
- 227 名前：１３２人目の素数さん [2015/07/09(木) 16:16:04.07 ID:cP+R7nhb.net]
- と思ったけど、（※）は成り立ちそうにないな・・・・
- 228 名前：１３２人目の素数さん [2015/07/19(日) 22:16:09.84 ID:4WcEMeLJ.net]
- 任意の2以上の整数nに対して,
不等式 tan(π/(2n))≦2/((n-1)*n^(1/(n-1)))
が成り立つことを示せ.
- 229 名前：１３２人目の素数さん mailto:sage [2015/07/21(火) 11:08:25.82 ID:kYxHbe+8.net]
- タスケテ。
複素数xyzがx+y+z=1,x³+y³+z³=10,xyz=2の時
xy+yz+zxとx²+y²+z²を求めよ。
またこの時x,y,zの値の組をそれぞれ求めよ。
- 230 名前：１３２人目の素数さん mailto:sage [2015/07/21(火) 12:32:55.45 ID:yFoYYNcQ.net]
- スレ違い。最低限のルールを守れないやつは
- 231 名前：相手にしない []
- [ここ壊れてます]
- 232 名前：１３２人目の素数さん mailto:sage [2015/07/21(火) 22:33:29.92 ID:rZmsaMCj.net]
- >>218に書いた問題、証明できたっぽい。
あらためて書くと、こういう問題。
[問題]
正の整数からなる集合Aは次の条件(i),(ii),(iii)を全て満たす：
条件(i)：Aは3個以上の元を持つ
条件(ii)：a∈Aかつ d|a (d>0)ならばd∈A
条件(iii)：a, b∈Aかつ1<a<bならばa^2+b^2∈A
このとき, Aは4n+3型の素因数をもたない正整数を全て含むことを示せ.
証明は結構長くなってしまったけど、せっかくなので投稿する。
[1,2,4∈Aの証明]
1<a<bなるa,b∈Aをとるとa^2+b^2,b^2+(a^2+b^2)^2∈Aで、
b,a^2+b^2,b^2+(a^2+b^2)^2のどれかは4以上の偶数（=2dとおく）。
2d∈Aより2∈Aおよび(2d)^2+2^2=4(d^2+1)∈Aとなり、1,2,4∈Aがいえる。
[Sの定義]
{1,2,4}から出発し、この集合に属する数の約数(>0)をこの集合に付け加える、
またはこの集合に属する2つの数(≧2)の平方の和をこの集合に付け加える、
ということを繰り返して得られる数全体からなる集合をSとする。
Sは明らかに条件(i)～(iii)を満たす最小の集合である。
つづく。
- 233 名前：１３２人目の素数さん mailto:sage [2015/07/21(火) 22:34:56.32 ID:rZmsaMCj.net]
- [a∈S⇒2a∈Sの証明]
a=1のときは明らか。a≧2とする。
あるk(≧2)が存在してa∈Sかつak∈Sならば、
2a|akまたは2a|a^2+(ak)^2より2a∈Sがいえる。
このようなkが存在しないような最小のa∈Sがあると仮定すると、
Sの定義より、あるb,c∈Sによってa=b^2+c^2と表せる。
b,c<aより2b,2c∈Sなので、(2b)^2+(2c)^2=4a∈Sとなり矛盾。
以上よりa∈S⇒2a∈Sが示せた。
[a,b∈S⇒ab∈Sの証明]
a,b∈Sとすると2a,4a∈Sである。
Sの定義で述べた方法によってbを生成する数列が存在するが、
この数列の各項をa倍したものを考えると、これはabを生成する数列となる。
（x,y,x^2+y^2をa倍するとax,ay,a(x^2+y^2)となるが、
(ax)^2+(ay)^2からa(x^2+y^2)が得られるので問題ない。）
よってSの定義によりab∈Sである。
[Sの性質]
a∈Sとすると、2a∈Sより(2a)^2+2^2=4(a^2+1)∈Sからa^2+1∈Sがいえる。
またa^2∈Sおよび2a^2∈Sもいえる。
これにより、Sにおいては条件(iii)の1<a<bは不要となる。
ここまでをまとめると、Sは次の性質をもつ。
(1)1,2,4∈S
(2)a∈Sかつd|a(d>0)ならばd∈S
(3)a,b∈Sならばa^2+b^2∈S
(4)a,b∈Sならばab∈S
る。
- 234 名前：１３２人目の素数さん mailto:sage [2015/07/21(火) 22:35:54.68 ID:rZmsaMCj.net]
- [Sの元は4n+3型の素因数をもたないこと]
p=4n+3なる素数pについて、p|aなるa∈Sが存在すると仮定すると、
b^2+c^2≡0(mod p)なるb,c∈S（pの倍数ではない）があって、
b^2≡(-1)c^2(mod p)となるが、-1はmod pで平方非剰余なので矛盾。
よってSの元の素因数は2または4n+1型の素数となる。
よってもし
「任意の4n+1型素数はSに属する」
ということがいえれば、Sの性質(1),(4)より
「Sは4n+3型の素因数をもたない正整数からなる集合である」
といえ、Sの元が全て確定する。
[Mの定義]
4n+1型素数でSに属さないものがあると仮定し、その最小のものをpとする。
Sの元をpで割った剰余類として得られるもの全体からなる集合をMとする。
Mは
Z/pZ={[0],[1],…,[p-1]}（[a]はaを代表元とする剰余類）
の部分集合である。
pはSに属さないので、[0]はMの元ではない。
なお、以下の記述においてaと[a]を区別しない場合がある。
[Mの性質]
Sの性質(1),(3),(4)はそのまま（剰余類の演算として）Mにもあてはまる。
ただし(2)はMにおいては使えなくなる。
また、pより小なる4n+1型素数は全てMの元であり、
Sの性質(4)より、これらおよび[2]からなる積は全てMの元である。
- 235 名前：１３２人目の素数さん mailto:sage [2015/07/21(火) 22:36:27.59 ID:rZmsaMCj.net]
- [Mは乗法に関して巡回群であること]
Mは乗法について閉じており、x∈Mなるxについてxの冪は全てMに属する。
x^m=1なるmが存在し、x^(m-1)がxの逆元となる。
よってMは乗法に関して群である。
とくにMはZ/pZ-{[0]}（巡回群）の部分群なので、あるg∈Sにより
M={[1],[g],[g]^2,…,[g]^(m-1)}
と表される。ただしmはMの位数であり[g]の位数である。
[m≡2(mod 4)の証明]
mが奇数と仮定すると、Mの任意の元[a]=[g]^kについて、
[a+1]=[a]+[1]=[g]^k+[1]={[g]^(m+1)}^k+[1]={[g]^(k(m+1)/2)}^2+[1]^2∈M
がいえるが、これにより[0]∈Mとなり矛盾。
mが偶数のとき、{[g]^(m/2)}^2=[1]より[g]^(m/2)=[-1]がいえる。
とくにmが4の倍数と仮定すると、{[g]^(m/4)}^2=[-1]より
{[g]^(m/4)}^2+[1]^2=[0]∈Mとなり矛盾。
以上よりm≡2(mod 4)である。
このことから、[-1]は[g]の奇数冪となる。
[q,rの仮定]
q<r<pなる素数q,rが存在して[q],[r]はMに属さないと仮定する。
（pはMの定義で登場した、Sに属さない最小の4n+1型素数）
ただしrより小なるq以外の素数は全てMに属するとする。
q,rは4n+3型の素数である。
- 236 名前：１３２人目の素数さん mailto:sage [2015/07/21(火) 22:36:59.06 ID:rZmsaMCj.net]
- [命題P]
「rより小なるq以外の任意の素数sについて、
sがmod qで平方剰余ならば[s]は[g]の偶数冪
sがmod qで平方非剰余ならば[s]は[g]の奇数冪
である」
という命題Pを考える。
Pを満たさないような最小のsが存在すると仮定する。
このとき、[-1]が[g]の奇数冪であることから、
sはmod qで平方剰余であり、かつ[-s]は[g]の偶数冪
-sはmod qで平方剰余であり、かつ[s]は[g]の偶数冪
のいずれかが成り立つ。
前者の場合、s≡a^2(mod q)なるa(1≦a≦(q-1)/2)があり、
[-s]=[g]^(2k)と表せる。
よって[a^2-s]=[a]^2+([g]^k)^2∈Mとなるが、
(a^2-s)/qは整数でありその絶対値はqより小さいので
[(a^2-s)/q]∈Mであるから、
[q]=[a^2-s]*[(a^2-s)/q]^(m-1)∈M
となって矛盾（ここでmはMの位数）。
後者の場合も、sと-sを入れ替えて同様に矛盾。
したがって命題Pは成り立つ。
[命題Pからいえること]
平方剰余は乗法性をもつので、
「qの倍数を除いて、rより小なる任意の正整数sについて、
sがmod qで平方剰余ならば[s]は[g]の偶数冪
sがmod qで平方非剰余ならば[s]は[g]の奇数冪
である」
といえる。
- 237 名前：１３２人目の素数さん mailto:sage [2015/07/21(火) 22:37:21.75 ID:rZmsaMCj.net]
- [q,rの仮定による矛盾]
(r+q)/2≡(r-q)/2(mod q)より、
(r+q)/2,(r-q)/2がともに[g]の偶数冪であるか、
または、-(r+q)/2,-(r-q)/2がともに[g]の偶数冪である。
よって[(r+q)/2]+[(r-q)/2]=[r]∈M
または[-(r+q)/2]+[-(r-q)/2]=[-r]∈Mより[r]∈M
となって矛盾。
[[1],[2],…,[p-1]∈Mの証明]
Mに属さない素数でpより小なるものが存在するならばただ1つである。
これをqとすると、(p+q)/2はpより小さくqの倍数でないので
[q]=[p+q]=[(p+q)/2]*[2]∈M
となって矛盾。
したがって、pより小なる任意の素数がMの元であり、
それらの積もMの元であるから[1],[2],…,[p-1]∈M
[Mは存在しない]
pは4n+1型の素数なので、p=a^2+b^2を満たすa,bが存在する。
よって[a],[b]∈Mより[a]^2+[b]^2=[p]=[0]∈Mとなって矛盾。
したがって、Mの定義を満たすpは存在しない。
すなわち、「任意の4n+1型素数はSに属する」。おしまい。
- 238 名前：１３２人目の素数さん mailto:sage [2015/07/22(水) 00:36:28.04 ID:7w9t1PZg.net]
- 4=b^2+c^2.
- 239 名前：１３２人目の素数さん mailto:sage [2015/07/22(水) 07:32:30.94 ID:qRulk97x.net]
- >>232
>>226で4∈Aは証明してある。
4自体がb^2+c^2と表せる必要はない。
- 240 名前：１３２人目の素数さん mailto:sage [2015/07/28(火) 00:04:52.15 ID:V0v013Ov.net]
- プログラムの問題
入力ストリームと出力ストリームととn個のスタックがある。
n個のスタックを使って入力の順番を入れ替えて出力へ出すことを考える。
１ステップで次のことができるとする
(1)入力ストリームから一文字取り出しスタックへ積む
(2)スタックから一文字取り出しほかのスタックへ積む
(3)スタックから一文字取り出し出力ストリームへ出力する
n個のスタックを使うと入力k文字に対して任意の順番に入れ替えて出力できるとき
n個のスタックはk文字互換完備であるという。
ある定数cに対しc個のスタックが任意の有限の数mに対しm文字互換完備であるとき
c個のスタックは任意互換完備であるという。
任意互換完備となる定数cは存在するか？
存在するとしたらその最少の数はいくつか？
- 241 名前：１３２人目の素数さん mailto:sage [2015/07/28(火) 02:28:28.92 ID:QlC/V4UF.net]
- 2
- 242 名前：１３２人目の素数さん mailto:sage [2015/07/28(火) 03:03:42.46 ID:dO/BAI9e.net]
- スタックって何かわからんハノイの塔みたいなことが出来るってことでいいのか
- 243 名前：１３２人目の素数さん mailto:sage [2015/07/28(火) 06:14:44.23 ID:A50AzsVE.net]
- 思考停止のことじゃない？
- 244 名前：１３２人目の素数さん mailto:sage [2015/07/28(火) 08:22:48.08 ID:V0v013Ov.net]
- 同じスタックに何回も積みなおしていいんなら２個のスタックで簡単にできちゃうなぁ
各スタックに番号を振って、スタックからスタックへ積みなおすのは
取りだすスタックが積むスタックより番号が若いときに限る、
としたらちょっとは面白くなるかな？
- 245 名前：１３２人目の素数さん [2015/07/29(水) 16:20:02.76 ID:CZbY/wc3.net]
- (cos(2π/7))^(1/3)+(cos(4π/7))^(1/3)+(cos(8π/7))^(1/3)の値を求めよ.
- 246 名前：１３２人目の素数さん mailto:sage [2015/07/29(水) 17:11:12.92 ID:PHmkOzke.net]
- 234-238のスタック２個っていうのは
入力から文字 x_i を取り出す前に
最終的な出力での登場位置が x_i より早い文字をスタック1に
最終的な出力での登場位置が x_i より遅い文字をスタック2
- 247 名前：に
集めるみたいなことをしてけばいいってことかな
スタック1個だと、x_1x_2x_3->x_3x_1x_2 みたいなことができなそうだな [] - [ここ壊れてます]
- 248 名前：１３２人目の素数さん mailto:sage [2015/07/29(水) 19:47:09.55 ID:s8W1tV31.net]
- スタック２個あれば取り出したい文字の上に積んであるやつを全部もう一個のスタックに移せば好きな文字が取り出せる。
- 249 名前：１３２人目の素数さん mailto:sage [2015/07/29(水) 19:52:11.28 ID:/rcHIzs4.net]
- むしろ、スタック１つでできる置換できない置換の判別法が知りたい。簡明なものがあるか？
- 250 名前：１３２人目の素数さん mailto:sage [2015/07/29(水) 20:31:05.18 ID:s8W1tV31.net]
- スタック１個なら入力からスタックへ積むかスタックから出力へ出すかだけだから、
探索しても分岐は起きないんじゃない？
- 251 名前：１３２人目の素数さん mailto:sage [2015/07/29(水) 22:18:24.98 ID:PHmkOzke.net]
- ああ
スタックへの積み方を工夫する必要すらないのか
スタックが２つあれば、取り出したいものをどんなタイミングでも取り出せる
- 252 名前：１３２人目の素数さん mailto:sage [2015/07/29(水) 22:41:11.60 ID:zneU1ISF.net]
- >>234
スタックを2個として、入力長Mの任意の置換に対して
a)最大スタック操作回数が最小となる手順とその回数
b)平均スタック操作回数が最小となる手順とその回数
|
 |
