自然数Nをいくつかの自然数に分割してから積をとるときの最大値

質問

与えられた自然数Nに対して、Nをいくつかの自然数に分割してから積をとる。
このとき、その積が最大となるのはどのように分割したときでしょうか？

たとえば、

５＝３＋２
と分解したとき、積の最大値は６

６＝３＋３
と分解したとき、積の最大値は９

７＝３＋４＝３＋２＋２
と分解したとき、積の最大値は１２

１０＝３＋３＋４＝３＋３＋２＋２
と分解したとき、積の最大値は３６

このように分割の個数はいくつでもいいです。

できるだけ、３ずつに分割したほうがよさそうなことが予想できると思います。

この辺の証明や、また、条件を適度に変えたときの話題について、アイデアがありましたら、教えていただけないでしょうか？

たとえば、和と積を交換したら、どのような結果が予想されるでしょうか？

回答No.11

stomachman · ベストアンサー

No.10でそのうちやってみます、とか言ってますが、何をやってみる積もりなのかを書いておかなくちゃいけない子のstomachmanです。

「正の整数Sをn個の実数a[i] (i=1,2,…,n)の和として表したとき、それらの積Mを最大にするようなnをカンタンに計算する方法を求む」
をやってみようかな、と思う訳です。

nを固定した場合、a[i]はどれも同じ値 a=S/n であるときにMが最大なのは自明だから
M(S,n) = (S/n)^n
を最大化するnを求めるという問題です。

　Sが正の実数の場合、正の実数xについて　
M(S,x) = (S/x)^x
あるいは対数をとって
P(x) = x (ln(S/x))
を最大化するxは、Pをxで微分して
P' = dP/dx = ln(S) -ln(x) - 1
P'' = dP/dx = 1/x ＞0
だから、極大がただ１個あり、それはdP/dx = 0 となるxであって、
x = S/e
であることが分かります。

　従って、
N = floor(S/e)
とすると、M(S,N)かM(S,N+1)が最大である。当たり前です。
　そして、M(S,N)とM(S,N+1)の大小関係はどうかと言うと、
M(s,N)/M(s,N+1) = 1
とすると
s = ((N+1)^(N+1))/(N^N)
が直ちに出ますから、まとめると

N=floor(S/e)
s=((N+1)^(N+1))/(N^N)
とするとき、
S≧s→M(N+1)が最大
S≦s→M(N)が最大

と、ここまでは自明です。

さて、
N = floor(S/e)
K = floor(S/e+α)
としたとき、
S≧s→K=N+1
S≦s→K=N
となるα（0≦α＜1）は定数になる？そんな旨い話はあるのか？

　Sが実数の時には無理でしょう。例えば、α=0.5 （素直に四捨五入）だと、S=12.21～12.22のときにダメです。
　しかし、Sを整数に限定したらどうなのか、ってことが気になってる訳です。

回答No.10

stomachman

No.7 (No.8)について、直感の直感による直感のための修正です。

どうも一番素直に、項数は「(S/e)の四捨五入」にするのが積が最大、という気がしてきました。が、
floor(S/e+1/2)なのか、
ceil(S/e-1/2)なのか、
というのはよく分からない。

そのうちやってみます。

回答No.9

Tofu-Yo

ほとんどやってることは他の方と同じですが、以下のような手順で証明したらすっきりするかと思います。

自然数N(≧2)をいくつかに分けたとき、その中に、
１．1がひとつでもあると最大にならない。
（その1を他のどこかに合併させた方が必ず大きいので）
２．2が3つ以上あると最大にならない。
（3つの2を2つの3に置き換えたほうが大きいので）
３．4が2つ以上あると最大にならない。
（4が1つあることと2が2つあることは同じことなので２に従う）
４．5以上がひとつでもあると最大にならない。
（偶数の場合と奇数の場合に分けて証明する。偶数のときを言うには2mとm^2をm≧3に注意して比較する。奇数のときは2m+1とm(m+1)をm≧2に注意して比較する。）
以上よりなるべく3ずつに分け、端数があれば最後を2または2,2（4でも同じ）にして調整したときに最大となる。

・・・でどうでしょうか。

回答No.8

Tacosan

実数を許すならなるべく e に近い数値を使う方がいいので (これは解析的に出せます), 基本的には #7 の通りです. ただし ceil か floor かは場合によります.
手元計算だと 193/e = 71.0007... で,
(193/71)^71 = 6.842679...×10^30,
(193/72)^72 = 6.794953...×10^30
なのでこの場合は floor の方が有利. 一方 2721/e = 1000.99995... で
(2721/1000)^1000 = 5.3523...×10^434,
(2721/1001)^1001 = 5.3549...×10^434
となり ceil の方が有利.

回答No.7

stomachman

No.6の「お礼」について、

> 各成分をe（自然対数の底）にしたほうがよさそうです。

直感的には a=(S/ceil(S/e)), M=a^ceil(S/e) じゃないかなー。

回答No.6

stomachman

項の個数nを定数（ただしn≧2)に固定すると、丁度 質問q=2347447 と同じ問題になります。jlglgさんはq=2347447に回答なさってるうちにいわゆる「インスパイヤされた」ってやつですね。

　「N≧2のとき、項の数nをfloor((N+1)/3)にして、全ての項をm = floor(N/n)かm+1にする」というのがこのご質問の答です。これはN≧3の場合なら、「全ての項を3にするが、4も高々１個ある」というのと同じことになります。
　証明は、Quattro99さんのNo.2のアプローチが単純明快だと思います。（つまり項の個数を定数に固定した場合とはかなり違う性格の問題になってる、ということですね。）

　さて、条件を適度に変えたとき、というお話ですが、和と積を交換したらどうなるか、というのは、積を一定に保って和を極大あるいは極小にしろということでしょうか。こりゃ素因数分解にほかならず、これまた性格ががらりと変わるでしょう。ただ、極大にしろの場合、1をいっぱいかけ算するのを禁止しないとな。

お礼

6名の方の回答に感謝いたします。感想を書きます。

まず、素数の理論ではしばしば２が異質なように、今回も２は異質な気がします。
あと、
２＋２＝２＊２＝２＾２
というような不思議な関係もあるし。

Quattro99さんなどが書かれた証明の方針は分かりました。でも、次のような方針はどうでしょう。N=16で説明します。（mayan99さんと方針は同じ）

実際にN=16を分割して、成分の積を大きくしていく操作を考える。
16のままよりも、16=2+14に分割したほうがよい。
その中の14をさらに分解して、16=2+2+10にしたほうがいい。
その中の10をさらに分解して、16=2+2+2+8にしたほうがいい。
同様に、16=2+2+2+2+2+2+2+2にしたほうがいい。
その中の2+2+2を3+3に変えて、16=3+3+2+2+2+2+2にしたほうがいい。
同様に、16=3+3+3+3+2+2にしたほうがいい。
それ以上にいい分解はない。
もちろん、この説明には不備がありますが、「場合分けは不要」「自然数の素因数分解のように、実際の分割の方法を示している」というメリットがあると思います。

さて、条件を適度に変えたとき、和と積を交換して考えたとします。24で考えたとき、
24=2*12=3*8=4*6=2*2*2*3=2*3*4
となるが、成分の和が最小となるのは？

これは積の分解を細かくするにつれ、和が小さくなっていき、一番細かい分割のとき、つまり素因数分解のときが和が最小になりそうです。

もどって、条件を適度に変えたとき、正の実数を有限個の正の実数の和に分割したとき、積が最大になるのは？
字数制限があるので、結果だけを言うと、各成分をe（自然対数の底）にしたほうがよさそうです。
自然数の場合は３、実数の場合はe(=2.71…)、この辺関連性ありそうです。

回答No.5

kabaokaba

No.4です
>i=2 のとき
>N=3+3+・・・+3（(k-1)個の和）+2で積は 3^{k-1}・2

書き間違った(-_-;;

i=2 のとき
N=3+3+・・・+3（k個の和）+2で積は 3^{k}・2

とどのつまり，No.2さんと同じですね

回答No.4

kabaokaba

>できるだけ、３ずつに分割したほうがよさそうなことが予想できると思います。

>16=3+3+3+3+4

「できるだけ，3ずつ」というからには

16=3+3+3+3+3+1
というのが予想の分割で，これは81，
一方，16=3+3+3+3+4 でこれは108

ということで，予想は違いますね

ちょっと予想を整理してみます

自然数Nに対して，N=3k+i (i=0,1,2, kは自然数か0)
とする
このとき，Nを任意の自然数の自然数の和で表したとき
それらの自然数の積が最大になるのは
以下のようなときである
i=0 のとき，
N=3+3+・・・+3（k個の和）で積は 3^k
i=1 のとき，
N=3+3+・・・+3（(k-1)個の和）+4で積は 3^{k-1}・4
i=2 のとき
N=3+3+・・・+3（(k-1)個の和）+2で積は 3^{k-1}・2
ただし，k=0，i=1，2のとき，すなわち
N=1のときは 1
N=2のときは 2

こんな感じかな．

証明は・・・・こんな方針でどうでしょう
かなり大雑把で穴だらけです．
＃裏側にはkによる帰納法が隠れています．

(1)積が最大となる分割には1は存在しない
これは自明

(2)N=3kの場合
{3,3,...,3}（k個）の分割の個数を増やそうとすると
必ず1が分割に表れるので，最大の分割は
この分割の個数以下の分割である．
次にこの分割の数を減らしてみる
3をひとつ1と2にして，それぞれを別の3に配分する
{3,...,3, 4,5}（3はk-3個）
このとき，3^{k-3}・3^3と3^{k-3}4・5は
前者の方が大きい(*)．
また，3=1+1+1として
{3,..,3, 4,4,4}(3はk-4個)とする
3^{k-4}・3^4と3^{k-4}・4^3では
前者の方が大きい(*)
このように処理していくことで
「3をなくす」と積が小さくなることが分かる

＃(*)ではkが小さい場合に別途議論が必要

よって，N=3kのときは3^kが最大．

N=3k+1，N=3k+2のときも同様に示す．

回答No.3

mayan99

おもしろい問題ですね。

まず以下の数字に分割した場合を検証します。

２：１＋１に分割しても積が上回らないのでこれ以上分割できない。

３：１＋２に分割しても積を上回らないのでこれ以上分割できない。

４：２＋２に分割できる。（イコールですが便宜上分割します）

５：３＋２に分割した方が積が上回る。２，３は上記でさらに分割できない。

６：３＋３に分割した方が積が上回る。

７：同様

・
・

以上で４以上はさらに分割した方が有利である。
したがって２または３に分割した方がよいことが分かる。

次に２が３個あった場合　２＋２＋２は　３＋３の方が上回るので３に分割する。

以上で３または２に分割した方が積が最大になる。ただし２は２つまで含まれること。

ではいかがでしょう。

回答No.2

Quattro99

とても稚拙ですが。

１．奇数は2a+1、偶数は2aとおけるので（aは自然数）、5以上だとa+(a+1)あるいはa+aに分けてa(a+1)、a*aとしたほうがより大きくなるので、分割した数の積が最大になるときそれらの数は4以下である。

２．a＞1*(a-1）なので、分割した数の積が最大になるときそれらの数に1はない（N=1の場合を除く）。

３．１．２．より、分割した数の積が最大になるときそれらの数は2、3、4である（4は2と2に分けても同じだがこの後を考えるときに都合がよいので残した）。

４．5以上の自然数は、3a+2、3a、3a+4の3種類に分類出来る（aは自然数）。これらを3a+2なら、「3をa個と2」のようにに分ける場合を考え、それ以外の分け方をした場合と比較してみる。

「3をa個と2」に分けた場合、a+1個に分けられているが、a個以下に分けるには、4が2個以上になる（それ以外では5以上が出来てしまう）。しかし、4、4（合計8）は3、3、2と分けた方が積が大きくなるのでa個以下に分けた場合は最大にならない。
a+2個以上に分ける場合、「3をa個と2」に分けた場合の3から1ずつ持ってきて（2から持ってくると1が残ってしまう）2、3、4を作ることになり、2が3個以上になる。しかし、2、2、2なら3、3の方が積が大きくなるのでa+2個以上に分けた場合は最大にならない。
よって、3a+2は「3をa個と2」に分けた場合が積が最大である。
同じようにして、3a、3a+4もたぶん「3をa個」、「3をa個と4」に分けた場合が最大になると示せるのではないかと思います。

回答No.1

Ichitsubo

16を3つの自然数に分けた場合、
14,1,1　　10,1,5　　8,1,7　　7,3,6
13,1,2　　10,2,4　　8,2,6　　7,4,5
12,1,3　　10,3,3　　8,3,5　　6,4,6
11,1,4　　9,2,5　　_8,4,4　　6,5,5
11,2,3　　9,3,4　　_7,2,7
の19通りがあり、その組の積の最大値は6,5,5の時で150
しかし4,4,4,4と4分割をすると積は256となり矛盾。

説が正しくないことが証明された。

お礼

>説が正しくないことが証明された。

僕が書いた説とは、

できるだけ、３ずつに分割したほうがよさそうなことが予想できると思います。

つまり、３個に分割という意味ではなく、成分ができるだけ３であったほうがいいという意味です。

N=3+3+3+・・・+3
or
N=3+3+3+・・・+3+4

という意味です。

16=3+3+3+3+4

がたぶん、積が最大になる分割でしょう。