縦と横が〟X〝のマス目がぁり ます~ 左下隅の開始点(S)から 右上隅の

解答者は10代2名, 20代5名, 30
代6名, 40代8名, 50代20名, 60､代
13名, 70代1名, 80代1名の計56名
縦と境がnXnのマス目があります.左下隅の開始点(S)から
で,正解者は36名でした.証明方法
右上隅の終了点(G)までの最短経路i,∈Pを考えるとき,この経
路♪が対角線に出会う回数をV(p)とします.ただし,開始点と
の内訳は重複解答を含めると,カタラ
蘇了点も対角線上にあるとして回数に含めます.図では,対角線
ン数によるものが圧倒的に多くで34名,母関数によ
に5回出会っていることになります. SからG-のすべての最短
経路Pについて考えるとき,対角線に出会う絵回数をV(n)とす
るものが13名,二項定理による証明が7名,その他が
1名でした･ ｢高校生程度の知識で｣と書きましたので,
ると,
V(n)-4n
母関数による証明や高校生にとって難解な証明は不正
の関係式が成り立つことが知られています.たとえば,
解としました･私が出題時に知っていた証明は母関数
V(2)-16, V(3)-64, V(4)-256
です･このことをなるべく高校生程度の知識で証明できないも
のでしょうか.
によるものです[1].
読者の解答を拝見しながら,カタラン数は果たして
高校生の範囲内だろうかと悩みました.その中で,秦
G
晴らしい証明を見つけることができたのは幸運でした.
静岡市･鈴木丈喜さんのエレガントな解答を紹介しま
≡
S
す.
㊨-1通過方法に着日する証明
縦と横がnXnのマス目において,対角線上にはPo,
Pl,P2,･･･,Pnのn+1個の点がある.この対角線上での
《通過方法》に着日すればよい.
v(p)-5
(1) pl,P2,-,Pn_1の各点については
① 下から上に直進する
② 左から右に直進する
③ 左から上に左折する
④ 下から右に右折する
以上4通りの経路が選択可能である(図1).
(2) poとPnの各点については,端点としての制
限から2通りしか経路の選択はない.
(1), (2)からPo,Pl,=･,Pnの順に積の法則が成り立ち,
●10代
京田辺市･竹内大智
十日町市･難波弘晃
松山市･冨永昌以
所沢市･朝倉蓑之
●20代
東京都･野崎雄太
町田市･将衛門
●40代
鯖江市･山本ジョージ
●30代
秋田市･千葉隆
東京都･波田野茂男
東京都･ 9浪判官
小金井市･田中昌樹
東広島市･松原和樹
●50代
静岡市･鈴木丈書
仙台市･金沢俊郎
京都市･清洲早紀
福井市･森茂
加須市･小林国雄
名古屋市･山本長晴
東京都･升田春夫
山口市･奈良同情
さいたま市･河村直彦
観音寺市･香川小三元
東京都･宮村恵一
亀岡市･森修啓
横浜市･高橋利之
さいたま市･荻原綜夫
千曲市･山岸昭善
三重県･奥田真吾
東京都･E
三条市･加卜
横浜市･水谷一
東京都･渡遵芳行
徳島市･古川民夫
市川市･ K. Tezuka
●80代
●60代
志木市･細野源蔵
甲府市･庚午
i 2012･03懐学セミナ1 101
されます.これらの経路は対角線に関して対称になっ
ているので容易に理解できるでしょう(図2-1).
つぎに点plの通過方法は,下から上に直進,左から
三三三三三=='
三三=+li='≡
右に直進,左から上に左折,下から右に右折の4通り
があり,仝20通りの経路のうち12通りは,この方法
で4分頬されます. Plを通過しない経路が8通りあり
ますが,これらは, 4分頬のどれかに振り分けること
ができます(図2-2).ただし,これには証明が必要で
V(n+1) - V(n)×2×2-4V(n)
となります.図4はV(2)とV(3)の関係を示したも
のです.
三三三三三三
宣言≡≡≡
≡
≡≡≡≡≡
軒囲囲宙EE田
す.
図1 4通りの通過方法
法則が成り立ち,
図214 点P3-Pnへの到達経路(2分類)
V(n) -2×4×4×･･･×4×2
このようにして,対角線の各点の通過方法は互いに
- (2×2)×4×4×･･･×4
独立しているため,積の法則が成り立ち,
- 4×4n-1
以上よりV(n)-4nが示される.
[コ
私は,この証明に驚くと同時に感動しました.こん
なに簡単に証明できるのだろうかと.また積の法則が
成り立つのだろうかとも考えました.この簡潔な証明
は｢分かる生徒には分かる｣証明でしょうが,普通の
三至言≡.田≡
≡三三三三三
図2-2 点Plの通過方法(4分類)
ならず,その規則も明記しておかねばならないので,
20通りあり
4通りがあり,全20通りの経路は4分類されます(図
通過方法に従って分類すると
2-3).
力タラン数を使った証明は次の通りです.
nXnのマス目をxy座標で考え, S(0,0),G(n,n)と
する.対角線上にある点Pk(A,k)(0≦k≦n)を通る
最短経路の本数は
左から右に直進,左から上に左折,下から右に右折の
対角線上で出会うのは43-64回ありますが,これを
㊨-2 カタラン数による証明
厳密な証明が必要です,そこで,別の角度から,数学
点P2の通過方法は,点Plと同様に下から上に直進,
しておきます.
図4 n-2とn-3の関係
点Sと点Gでの2分頬は明らかですが,それ以外の
4分類は対角線の点を通過しない経路も振り分けねは
的帰納法による証明を試みてみましょう(図3).
高校生にも理解できるように,もうすこし説明を補足
n-3の場合は,最短経路は
Ⅴ(3) -2×4×4×2-43-64
となります,
V(n, - k!0(2kk)(2'nn_-kk') "
であるから, V(n) -4nであることを数学的帰納法で
2×4×4×2
となります.点Poからは左方向と上方向の2通りの
出方があり,全20通りの経路は出方によって2分類
≡ ≡≡≡三三
='三三T=≡
EEfj宙#囲囲囲
三三三三三≡
± ≡≡≡三≡
±三三≡≡≡
±三.i=±三≡
≡≡≡≡≡
図211点P.から出る経路(2分頬)
102 ‡教学セミナー1 2012ー03 I
示す.
n-1のとき, V(1)-4は明らか.
図3 数学的帰納法
(n+1)×(n+1)のマス目において,対角線上の点
をPo,Pl,P2,A.･,Pn,Pn'1とし, PoからPnまでの最短経路
V(n, - 4n - k!0(2kk)(2'nnlkk')
(2)
が成り立つと仮走する.
V(n･1, -薫(2kk)(2'nn.'11二kk')A
(3)
が対角線に出会う回数をV(n)とします. nxnのマ
ス目と(n+1)×(n+1)のマス目の関係に注目します
点Pnからの出方は右方向と上方向の2通りがあるの
で経路は2倍となります(図3左).一方, pn.1への経
図2-3 点P2の通過方法(4分頬)
( 2'nn.'ll_-kk ')
(2n+2-2k)i
(n+1-A)!(n+1-A)!
路はPnを通過しない経路もありますが, Pn.1への入
(2n12k)
最終点P,へは下からと左からの2通りの入り方が
り方は下からと左からの2通りがあるので経路は2倍
あります.全20通りの経路は2分類されます(図2-
となります(図3右). Pnに関する経路の2倍と, Pn.1
4).
に関する経路の2倍はそれぞれ独立しているので積の
! (2n+i-2k)(2n+2-2k)
(n-A)!(n-A)!
(n+1-A)(n+ilk)
- (2'nn_-kk')(2一志)･2
F 2012･03慨学セミナーE 103
k+1
となるから, (3)より
a-k
V(n+1)
Pn
- k!.(2kk)(2'nn_-kk'日2-読) ･2
A+
･(2nn.'12)(Z)
Pk
-4V(n)+
Pl
( 2nn.'12 )
ー2k!0忘(2'nn_-kk))(2kk)･ (4)
(4)において,
2真読苛(2'nn二kk')(2kk) - (2nn.'12) (*)
が証明されれば
V(n+1) -4V(n) -4n'1
となり題意成立が示される. (*)は次のように変形で
きる.
h!.2･&(2kk)(2'nnlkk') - (2nn.'12) (**,
(**)の右辺はP.からPn.1までの最短経路の総数で
ある.左辺は｢PlからPkまでほどの対角線上の点も
通らず, Pk十1で初めて対角線上の点に達し,残りPn.1
cn -孟(2nn)
は, nxnのマス目において対角線をまたがない最短
経路の総数で,カタラン数として知られている. (n+
1)×(n+1)のマス目とすれば,対角線上の点を一度も
通らない最短経路の総数となる. □
参考文献
[1]西山豊, ｢赤と黒のゲーム必勝法｣, 『理系への数
学』 2010年9月号, Vol.43,No 9, 22-25.
までの最短経路の総数｣の0≦k ≦nについての総和
である.ここに,
104 1数学セミナーl 2012_03 E
[にしやまゆたか/大阪経済大学経営情報学部]