和が最大になるような数列の並びかえの問題

青チャート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 という恒等式を引っ張り出して、解答するなんていうのは、馬鹿な自分からするとよほど頭がいい人じゃない限り浮かぶものなのかなと思ってしまいます。

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

No.4 ベストアンサー 回答者： aquarius_hiro 回答日時： 2007/07/27 03:12

こんにちは。

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

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

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

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

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

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

　Σ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の皆さんの証明と同じようなものですが…。

この回答へのお礼

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

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

No.3 回答者： a-saitoh 回答日時： 2007/07/26 00:03

うーん。

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

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

問題の性質からして、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=　　ｋ・Bｋ＋(k+1)Bk+1-ｋ・Aｋ＋(k+1)Ak+1
=ｋ・Aｋ+1＋(k+1)Ak-(ｋ・Aｋ＋(k+1)Ak+1)
=Ak-Ak+1 >0

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

よって、｛Ai}内にどこか昇順でないところがあるという仮定が否定されました。
１～ｎを並び替えた順列で至るところ昇順な数列は、１，２，３，・・・n
だけです。
QED

この回答へのお礼

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

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

No.2 回答者： ---------- 回答日時： 2007/07/25 23:53

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

となれば、たぶん、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じゃなかったら、入れ替えたほうが大きくなるよ、と
証明すれば言いだけの話。
参考書には時々思いつきもしないような解法を載せていたりするけど、
必ずしも、それを思いつかないとできないわけではないです。

この回答へのお礼

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

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

No.1 回答者： tinantum 回答日時： 2007/07/25 23:43

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

任意の並び方(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を最大にするのだとはわかります．

この回答へのお礼

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

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