Challenge!

問題176　棒の分割
Weekend Mathematics／問題／問題176　棒の分割

問題176　棒の分割

長さａセンチの棒をｂセンチとｃセンチに分割（ｂ＋ｃ＝ａ）するには、 ｂ×ｃ円の料金がかかるという。
今、ｎセンチの棒からスタートして、長さが自然数であるように分割を繰り返し、 最後に１センチの棒ｎ本を作るとする。
このとき、どのような過程を経て分割しても、かかる料金は同じであることを証明せよ。

問題の出典

キュートな数学名作問題集

小島寛之著

解答

～到着順にご紹介します～

解答・その1

（ペンネ－ム：haya）

解答・その2

（ペンネ－ム：マシャ）

nセンチのときにかかる料金をanとおく。

(命題)
「an=(1/2)n(n-1)でありかつどのような過程を経て分割しても、かかる料金は同じである」

この命題を数学的帰納法を用いて証明する。
[1] n=1,2,3のとき
分割の過程は1通りのみであるので、
　　a1 = 0(分割する必要が無いから)
　　a2 = 1*1 = 1
　　a3 = 2*1 + 1*1 = 3
となり命題は成り立つ

[2]n=4のとき
分割は　4 → (2,2) → (1,1,1,1)　と
　　　　　4 → (3,1) → (2,1,1) → (1,1,1,1)
の2通りある。
前者の場合、a4 = a2 + a2 + 2*2 = 6
後者の場合　a4 = a3 + 3*1 = 6
よって命題は成り立つ

[3]n=k　(k=1,2,3,…)　以下のとき全てにおいて命題が成り立つと仮定する。
このときにn=k+1を考える。

　　ak+1 = ak+1-m + am + (k+1-m)*m     (m=1,2,…,k)
      　 = (1/2)(k+1-m)(k-m) + (1/2)m(m-1) + (k+1-m)*m
      　 = (途中計算省略)
       　= (1/2)(k+1)(k+1-1)

よってn=k+1のときも命題が成り立つ。

[4] [1]から[3]により数学的帰納法により命題が真であることが証明された。
QED

解答・その3

（ペンネ－ム：ちょろんは太太）

☆　直感的証明
1x1のタイルを 縦 n個、横n個に以下の図のように並べる。 n （ = a+b） を a と b に分割したとすると、
その料金（a x b）は、太線で囲われた長方形の面積に対応する。
残された部分についても分割を繰り返し行うと、料金は、順次、青色のタイル部分に対応される。
最終的に長さ１センチの棒に分割した場合は、総料金は、図中の青色タイルの総面積に対応する。
従って、どのような過程で分割しても、料金は、 となる。



☆　帰納法的証明
長さ n の棒の分割料金の総和は、 必ず となることを証明する。
n=1 の場合は成立する。n以下の場合、成立するとして、n+1 の場合を考える。
n+1 の棒を最初に　n+1-iと、iに分割したとすると、総料金は、



　 これは、iの値に依存せず、 の n を、n+1としたもの。
　 よって、n+1の場合も証明された。
　

解答・その4

（ペンネ－ム：スモークマン）

n cm の時にかかる料金をf(n) とすると…
　　f(2)=1*1=1
　　f(3)=1*2+f(2)=2+1=3
　　f(4)=1*3+f(3)=3+2+1=6
　　　or =2*2+2*f(2)=4+2*1=6
そこで…
f(n)=n(n-1)/2 と考えられるのでそう仮定すると…
最初、任意 m個とn-m 個に分けた場合、以下の式で表されるが…
f(n)=m*(n-m)+f(m)+f(n-m)
=m*n-m2+m(m-1)/2+(n-m)(n-m-1)/2
=m*n-m2+(m2-m+n2-2m*n+m2-n+m)/2
=(n2-n)/2
=n(n-1)/2
から、如何様に分割しても最終的には同じ料金になることがわかる。

解答・その5

（ペンネ－ム：のっこん）

nセンチの棒を1センチ刻みで分割していくと料金は

　　　1・(n-1)+1・(n-2)+1・(n-3)+・・・・・+1・3+1・2+1・1
　　=(1/2)・n・(n-1)円となる

従ってnセンチの棒を分割する時の料金は（どのような過程を経て分割しても）
　　　(1/2)・n・(n-1)円であること・・・・・・・・(1)　
を証明すればよい

Ⅰ　n=2の時　(1)は成り立つ

Ⅱ　n=kの時　(1)が成り立つと仮定する
　　つまりkセンチの棒を分割する時の料金は
　　(1/2)・k・(k-1)円であると仮定する

Ⅲ　(k+1)センチの棒を
　　mセンチと(k+1-m)センチに分割すると（mは1以上k以下の整数）
　　この分割にかかる料金はm・(k+1-m)円、
　　mセンチの棒の分割にかかる料金はⅡより (1/2)・m・(m-1)円、
　　(k+1-m)センチの棒の分割にかかる料金はⅡより (1/2)・(k+1-m)・(k-m)円だから
　　合わせた料金は (1/2)・(k+1)・k円となる

　これはn=kの時　(1)が成り立つならば
　n=k+1の時も成り立つことを示している
　よって(1)は証明された

(1)は料金が棒の長さにのみ関係することを示している
また料金が１通りに定まることから明らかなように
料金は分割の仕方に関係しないことを示している
　　　　　　　　　　　　　　　　　　　（証明終わり）
※nセンチの時の料金が
　nC2（円）になるところが面白いと思いました

解答・その6

（ペンネ－ム：T_Tatekawa）

n=2 の時，1センチの棒2本に分割するのにかかる料金は
　　　1x1=1 円．

n=3 の時，まず2センチの棒と1センチの棒に分割し，次に2センチの棒を分割する． 合計の料金は
　　　2x1 + 1x1 = 3円．

n=4 の時，最初の分割が3センチと1センチか，2センチ2つかで場合分け．
　3センチと1センチの場合，最初にかかる料金は 3x1 = 3円．
　　この後にかかる料金は3円．合計6円．
　2センチ2つに分ける時の料金は 2x2 = 4円．
　　この後にかかる料金は 1x2=2円．合計6円．
　いずれもかかる料金は同じ．

さて，n=k の時，かかる料金が k(k-1)/2 円と仮定する．
n=k+1 の時，まずmセンチと (k-m+1)センチの棒に分割する．
この時にかかる料金は m (k-m+1) 円．
この後でかかる料金は，
m センチの棒を最後まで分割するのに m(m-1)/2 円．
(k-m+1) センチの棒を最後まで分割するのに (k-m)(k-m+1)/2 円．
以上を合計すると
　　　m (k-m+1) + m(m-1)/2 + (k-m)(k-m+1)/2 = k(k+1)/2 円

よって，n=k+1 の時でも仮定が成り立つ．

以上から，n センチの棒の分割にかかる料金は分割の方法によらず
　　　n(n-1)/2 円
である．

解答・その7

（ペンネ－ム：MVH）

〔解答〕
結論から述べます。
本問において、どのような過程を経て分割しても、かかる料金は、(n－1)n/2 円です。

このことを、自然数nに関する数学的帰納法により、示します。
ⅰ）n=1のとき、自明です。
ⅱ）n以下の全ての自然数で成立する、と仮定します。
今、(n+1)センチの棒を、aセンチとbセンチに分割するとします（n+1=a+b）。
すると、仮定により、最後に１センチの棒をn+1本作るまでにかかる料金は、

　　ab+(a－1)a/2+(b－1)b/2=a(n+1－a)+(a－1)a/2+(n+1－a－1)(n+1－a)/2=n(n+1)/2

ですから、n+1のときも成立します。
以上ⅰ）ⅱ）により、任意の自然数ｎで成立することが示されました。
従って、題意は示されました。（証終）■

解答・その8

（ペンネ－ム：転位反応）

長さｎセンチの棒を端からｋセンチで分割すると、それぞれｋセンチ、（ｎ－ｋ）センチの棒になり、 分割の料金はｋ（ｎ－ｋ）で表される。但し、ｋは、１≦ｋ≦ｎ－１を満たす整数である。
更に、ｋ（ｎ－ｋ）を長方形（または正方形）の面積として捉えると、 ｋ、ｎ－ｋを２軸とする座標系により、分割する位置と面積を以下の通り表現できる。

さて、ｎ＝５として具体的に考えてみる。
ｋ＝１，２，３，４で分割した場合に生成する長方形は、それぞれ図Ⅰ～Ⅳの通りである。
但し、これらの長方形は最初に棒が分割された時に生成するものであり、二回目以降に分割された 場合には、先行して分割された棒の長さに対応した面積が減少することになる。

例えば、最初にｋ＝１で分割して、続いてｋ＝２、３、４で順次分割すると、図Ⅴに示した通りとなる。
分割の順序に応じて、図Ⅱ～Ⅳの長方形の重なる部分の面積が減少することになり、 最終的に残った各長方形の２辺の長さが分割直後の二つの棒の長さに対応している。
同様に、最初にｋ＝３で分割し、続いてｋ＝２、１、４と順次分割した場合を図Ⅵに示した。
長方形の面積が異なるものがあるが、それらの四角形の面積の総和は図Ⅴと図Ⅵでは同じになる。

以上の考察により、長さｎセンチの棒を長さ１センチのｎ本の棒に分割するのに要する料金の合計は、 図Ⅶに示した図形として表現でき、棒の長さｎに依存している。
なお、この図形の内部の切り分け方は、棒を分割する位置と分割の順序により一意的に決まる。

よって、長さｎセンチの棒の分割に要する全料金Ｓは、下記の式で与えられる。

　　Ｓ＝１＋２＋３＋・・・＋（ｎ－１）＝（ｎ２－ｎ）／２

解答・その9

（ペンネ－ム：Ryu1128）

すぐに回答が得られるのにその回答を表現することが出来ない難問だと思います。
先ず、左側から１づつ折った場合を考えました。
その時の値段は下図赤で囲まれた面積になります。
即ち、ｎ（ｎ-1）/2です。

次に無作為に折った時を考えるとどのような順で折ったとしても下図の朱線を超えられなく且つ埋め尽くさなければ、 全てを１にすることが出来ないことがわかります。 なぜなら、１回目に折る位置を左からｐとすると右側はｎ-ｐとなり上図Lに乗ります。以下グラフ上、点（ｐ、ｎ-ｐ）より右側上側は同じ理由で埋め尽くされなければならないからです。（（ｐ、ｐ）及び（ｎ-ｐ、ｎ-ｐ）のグラフに帰結されるため。）

代数的に解こうとしたのですが迷路にはまり込んで、どうもうまく行かず上記が証明とはいえないことは自覚していますがとりあえず直感としては受け入れられるのではないかと考え投稿します。

解答・その10

（ペンネ－ム：atsuhiro）

どのような切り方に対してもかかる料金
　　P(n)=(n-1)n/2・・・＊
であることを数学的帰納法により示す

ⅰ)n=1のとき
　　P(1)=0　より　＊　成立
ⅱ）n≦k (≧1) のとき　＊　を仮定
　n=k+1のとき１回目の分割でaとbに分かれたとすると(a+b=k+1，a,b∈N)
　　　P(k+1)=ab+P(a)+P(b)
　　=ab+(a-1)a/2+(b-1)b/2 (∵仮定)
　　={(a+b)2,/sup>-(a+b)}/2
　　=(k+1)k/2
　よってn＝k+1のときも?成立
ⅰ，ⅱより任意のnに対して?成立(Q.E.D)

解答・その11

（ペンネ－ム：杖のおじさん）

Ｙ＝－Ｘ＋Ｎ　とします。

Ｙ＝残りの長さ　Ｘ＝切る長さ　Ｎ＝棒の長さ
例として長さ５cmとして

(1)
　１回目１㎝で切ると　残りY=-1+5=４㎝　手数料は１×４＝４円
　２回目２㎝で切ると　手数料は２×２＝４円
　３回目それぞれ１㎝で切ると１×１×２＝２円
　合計手数料は４＋４＋２＝１０円

(2)
　１回目２㎝で切ると２㎝と３cmになる手数料は２×３＝６円
　２回目２㎝を１㎝づつに切るので手数料は１×１＝１円
　３回目３cmを１㎝と２㎝にします。手数料は１×２＝２円
　４回目２㎝を１㎝づつにしますので１×１＝１円
　合計手数料は６＋１＋２＋１＝１０円

(3)
　１回目３cmで切ると３cmと２㎝になる手数料は３×２＝６円
　２回目３cmを１㎝と２㎝に切る手数料は１×２＝２円
　３回目は１回目と２回目で出来た２㎝を１㎝で切る。
　手数料は１×１×２＝２円
　手数料合計は６＋２＋２＝１０円

(4)
　１回目は４㎝で切ると手数料は１×４＝４円
　残った４㎝を２㎝で切ると手数料は２×２＝４円
　２㎝の棒をそれぞれ１㎝に切ると手数料は１×１×２＝２円
　手数料の合計は４＋４＋２＝１０円
　このようにどの様な位置から切っても同じ手数料になります。

上記の通り図をみて手数料はY=－X＋５のグラフとY＝０、 X=０に囲まれる中にある枡の数であることが分かります。

従って。N㎝の棒の場合の手数料は次の計算式になります。 手数料=（N×N－N)÷２となります。何処から切っても同じ手数料になる事が証明出来ました。

解答・その12

（ペンネ－ム：Part Marty）

１）ncmの棒を1cmと(n-1)cmに分割すると1X(n-1)=n-1,
(n-1)cmの棒を1cmと(n-2)cmに分割すると1X(n-2)=n-2,
最後に１センチの棒ｎ本を作るとする。
1からn-1までの足し算Σなので、nX(n-1)/2である。

2)どのような過程を経て分割しても、かかる料金は同じであることを証明せよ。
ncmの棒を(n-m)cmとm cmに分割すると(n-m)Xm円
ncmの棒を１センチの棒に分割するとmx(m-1)/2円
(n-m)cmの棒を１センチの棒に分割すると(n-m)X(n-m-1)/2円
(n-m)Xm+mX(m-1)/2+(n-m)X(n-m-1)/2=nx(n-1)/2
１）の方法で分割した値段と同じになる。
従って、どのような過程を経て分割してもかかる料金は同じである。

解答・その13

（ペンネ－ム：夜ふかしのつらいおじさん）

● nセンチの棒から1センチの棒n本を作るのに必要なお金をf(n)円とします。
具体的に、いくつか調べます。
　　f(2)＝1×1＝1
　　f(3)＝1×2＋f(2)＝2＋1＝3

<

f(4)は2通りの場合を調べます。
　　・1と3に分けるとき、
　　　f(4)＝1×3＋f(3)＝3＋3＝6
　　・2と2に分けるとき、
　　　f(4)＝2×2＋2×f(2)＝4＋2＝6
よりf(4)＝6です。

● nセンチの棒を1センチずつ分割していくとすると、
　　f(n)＝1×(n－1)＋f(n－1)より
　　f(n)＝f(n－1)＋n－1
という漸化式が考えられます。

これは、
　　f(n)＝f(n－1)＋n－1
　　f(n－1)＝f(n－2)＋n－2
　　f(n－2)＝f(n－3)＋n－3
　　　･･････
　　f(4)＝f(3)＋3
　　f(3)＝f(2)＋2
　　f(2)＝1
と並べて、合計し整理すると、
　　f(n)＝1＋2＋3＋･･････＋(n－3)＋(n－2)＋ (n－1)＝1／2×n(n－1)
となります。

● nセンチの棒を分割して1センチの棒n本を作るのに必要なお金は過程に関係なく一定であることを調べます。 　f(n)＝1／2×n(n－1)　と仮定します。
　　・n＝2のとき、
　　　f(2)＝1／2×2(2－1)＝1で上の結果と一致します。
　　・nのときの仮定を踏まえて、n＋1のときを調べます。
　　　n＋1センチの棒をkセンチとn＋1－kセンチに分けたとすると、

となり、n＋1センチをどう分けても結果は同じになります。

解答・その14

（ペンネ－ム：まーりんａｎｄさとりん）

長さがｋｃｍの棒が１ｃｍ長くなったときに、増加する料金について考える。
"ｋ の部分をどのような手順でばらばらにしても、右端の１ｃｍを含む棒を切るたびに、 切り口の左側の長さに等しい料金分が増加することになる （右端の１ｃｍを含まない棒を切るときは料金増に関係しない）。
よって、料金増分の総和は常に（ａ＋ｂ＋ｃ＋・・・＝ｋなので）ｋ円である。 "
ここで、２ｃｍの棒を切る方法は１種類（１ｃｍ×１ｃｍ）なので１円で決まっている。 つまりk＝２ｃｍのときに１円で、１ｃｍ長くなるたびに元の長さの値段分が切り方によらず一定で増加する。
したがって、ある長さｎｃｍの棒を切る料金は、切り方によらず一定になる。

* 中学１年生ということですから、まだ「数学的帰納法」を学校で勉強していないと思いますが、 その考え方が表現されていると思います。（Ｊ）

解答・その15

（ペンネ－ム：迷子の雄猫）

長さａセンチの棒をｂセンチとｃセンチに分割（ｂ＋ｃ＝ａ）するには、ｂ×ｃ円の料金がかかるという。
まず、ａ人から２人の組を選ぶことを考えよう。当然ａＣ２通りの組み合わせがある。
さて、ａ人をｂ人とｃ人のグループ２つに分割したとする。
この場合、ａ人から２人の組を選ぶ方法が、以下の3つに重複やもれがなく分割されることになる。
　あ．ｂ人のグループとｃ人のグループから１人ずつ選ぶ
　い．ｂ人のグループから２人選ぶ
　う．ｃ人のグループから２人選ぶ
上記「あ」の選び方はｂ×ｃ通りであるので、 「ｎセンチの棒からスタートして、長さが自然数であるように分割を繰り返し、 最後に１センチの棒ｎ本を作る」 までにかかる費用は、ａ人から２人の組を選ぶ選び方の数と１：１に対応する。 よって、「どのような過程を経て分割しても、かかる料金は同じである」。

解答・その16

（ペンネ－ム：三角定規）

n センチの棒を 1 センチ× n 本に分割するのにかかる料金を f (n) 円とすると，題意より

　　　f (m＋n)＝mn＋f (m)＋f (n) …(1)

(1)は n＝1 で成り立つことが必要だから
　　　f (m＋1)＝m＋f (m)＋f (1)
　　　　　　　　＝m＋f (m) 　(∵ 明らかに f (1)＝0 ) …(2)
(2)より　f (m)＝m(m－1)/2 …(3)

逆に

　　　(m＋n)(m＋n－1)/2＝mn＋m(m－1)/2＋n(n－1)/2

より，(3)は任意の m，n について(1)を満たす。
以上より所要の料金は (3) で，これは，分割の仕方に依らない。　[証明了]

解答・その17

（ペンネ－ム：浦岡）

この問題は図形的に捉えると、首尾良く解決する。
まず、直交座標を準備し、y=-x+n(0≦x≦n) …（※）をnセンチの棒に見立てる。

つぎに、（※）上の格子点を棒を分割する点と見立て、その点を1つの頂点とし座標軸とで囲まれた長方形を作る。
すると、長方形の面積が、その分割にかかる料金と対応することになる。
このとき、（※）上の格子点を1つの頂点とし座標軸とで囲まれた （または辺が座標軸と平行となる）長方形を可能な限り作ると、 最後にできる図形は、どのような過程を経ても図に示した階段状になることから、分割の過程によらずかかる料金は一定である。（証明終）

コメント

長さｎの棒を分割するのに必要な料金の総数は、例えば端から１ずつ切っていくことを考えれば求めることができます。
　　ｎ(ｎ－１)/2
です。しかし、この問題は、これを求めることにあるのではなく(従って、求めていなくてもＯＫです)、 「どのような過程を経て分割してもかかる料金が同じ」というところを示す必要があります。 多くの方が、任意の分割を想定して、それに寄らずに料金が一定であることを示してくださいました。
また、分割の料金は、長方形の面積で表すことができます。 転位反応さん他、何人かの方がこのことを 示してくださっています。転位反応さんの図をお借りして、 別な表現をすると、

例えばｎ＝５の棒を分割するのは、上の図のように、 斜辺が５√２の直角三角形の斜辺を５等分することに相当すると考えられます。 そして、例えば、ｎ＝２とｎ＝３に分割する場合は、２×３の料金がかかりますが、 これが図では、長方形の面積になるわけです。 そして、さらに、ｎ＝２とｎ＝３の分割をしますが、 それは、斜辺が２√２と３√２の直角三角形の斜辺を分割することを意味します。 従って、最終的には、どのような経路をたどっても 転位反応さんのこの図のようになるというわけです。

top