初めての店舗開業を成功させよう>>

青チャートBの101番は以下のような問題です。

『自然数 1,2,3,・・・・,n をある順に並べ替えたものの一つをA1,A2,A3,・・・,An とする。1・A1 + 2・A2 +・・・+ n・An を最大にするような{An}はどのような数列か?』

この問題の解き方の指針は、こうあります。

『一般に、k・Anにおいて、k=An、すなわちAk-k=0のとき、Σk・Akが最大になる。
そこで、Ak-kとk・Akの関連を調べ、恒等式(Ak-k)^2 = Ak^2-2kAk+k^2 を考える。』

とあります。それに乗っ取り、解答では
Σk・Ak=1/2Σ{k^2+Ak^2-(Ak-k)^2}
という式から始まります。

上記のことを読んでいて理解はできるのですが、数学が苦手な自分すると、「もしこの問題を見たことがない人が初見でこの問題をテストで見たら、こんな発想できるものだろうか?」と考えてしまいました。

まずAk-k=0のとき、Σk・Akが最大になるということに気付き、そこから (Ak-k)^2 = Ak^2-2kAk+k^2 という恒等式を引っ張り出して、解答するなんていうのは、馬鹿な自分からするとよほど頭がいい人じゃない限り浮かぶものなのかなと思ってしまいます。

聞きたいことは、(受験勉強では)この問題は定石として覚えておくような問題なんでしょうか?
それとも、このくらいの発想は進学校の人はできるものなのでしょうか・・・。

A 回答 (4件)

こんにちは。



英語のほうでお目にかかったような気が…

> 聞きたいことは、(受験勉強では)この問題は定石として覚えておくような問題なんでしょうか?

全く覚える必要はありません。

> それとも、このくらいの発想は進学校の人はできるものなのでしょうか・・・。

それは人に依るでしょうが、同じ発想で解くにしても、その模範解答は説明の仕方が不自然でわかりづらいと思います。

問題集の模範解答を作った人は、本当はおそらく先に、

 Σk・Ak=1/2Σ{k^2+Ak^2-(Ak-k)^2}

を思い出したのだと思います。
これは掛け算の和を考えるときに、よく出てくる形ですので。
これは覚えるというか、知っておくと重宝すると思います。
ちなみに「知る」と「暗記する」はだいぶ違います。


しかし、模範解答のように、先に、Ak = k を予想して、それが動機で k・Ak と (Ak-k) の関連性を調べて…というのは、こじつけに見えます。



ちなみに、私なら次のように考えます。

> 『自然数 1,2,3,・・・・,n をある順に並べ替えたものの一つを> A1,A2,A3,・・・,An とする。1・A1 + 2・A2 +・・・+ n・An を最大にするような{An}はどのような数列か?』

これを一種の最適化問題ととらえます。そして、

1・A1 + 2・A2 +・・・+ n・An

を 1~n の因子のかかった A1~An と解釈します。

当然、大きい因子がかかっている Ak ほど大きくなるようにした方が大きくなりますよね。

ということは、A1=1, A2=2, … An=n が最大になることが明らかです。

私が採点者ならこれで十分に正解にすると思いますが、もしもっと厳密な証明が必要と感じる場合には、次のような証明を加えればよいと思います。

k<mとして、第k項と第m項の和を k Ak + m Am を取り出して、Ak > Am と仮定すると、AkとAmを入れ替えたものの方が大きくなってしまいます。(k Ak + m Am < k Am + m Ak という意味。移項すればすぐにわかります。)

従って、どの二つの項を取り出しても、k<m なら Ak<Am になるはずです。従って、A1=1, A2=2, … An=n となります。

この証明は、本質的にはANo.1~3の皆さんの証明と同じようなものですが…。
    • good
    • 0
この回答へのお礼

解答ありがとうございました。
答えが自明な気がしてよくわからないんですよね。
参考にさせていただきます。

お礼日時:2007/07/29 00:46

うーん。

そういう発想は出来るかなぁ。

でも、解法を覚えておかなくてもその場で証明を思いつくと思いますよ。

問題の性質からして、A1,A2...Anは比較的「揃った/規則的な」数列であろうと推測できます。
直感的に、A1,A2...Anは1,2,3....nであるときが最大になりそうだと言うことも思いつくでしょう。
あとは、帰納法で行くか、一般的に成り立つことを論証するかどっちかですが、後者を選んでみましょう。で背理法で考えてみます。

あるn(n>1)について
1・A1 + 2・A2 +・・・+ n・An =Xを最大にする{Ai}が
昇順でないと仮定します。
昇順でないということは、Ak>Ak+1が成り立つ k(1<=k<n)が少なくとも1つ存在します。
ここで、{Ai}の2要素を入れ替えた以下のような{Bi}を考えます。
Ai=Bi(i<kまたはi>k+1)
Ak=Bk+1
Ak+1=Bk

1・B1+2・B2+・・・・+n・Bn=Yと置きます。
XとYを比べてみます。
Y-X=  k・Bk+(k+1)Bk+1-k・Ak+(k+1)Ak+1
=k・Ak+1+(k+1)Ak-(k・Ak+(k+1)Ak+1)
=Ak-Ak+1 >0

これは Xが最大であるという仮定と矛盾します。

よって、{Ai}内にどこか昇順でないところがあるという仮定が否定されました。
1~nを並び替えた順列で至るところ昇順な数列は、1,2,3,・・・n
だけです。
QED
    • good
    • 0
この回答へのお礼

回答ありがとうございました。
参考にさせていただきます。

お礼日時:2007/07/29 00:47

ΣkAkを最大に、しかもAkは1からnまでを並び替えたもの、


となれば、たぶん、Ak=kが答えだろうなぁ、と
推測はつくんじゃないかと思います。

それをもとに、もしAk=kじゃなかったら、どうなるかを考えます。

もし、An=nでないとする。
このとき、Am=nとなるnより小さいmが存在する。
また、An=aとすると、aはnより小さい値となる。
ここで、
(nAm+mAn)-(nAn+mAm)
=nn+ma-na-mn
=n(n-m)-a(n-m)
=(n-a)(n-m)
ここで、aもmもnより小さいので、上の値は正。
つまり、nAm+mAn>nAn+mAmがいえる。
これは、
Anがnではなかったら、Am=nとなるmに対し、
AmとAnを入れ替えたほうがΣkAkが大きくなる、
つまり、An=nとしたほうがΣkAkが大きくなることを
示している。
以下同じ議論をn-1、n-2…と繰り返していくと、
Ak=kがすべてのkにたいして成り立たないといけないことがわかる。

Ak=kじゃなかったら、入れ替えたほうが大きくなるよ、と
証明すれば言いだけの話。
参考書には時々思いつきもしないような解法を載せていたりするけど、
必ずしも、それを思いつかないとできないわけではないです。
    • good
    • 0
この回答へのお礼

回答ありがとうございました。
もっと色々な解法を載せて欲しいです。
参考にさせていただきます。

お礼日時:2007/07/29 00:48

私なら次のように発想します.


任意の並び方(Ak)_{k=1,…,n}を考えます.
もしAn≠nであるならば,ある番号j<nがあって,Aj=nとなりますが,
(Ak)からjとnだけを入れ替えた新しい並び替え(Bk)を考えると,
Σk・Ak < Σk・Bk
であることが簡単にわかります.
よって,Σk・Akを最大にしたいのであれば,少なくともAn=nであることがわかります.
次に,An=nを満たすような並び方を考え,A{n-1}≠n-1となるならば,また同じように並び替えをすればΣk・Akを大きくできるので,また,
A{n-1}=n-1で考えればよいことになって…,以下同様に考えると,
結局 An=n,A{n-1}=n-1, … A2=2,A1=1
がΣk・Akを最大にするのだとはわかります.
    • good
    • 0
この回答へのお礼

回答ありがとうございました。
色々な着想がありますね。
参考にさせていただきます。

お礼日時:2007/07/29 00:48

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qy=x^(1/x) の 微分

y=x^(1/x) の微分を教えてください。
簡単な問題なのにすいません。

Aベストアンサー

対数微分法で微分できます。まずは両辺の対数をとって

y = x^(1/x)
→log|y| = log|x^(1/x)|
→log|y| = (1/x)log|x|

このlog|y| = (1/x)log|x|の両辺をxで微分します。

まず左辺をxで微分することを考えます。
f(x) = log|x|とおき、g(x) = yとおくと、
log|y| = f(g(x))
ですので、

(log|y|)'
={ f(g(x)) }'
= f'(g(x)) × g'(x)

です。f'(x) = 1/xですのでf'(g(x)) = 1/y、
g'(x) = (y)' = y'より、
(log|y|)'
= f'(g(x)) × g'(x)
= y' / y

です。
y = x^(1/x)を代入すると

(log|y|)'
= y' / y
= y' / { x^(1/x) }

となります。

(log|y|)' = { (1/x)log|x| }'
→y' / { x^(1/x) } = { (1/x)log|x| }'

この両辺に{ x^(1/x) }をかけると

y' = { x^(1/x) } × { (1/x)log|x| }'

となります。
なので{ (1/x)log|x| }'の計算をすればy'が求まります。
積の微分で解いてください。

対数微分法で微分できます。まずは両辺の対数をとって

y = x^(1/x)
→log|y| = log|x^(1/x)|
→log|y| = (1/x)log|x|

このlog|y| = (1/x)log|x|の両辺をxで微分します。

まず左辺をxで微分することを考えます。
f(x) = log|x|とおき、g(x) = yとおくと、
log|y| = f(g(x))
ですので、

(log|y|)'
={ f(g(x)) }'
= f'(g(x)) × g'(x)

です。f'(x) = 1/xですのでf'(g(x)) = 1/y、
g'(x) = (y)' = y'より、
(log|y|)'
= f'(g(x)) × g'(x)
= y' / y

です。
y = x^(1/x)を代入すると

(log...続きを読む

Q積分で1/x^2 はどうなるのでしょうか?

Sは積分の前につけるものです
S dx =x
S x dx=1/2x^2
S 1/x dx=loglxl
まではわかったのですが
S 1/x^2 dx
は一体どうなるのでしょうか??

Aベストアンサー

まず、全部 積分定数Cが抜けています。また、積分の前につけるものは “インテグラル”と呼び、そう書いて変換すれば出ます ∫

積分の定義というか微分の定義というかに戻って欲しいんですが
∫f(x)dx=F(x)の時、
(d/dx)F(x)=f(x)です。

また、微分で
(d/dx)x^a=a*x^(a-1)になります …高校数学の数3で習うかと
よって、
∫x^(a-1)dx=(1/a)*x^a+C
→∫x^adx={1/(a+1)}*x^(a+1)+C
となります。

つまり、
∫1/x^2 dx=∫x^(-2)dx
={1/(-2+1)}*x^(-2+1)+C
=-x^(-1)+C
=-1/x+C

です。

Q高校数学、整数問題

(問題)
αは0<α<1を満たす実数とする。任意の自然数nに対して、2^(n-1)αの整数部分をa(n)、2^(n-1)α=a(n)+b(n)とおくとき、
nが奇数の時、0≦b(n)<1/2,
nが偶数の時、1/2<b(n)<1になるという。αを求めよ。
(疑問)
方針が立ちません。ヒントをください。お願いします。

Aベストアンサー


とりあえず、
2^(n)*α=a(n+1)+b(n+1)=2*a(n)+2*b(n)
となります
nが奇数の時、0≦b(n)<1/2,
nが偶数の時、1/2<b(n)<1になるという。
とあるので、2*b(n)は
nが奇数の時、0≦2*b(n)<1,
nが偶数の時、1<2*b(n)<2
になります
ですので、
nが奇数の時は a(n+1) = 2*a(n) (2*b(n)は1未満なので関係してきません)
nが偶数の時は a(n+1) = 2*a(n)+1 (2*b(n)が1.xxxなのでa(n+1)に+1, b(n+1)=0.xxxx)
となります

aはどこか(n=k)で初めて1になるので、その後は2倍する、2倍した後+1する、2倍する、2倍した後+1するの繰り返しになります
こう書くと分かりにくいですが、式にきちんと書いて展開してみたら、等比数列の和になります
最後に無茶ですが、nが限りなく大きい時bなんて小さいものだからと無視して、a(n)の形からαを推察することになると思います
(正確には、a(n)の形を推測する時点でbも同時に裏で推測されてることになると思います)

②おっしゃられるように、2^(n-1)と2の冪乗を掛けているところと、b(n)が1/2を境に条件分けされてるから、だと思います
1/2未満ということは2進数表記で 0.0xxxxxx
1/2以上1未満ということは2進数表記で0.1xxxxx
とりあえず、どちらかから初めて2倍すると桁が一つ上がるので
0.xxxxxか1.xxxxx
次は0,1が逆転するはずなので
0.1xxxxと1.0xxxx
また、2倍(桁上り)して、杉の数が逆転するので
01.0xxxxと10.1xxx
みたいな感じで01が交互に来るんだなぁ、あとはn=1の時α=a(1)+b(1)でb(1)<1/2から0.101010なのか0.010101なのか判断してという感じですかね
2進数の小数点は、k桁目が1なら(1/2)^kを足すという計算で求めれるので


とりあえず、
2^(n)*α=a(n+1)+b(n+1)=2*a(n)+2*b(n)
となります
nが奇数の時、0≦b(n)<1/2,
nが偶数の時、1/2<b(n)<1になるという。
とあるので、2*b(n)は
nが奇数の時、0≦2*b(n)<1,
nが偶数の時、1<2*b(n)<2
になります
ですので、
nが奇数の時は a(n+1) = 2*a(n) (2*b(n)は1未満なので関係してきません)
nが偶数の時は a(n+1) = 2*a(n)+1 (2*b(n)が1.xxxなのでa(n+1)に+1, b(n+1)=0.xxxx)
となります

aはどこか(n=k)で初めて1になるので、その後は2倍する、2倍した後+1する、2倍する、2倍した...続きを読む


人気Q&Aランキング

おすすめ情報