FC2ブログ

Welcome to my blog

[答1400] 左右の★の数の積

ヤドカリ

ヤドカリ

P5200794.jpg



[答1400] 左右の★の数の積


 『n個の★の間に記されるk個の数』とは、横1列に並んだn個の★に対して、「★2個の間の1ヶ所に着目し、

 その場所より左側の★の個数と右側の★の個数の積を記す」をk回繰り返して記されたk個の数とします。

 ただし、★の個数は既に数が記されている場合はそこまでの個数とします。( 下の[具体例]参照 )

 この規則で、「58個の★の間に記される35個の数」の、和の最大値は? また、和の最小値は?

 [具体例] 「8個の★の間に記される4個の数」は、『 ★★★★★★★★ 』に対して、
  ★2個の間の数を記す場所を□とする場合、記す積の対象となる★を下線で示すと、
  最初に、★★□★★★★★★ は、左側に2個,右側に6個だから ★★12★★★★★★ 、
  次に、★★12★★★★□★★ は、左側に4個,右側に2個だから ★★12★★★★8★★ 、
  更に、★★12★★★□★8★★ は、左側に3個,右側に1個だから ★★12★★★3★8★★ 、
  最後に、★□★12★★★3★8★★ は、左右に1個ずつだから ★1★12★★★3★8★★ になります。
  記した数の和は 12+8+3+1=24 になります。
  なお、並んだ8個の★の間の4ヶ所に数を記すと、和の最大値は 25,和の最小値は 22 になります。



[解答1]

 並んだ(n+1)個の★の間のnヶ所すべてに数を記すときの和は、

 n=1 のとき 1 ,n=2 のとき 2+1=3 ,n=3 のとき 3+2+1=6 または 4+1+1=6 ,

 n=4 のとき 4+3+2+1=10 または 4+4+1+1=10 または 6+2+1+1=10 ですので、

 数を記す場所の順序に関わらず 和は n(n+1)/2 であると 推測されます。

 nより小さいすべての自然数 a,b について、

 間がaヶ所のときの和が a(a+1)/2 ,間がbヶ所のときの和が b(b+1)/2 と仮定すれば、

 間がnヶ所のときの 最初に数を記す場所の 左に間がaヶ所,右に間がbヶ所とすれば、

 ★の個数は (a+1)+(b+1)=n+1 だから、a+b+1=n で、

 和は、(a+1)(b+1)+a(a+1)/2+b(b+1)/2=(a+b+1)(a+b+2)/2=n(n+1)/2 だから、

 間がnヶ所のとき 数を記す場所の順序に関わらず 和が n(n+1)/2 であるという推測は、

 すべての自然数nについて成り立つことが数学的帰納法により示されたことになります。

 問題文の例の、並んだ★が8個で、数を記せる7ヶ所のうち 4ヶ所に数を記すとき、

 ★□★□★□★□★□★□★□★ の□全部に数を記せば、和は 7(7+1)/2=28 ですが、

 数が記されない所が3ヶ所あり、

 ★□★12★5★□★6★□★2★ のように、残り3ヶ所が連続しない場合は

 この3ヶ所に数を記すとすれば、全部 1 だから、和は 28-3=25 、

 ★7★□★□★□★12★2★1★ のように、残り3ヶ所とも連続する場合は

 この3ヶ所に数を記すとすれば、3ヶ所で 3(3+1)/2=6 だから、和は 28-6=22 、

 並んだ8個の★の間の4ヶ所に数を記すとき、和の最大値は 25,和の最小値は 22 になります。

 並んだ 58個の★の間の数を記せる 57ヶ所全部に数を記せば、和は 57(57+1)/2=1653 ですが、

 57ヶ所のうち 35ヶ所に数を記すとき、数が記されない所が 22ヶ所あり、

 残り22ヶ所が連続しない場合は この22ヶ所に数を記すとすれば、全部 1 であり、

 残り22ヶ所とも連続する場合は この22ヶ所に数を記すとすれば、和は 22(22+1)/2=253 、

 よって、和の最大値は 1653-22=1631 、和の最小値は 1653-253=1400 です。


[解答2] たけちゃんさんの解答より

 以下において,C(n)はn個のうち2個を選ぶ組合せ C(n)=n(n-1)/2 を表すものとする.

 ある2つの★について,

  ・その間に数が記されていないときは,「2つの★は同僚である」といい,

  ・その間に数が記されているときは,「2つの★は同僚でない」ということにし,

 同僚である2つの★の組の個数を「同僚数」と名付ける.

 数を記すとき,その数は同僚数の減り方そのものだから,

 n個の★の間に記されるk個の数の合計は,(初期状態での同僚数)-(最終段階での同僚数) である.

 (例) 問題で示された「★□★□★★★□★□★★」については,

 (初期状態での同僚数)=C(8)=28,

 (最終段階での同僚数)=C(3)+C(2)=4 ( C(1)+C(1)+C(3)+C(1)+C(2) と表してもよい )だから,

 記した数の和は 28-4=24 となり,これは□の順番によらない.

 例えば,左の□から順に数を記した場合は 「★7★6★★★9★2★★」となって,7+6+9+2=24.

 58個の★があるとき,(初期状態での同僚数)=58C2=1653.

 35個の数が記されるとき,★は36組に分けられる.

 その個数を a1,a2,……,a36 とすると,ak はすべて自然数であり,

 Σを k=1 から k=36 のときの和とすれば,

 (最終段階での同僚数)=ΣC(ak)=(1/2)Σ(ak2-ak)=(1/2)Σ(ak2)-(1/2)・58=(1/2)Σ(ak2)-29.

 ここで,自然数x,yが x+y=k(一定)を満たすとき,

 C(x)+C(y)=x(x-1)/2+y(y-1)/2=(x2+y2-x-y)/2={(x+y)2+(x-y)2-2(x+y)}/4

 C(x)+C(y)={k2-2k+(x-y)2}/4 だから,|x-y| が大きいほど C(x)+C(y) は大きくなる.

 したがって,(最終段階での同僚数)が最小になるとき,

 a1,a2,……,a36 のうちの2数の差が2とはなり得ず,

 a1,a2,……,a36 の最小値は1,最大値は2であり,

 「2が22個,1が14個」となって,(最終段階での同僚数)の最小値は C(2)・22+C(1)・14=22.

 また,(最終段階での同僚数)が最大になるとき,

 a1,a2,……,a36のうちには35個の1があり,残り1数は23であって,

 (最終段階での同僚数)の最大値は C(1)・35+C(23)・1=253.

 以上より,求める和の最大値は 1653-22=1631 ,求める和の最小値は 1653-253=1400.

.
スポンサーサイト



Comments 2

There are no comments yet.
ニリンソウ  

高貴な雰囲気のこの花は見る事もなく
ブログ始めてから
皆さんに見せていただく花です。

西日本では山に行かなくても見れますか。

ヤドカリ
ヤドカリ  
Re: タイトルなし

ニリンソウさん、コメントを有難うございます。
オオヤマレンゲは堺市都市緑化センターに咲いていますが、
花の文化園の普段いかない奥の方に行くと見られ、ラッキーでした。