平成２６年６月８日

[流れ星]

　　　　　第306回数学的な応募解答

　　　　　　＜解答募集期間：5月11日〜6月8日＞

［ｋ色で塗り絵］

Ｏを中心とする正ｎ角形Ａ_１Ａ_２・・・Ａ_ｎがある。ｎ個の三角形ＯＡ_ｉＡ_ｉ＋１，１≦ｉ≦ｎ（ただし、Ａ_ｎ＋１＝Ａ_１とする）をｋ色のいずれかの色で塗り、隣り合う２つの三角形は異なる色で塗り分けたい。このような塗り絵の数をＰ（ｎ，ｋ）とする。ただし、回転して重なるものも別のものとして数える。

問題１：Ｐ（３，３）、Ｐ（４，３）を求めよ。

問題２：Ｐ（３，ｋ）、Ｐ（４，ｋ）をｋで表せ。

問題３：Ｐ（ｎ−１，ｋ）とＰ（ｎ，ｋ）の間にある漸化式を求めよ。

問題４：Ｐ（ｎ，ｋ）をｎ、ｋで表せ。

NO1「uchinyan」 　　　 05/11 13時27分　受信 更新06/08

問題１：

一つの三角形を固定し，反時計回りに考えて，

P(3,3) = 3 * 2 * 1 = 6

一つの三角形を固定し，それに向かい合う三角形が同じ色か異なる色かで場合分けして，

P(4,3) = 3 * 1 * 2 * 2 + 3 * 2 * 1 * 1 = 12 + 6 = 18

問題２：

一つの三角形を固定し，反時計回りに考えて，

P(3,k) = k * (k-1) * (k-2) = k(k-1)(k-2)

一つの三角形を固定し，それに向かい合う三角形が同じ色か異なる色かで場合分けして，

P(4,k) = k * 1 * (k-1) * (k-1) + k * (k-1) * (k-2) * (k-2) = k(k-1)(k^2 - 3k + 3)

問題３：

P(n,k) は，正n角形の k 個以下での塗り分けですが，これは，

正n-2角形の三角形の一つを二つに分け間に三角形一つを挟み込む，か，

正n-1角形の二つ三角形の間に三角形一つを挟み込む，のいずれかで実現できます。

このことを使うと，

P(n,k) = P(n-2,k) * (k-1) + P(n-1,k) * (k-2)

これより，

P(n,k) - (k-1) * P(n-1,k) = - (P(n-1,k) - (k-1) * P(n-2,k)) = …

= (-1)^(n-4) * (P(4,k) - (k-1) * P(3,k))

= (-1)^(n-4) * (k(k-1)(k^2 - 3k + 3) - (k-1) * k(k-1)(k-2))

= (-1)^(n-4) * k(k-1)((k^2 - 3k + 3) - (k^2 - 3k + 2))

= (-1)^(n-4) * k(k-1)

= (-1)^n * k(k-1)

つまり，

P(n,k) - (k-1) * P(n-1,k) = (-1)^n * k(k-1)

これだけでもいいのですが，問題４：のことも考慮して，次のような関係式も導いておきます。

P(n,k) = P(n-2,k) * (k-1) + P(n-1,k) * (k-2)

は，次のようにも変形できます。

P(n,k) + P(n-1,k) = (k-1) * (P(n-1,k) + P(n-2,k)) = …

= (k-1)^(n-4) * (P(4,k) + P(3,k))

= (k-1)^(n-4) * (k(k-1)(k^2 - 3k + 3) + k(k-1)(k-2))

= (k-1)^(n-4) * k(k-1)((k^2 - 3k + 3) + (k-2))

= (k-1)^(n-4) * k(k-1)^3

= k(k-1)^(n-1)

つまり，

P(n,k) + P(n-1,k) = k(k-1)^(n-1)

結局，

P(n,k) - (k-1) * P(n-1,k) = (-1)^n * k(k-1)

又は

P(n,k) + P(n-1,k) = k(k-1)^(n-1)

です。

問題４：

問題３：の二つの式より，

1 * P(n,k) + (k-1) * P(n,k) = 1 * (-1)^n * k(k-1) + (k-1) * k(k-1)^(n-1)

k * P(n,k)= k(k-1)((k-1)^(n-1) + (-1)^n)

P(n,k)= (k-1)((k-1)^(n-1) + (-1)^n)

になります。

(感想)

これは以前に類題を解いたことがありました。しかも算数問題として！

ポイントは，問題３：の漸化式を作るところでしょうか。

直接に，P(n-1,k)，P(n,k) の漸化式を求めることもできると思いますが，

問題３：で示したように３項漸化式を求めるのが単純で分かりやすいと思います。

漸化式ができてしまえば，後は解くだけですね。

＜水の流れからお詫び：問題４と感想の掲載を忘れていました。お詫びします。

「uchinyan」 からのご指摘で修正しました。　6月8日午後7時記入＞

NO2「ｽﾓｰｸﾏﾝ」 05/11 18時44分　受信　更新06/08

問題1

P(3,3)=3!=6

P(4,3)=3*2*(1+2)=18

「ｽﾓｰｸﾏﾝ」 05/12 02時50分　受信 　更新06/08

問題2

P(3,k)=k(k-1)(k-2)

P(4,k) は、直線上に並べることを考えると…最初と最後が同じものは駄目…

同じものは2枚を1枚と見れば…P(3,k) そのものだから…

P(4,k)=k*(k-1)^3-P(3,k)=k(k-1)((k-1)^2-(k-2))

=k(k-1)(k^2-3k+3)

P(3,k)=k(k-1)^2-P(2,k)

=k(k-1)^2-k(k-1)

=k(k-1)(k-2)

問題３：Ｐ（ｎ−１，ｋ）とＰ（ｎ，ｋ）の間にある漸化式を求めよ。

問題４：Ｐ（ｎ，ｋ）をｎ、ｋで表せ。

同じ考えで…

P(n,k)=k(k-1)^(n-1)-P(n-1,k)

=k(k-1)^(n-1)-(k(k-1)^(n-2)-P(n-2,k))

=k(k-1)((k-1)^(n-2)-(k-1)^(n-3)+(k-1)^(n-4)-・・・+(-1)^n)

n=偶数と奇数で場合分けが必要のよう…

NO3「二度漬け白菜」 05/12 21時02分　受信 　更新06/08

第306回数学的な応募問題の解答をつくりました。
よろしくお願いします。

三角形 OA_iA_(i+1) を T_i と書くことにします。

問題1:
P(3,3)=6, P(4,3)=18 (答)

T_1，T_2，T_3, … の順で三角形を着色していく状況を考えます。

P(3,3)について：
T_1の着色は3通り。
T_2の着色は2通り。
T_3の着色は1通り。
よって、P(3,3)=3*2*1=6.

P(4,3)について：
T_1とT_3が同色で着色されるかどうかで場合分けします。
T_1とT_3が同色の場合は、
T_1の着色は3通り。
T_2の着色は2通り。
T_3の着色は1通り。
T_4の着色は2通り。

T_1とT_3が異なる色の場合は、
T_1の着色は3通り。
T_2の着色は2通り。
T_3の着色は1通り。
T_4の着色は1通り。
以上より、P(4,3)=3*2*1*2+3*2*1*1=18.

問題2:
P(3,k)=k*(k-1)*(k-2), P(4,k)=k*(k-1)*(k^2-3*k+3).  (答)

問題1と同様に考えました。
P(4,k)については、
P(4,k)=k*(k-1)*1*(k-1)+k*(k-1)*(k-2)*(k-2)=k*(k-1)*(k^2-3*k+3).

問題3:
P(n,k) = k*(k-1)^(n-1) - P(n-1,k)  (答)

n個の三角形 T_1，T_2，…， T_n　について、隣り合う三角形を異なる色で着色する状況を考えます。
ただし、このとき T_1 と T_n は同じ色で着色してもよいものとします。
このような方法は k*(k-1)^(n-1) 通りあります。
この k*(k-1)^(n-1)通りの着色の仕方のうち、T_1 と T_n が同色のものは P(n-1,k) 通りあります。
したがって、漸化式
P(n,k) = k*(k-1)^(n-1) - P(n-1,k)
が成り立ちます。

問題4:
P(n,k)=(k-1)*((k-1)^(n-1)+(-1)^n)  (答)

問題3で得た漸化式を変形すると、
P(n,k)-(k-1)^n = (-1)*(P(n-1,k)-(k-1)^(n-1)).
この式から、
P(n,k)-(k-1)^n = ((-1)^(n-3))*(P(3,k)-(k-1)^3).
よって、
P(n,k)=(-1)^(n-3)*(P(3,k)-(k-1)^3)+(k-1)^n
=(k-1)*((k-1)^(n-1)+(-1)^n).

以前、「大学への数学」という雑誌に本問と同じような問題が
掲載されていたのを思い出しました。
押入れを探して、ようやくその雑誌を見つけました。
1996年の11月号でした。
それによれば、難易度がかなり高い問題であるとのことです。

NO4「早起きのおじさん」 05/18 15時53分　受信　更新06/08

今回は、はじめｋ色は全部使うのか一部でもよいのかを少し考えました。

全色使うとすると、

　・P(3,k)でｋは3しかない

　・P(n,k）でｎ>=kの制約がある

　・・・・

などのため、一部でもよいとして考えました。

結果が面白かったことと全色使うとするのは難しいのでそのあとは今は考えていません。

問題０

　三角形はできませんが、あとの便宜のためP(2,3)＝₃P₂＝3･2＝6と考えます。

　　　

問題１

n＝3の場合�@、�A、�Bのどの場所も他と異なる色で塗るので3色必要です。

k＝3なので、3色の3つの場所の順列を考えて、P(3,3)＝₃P₃＝3･2･1＝6です。

n＝4（偶数）の場合隣り合う2つの三角形が異なる色であればよいので2色でも塗れます。

右の表のように、�@の場所を色aで塗ったとすると、６通りの場合があります。

　場所�@は色bでも色cでもよいので、P(4,3)＝3×6＝18です。

　　　

　さて、もう少しP(3,3) やP(4,3)の関係について調べます。

　P(4,3) を考えるとき、

（ア）P(3,3)を元にして、1つ三角形を割り込ませた場合があります。

　　このとき、�Bは�@と必ず色違いです。

※ �@と�Bが同じ色の場合が欠けています。

（イ）P(2,3)を元にして、2つ三角形を割り込ませた場合があります。

　　このとき、�Bの三角形は�@と同じ色にし、(ア)を補います。

　この二通りでみてみます。

　　

　　

（ア）�Cの色は、�@と�Bと異なります。

(イ) �Cの色は、�Bが�@と同じ色なので�@以外になります。

これで、最初の表の場合が全部揃いました。

問題２　問題１と同様に考えて、

　P(3,k)＝_kP₃＝k(k−1)(k−2)＝k³−3k²＋2k （＝(k−1)³−(k−1) ）

　P(4,k)＝P(3,k)×(k−2)＋P(2,k)×(k−1)＝_kP₃×(k−2)＋_kP₂×(k−1)

＝k(k−1)(k−2)×(k−2)＋k(k−1)×(k−1)＝k(k−1){(k−2)²＋(k−1)}

＝k(k−1)(k²−3k＋3)　（＝(k−1)⁴＋(k−1) ）

※ 便宜的に、P(2,k)＝_kP₂＝k･(k−1)と考えます。

問題３

　今までの考えから、

P(n,k)=P(n−1,k)×(k−2)＋P(n−2,k)×(k−1)

問題４

　上の漸化式から、特性方程式t²−(k−2)t−(k−1)＝0の解t＝−1, k−1を用いると上の漸化式は、

　

　の2つの形で表現できます。

(1) について

　　は、初項、公比(k−1)の等比数列なので、

　 ･････(3)

(2) について

　　は、初項、公比(−1)の等比数列なので、

　 ･････(4)

　(3)、(4)を連立させてP(n,k)について解きます。

(3)に(k−1)をかけて(4)と加えると、

　　

　P(3,k)＝k(k−1)(k−2)、P(2,k)＝k･(k−1)を代入して整理すると、

　　

「早起きのおじさん」 05/22 12時34分　受信 　更新06/08

問題３、問題４

●漸化式ができているところから考えます。

●具体的にP(n,k)を計算してみます。

・展開した形で整理すると、

　　　　　　　　

　　　　

　　　　

　　　

　　　　

　　　

展開して整理すると、 と との加減で表されることが分かります。（パスカルの三角形と比較すると分かりやすいと思います）

よって、　

このことは数学的帰納法で証明することができます。

パスカルの三角形

以下蛇足です。

●さて、P(n,k)の因数k(k−1)以外の因数に注目してみます。（上の赤の部分）

・どの項もとの整式になっています。

　漸化式の計算のときによく注意して観察すると、

nのときの展開の第m項は、です。

・係数は下の表の様になっています。

黄色の部分は1です。

三角形の位置の二数の和が六角形の位置の数という仕組みになっています。

（ある数は、そのすぐ上と左上の桂馬の位置の2数の和）

　　

　上の仕組みをよく考えて整理すると、

　第1項は、常に1

　第2項は、n−3

　第3項は、n−5番目の三角数

　　第4項は、n−7番目までの三角数の和

　　・・・

　　第m項は、n−(2m−1)までの一連の和

　　（ただし、m≧3）

　というふうになっています。

まとめると、P(n,k)の式の第m項は、

となっています。

NO5「にいばりZ12」 05/30 01時49分　受信

問題では、Ｏを中心とする正ｎ角形しているので正３角形から始まりますが

少し一般化して、「Ｏを中心とする円を円周上の任意の点A1,A2,A3・・・AnとOと結ぶ線分で分割する時」

と考えるとn=1の時から考えることができます。

このように考えると、（Aが任意の点（合同な扇がない）であることから）回転して重なるものは無いので

ただし書きの条件が必要なくなります。問題の本質は変わらないのでこの形で考えてみます。

天下りになりますが最後のほうから考えてみました。

(準備1)

ｎ=1の時はｋ色（塗る場所が一つしかないので）

ｎ=2の時は円は２分割されるので

先ず1方1色を塗るともう1方は最初に塗った色は使えないのでｋ-1種の色から選んで塗ることになり

その場合の数は１色目のｋ通と２色目のk-1通りの積でk(k-1)となります。

ｎ=3の時は円は３分割されるので

先ず1か所に1色を塗り反時計回り（時計回りでもいいのですが便宜上）に次の領域に塗ります。

最初に塗った色は使えないのでｋ-1種の色から選んで塗ることになり

さらに次（３つ目）の領域には２つ目の領域に塗った色以外をｋ色から選んで塗ります

つまり、３つ目の色の選択肢もまたｋ-1色です。（ここで、一回りしているので最初の色は使えないのですがここでは一時棚上げします）

同様にして一般のｎの時、第ｎ番目の領域が取る色の選択肢はｋ-1です（同様にここで、一回りしているので最初の色は使えないのですがここでは一時棚上げします）

したがって色の塗り方の場合の数は次のように表せます

ｋ（ｋ-1）＾0

ｋ（ｋ-1）＾1

ｋ（ｋ-1）＾2

・

・

・

ｋ(ｋ-1)^(n-1)

(準備2)

ｋ色に色の名前を付けます

色の名前は、1,2,3,4,・・,i,・・,kとします

最初に選ぶ領域に塗る色をiとします。

準備１で棚上げにした最初の色のことを考えます。

第ｎ番目の領域に塗る色がiである場合の数は除かなければなりません

そのためには、第ｎ-1番目の色がiであるかi以外であるかを調べなければなりません

そう考えると、最初に塗ったiという色が第２番目、第３番目・・・第n-１番目でどの様な場合の数を取るか順次調べる必要がある事が解ります。

そこで、次に各領域迄でiの取る場合の数を示します

第一領域・・・1　・・・・・・・・第一領域はとりあえずiの1種類

第二領域・・・0=(k-1)^0-1　　　・・・・・・・・第一領域のiと同じ色は塗れない(第一領域のi以外の色のとる場合の数)

第三領域・・・(ｋ-1)^1-(k-1)^0+1  　・・・・・・・・第二領域にはiがないので第二領域の場合の数に一致(第二領域のi以外の色のとる場合の数)

第四領域・・・(ｋ-1)^2-(k-1)^1+(k-1)^0-1  ・・・・・・・・第三領域のi以外の色のとる場合の数に一致

第五領域・・・(ｋ-1)^3-(k-1)^2+(k-1)^1-(k-1)^0+1 ・・・・・・・・第四領域のi以外の色のとる場合の数に一致

第六領域・・・(ｋ-1)^4-(k-1)^3+(k-1)^2-(k-1)^1+(k-1)^0-1　　・・・・・・・・第五領域のi以外の色のとる場合の数に一致

第n領域・・・(ｋ-1)^(n-2)-(k-1)^(n-3)+(k-1)^(n-4)-(k-1)^(n-5)+・・・・　　・・・・・・・・第(n-1)領域のi以外の色のとる場合の数に一致

問題4

準備1から

最初の色を考えなければ、領域ｎ番目迄の色の塗り方の場合の数は

ｋ(ｋ-1)^(n-1)

ですが準備2から第一領域の色が除かれ、第一領域ｉの塗り方はｋ種あることから

P(n,k)=k((k-1)^(n-1)-(k-1)^(n-2)+(k-1)^(n-3)-(k-1)^(n-4)+(k-1)^(n-5)+・・・・-((k-1)^0)(-1)^(n-1)+(-1)^(n-1))

下線部を計算します(n項目とn+1項目の和はつねに0なので)

　ｎが偶数の場合(項の順序を逆にして)

　　　　 (k-1)^1-(k-1)^2+(k-1)^3+・・・・+(k-1)^(n-3)-(ｋ-1)^(n-2)+(k-1)^(n-1)

　　　これは初項k-1公比1-k項数n-1の等比数列の和なので

　　　　　(k-1)(1-(1-k)^(n-1))/(1-(1-k))=(k-1)((k-1)^(n-1)+1)/k

　ｎが奇数の場合同様にして

　　　　 -(k-1)^1+(k-1)^2-(k-1)^3+・・・・+(k-1)^(n-3)-(ｋ-1)^(n-2)+(k-1)^(n-1)

　　　これは初項1-k公比1-k項数n-1の等比数列の和なので

　　　　　(1-k)(1-(1-k)^(n-1))/(1-(1-k))=(k-1)((k-1)^(n-1)-1)/k

　よって偶奇をまとめ、kをかけると

P(n,k)= (k-1)((k-1)^(n-1)+(-1)^n)＝(k-1)ⁿ+(k-1)・(-1)ⁿ・・・・・・回答

問題3

準備1から

最初の色を考えなければ、領域がｎの時の塗り方の場合の数は

ｋ(ｋ-1)^(n-1)

準備2から

最初の色が上記に存在する場合の数はn-1の場合の数である事が解ります

よって漸化式は

P(n,k)= ｋ(ｋ-1)^(n-1)-P(n-1,k) ・・・・・・回答

問題1,2

P(n,k)＝(k-1)ⁿ+(k-1)・(-1)ⁿ

から

P(3,3)＝(3-1)³+(3-1)・(-1)³

　　　＝6                       ・・・・・・回答

P(4,3)＝(3-1)^４+(3-1)・(-1)^４

　　　＝16                     ・・・・・・回答

同様に

P(3,k)＝(k-1)³+(k-1)・(-1)³＝k(k-1)(k-2)                         ・・・・・・回答

P(4,k)＝(k-1)⁴+(k-1)・(-1)⁴＝(k-1)⁴+(k-1)=k(k-1)(k²-3k+3)      ・・・・・・回答

ＮＯ６「ＳＰＣ」 06/07 17時08分 受信 更新 06/8

SPCです。
　パソコンのゲーム作成プログラムＨＳＰで解きました。
　ｋ色を数０、１、２、・・・、ｋ−１で表します。
　　Ｐ（３、３）、Ｐ（４、３）、Ｐ（５、３）、・・・、Ｐ（１０、３）、
　　Ｐ（３、４）、Ｐ（４、４）、Ｐ（５、４）、・・・、Ｐ（８、４）、
　　Ｐ（３、５）、Ｐ（４、５）、Ｐ（５、５）、Ｐ（６、５）、
　　・・・
を計算して、データを集めます。

p = 0
repeat 3 : c1 = cnt
   repeat 3 : c2 = cnt
     repeat 3 : c3 = cnt
       if (c1 != c2) & (c2 != c3) & (c3 != c1) : p+
     loop
   loop
loop
mes "P(3,3)=" + p
p = 0
repeat 3 : c1 = cnt
   repeat 3 : c2 = cnt
     repeat 3 : c3 = cnt
       repeat 3 : c4 = cnt
         if (c1 != c2) & (c2 != c3) & (c3 != c4) & (c4 != c1) : p+
       loop
     loop
   loop
loop
mes "P(4,3)=" + p

　これで、P(3,3)=6、P(4,3)=18と求められました。

　同じように計算して、
　　P(3,3)=6=8-2=2^3+(-1)^3･2
　　P(4,3)=18=16+2=2^4+(-1)^4･2
　　P(5,3)=30=32-2=2^5+(-1)^5･2
　　P(6,3)=66=64+2=2^6+(-1)^6･2
　　P(7,3)=126=128-2=2^7+(-1)^7･2
　　P(8,3)=258=256+2=2^8+(-1)^8･2
　　P(9,3)=510=512-2=2^9+(-1)^9･2
　　P(10,3)=1026=1024+2=2^10+(-1)^10･2
となるので、
　　P(n,3)=2^n+(-1)^n･2
です。
　同じように計算して、
　　P(3,4)=24=27-3=3^3+(-1)^3･3
　　P(4,4)=84=81+3=3^4+(-1)^4･3
　　P(5,4)=240=243-3=3^5+(-1)^5･3
　　P(6,4)=732=729+3=3^6+(-1)^6･3
　　P(7,4)=2184=2187-3=3^7+(-1)^7･3
　　P(8,4)=6564=6561+3=3^8+(-1)^8･3
となるので、
　　P(n,4)=3^n+(-1)^n･3
です。
　同じように計算して、
　　P(3,5)=60=4^3+(-1)^3･4
　　P(4,5)=260=4^4+(-1)^4･4
　　P(5,5)=1020=4^5+(-1)^5･4
　　P(6,5)=4100=4^6+(-1)^6･4
となるので、
　　P(n,5)=4^n+(-1)^n･4
です。
　つまり、
　　P(n,k)=(k-1)^n+(-1)^n･(k-1)
です。

皆さん、問題や質問に答えてください。一部でも構いませんから、解答とペンネームを添えて、メールで送ってください。待っています。