高校数学、数列

添付図の鉛筆をピラミッドのように積み上げる問題について、自分でいくつか具体的に考えてみたのですが、解法が思いつきません。具体例からどのように考えればよいのかを教えてください。

（例）○は最少のものである。
(1)６本（下から）
（６）、（５、１）、（４，２）、○（３，２，１）（２，１，１，１，１）→ダメ
（１，１，１，１，１，１）→ダメ
(2)５本（同様に）
（５）、（４，１）、○（３，２）
(3)７本
（７）、（６，１）、（５，２）、○（４，３）（３，２，１，１、）ダメ、以下はだめ
(4)１０本
（１０）、（９，１）、（８，２）、（７，３）、（６，４）（５，４，１）、○（４，３，２，１）、（３，２，１，１，１，１，１）ダメ、以下ダメ
ここからその本数が最少かどうかは結局１本減らして次の本数が適するかどうか試さないとわからないのかと思い、ここからわかりません。
どう考えてゆけばよいのでしょうか？

No.5 ベストアンサー 回答者： MagicianKuma 回答日時： 2014/07/01 19:58

最下限をmとしたとき最大の積める個数をK(m)とするとK(m)=1+2+3+・・・+m=(m+1)m/2ですね。

さてn個の鉛筆を積むためには、K(m)≧nである必要があります。またその時のmが最小値なら、K(m-1)では積めない事になります。すなわちK(m-1)<nです。
ここから、(m+1)m/2≧n＞m(m-1)/2　を満たすmを求めれば良いわけです。これを解くと
(1+√(8n+1))/2＞m≧(-1+√(8n+1))/2 を得ます。
例 n=209 20.95>m≧19.95　よってm=20

この回答へのお礼

ありがとうございました。

お礼日時：2014/07/01 21:54

No.4 回答者： stomachman 回答日時： 2014/07/01 07:28

てっぺんが1本になるようにn段積み上げたときの鉛筆の数をS(n)、そのときの最下段の鉛筆の数をB(n)とします。

(1) まずB(n)とS(n)をnの式で表しておきます(n=0の場合も含めて）。得られた
　　S(n)=(nの式）
という形の式の左辺をSに書き換えて、
　　S=(nの式)
とし、これをnについて解いて、nをSで表す式を作っておきます。すなわち
　　n = (Sの式）…★
という風にするんです。この式は、S本の鉛筆で最高何段まで積めるか、を表していますが、Sの値によっては整数になりません。

(2) 鉛筆がm本あるとき、S(j-1)＜m ≦ S(j)となるjが分かれば、最下段は最少B(j)本である、ということが分かります。
　そのようなjを知るために、式★のSにmを代入してnを計算する。得られたnは必ずしも整数ではありません。n以上の最小の整数（これをceil(n)と書きます。ceilはceiling:天井という意味です）をjとすると、S(j-1)＜m ≦ S(j) である。
　n=jになった場合に限りm=S(j)であり、てっぺんは1本。また、n＜jの場合にはS(j-1)＜m ＜ S(j) です。

(3) さて、最下段をB(j)本としてm本の鉛筆を積み上げた山とは、最下段をB(j)本としてS(j)本の鉛筆をj段積み上げた山（てっぺんは1本）からS(j)-m本を取り除いた山と同じことです。

(4) 今度は、取り除かれた部分に着目しましょう。最下段をB(k)本としてS(k)本の鉛筆をk段積み上げた山（てっぺんは1本）から、最下段の鉛筆だけをr本（ただし 0≦r＜B(k)）取り除いた山を考えます。これが取り除かれた部分です。この山に含まれている鉛筆の数はもちろんS(k)-r本。

というわけで、
(5) S(j)-m = S(k)-r （ただし0≦r＜B(k)）となるrが分かれば、最下段をB(j)本としてm本の鉛筆を積み上げた山の最上段にある鉛筆の本数はB(k)-rだと分かります。
　　r = S(k)-S(j)+m
だから、
　　(S(j)-m) ≦ S(k) ＜B(k)+(S(j)-m)
となるkが分かれば、rが決まります。これは
　　(S(j)-m) ≦ S(k)
を満たす最小のkに他なりません。既に(S(j)-m)は決まっているから、式★を利用してkを計算できますね。すなわち、★のS(に(S(j)-m)を代入してnを計算すれば、得られたnを越えない最小の整数がkです。

この回答へのお礼

ありがとうございました。
自分でももう一度解答を書いてみます。

お礼日時：2014/07/01 21:55

No.3 回答者： MagicianKuma 回答日時： 2014/06/30 19:02

最下段におく本数をmとしたとき最大で何個つめるか(mで決まるはず)を考えたらどうでしょう。

でもって実際に積む本数nは上の求めた最大数以下でないとだめですね。

この回答への補足

私の調べた結果はどのような時に、最少になるか?を調べようとしたものですが、それはわからないので、そもそも、最下段をｍ個とした時、最大でいくつ積めるのか?を考えていくということでしょうか？

補足日時：2014/07/01 01:53

No.2 回答者： trytobe 回答日時： 2014/06/30 17:58

補足いただいたその通りで、６本、１０本、・・・という正三角形になる本数は、一番下の段を跳び箱のように付け足したような形になるので、１＋２＋３＋４＋５＋・・・本なんですよね。

（ここくらいしか数列っぽい要素がないのですが）

６本から１本とったときが５本の最適解、１０本から３本とったときが７本の最適解、というように、正三角形になる本数から何本かとったときが１２５本の最適解、になるかと思います。

この回答へのお礼

ありがとうございました。
自分でも解答を書いてみようと思います。

お礼日時：2014/07/01 21:56

No.1 回答者： trytobe 回答日時： 2014/06/30 16:56

あと何本か足して、ちょうど正三角形の山にできる、

という本数を見つけてから、鉛筆を除去してみては。

この回答への補足

１２５本で完全なピラミッドが出来ればもちろん最小だし、出来なくても、７本の場合のように、７本以上で作った最小のピラミッドから７本まで、削ったものは最少になる。という考えでしょうか?

補足日時：2014/06/30 17:39

この回答へのお礼

自分でも解答を書いてみます。
有難うございました。

お礼日時：2014/07/01 21:56