【1】 次のような問題を考える.
という名前の商品がそれぞれ個ずつあり,これらを台のトラックで運びたい.ただし,商品の重量は売れた時の利益は万円である.また,トラックにはという制限重量を超えて荷物を詰め込むことはできない.このとき運んだ商品の利益の合計をできるだけ大きくするには,どの商品を運べばよいだろうか.
この問題を含んだ問題群として,運べる商品をの個に制限し,制限重量がである場合を考える.この問題に対して,運んだ商品の利益の合計の最大値(以下では最大利益と呼ぶ)を関数で表現する(ただし,で定義されているものとする).例えば,は,個の商品の中から制限重量を超えないように幾つか選んで運んだときの最大利益を意味している.このとき,次の問(1)〜(3)に答えよ.
(1) とする.の範囲で場合分けして考えることにより,関数とのグラフを図示せよ.また,各場合での関数値の計算法を簡潔に説明せよ.
(2) 上記で定義した関数には以下の関係が成り立つ.
に対し,
ただし,はとでより大きな方の数を意味する.このとき,の場合では,という関係が成り立っているが,これは次のように説明することができる.
はの商品から制限重量を超えないように運ぶ時の最大利益であるが,であるため商品を運ぶことはできない.ということは,の商品から制限重量を超えないように運ぶということは,の商品から制限重量を超えないように運ぶことに他ならない.このときの最大利益はであるので,となる.
この説明を踏まえて,の場合において,という関係が成り立つことを証明せよ.
(3) 冒頭の枠内に記述した問題に対する最大利益はに相当する.いま,とは自然数であることを仮定する.このとき,次の手順によってを計算することができる.
ステップ1.
との最大公約数を求めとする.
ステップ2.
まず,に対し,次式よりを計算する.
ステップ3.
次に,に対し,次式よりを計算する.
ステップ4.
以下,に関して同様の手順を実行する.
すなわち,に対し,が計算されていれば,次式よりを計算できる.
これを繰り返すと,最終的にの値が得られる.
上記の手順を実行することにより,表1で与えられているような個の商品を制限重量がのトラックで運ぶ時の最大利益を求める.
表1 商品の重量と利益
商品 | |
|
|
|
|
重量 | | | |
| |
利益 | 万円 | 万円 | | | 万円 |
解答では計算法は述べなくてよいので,上記の手順に基づいての値を順番に計算し,その結果を答案用紙の表中に記入せよ.