ベストアンサー ※ ChatGPTを利用し、要約された質問です（原文：符号の決定） 符号の決定に関するアルゴリズムの設計と解析II 2012/12/06 17:07 このQ&Aのポイント アルゴリズムの設計と解析IIの82ページで符号の決定について説明されています。条件として、すべての文字は否定的で整数であることが指定されています。質問者は、示して欲しい証明ができない状況にいて助けを求めています。 符号の決定 アルゴリズムの設計と解析II の82ページです。 条件：文字はすべて否負の整数とする。さらに、 f > g f = (f_1)*2^k + (f_2) g = (g_1)*2^k + (g_29 (f_2) < 2^k (g_2) < 2^k (f_1) <= (g_1)^2 f = qg + r r < g (f_1) = (q_1)*(g_1) + (r_1) (r_1) < (g_1) このとき、 (g_1)*(2^k)*(q - q_1) = (f_2) + (r_1)*(2^k) - q*(g_2) - r が成立し（確かに成立します。） q - (q_1) <= 0 を簡単に示すことが出来る。のだそうですが 示せません。 助けて下さい。 質問の原文を閉じる 質問の原文を表示する みんなの回答 （2） 専門家の回答 質問者が選んだベストアンサー ベストアンサー Tacosan ベストアンサー率23% (3656/15482) 2012/12/07 13:04 回答No.2 って～か, q - (q_1) <= 0 を示すのに (g_1)*(2^k)*(q - q_1) = (f_2) + (r_1)*(2^k) - q*(g_2) - r なんていらんよねぇ. ほぼ当たり前なわけだし. 質問者 お礼 2012/12/07 17:45 ありがとうございました。 q=q_1 + k として、 f = (q_1 + k)g +r を計算したら、 f_2 > 2^k となりました。 通報する ありがとう 0 広告を見て他の回答を表示する（1） その他の回答 (1) Tacosan ベストアンサー率23% (3656/15482) 2012/12/07 00:32 回答No.1 最悪背理法を使えば q_1 ≧ q が示せる. 通報する ありがとう 0 カテゴリ 学問・教育数学・算数 関連するQ&A 関数の問題 関数gは任意の非負整数mに関して以下の性質を持ちます。 g(2m)=g(g(m)) g(2m+1)=g(2m)+1 例えば、もしg(0)=0なら、g(k)は任意の非負整数ｋに対して非負整数の値を返します。（これは数学的帰納法で証明できます） しかしながら、もしg(0)=１とすると、関数ｇは矛盾をはらむのでg(0)は１に等しくならないことが分かります。（これも比較的簡単に証明できます） また同様に任意の非負整数ｋに対して、g(0)=2^k としたり、g(0)=2^k + 2 としたりすると、矛盾を導きます。 それでは、どのような非負整数にg(0)が等しければ、関数gは矛盾をはらまずに任意の非負整数ｋに対してg(k)が非負整数の値を返すでしょうか。 もし何かそのようなg(0)の値に決まった性質があったら教えてください。 整数の組合せ おはようございます。 以下の条件を満たす負でない整数の組合せを考えていたら、わけがわからなくなりました。考え方がわかれば教えてください。 条件 ｐ＋ｑ＋ｒ＋ｓ＝４、ｑ＋２ｒ＋３ｓ＝４の２つです。 解答 （ｐ、ｑ、ｒ、ｓ）＝（２，１，０，１）（０，４，０，０）（１，２，１，０）（２，０，２，０）の４つです。 数学的帰納法について 数学的帰納法についての問題で、ちょっと悩んでいますので、 どなたかお教えください＞＜； とある、国立医学科の問題です。 「 a,bを負でない整数とし、a>bとする。 a1=a, a2=b, a(n+2)=la(n+1)-anl (n=1,2,3・・・)によって定義される 数列{an}について、次の問いに答えよ。 q,rを負でない整数として、a=(2q+1)b+r,r<bとする。 このとき、初めてan=rとなるnを求めよ。 」 との問題で回答が以下のようにようなっています。 「 m=1,2,3・・・,q+1 に対して a(3m-2) = {2q+1-2(m-1)}b+r a(3m-1) = b a(3m) = {2q-2(m-1)}b+r が成り立つことを数学的帰納法により示す。 n=1の時、、、、と以下解説が続くのですが、 ここで質問です＞＜； 何で、最初の一行が 「m=1,2,3・・・,q+1」となっているのでしょうか？ 「m=1,2,3・・・」ではダメなんでしょうか？ どの参考書、問題集を見ても、 「m=1,2,3・・・」となっているんですが、こうしたらダメなんでしょうか？ 赤本の解説以外に、東進の解説も確認したら、全く同じようになっていました。 また、仮定条件の時には 「m=k(k=1,2,3・・・q)のとき、成立すると仮定する」と書いてありますが、 「m=k(k=1,2,3・・・)」じゃダメなんでしょうか？ 何で、 「q+1」や「q」までとなっているのでしょう？ しかも、「q」は「a=(2q+1)b+r」の中で使用されている文字なのに、、、、、 さっぱり分かりません。(/_<。) どなたか教えてください(>_<。)HelpMe!! 証明について a,bを整数とするとき次の2つの条件(i),(ii)について(i)と(ii)は同値であることを証明する問題です。 (i) a,bはお互いに素である。すなわち、aとｂの最大公約数は1である。 (ii) ax(0)+by(0)=1となる２つの整数x(0),y(0)が存在する。 (i)の問題について ２つの整数aとbの最大公約数をGとおくと a=a'G,b=b'G(a',b'はお互いに素）とする。 (1)aをbで割ったときの商をq,余りをrとするとa=bq+r rについて解くと r=a-bq 2つの整数はaとbはa=a'G,b=b'G(a',b'とおけるので r=a'G-b'G この後どのように証明するのでしょうか？ (ii) ax(0)+by(0)=1となる２つの整数x(0),y(0)が存在はどのように証明するのでしょうか？ 原始ｎ乗根 FMTの話しの中に、ｎを偶数として、 整数ω＞＝２とすると、P=1+ω^(n/2)上でωは原始ｎ乗根となる。 と書いてある。 たしかに、ωはｎ乗して初めて１とPを法として合同になる。 これは、Pが素数でなくても成立します。 しかし、 原始ｎ乗根の性質として ω^0 + ω^j + ・・ + ω^((n-1)j) = 0 (j=1,2,...,n-1) が成立すると書いてある。 ω＝２、ｎ＝6とすると、 ｊ＝１のときは 1+２+４+８+16+32＝63＝9*7≡0 mod(9) 9=2^(6/2)+1 j=2のときは、 １+４+16+64+256+1024＝1365＝151*9+6 アルゴリズムの設計と解析II （エイホ 他）の28ページには 原始ｎ乗根の定義の中の条件として、原始ｎ乗根は条件 ω^0 + ω^j + ・・ + ω^((n-1)j) = 0 (j=1,2,...,n-1) を満たさなくてはならない。 と書いてある。 さて、原始ｎ乗根の定義は何でしょうか？ 最初の２は原始ｎ乗根なのでしょうか？ Pには他に条件が付くのでしょうか？ ｊ に条件をつけるのでしょうか？ 計算間違いなのか、誤解なのかよく分かりません。 混乱しています。よろしくお願いします。 お願いします！ 二次関数f(x)，g(x)および実数kが以下の(I)，(II)，(III)の条件をすべて満たしているとする。 (I)f(x)はx＝kで最大値をとる (II)f(k)＝１３，f(－k)＝－２３，g(k)＝４９，g(－k)＝７ (III)f(x)＋g(x)＝２x2＋１３x＋５ このとき，kの値とf(x)，g(x)を求めよ 。 お願いします っ F(x)は実数を係数とするxの多項式。 F(x)は実数を係数とするxの多項式。 すべての整数kについて、f(k)が整数であるための必要十分条件は、 f(0)が整数で、すべての整数kについてf(k)-f(k-1)が整数となる。 このとき、f(x)=ax^2+bx+cについて、すべての整数kについて、f(k)が整数 となるために、係数a,b,cがみたすべき必要十分条件をもとめよ。 次のように考えましたが、最後の詰めができません。 aとbの条件はどうなるのか、よろしく、おねがいします。 f(0)=cより、cは整数。 f(k)-f(k-1)=(2k-1)a+bより、任意のkについて(2k-1)a+bは整数。 これで、k=1のときより、a+bは整数...(1)。 k=2のときより、3a+bは整数...(2)。 (2)－(1)より、2aは整数。(1)×3-(2)より、2bは整数。 ここで、行き詰まりました。このあとどう処理すれば、a,bの条件をもとめられるか よろしくおねがいします。 割り算の定義 aを整数、bを正の整数とするとき、 a = bq + r , 0 ≦ r < b を満たす整数q、rの組みがただ一つ存在する。（qは商、rは余り） と「大学への数学」という雑誌にありました。 bが負の整数のときは、 0 ≧ r > bと考えるべきでしょうか？ そもそもこの定義、q以外は整数から拡張して有理数や実数にも適用できるものなのでしょうか？（出来るような気がしますが。） ゲートドライブ電流決定 FETのゲート抵抗選定について質問させてください。 CQ出版トランジスタ技術スペシャル No88 改訂新版ダイオード/トランジスタ/FET活用入門 という本の248ページに ゲート電流決定に関して Ig=Qg(d/dt)=Ciss(Vgs×d/dt)とあり更に Ipeak=(Ciss×Vgs)÷Tr とありました。 Cissで計算したものは例題として計算結果が載せてありました。 ここで出てくるCissなんですがデータシートを見ると測定条件にVgs=0と書いてあるのですがこの値を使ってもよいのでしょうか？？ それともVgs=0でCissが最大になるからこの値を充電できれば良いという意味なのでしょうか？ 参考サイトの4ページの図3-aを見るとFETの等価回路的なものが書いてあってG-D、G-S間にコンデンサが書かれているのですが この二つを充電すれば良いのですか？？ でも、これも定義式に当てはめて計算するとCissだけが残ってしまいます… しかしながら、この参考サイトにはCissだけでは問題が生じるとありました。 以前から質問に答えてくださった方々の内容(又は参考サイト)からゲート電流を決定するのにi(rush)=Qg/tという式を教えていただいたので試しに計算比較してみました。 以下の内容で計算してみました。 素子 K2586 電源電圧 10V 負荷 モータ Max4A程度を想定 ゲート電圧 6V(4V駆動なので余裕を見て1.5倍にしました) スイッチング時間 1μs Cissのケース I=3550(pF)×6(V)÷1(μs)=21.3mA R=6(V)÷21.3(mA)=281.69Ω Qgのケース グラフよりQg≒70nc I=70(nc)÷1(μs)=70mA R=6(V)÷70(mA)=85.71Ω となり3倍以上差が出てしまいました。 使用するのはQgの値で良いんですよね…？ 書籍に載っているくらいなのでそんなに大きな間違いがあるとも考えにくいのですがすが、参考サイトの内容や過去の回答者様の話の内容と比較するとどうにも本が間違ってるように感じています。 それともIgで示してある式には別の意図でもあったのでしょうか？？ サイトに載ってるだけなら他の大量な情報で[間違ってるだろう]と判断もできそうですが本となるとどうにも気になってしまいます。 また、Qgを読みとる際にVDDの値が3種類程度しか書いてないのですが、これ以外の値を使いたいときはどうすれば良いのでしょうか？グラフに書いてある値で近い方を参照すれば良いのでしょうか？？ また、Qgを読み取る際にVgsの値が大きくなるとQgが大きくなる理由って何なんでしょうか？？読み方がおかしいのでしょうか？ また、プルダウン抵抗の選定の際にCR時定数の考えでRを決定しようと考えているのですが、これもQgの値をFに直して計算すれば良いのでしょうか？？ あれもこれもと質問が多くなってしまいましたが、よろしければお願いします。 参考にしたサイト(6ページあたり) http://www.fujielectric.co.jp/fdt/scd/pdf/SuperFAP-G.pdf データシート http://documentation.renesas.com/jpn/products/transistor/rjj03g0909_2sk2586ds.pdf 二項関係の問題 X=Z×(Z-{0})とし、X上の二項関係ρ1,ρ2をそれぞれ G(ρ1)={((p,q),(r,s))∈X×X|ps=qr} G(ρ2)={((p,q),(r,s))∈X×X|pqs^2≦q^2rs} により定める。 写像f:X×X→Xを f((p,q),(r,s))=(ps+qr,qs) ((p,q),(r,s)∈X) により定める。 (p,q)ρ1(i,j),(r,s)ρ1(k,l)ならば f((p,q),(r,s))=f((i,j),(k,l)) であることを示せ。 という問題に苦戦しています。 条件からpj=qi,rl=skを求めてこれを使って (ps+qr,qs)=f((i,j),(k,l))を示そうとしているんですが どうしても行き詰ってしまいます。 単なる計算ミスなんでしょうか？ それとも方針すら間違っているのでしょうか？ とける方、どうか教えてください！ 費用関数の微分 今短期総費用関数をｃ＝ｗＧ(Ｋ，ｑ)＋ｒＫ と表し、次に長期費用関数関数を求めるために上の式が最小となるようにＫを決定したいのですが、費用が最小となるための条件(Ｋについて微分してゼロとおく)が、ｗＧｋ(Ｋ，ｑ)＋ｒ＝０と成立するとあるんですが、微分の過程がわかりません。どなたかおしえて下さい！！(ｗＧｋのｋはＧについている小さいｋです) また、費用が最小となる条件が微分して０となるというのは、自分は一階の条件として単に極値を持つことを意味すると考えているのですが、あってるでしょうか・・・？ 指数不等式と対数不等式の問題です 定数ｋを整数として、ｘに関する不等式 log[6]ｘ+log[6](2^k+3^k-x)>k……(*) （１）不等式(*)をみたす実数ｘの範囲 （２）不等式(*)をみたす整数の個数をf(k)とする。f(k)は？ （３）すべての整数ｋに対して不等式f(k)≦f(k+1)が成立ことの証明と f(k)=f(k+1)をみたす整数ｋをすべて求めよ。 （４）不等式0<f(k+1)－f(k)<2^(k+3)をみたす整数ｋをすべて求めよ。 ただし、必要ならばlog[2]3=1.58とする。 難しいらしいです…。 解ける方がいらっしゃいましたら 解説お願いしますm(_)m 回転移動と整数問題 行列A=1/2(1 -√3),B=1/√2(1 -1)で表される１次変換をそれぞれf,gとする。変換fをｍ回,gをn回適当な順序で (√3 1 ) (1 1) 繰り返すと,点P(2,0)は点Q(√3,1)に移る。このような自然数の組(m,n)のうち,m+nが最小となるものを求めよ。 解 １次変換f,gはそれぞれ原点を中心とする60°,45°の回転移動である。また,原点をOとするとOP=OQ=2 ∠POQ=30° 変換f,gはそれぞれ原点m回,n回繰り返したときの点Pの像がQとなるから60°×m+45°×n==30°+360 ×kを満たす負でない整数kが存在する。よって 4m+3n=24k+2 k=0とすると 4m+3n=2 これを満たす自然数m,nは存在しない。 k=1とすると4m+3n=26・・・・(1) nは自然数であるから,3m=26-4m>=3・１より m=1,2,3,4,5 各mの値に対して,(1)を満たすnの値を調べることにより,(1)の整数解は(2,6),(5,2) k>=2のとき,4m+3n=24k+2を満たす(m,n)について 4(m+n)>4m+3n>=24・2+2からm+n>7 したがって,m+nが最小となるものは(m,n)=(5,2) 教えてほしいところ 何のために、kの値で場合分けみたいなことしているんですか？？ また、4(m+n)>4m+3n>=24・2+2となると何故m+n>7となるんですか？？ オートマトン (1)決定性有限オートマトンが与えられているとき、Mによって受理される言語L(M)が存在しないかどうかを判定するアルゴリズムを与え、その正当性について議論せよ (2)Σを有限の入力アルファベットとする。２つの決定性有限オートマトンM1=(Q1,Σ,δ1,q1,F1)とM2=(Q2,Σ,δ2,q2,F2)が入力として与えられたとき、L(M1)がL(M2)に含まれるか否かを判定するアルゴリズムは存在するか。存在するならアルゴリズムの概要を書け。存在しなければそのことを証明せよ。 という問題の解答が分かりません。 どなたか教えてください。 今度こそ単位分数の問題を解くぞ。 ｓ＝4abc-b-c, q=4efg-f-4g r =4abc-b-jc ,p=4abc-b-jc-k ちなみにｓとｑは３つの単位分数の解が存在していて解けるものです。 式を変形して 4ab-{r+b}/c=j より、aとｂがある程度自由に決められるとすると １≦ｊ≦４といいかげんですがこの範囲に決められるはずです。そうすると 比較的自由にｊｃ＋ｋ＝４ｇを決められるはずです。 そして、この場合、sが解けない場合を想定しています。 p=4abc-b-jc-k=24n+1,q=4efg-f-4g=24n+1 とします。 jc+k=4g、a=jg、e=4g-k、b=f とすると、 p=4jgfc-f-4g=4(4g-k)fg-f-4g p=4(4g-k)fg-f-4g=q となり、たとえｓが解けない24ｎ+1の素数が現れたとしても、 qの形をした変形で解けるのではないでしょうか。 Q∩[0,1]全体の測度=Σ[r∈Q∩[0,1]]点{r}の測度=0は何故? Q∩[0,1]全体の測度=Σ[r∈Q∩[0,1]]点{r}の測度=0 と本で見かけたのですが測度とは関数の事ですよね。だからこれは Q∩[0,1]全体の測度による像=Σ[r∈Q∩[0,1]]点{r}の測度による像=0 という意味ですよね。 測度とは 「(Ω,B)を可測空間(Bはσ集合体)とする時,f:B→Rが(Ω,B)上の可測 ⇔ (i) ∀A∈B,f(A)∈{r∈R;0≦r}∪{+∞},f(φ)=0 (ii) ∀m,n∈N (m≠n), B∋b_m,b_nは互いに素 ⇒ f(∪[k∈N]b_k)=Σ[k=1..∞]f(b_k)」 の事だと思います。 点{r}の測度fによる像=0だから Σ[r∈Q∩[0,1]]点{r}の測度fによる像=0なんだと思います。 どうして (点{r}の測度fによる像)=0 と言えるのでしょうか? つまり, (Q∩[0,1]全体の測度fによる像)=f(∪[b∈Q∩[0,1]]{b})=Σ[b∈Q∩[0,1]]f({b})と変形できると思いますが これからどうしてf({b})=0が言えますでしょうか? 推測ですが f({b})=#{b}/#(Q∩[0,1])=1/(アレフ0)=0と乱暴に計算してもいいでしょうか? (上の定義からはf({b})=#{b}/#(Q∩[0,1])と書ける事すらも言えてませんが…) 整数問題 実数を係数とするxの多項式f(x)について、すべての整数kに対してf(k)が整数であるための必要十分条件は、 f(0)が整数 かつ すべての整数kについてf(k)-f(k-1)が整数である ことを証明せよ。 この問題でf(x)=ax{n}+bx{n-1}+・・・ とおいてやったのですが できませんでした 他に何か考え方はないでしょうか？ 解答の指針を教えてください 整数問題の必要十分条件の求め方 kを負でない整数とし、 x^2-y^2=k …(*) の解(a,b)でa,bがともに奇数であるものを奇数解と呼ぶ。 (*)が奇数解を持つための必要十分条件を求めよ。 この問題では(*)が奇数解をもてば kは8の倍数であることが知られています。 そこでタイトルの通り求め方なのですが、 k=8n (n:負でない整数) とおくと、nを用いた 2n-1, 2n+1は奇数である。 x=2n+1, y=2n-1をx^2-y^2に代入すると (2n+1)^2-(2n-1)^2=4n*2=8n=k したがって、(x,y)=(2n+1,2n-1)は(*)の解である。 よって(*)が奇数解をもつための必要十分条件は 「kが8の倍数であること」 Ｑ.「奇数解をもつ」ならば「kは8の倍数」 という必要条件だけをもう一度証明したみたいで、 これで必要十分条件たりえるのでしょうか？ 高校数学；数と式とその論証 [問] 整式 f(x) と実数a があり、条件(I)(II)(III)をみたしている。 (I) f(x) を x^2+3x+2 で割ると 5x+7 余る。 (II) f(x) を x^2+4x+3 で割ると 2x+a 余る。 (III) f(x) は(I)(II)をみたす整式の中で次数が最小である。 このとき、a の値と f(x) を求めよ。 [解答] (I)より、 f(x)=(x+1)(x+2)Q(x)+5x+7 ―(1) (II)より、 f(x)=(x+1)(x+3)P(x)+2x+a ―(2) (Q(x),P(x)ともに整式) ~途中省略~ (x=-1などを代入していく) ......a=4 と求めることができる。 (1),(2)より.f(-3)=2Q(-3)-8=-2 ∴ Q(-3)=3 ⇔ Q(x)=(x+3)R(x)+3 (R(x)は整式) と書ける。 (1)に代入すると f(x)=(x+1)(x+2)(x+3)R(x)+3(x+1)(x+2)+5x+7 が得られ、条件(III)によりR(x)=0 である。 ∴ (最低次のf(x)) = 3x^2+14x+13 [質問] 最終的にR(x)=0としましたが、(1)の時点でQ(x)=0とすると どこに問題が生じるのでしょうか？ (1)でQ(x)=0、(2)でP(x)=0とすると明らかにおかしくなるのですが、 具体的に説明することができません。 よろしくお願いします。 必要十分条件の証明 x=(αr-βp)/(r-pq) y=(β-αq)/(r-pq) ただしp、q、r、α、β∈Z 整数p、q、rに関する条件|r-pq|=1は、任意の整数α、βに対し解x、yが整数であるための必要十分条件であることを証明しなさい という問題について解答が α=0、β=1とすると、y=1/(r-pq) y=整数であるから、r-pq=±1が必要である 逆に、r-pq=±1のとき、x、yは任意の整数α、βに対して整数となるから十分である したがって、求める必要十分条件は |r-pq|=1 となっていました ここで疑問に思ったのは任意の整数α、βに対し解x、yが整数であるからα=0、β=1とするのは理解でき、そのとき|r-pq|=1が成り立ち、逆に|r-pq|=1のとき任意の整数α、βに対して整数となるとなるのも分かるんですが、これで証明がほんとに完了してるのかということです 最初に任意の整数α、βに対しα=0、β=1を代表させていますが、例えばα=1、β=2とかα=3、β=-2とかの場合を考慮する必要はないのでしょうか？ 友人にも尋ねてみたのですが、曖昧です 自分なりに考えてみた結果は、任意の整数α、βに対し解x、yが整数であることの必要条件を求めるときは、任意の整数α、βに対し解x、yが整数であるというのはあくまで条件、前提であるからその段階ではα=0、β=1と代表させても問題ない、というものなのですが果たして正しいのでしょうか？ 長文で申し訳ありませんが、ご教授お願いいたします
お礼
ありがとうございました。 q=q_1 + k として、 f = (q_1 + k)g +r を計算したら、 f_2 > 2^k となりました。