面白い問題おしえて〜な 28問目
■ このスレッドは過去ログ倉庫に格納されています
できるわけないやん。trは等しいけどdetは異なる行列なんか死ぬほどあるやろ? >>271 正解です。直ぐに出てくるなんて凄いな。 私は最近知ったんだけど、この手の内容について参考文献とかあったら教えてください。 >>273 大学で使うような線形代数の教科書だったら何でも載ってる気がするけどなあ、わからんが wikipedia の固有多項式の項目を見てみるだけでも結構色んな情報引き出せたりすると思うけど、 もし文献が欲しいならすまんが数学の本スレとか別のところで聞いてみてくれ 類題 3次正方行列Aについて、tr(A) を det(Aと単位行列Eの式) の式で表せ。(detの中身は複数種類でも可) 池の鯉を網で56匹すくいました。 すくった56匹に目印をつけ、池にもどしました。 次の日に鯉45匹をすくったところ、36匹に目印がついていました。 池の鯉はおよそ何匹ですか。 これ、70匹でも69匹でも同確率になるよね? 56*45/36=70で求まる70匹のとき36匹の目印が見つかる確率 137149850039891/562949953421312 0.2436270741410791 69匹のときの36匹の目印が見つかる確率も 137149850039891/562949953421312 0.2436270741410791 となった。 import math from fractions import Fraction def choose(n, r): return math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) def dhyper(x,g,b,s): return choose(g,x)*choose(b,s-x) / choose(g+b,s) f69 = dhyper(36,56,69-56,45) print (Fraction(f69)) print(f69) f70 = dhyper(36,56,70-56,45) print (Fraction(f70)) print (f70) プログラムのご紹介、乙。 でも、ま、プログラムとしての新規性の証明、解説が必要かな? >>280 Rの超幾何分布関数で算出したら 最頻値が2つ出てきたので分数表示できるpythonでやっても同じになって困惑してるのが現状。 全ての成分が自然数で、対角成分が全て0の正方行列Aについて tr(A^3)は6の倍数であることを証明せよ >>282 >>283 B = A^3, tr(B) = Σ[i=1,n] B(i,i) = Σ[1≦i,j,k≦n] A(i,j) A(j,k) A(k,i) = 6Σ[1≦i<j<k≦n] A(i,j) A(j,k) A(i,k) ∵ {i,j,k} のどれかが一致すれば 0 ぢゃね? 単発質問スレより 引用 1問目は1から9を多くて1回づつ使って等式を完成させる https://i.imgur.com/os8xCr9.jpg □/□ * □/□ = □□/□ (a/b)*(c/d) = (10*e+f) /g 左辺の分数は互換なのでa>cとして Prelude> let r = [[a,b,c,d,e,f,g]|a<-[1..9],b<-[2..9],c<-[1..9],d<-[2..9],e<-[1..9],f<-[1..9],g<-[2..9],(a/b)*(c/d)==(10*e+f)/g, a/=b,a/=c,a/=d,a/=e,a/=f,a/=g,b/=c,b/=d,b/=e,b/=f,b/=g,c/=d,c/=e,c/=f,c/=g,d/=e,d/=f,d/=g,e/=f,e/=g,f/=g,a>c] Prelude> let f x = map floor x Prelude> map f r [[7,2,3,6,1,4,8],[7,6,3,2,1,4,8],[8,2,3,6,1,4,7],[8,2,7,4,6,3,9],[8,2,7,6,1,4,3],[8,4,7,2,6,3,9],[8,4,7,6,2,1,9],[8,6,3,2,1,4,7],[9,2,7,4,6,3,8], [9,2,8,4,6,3,7],[9,4,7,2,6,3,8],[9,4,7,6,2,1,8],[9,4,8,2,6,3,7],[9,4,8,6,2,1,7],[9,6,7,4,2,1,8],[9,6,8,4,2,1,7]] 2問目は2個答える 最大になるように-5から5を多くて1回づつ使う 最小になるように-5から5を多くて1回づつ使う https://i.imgur.com/H7btl39.jpg こっちが終わらない :( 前>>277 訂正。 16×5⇒14×5 ま、でも印をつけられる段階ですでに「ぜんぜん捕まらないすばっしっこい鯉」が10匹ぐらいいると思うんだよね。 すべての鯉をx匹、ぜんぜん捕まらないすばっしっこい鯉をy匹とおくと、 x-y=70(匹) 印をつけられる確率は4/5じゃない気がする。 印をつけるたびすでに印をつけられた鯉が生け簀に増えてくわけで、 すでに印をつけられた鯉を捕ることもあるはず。 y=10なら80匹だし、それに70匹ぐらいなら80匹もぎりぎりオッケーじゃないの。 >>285 2問目も計算、終わってた y = [a/b*(c-d)-e*(f-g)|a<-[-5..5],b<- [-5..(-1)]++[1..5],c<-[-5..5],d<-[-5..5],e<-[-5..5],f<-[-5..5],g<-[-5..5], a/=b,a/=c,a/=d,a/=e,a/=f,a/=g,b/=c,b/=d,b/=e,b/=f,b/=g,c/=d,c/=e,c/=f,c/=g,d/=e,d/=f,d/=g,e/=f,e/=g,f/=g] f x = map floor x yMax = maximum y z=[[a,b,c,d,e,f,g]|a<-[-5..5],b<- [-5..(-1)]++[1..5],c<-[-5..5],d<-[-5..5],e<-[-5..5],f<-[-5..5],g<-[-5..5] ,a/=b,a/=c,a/=d,a/=e,a/=f,a/=g,b/=c,b/=d,b/=e,b/=f,b/=g,c/=d,c/=e,c/=f,c/=g,d/=e,d/=f,d/=g,e/=f,e/=g,f/=g,a/b*(c-d)-e*(f-g)==yMax] map f z Prelude> map f z [[-5,-1,3,-4,5,-3,4],[-5,-1,3,-3,5,-4,4],[-5,-1,4,-4,5,-3,3],[-5,-1,4,-3,5,-4,3],[-5,1,-4,3,5,-3,4],[-5,1,-4,4,5,-3,3],[-5,1,-3,3,5,-4,4],[-5,1,-3,4,5,-4,3], [5,-1,-4,3,-5,4,-3],[5,-1,-4,4,-5,3,-3],[5,-1,-3,3,-5,4,-4],[5,-1,-3,4,-5,3,-4],[5,1,3,-4,-5,4,-3],[5,1,3,-3,-5,4,-4],[5,1,4,-4,-5,3,-3],[5,1,4,-3,-5,3,-4]] >>286 70匹のときの確率 137149850039891/562949953421312 = 0.2436270741410791 80匹のときの確率 639173184839639/36028797018963968 = 0.017740619663298957 だから、80匹は可能性が低い >>286 池の鯉の可能性を56+(45−36)=65匹から上限を10000匹にして その確率は一様分布に従う(つまり、65匹の確率も10000匹の確率も同じ)として計算したら 最頻値 $`mode` [1] 69 70 中央値 $median [1] 71 期待値 $mean [1] 71.17647 95%信頼区間(highest density) $CI.hdi [1] 65 78 パーセンタイル(2.5.%-97.5%) $CI.Qqtl [1] 66 80 80匹はまあ、ギリギリセーフといえなくもない。 >>36 の出題者らしきレスなんにも出てこないけど、これ本当にとけるんかな?時々未解決問題貼るやついるからなぁ。 まぁもう諦めたからどっちでもいいけど。 >>281 Wolframdでも同じだなぁ。69匹と70匹は同確率。 では、56*45/36=70の値は一体なんだろ choose(56,36)*choose(13,9)/choose(69,45) https://www.wolframalpha.com/input/?i=choose (56,36)*choose(13,9)%2Fchoose(69,45) 3591292705/14740942556 choose(56,36)*choose(14,9)/choose(70,45) https://www.wolframalpha.com/input/?i=choose (56,36)*choose(14,9)%2Fchoose(70,45) 3591292705/14740942556 choose(13,9)/choose(69,45) 11/35471218518158136 (13!/(4!*9!)) /(69!/(24!*45!)) choose(14,9)/choose(70,45) 11/35471218518158136 (14!/(5!*9!))/(70!/(25!*45!)) 大きな数を扱う化学では コップの中の真水56ccを濃度1%の食塩水56ccで置き換えました。 よく混ぜた後45cc取り出して濃度を測ると36/45%でした。 最初の真水の量は何ccだったのか計算せよ。 36/45=56/x x=70 答え 70cc とかしてるわけだけど、 確率分布はどんな様子になってるんだろう。 >>276 の問題の各数値を10^23倍くらいにすればいいわけだよね 小学校 「さくらんぼ計算」に戸惑う声 https://headlines.yahoo.co.jp/hl?a=20181115-00000006-jct-soci https://amd.c.yimg.jp/im_sigg4tEc9zbWoY9xWDiiNhYroA---x900-y720-q90-exp3h-pril/amd/20181115-00000006-jct-000-1-view.jpg さくらんぼ計算とは、「8+7」の足し算で、7を2と5に分け、8にこの2を足して10にする。 そして、10と残りの5を足して15と計算するやり方だ。7の下にぶら下がったさくらんぼの実を2つ描き、 2と5を実の中に書くことから、さくらんぼ計算と呼ばれている。 報告主は、「10+7」の10を3と7に分けるといったムダなことをする子供もいたとして、 こうした考え方を示した文科省に疑問をぶつけていた。このほかにも、さくらんぼ計算のせいで 娘が算数が大嫌いになり、中学3年になっても苦手から抜け出せずに数学を拒否している。 >>95 ■P1stを求める 宝一つの時の自陣当たり数 (n(n+1)/2)-1 ……@ その中での宝二個の組み合わせ数 ((n(n+1)/2)-1)(((n(n+1)/2)-1)-1)/2 ……A 最終マスと@との組み合わせ数 (n(n+1)/2)-1 ……B 自陣の当たりと相手の当たりで自分が勝つ 組み合わせはAと差分の和 差分は1 3 7 13 22 34 50 70 95 125 161 203 252 308 372 444 525 615…… それを表す関数 (4n^3+6n^2-4n-3+3(-1)^n)/48 nが一つずれているのでn-1に補正 {4(n-1)^3+6(n-1)^2-4(n-1)-3+3(-1)^(n-1)}/48 ……C 計算知能でAx2+B+Cを入力すると P1st ={12n^4+28n^3-42n^2-52n-3(-1)^n+51}/48 ……D 全n(n+1)マスで宝二個の組合わせ数 n(n+1){n(n+1)-1}/2 ……E 引き分け数は、n(n+1)-1と同着数の和 同着数は1 2 4 6 9 12 16 20 25…… これを表す関数は {2n^2-1+(-1)^(n)}/8 ……F n(n+1)-1 ……G 計算知能でF+Gを入力すると even =(10n^2+8n+(-1)^n-9)/8 ……H 計算知能でE-D-Hを入力すると Q1st ={12n^4+20n^3-18n^2-20n-3(-1)^n+3}/48 前>>286 >>288-289 >>291 期待値の問題か。 80匹もぎりぎりセーフってことで正解だね。 一万匹は無理だね。 金銭的にも興行的にも。 どこ〜かで〜かね〜がな〜ぁて〜♪ らし〜くな〜ぃこと〜ばか゚〜ぅか〜んで〜♪ さむ〜さか゚〜ここ〜ちよ〜くて〜♪ な〜んでこ〜ぃな〜んかして〜んだろ〜♪ 前>>295 ~、、,, ~~゚~~~。~ ~~~ ~ (-.-))⌒〜っ゙~ ~ ~~~ υυ〜~~~ ~~ ~ ~゚ ~~ ~~~~゚ ~ ~ ~~ ゚ ~~~ ~ >>279 この式で56匹から100匹までの確率の総和を取ったら約2になった sigma[choose(56,36)*choose(n-56,9)/choose(n,45), n = 56 to 100] https://www.wolframalpha.com/input/?i=sigma%5Bchoose (56,36)*choose(n-56,9)%2Fchoose(n,45),+n+%3D+56+to+100%5D >>292 カードの照合の問題も、最初に選んだ10枚に印をつけて再捕獲したと考えればいいんだろうけど 200/3=66.6枚という最頻値がどれほどの信頼できるのか疑問。 固有の番号の書かれたカードが何枚あり、 その枚数は1000枚以下であることはわかっているが、その数を推定したい。 調査員が無作為に10枚選んで番号を記録して元に戻した。 別の調査員が無作為に20枚選んで番号を記録した。 二人の調査員の記録した番号を照合すると3枚の番号が一致していた。 この情報からカード枚数の期待値を求めよ。 事前分布としてある枚数である確率を一様分布にするのが現実離れといえるけど。 まあ、男女の生まれる確率分布を一様分布として計算するのに似ているかも。 >さくらんぼ計算のせい アベノセイダーズを彷彿とさせるような記述だなぁ。 >>297 サイコロをふって1回1の目がでた。 サイコロを降った回数は1から100回のどれかである。 1回ふって1回出た確率、2回ふって1回出た確率、3回ふって1回出た確率、...、100回ふって1回出た確率 全部足したらいくらになる? 問題の数値を変えてわずか3匹しか目印なしとすると 池の鯉を網で56匹すくいました。 すくった56匹に目印をつけ、池にもどしました。 次の日に鯉45匹をすくったところ、3匹に目印がついていました。 池の鯉はおよそ何匹ですか。 56*45/3=840匹になるのだけど、 この数値ってどれほどアテにしていいんだろうね? 数値を10倍、100倍にしたときのグラフを描かせてみた 青が10倍で範囲は690匹から7100匹、 赤が100倍で範囲は6900〜7100匹 https://www.wolframalpha.com/input/?i=plot+choose (560,+360)*choose(x-560,+90)%2Fchoose(x,450),++choose(5600,+3600)*choose(x*10-5600,+900)%2Fchoose(x*10,4500),+from+x%3D690+to+710 https://i.imgur.com/wMoy71B.jpg 10倍程度だとあまり先鋭化しない 100倍でも思ったより先鋭化しない 化学で扱うような10^23あたりのサンプル数なら推定値の ±0.001%の範囲である確率が0.9999とかになるんだろうな そこが統計が数学科であんまり好まれないとこだろうねぇ。 確率の問題と深く関わってはいるけど厳密には確率の問題ではない。 母数の分布とは言うけどそんなもんわかりっこないから本来どうしようもないし。 けどわからんわからんいうてても何も始まらんので適当に××仮説とか立てて「こう考えるとするとこうなる」ぐらいの事しか言えない。 信頼区間にしてもwikiにも明示されてるけどあくまで"指標"でしかない。確率でもなんでもない。 確率だと思うには母数の分布になんかの仮定入れないと無理だけど、その仮定の入れ方ごとに答え変わるし、ましてや次はその仮定どれくらい信頼できるねんと言う話に戻ってしまう。 >>303 全体の数より、再捕獲での陽性割合を変化させた方がグラフは大きく変化すると思う。 目印陽性がすくないと信頼区間が広くなって推定値が信頼できないが、目印陽性が多いと信頼区間が狭くなる。 >>305 なるほど。 とはいえさっきはグラフの形だけ見て「あまり先鋭化しない」なんて書いたけど、 10倍では690〜710以外の範囲でも無視できない程の確率があるのに 100倍だと6900〜7100以外での確率はほぼゼロだから大分違うか >>306 10打数で1安打と1000打数100安打での信頼区間の差では? そもそも信頼区間の定義とは違う意味で信頼区間という用語使ってるレス多いな。 信頼区間の計算式って沢山あるよな。 1000打数100安打の95%信頼区間 > binom::binom.confint(100,1000) method x n mean lower upper 1 agresti-coull 100 1000 0.1000000 0.08284688 0.1202145 2 asymptotic 100 1000 0.1000000 0.08140615 0.1185939 3 bayes 100 1000 0.1003996 0.08206073 0.1191877 4 cloglog 100 1000 0.1000000 0.08239444 0.1195577 5 exact 100 1000 0.1000000 0.08210533 0.1202879 6 logit 100 1000 0.1000000 0.08288164 0.1201906 7 probit 100 1000 0.1000000 0.08264461 0.1198768 8 profile 100 1000 0.1000000 0.08243331 0.1196133 9 lrt 100 1000 0.1000000 0.08243172 0.1196130 10 prop.test 100 1000 0.1000000 0.08245237 0.1206909 11 wilson 100 1000 0.1000000 0.08290944 0.1201520 >>305 自分でも興味があったので弄ってみた。 魚の総数を上限1万匹とし、その確率分布は一様分布を仮定。 再捕獲した45匹中何匹に目印がついているかで推測される95%信頼区間(Highest Density Interval)をグラフにしてみた。 http://i.imgur.com/NKcQ61u.png Rのコードはここに置いた(通知を変えて実行できる) http://tpcg.io/TBD7MO >>271 tr(AA) や tr(A^3) も使えばできますね。 Aの固有多項式は f(x) = det(A-xI) = det(A) - {(tr A)^2 - tr(AA)}/2・x + tr(A) xx - x^3, ケーリー・ハミルトンにより f(A) = det(A)I - {(tr A)^2 - tr(AA)}/2・A + tr(A)AA - A^3 = O, det(A) = (1/3)tr[ {(tr A)^2 - tr(AA)}/2・A - tr(A)AA + A^3 ] = … tr(A^i)全部使っていいなら固有多項式の係数全部表せるのはまんまニュートンの漸化式やん。 >>305 >>310 単に>>303 風のグラフを描くなら対数で計算すればコップの中の水分子とかでも計算できますね あとでやってみよう >>311 A = {a_ij} が3次行列のとき tr(A) = a11 + a22 + a33, tr(AA) = (a11)^2 + (a22)^2 + (a33)^2 + 2 a12 a21 + 2 a23 a32 + 2 a31 a13, ∴Aの固有多項式は det(A-xI) = det{[a11-x, a12, a13], [a21, a22-x, a23], [a31, a32, a33-x]} = det(A) - (a11 a22 + a22 a33 + a33 a11 - a12 a21 - a23 a32 - a31 a13)x + (a11+a22+a33)xx -x^3 = det(A) - {(tr A)^2 -tr(AA)}/2 x + tr(A) xx - x^3, >>312 n次多項式がn個の根λ1,λ2,・・・,λn をもつ(ガウス)が既知ならば tr(A^i) = (λ1)^i + (λ2)^i + … + (λn)^i, これは {λ1,λ2,…,λn} のi次の対称多項式だから、1〜i次の基本対称式で表わせる。 逆に、i次の基本対称式は tr(A) 〜 tr(A^i) で表わせる。 池の鯉の総数と調査します。 五郎君が名前に因んで56匹を捕まえて目印をつけ、池にもどしました。 次の日に三郎君が自分の名前に因んで36匹の目印のついた鯉を捕まえることにしました。 鯉45匹めで予定の36匹が捕まりました。 池の鯉はおよそ何匹ですか。 >>314 トレースって跡ともいうけど、ずっと「あと」って読んでいた。 線形代数の本の索引で、ア行になくサ行にあったので気づいたわ。 >>311 A = {a_ij} がn次行列のときも tr(A) = a_11 + a_22 + ・・・ + a_nn, tr(AA) = (a_11)^2 + … + (a_nn)^2 + 2 Σ[i<j] a_ij a_ji, (trA)^2 - tr(AA) = 2Σ[i<j] (a_ii a_jj - a_ij a_ji), ∴ Aの固有多項式は det(A-xI) = det{[a_11-x, a_12, …, a_1n], [a_21, a_22-x, …, a_2n], ……, [a_n1, a_n2, …, a_nn-x]} = det(A) - …… + Σ[i<j] (a_ii a_jj - a_ij a_jj) (-x)^{n-2} + (a_11+…+a_nn)(-x)^{n-1} + (-x)^n = det(A) - …… + {(tr A)^2 - tr(AA)}/2 (-x)^{n-2} + tr(A)(-x)^{n-1} + (-x)^n, 昨日出した問題だけど 数2Bまでの知識で解ける a,b,c,dは実数とする。 a+c=-4/3, b+4ac+d=-2, ad+bc=4, bd=1のとき、(a^2-b)(c^2-d)<0を示せ。ただし、計算機は使ってはならない。 あれ? a^2d=a(4-bc), bc^2=c(4-ad)より a^2d+bc^2=4(a+c)-(ad+bc)=-16/3-4 になって (a^2-b)(c^2-d) =(ac)^2-(a^2d+bc^2)+bd =(ac)^2-(-16/3-4)+1 になって負になりっこない希ガス。 >>319 f(x) = (x^2+2ax+b)(x^2+2cx+d) = x^4-(8/3)x^3-2x^2+8x+1 をxで微分したら 4(x-2)(x-1)(x+1) となるから、 x=-1 で極小 f(-1)<0, x=1 で極大 f(1)>0, x=2 で極小 f(2)>0 となってそれ以外の区間で単調であるから、 f は ちょうど2つの単根を持つ。 したがって、(x+a)^2 - (a^2-b) と (x+c)^2 - (c^2-d) はどちらも重根を持たず、どちらか一方のみが2つの実根を持つことから、題意が示される。 >>321 すげぇ……判別式の形露骨に出ないように姑息に2a,2cみたいな係数にしてたのによく見破ったな…… >>322 ある ウルフラム先生が言ってるんだから間違いない多分 >>321 すごいな。2つの判別式の積になってるって見抜けないと思いつかんなあ >>320 また現れたか、デキッコナイス。なんなんだこいつは。 https://i.imgur.com/bLyuU1o.jpg あれ?>>320 の間違いまじでわからん? どこ間違ってるかわかる? >>325 これa,b,c,dの値固定されてるからacの値によらず(ac)^2-(-16/3-4)+1が常に負になる必要はないんじゃね(特定のa,b,c,dで負になるなら良い) >>326 いや、変形に計算間違いがないならacが実数である限り何であっても正になってしまう。 いまパソコンが壊れててて計算しか出来ないから検算しようがない。 自分で再計算しても同じとこ間違うのが関の山だし。 まぁ問題に一言も実数とは断ってないから実数でないのかもしれないけど。 >>328 aについてしか解いてくれてないけど。 虚数解混じってるし。 全部実数になる解あるの? >>329 More rootってあるだろ、これ以上はスレチになるからこことは違うところで調べてくれ あ、いや、ごめんなさい。 実数解ひとつあれば全部実数になる解は自動的にあるな。 あれ?>>320 どこ間違ってるんだろう。 パソコンないとこうも手詰まりになるもんだな。 >>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) 計算見直すだけだろ 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) になって特に何が言える訳でもないと思うよ まだやってたのか、NG入れてあぼーんしてたから気づかなんだわ。 数学板の常連は意外と面倒見がいいんだな。 解決してた すまん 未解決だけど投稿します 各項の係数の絶対値が1以下であるような整数係数多項式 f(x)≠0 であって、x^4+x^3+3x^2+x+1 で割り切れるようなものは存在するか。 >>334 ありがとう。 後で気づいた。 お騒がせしました。 m種類の文字をm^n個並べた円順列で、連続するn文字の並びがすべて異なるものは常に存在するか? 例:文字0,1の円順列[00011101]中の3文字の並びは 000,001,011,111,110,101,010,100 で、すべて異なる。 じゃトレースがらみで 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 刺身にタンポポの花を乗せるような単調作業は、このスレにはふさわしくない。 ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.1 2024/04/28 Walang Kapalit ★ | Donguri System Team 5ちゃんねる