図形の問題

質問

正方形□を組み合わせて出来る階段の階数をnとするとき、出来た階段の図形をS_nとします。
例えばS_4は
　　　□
　　□□
　□□□
□□□□
と言った具合です。

この時、S_nがS_3を組み合わせて作れる為のnの必要十分条件を求めよ。

例えばS_6は
　　　　　■
　　　　■■
　　　■□□
　　■■　□
　■□　　■
■■□□■■
なのでn=6は条件を満たしているわけです。

一般の場合のnの満たすべき必要十分条件とその証明をお願いします。
（横位置がずれて上手く階段に見えない時はメモ帳などにcut&pasteして見てください。）

回答No.1

stomachman · ベストアンサー

[1] n段の階段に含まれる□の個数をM[n]とすると
M[n]= 1+2+....+n = n(n+1)/2
これが３の倍数であることが必要であるのは自明ですね。たとえばM[4]=10ですから、S_4をS_3の組み合わせで作ることは不可能。ですからn=3k+1(k=1,2,....)の場合、すなわちn=1,4,7,10,13,....の階段は作れない。

[2] さて、n=3の階段はどうか。これ無理です。では、n=5の階段は作れるのか。これも無理みたいですね。（証明は宿題。）

[3] n=6だと実際に構成できるのはご質問に示されています。S_3を７個使うんですね。
ではn=6k段(k≧2)の階段の作り方を考えましょう。
6×6の正方形を埋めるには
■■□□■■
□■□■□■
□□■■□□
■■□□■■
□■□■□■
□□■■□□
でオッケーです。だからS_6の下にこの6×6の正方形をk個入れたものを作って、S_6kの右にくっつければS_6(k+1)が作れます。つまりn=6,12,18,...が作れる。

[4]さて、S_9は構成可能です。
　　　　　　　　■
　　　　　　　■■
　　　　　　■□□
　　　　　■■□■
　　　　■○○■■
　　　■■●○□□
　　□□●●■■□
　■□●■□□■●
■■●●■■□●●
そして、6×9の長方形を埋めるには
■■□□■■
□■□■□■
□□■■□□
■■□□■■
□■□■□■
□□■■□□
■■□□■■
■□■□■□
□□■■□□
でオッケーですから、S_9の右にこれをくっつけて、上にS_6を載せればS_15が出来る。以下、6づつ増やすことができるので、
n=9,15,21,....は作れます。
以上から、nが3の倍数であるときS_nが作れないのはn=3の場合だけということになります。

[5] さらに既に出来ている3n段の階段の右に２段だけ追加することができる。これは、
　□
□□
の下に
■■
□■
□□
をn個入れてやれば作れる。この手で6段の階段を8段にすることが出来ます。

[6] 以上からn=3k, 3k+2 (k≧2)の場合には具体的に構成法が分かりました。
だから、必要十分条件は
「k≧2であって、n = 3k または n=3k+2 となる自然数kが存在すること。」
ですね。

お礼

そうですか、６×９、９×９、S_9を具体的に考えちゃえば良かったんですね。
お見事です。

S_5が作れるかどうかは３×３が作れるかどうかに帰着できるので、場合分けで
□□□
□□■
□■■
の場合と
□□□
□■□
□■■
に分けられ、無理である事が証明できますね。

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