【灘中学校2021年度入試(2日目)算数第2問】組合せの数、だけど見慣れぬ視点

投稿するのを忘れていました！

今回は組合せの数を並べた表の問題ですが、切り口が見慣れないため、ちょっと戸惑います。ですが、実際に書いてみるとどのようになるか推測がつくので易しいです。

灘中学校・高等学校
2011年8月28日、Saoyagi2撮影、Wikipediaより

問題

下の図のようにたくさんのマス目があります。最も上の段と最も左の列のマスにはすべて 1 を書き入れます。それら以外のマスには，その 1 つ上のマスに書かれた数と 1 つ左のマスに書かれた数の和を書き入れます。図で斜線(しゃせん)をつけたマスを左上の隅(すみ)とする，縦 4 マス横 4 マスの正方形の中に，偶数は全部で 7個あります。

(1) 図で斜線をつけたマスを左上の隅とする，縦 8 マス横 8 マスの正方形の中に，偶数は全部で(　　　)個あります。

(2) 図で斜線をつけたマスを左上の隅とする，縦 16 マス横 16 マスの正方形の中にある偶数の個数を求めなさい。

(3) 図で斜線をつけたマスを左上の隅とする，縦 32 マス横 32 マスの正方形の中に，偶数は全部で(　　　)個あります。

解答解説

この表、上から i 段目、左から j 列目のマスには (i-1) + (j-1) 個の要素から (i-1)個を取り出す組合せの数が入るのですが、それを使ってもあまりいいことはありません。

ということで、高校や大学的には「帰納法」と呼ばれる方法で考えていきたいと思います。まあ要するに繰り返しです。

いちいち縦○マス、横○マスの正方形というのが面倒なので、○×○の正方形という言い方をします。

また、マス目で重要なのは数そのものではなく、偶奇(偶数であるか奇数であるか)であるので、マス目には偶奇のみを書くものとします。

下の図では O = 奇数(英語でOdd Numberのため)、E = 偶数(英語で Even Numberのため)と書くことにします。

最初に1×1の正方形の場合、ただ１つのマスには奇が入ります。これをL1の並べ方と呼びます。偶数は0個です。

2×2の正方形の場合、L1が 3つと偶数のマスが下の図のように並びます(太い四角がL1)。これをL2の並べ方と呼びます。偶数は1個です。

4×4の正方形の場合、L2が3つと偶数だけの2×2の正方形が下の図のように並びます(太い四角がL2)。これをL4の並べ方と呼びます。偶数は 1 × 3 + 2 × 2 = 7個です。

8×8の正方形の場合、L4が3つと偶数だけの4×4の正方形が下の図のように並びます(太い四角がL4)。これをL8の並べ方と呼びます。偶数は 7 × 3 + 4 × 4 = 21 + 16 = 37個です。

同じように、16×16の正方形の場合、L8が3つと偶数だけの8×8の正方形が並ぶことになります。これをL16と呼びます。偶数は 37 × 3 + 8 × 8 = 111 + 64 = 175個となります。

32×32の正方形の場合、L16が3つと偶数だけの16×16の正方形が並ぶことになります。したがって、偶数は 175 × 3 + 16 × 16 = 525 + 256 = 781個となります。

どうしてこのような並び方になるかは考えてみてください。規則的なので、ちょっと考えれば分かるかと思います。

例えば、16×16の正方形を考える場合、分かっていることは
・一番左の列は全て奇数
・一番上の段は全て奇数
・左上の8×8の正方形の中の偶奇の並び
です。特に、8×8の正方形の中でも一番右の列と一番下の段は重要で、OEEEEEEEと並びます(Fig.1)。

OEEEEEEEのOの下にOが来るとどうなるでしょう？OEEEEEEEの下の段がOOOOOOOOとなります(Fig.2)。これによって、左下の8×8の正方形の中がL8になることが分かります(Fig.3)。同じように右上の8×8の正方形の中もL8になります。

ということは、右下の8×8の正方形の左隣と上隣はOEEEEEEEと並ぶことになります(Fig3)。したがって、右下の8×8の正方形の一番左の列と一番上の段が全てEとなる(Fig.4)ので、右下の8×8の正方形の中は全てEとなることが分かります。

これが 1×1 → 2×2 → 4×4 → 8×8 → 16×16 → 32×32 → 64×64 → 128×128 → … とすべての場合で成り立つので、上のような結果になります。

感想

こういう問題は規則性をいかに素早く見つけるかです。8×8までは書けばなんとかなると思いますが、16×16では無理です。

逆に言えば、16×16は規則性がなければ解けないと思ってこの問題を見ることです。そうすれば自ずと規則性を見つけることに意識が行くと思います。

そう思って表を書いていけば、意外に早く規則性が分かるのではないかと思いますが、もし分からなければ (2) と (3) は捨てるべきです。時間的に不可能です。

この問題は出来が大きく分かれる問題だと思います。規則性を見つけられた受験生はかなり有利に受験を進められたと思います。