コロキウム室(釣り銭の問題・大縄跳び)

NO.121　　　　 6/19 　　水の流れ　　　 つり銭の問題（１）

生徒が教材費に五百円払う必要があります。 そこに、五百円玉を 持ったｎ人の生徒と、 千円札しか持っていないｎ人の合計２ｎ人の クラス生徒がいます。 担任の私はつり銭を準備していませんでした。 つり銭が不足しないように生徒からもらう方法は 全部で何通りありますか。 ただし、生徒の２ｎ人に区別しないで、 お金の出し方で考えてください。

NO.124　　　　 6/21 　　Junko　　　 つり銭の問題（２）

千円札を受け取る前に、 おつりになる五百円玉を持っていればいいのですね。
具体的に数え上げてみることにします。
５００円玉をＡ、千円札をＢと表記することにします。

1. ｎ＝１のとき
   1. ＡＢ　　の１通り
2. ｎ＝２のとき
   1. ＡＡＢＢ
   2. ＡＢＡＢ　の２通り
3. ｎ＝３のとき
   1. ＡＡＡＢＢＢ
   2. ＡＡＢＢＡＢ
   3. ＡＡＢＡＢＢ
   4. ＡＢＡＡＢＢ
   5. ＡＢＡＢＡＢ　の５通り
4. ｎ＝４のとき
   1. ＡＡＡＡＢＢＢＢ
   2. ＡＡＡＢＢＢＡＢ
   3. ＡＡＡＢＢＡＢＢ
   4. ＡＡＡＢＡＢＢＢ
   5. ＡＡＢＢＡＡＢＢ
   6. ＡＡＢＢＡＢＡＢ
   7. ＡＡＢＡＢＢＡＢ
   8. ＡＡＢＡＢＡＢＢ
   9. ＡＡＢＡＡＢＢＢ
   10. ＡＢＡＡＡＢＢＢ
   11. ＡＢＡＡＢＢＡＢ
   12. ＡＢＡＡＢＡＢＢ
   13. ＡＢＡＢＡＡＢＢ
   14. ＡＢＡＢＡＢＡＢ　の１４通り

NO.127　　　　 7/4 　　水の流れ　　　 つり銭の問題（３）

問題の中で、500円玉を払うのをＡ，1000円玉を払うのをＢとします。 釣り銭がないので、常にａの数がｂの数より等しいか大きければよいのです。 これをａを→、ｂを↑と表せば、→がｎ個、 ↑ がｎ個を一列に並べる方法を考えます。

ここで、碁盤の目をした最短経路の問題に変化していきます。 分かり易くするために、求める数をＫ(n)とすると、 Ｋ(１)＝１，Ｋ(２)＝２，Ｋ(３)＝５は図を書いて、分かるとします。
ｎ＝４のときを描きます。 図のような△ＡＢＣの最短経路の道筋がＫ(４)になります。

＜考え方からの副産物＞

Ｋ(４)を求めるのに、

1. Ｂ１を通るとき、Ａから Ｂ１を通り、△Ｂ１ＤＢの最短経路Ｋ(３)の道筋
2. Ｂ１を通らず、Ｂ2を通るとき、 △GHLの最短経路Ｋ(１)から、道路ＬＢ２を通り、 △Ｂ２ＥＢの最短経路Ｋ(２)の道筋
3. Ｂ１、Ｂ２を通らず、Ｂ３を通るとき、 △ＧＩＭの最短経路Ｋ(２)から、道路ＭＢ３を通り、 △Ｂ３ＦＢの最短経路Ｋ(１)の道筋
4. 最後に、Ｂ１，Ｂ２、Ｂ３を通らず、 Ｂに行く場合は△ＧＣＦの最短経路Ｋ(３)に等しい。

よって、Ｋ(４)＝ Ｋ(３)＋Ｋ(１)Ｋ(２)＋Ｋ(２)Ｋ(１)＋ Ｋ(３)
              ＝５＋１×２＋２×１＋５＝１４　になります。

また、こんな数え方（書き込み方式）もできます。

 
　　　            14Ｂ　
                  ↑             
              ５→14Ｆ          
              ↑  ↑
          ２→５→９Ｅ          
　　　　  ↑　↑  ↑
　　　１→２→３→４Ｄ          
      ↑  ↑  ↑  ↑
  Ａ→１→１→１→１Ｃ

さらに、斜めの線に関しての対称性に気がつけば、
Ｋ(４)＝ １×１＋３×３＋２×２＝１４
Ｋ(５)＝ １×１＋４×４＋５×５＝４２
Ｋ(６)＝ １×１＋５×５＋９×９＋５×５＝１３２
したがって、カタラン数Ｋ(ｎ)は何個かの平方数の和でできています。

さて、本題に入ります。ｎ＝４で描きます。

□ＤＡＣＢの最短経路の道筋は、階乗の記号を使えば、
（４＋４）！÷（４！×４！）＝７０　通り あります。
ここから、対角線ＡＢと交わる経路が不適ですから、 この不適な経路を求めます。
例えば、図の太線の経路は不適ですが、 これを直線Ｔ１Ｔ４について対称移動します。
ただし、直線Ｔ１Ｔ４に始めて出会った点から 後の部分のみを対称に曲げて図の太い波線を考えると、 全ての不適な経路は□ＡＥＦＧの最短経路の数に等しくなります。
これは、 （５＋３）！÷（５！×３！）＝５６　通りとなり、 求めるカタラン数Ｋ(４)は、
Ｋ(４) ＝_８Ｃ_４−_８Ｃ_３ ＝７０−５６＝１４　になります。
一般に、
Ｋ(ｎ) ＝_２ｎＣ_ｎ −_２ｎＣ_ｎ−１ ＝_２ｎＣ_ｎ÷（ｎ＋１） となります。

そこで、また、問題です。 次の台形ＡＢＣＤの最短経路は何通りありますか。

　

第３６回数学的な応募問題

太郎さんの勤務している学校で、体育大会で「大縄跳び」競技があり、 こんな問題を考えました。

１直線上に２ｎ人の生徒が並んでいます。 大縄をｎ本渡して、２人で１組とし、 大縄が交差せずに競技ができるようにします。 このとき、生徒は区別しないで、ｎ本の大縄 の軌跡について、次の問に答えてください。

問題１：
ｎ＝１，ｎ＝２，ｎ＝３，ｎ＝４，のときの軌跡の数は何通りですか。

問題２：
一般の場合の軌跡の数を、ｎで表してください。

太郎さんは、過去に、このような数列を扱ったことを覚えています。

問題１：
ｎに対する軌跡の数をF(n)とすると、
n=1　　F(1)=1
n=2　　F(2)=2
n=3　　F(3)=5
n=4　　F(4)=14
これらは、図を描いて数えました。

問題２：

まず n=5の場合について考えてみました。(右図参照)
左から1,2,･･･,10と背番号をつけます。

• 1と10が縄をもつ場合
  その縄の中の人たちの縄の持ち方は、F(4)=14通りです。
  その縄の外には人がいません。
  
  
• 1と8が縄をもつ場合
  その縄の中の人たちの縄の持ち方は、F(3)=5通りです。
  その縄の外の人たちの縄の持ち方は、F(1)=1通りです。
  従って、F(3)×F(1)=5×1=5
  
  
• 1と6が縄をもつ場合
  その縄の中の人たちの縄の持ち方は、F(2)=2通りです。
  その縄の外の人たちの縄の持ち方は、F(2)=2通りです。
  従って、F(2)×F(2)=2×2=4
  
  
• 1と4が縄をもつ場合
  その縄の中の人たちの縄の持ち方は、F(1)=1通りです。
  その縄の外の人たちの縄の持ち方は、F(3)=5通りです。
  従って、F(1)×F(3)=1×5=5
  
  
• 1と2が縄をもつ場合
  その縄の中には人がいません。
  その縄の外の人たちの縄の持ち方は、F(4)=14通りです。
  
  

一般的にもこれと同じことが言えるはずですから、

F(n)=F(n-1)×F(0)+F(n-2)×F(1)+F(n-3)×F(2)+･･･+F(0)×F(n-1)

この問題は、ベーシック言語のFOR〜NEXT文の構造と同じですね。
水の流れさんの 「カタラン数のレポート」として、 歴史的経過を含めて詳細が報告されています。
Junko先生の一般式の他に色々表現があるようですがシンプル なのは以下のものではないでしょうか。

Combination　と言えば、パスカルの三角形です。
_2nC_n　は、左図のように パスカルの三角形において１段おきに中央に現れます。
これを順に (n+1) で割れば、カタラン数となるわけですね。
{1,2,5,14,42,132,429,1430,･･･}

縄の左側を持つ人をＬ、右側を持つ人をＲとします。
ｎ個のＬとｎ個のＲを１列に並べることを考えます。
ただし縄が交差してはまずいわけですから、左から数えていった時に常にＬの数がＲの数より等しいか 大きくなくてはなりません。
そう考えると、NO.121　つり銭の問題（１） と同じだということがわかります。

更に、NO.127　つり銭の問題（３）で、 「水の流れ」さんがおっしゃっているように、Ｌを「→」、Ｒを「↑」で表せば、 まさにこれを１列に並べることと同じです。
もちろん、左から数えて常に「→」の数が「↑」の数より等しいか 大きくなくてはなりません。
それは左図(n=5)で、ＡからＢへ黒い道だけを通って行く行き方を数えればよいということになります。

カタラン数はパスカル三角形の中で、
F(n)=_2nC_n-_2nC_n-1という観点から、
偶数段の中央値を ｎ＋１で割らなくても、中央値をから隣の数字を引くと生まれてきます。