5 Recursions 朴大地

5. Recursions Recursion テクニック 訳： 再帰、帰納 意味： あるものを記述する際に、それ自体が記述中にあらわれること テクニック という数を数えよう の表式

Example 5.1. 球と大円 大円(great circle)とは 球の表面に大円を描いていく その面が球の中心を通るような円 重ねてはいけない それで分断される領域の数 いくつか？ 5 click

今, 個の円があるとして 個目の円 を描くと? EX5.1 球に大円を5つ描く。できる領域の数の 最大値 , 最小値 はいくつか? 最大値 , 最小値 はいくつか? 今, 個の円があるとして 個目の円 を描くと? 1. 領域の数の増加 = ( の交点の数 ) c.f. 平面グラフのオイラーの公式 2. 交点の数は? 2つの大円は必ず2つの点で交わっているはず ～ 個

最小の場合 EX5.1 球に大円を5つ描く。できる領域の数の 最大値 , 最小値 はいくつか? 交点が一致するように描く また より、 最大値 , 最小値 はいくつか? 最小の場合 交点が一致するように描く 　また 　　　　　　より、 3 click

最大の場合 EX5.1 球に大円を5つ描く。できる領域の数の 最大値 , 最小値 はいくつか? 交点をずらすように描く また より、 最大値 , 最小値 はいくつか? 最大の場合 交点をずらすように描く 　また 　　　　　　より、 4 click

Example 5.2. fat集合 fat集合とは以下の条件を満たす整数集合 例 「集合内のどの要素も集合のサイズ以上」 ○ × [ MOSP 1999, by Cecil Rousseau] fat集合とは以下の条件を満たす整数集合 「集合内のどの要素も集合のサイズ以上」 例 ○ × MOSP : Mathematical Olympiad Summer Program

例 EX5.2 整数集合 の部分集合で どの数字も2以上離れているfat集合の数 、 どの数字も3以上離れている集合の数 とする どの数字も3以上離れている集合の数 とする このとき、 を証明せよ 例

例 EX5.2 整数集合 の部分集合で どの数字も2以上離れているfat集合の数 、 どの数字も3以上離れている集合の数 とする どの数字も3以上離れている集合の数 とする このとき、 を証明せよ 例 1 click

例 EX5.2 整数集合 の部分集合で どの数字も2以上離れているfat集合の数 、 どの数字も3以上離れている集合の数 とする どの数字も3以上離れている集合の数 とする このとき、 を証明せよ 例 4 click WHY?

一般に EX5.2 整数集合 の部分集合で どの数字も2以上離れているfat集合の数 、 どの数字も3以上離れている集合の数 とする どの数字も3以上離れている集合の数 とする このとき、 を証明せよ 一般に 1対1対応

例 EX5.2 整数集合 の部分集合で どの数字も2以上離れているfat集合の数 、 どの数字も3以上離れている集合の数 とする どの数字も3以上離れている集合の数 とする このとき、 を証明せよ 例

例 EX5.2 整数集合 の部分集合で どの数字も2以上離れているfat集合の数 、 どの数字も3以上離れている集合の数 とする どの数字も3以上離れている集合の数 とする このとき、 を証明せよ 例 -1 -1 -1 3 click -1 -1 -1 7を除去して 他を1づつひく

一般に EX5.2 整数集合 の部分集合で どの数字も2以上離れているfat集合の数 、 どの数字も3以上離れている集合の数 とする どの数字も3以上離れている集合の数 とする このとき、 を証明せよ 一般に 1対1対応

結局 より である。証明終 EX5.2 整数集合 の部分集合で どの数字も2以上離れているfat集合の数 、 どの数字も3以上離れている集合の数 とする このとき、 を証明せよ 結局 　　　より　　　　　　である。証明終

Example 5.3. 0～4 0, 1, 2, 3, 4 を使って 文字の数字列をつくる 但し、隣り合う数字の差は 例 0, 1, 2, 3, 4 を使って 文字の数字列をつくる 但し、隣り合う数字の差は 例 何通りの数字列が作れるか?

Sketch of Solution1 EX5.3 0,1,2,3,4で、隣り合う数字の差が1であるような 字の数字列をつくる。何通りつくれるか? Sketch of Solution1 偶奇を考える :奇数 :偶数 の決め方　　通り を決めた時の 左に 右に　　　　　　　で　 通り 通り 1 2 3 4

Solution2 EX5.3 0,1,2,3,4で、隣り合う数字の差が1であるような 字の数字列をつくる。何通りつくれるか? : 0, 4で終わる列の数 : 1, 3で終わる列の数 : 2で終わる列の数 8 click

Solution2 EX5.3 0,1,2,3,4で、隣り合う数字の差が1であるような 字の数字列をつくる。何通りつくれるか? : 0, 4で終わる列の数 : 1, 3で終わる列の数 : 2で終わる列の数 8 click

Solution2 EX5.3 0,1,2,3,4で、隣り合う数字の差が1であるような 字の数字列をつくる。何通りつくれるか? : 0, 4で終わる列の数 : 1, 3で終わる列の数 : 2で終わる列の数 8 click

Solution2 Answer EX5.3 0,1,2,3,4で、隣り合う数字の差が1であるような 字の数字列をつくる。何通りつくれるか? : 0, 4で終わる列の数 : 1, 3で終わる列の数 : 2で終わる列の数 Answer

Example 5.4. a, b, c a, b, c を使って記号列をつくる : a, b 同じものが連続して現れない [ Romania 1998] a, b, c を使って記号列をつくる : a, b 同じものが連続して現れない ○ : a b c c a b c c c a b c a × : a c b c a a c b c a c c a : 3種類異なるものが連続して現れない ○ : c b c c a c c a c c b b a × : c c b c c b c a c c c b b を証明しよう Romanian Mathematical Olympiad?

Solution1 ‘a’ → 1, ‘b’ → 2, ‘c’ → 0 でそれぞれ置き換える 写像 EX5.4 a, b, c で記号列 をつくる、そのうち a, b 同じものが連続して現れない集合 、 異なる3つが連続して現れない集合 とする このとき、 　　 を証明せよ Solution1 ‘a’ → 1, ‘b’ → 2, ‘c’ → 0 でそれぞれ置き換える 写像 : 0 1 0 1 2 2 1 2 1 1 1 0 2 0 2 : 1 2 1 1 0 2 1 2 0 0 2 2 1 2 WHY?

Solution1 写像 この写像は1対3対応 : 1 2 1 1 0 2 ・ 0 1 0 1 2 2 1 ・ 1 2 1 2 0 0 2 EX5.4 a, b, c で記号列 をつくる、そのうち a, b 同じものが連続して現れない集合 、 異なる3つが連続して現れない集合 とする このとき、 　　 を証明せよ Solution1 写像 この写像は1対3対応 : 1 2 1 1 0 2 ・ 0 1 0 1 2 2 1 ・ 1 2 1 2 0 0 2 ・ 2 0 2 0 1 1 0

Solution2 の中で EX5.4 a, b, c で記号列 をつくる、そのうち a, b 同じものが連続して現れない集合 、 異なる3つが連続して現れない集合 とする このとき、 　　 を証明せよ Solution2 の中で　　 : aで終わる記号列 : bで終わる記号列 : cで終わる記号列 3 click

Solution2 の中で EX5.4 a, b, c で記号列 をつくる、そのうち a, b 同じものが連続して現れない集合 、 異なる3つが連続して現れない集合 とする このとき、 　　 を証明せよ Solution2 の中で　　 : aで終わる記号列 : bで終わる記号列 : cで終わる記号列

Solution2 の中で EX5.4 a, b, c で記号列 をつくる、そのうち a, b 同じものが連続して現れない集合 、 異なる3つが連続して現れない集合 とする このとき、 　　 を証明せよ Solution2 の中で　　 : aで終わる記号列 : bで終わる記号列 : cで終わる記号列

Solution2 結局 の中で EX5.4 a, b, c で記号列 をつくる、そのうち a, b 同じものが連続して現れない集合 、 異なる3つが連続して現れない集合 とする このとき、 　　 を証明せよ Solution2 の中で　　 : aで終わる記号列 : bで終わる記号列 : cで終わる記号列 結局

Solution2 の中で EX5.4 a, b, c で記号列 をつくる、そのうち a, b 同じものが連続して現れない集合 、 異なる3つが連続して現れない集合 とする このとき、 　　 を証明せよ Solution2 の中で　　 : 同じ記号で終わる列 (…aa, …bb, …cc) : それ以外の記号列 (…ab, ba, ca, ac, bc, cb)

Solution2 の中で EX5.4 a, b, c で記号列 をつくる、そのうち a, b 同じものが連続して現れない集合 、 異なる3つが連続して現れない集合 とする このとき、 　　 を証明せよ Solution2 の中で　　 : 同じ記号で終わる列 (…aa, …bb, …cc) : それ以外の記号列 (…ab, ba, ca, ac, bc, cb)

Solution2 の中で EX5.4 a, b, c で記号列 をつくる、そのうち a, b 同じものが連続して現れない集合 、 異なる3つが連続して現れない集合 とする このとき、 　　 を証明せよ Solution2 の中で　　 : 同じ記号で終わる列 (…aa, …bb, …cc) : それ以外の記号列 (…ab, ba, ca, ac, bc, cb)

Solution2 2つのRecursion スタート EX5.4 a, b, c で記号列 をつくる、そのうち 異なる3つが連続して現れない集合 とする このとき、 　　 を証明せよ Solution2 2つのRecursion スタート

Example 5.5. コイン コイン投げを何回か繰り返す。 Success Failure [ AIME 1995] コイン投げを何回か繰り返す。 5回連続で表(H)が出たら成功 : Success それまでに、2回連続で裏(T)が出たら失敗 Success T H H H H T H T H H H H H Failure H T H H H T T AIME : American Invitational Mathematics Examination

Successとなる T, H 列を分類 EX5.5 コインを繰り返し投げる。2回連続で裏(T)が T H - - - - - - (success) H T H - - - - - - (success) H H T H - - - - - - (success) H H H T H - - - - - - (success) H H H H T H - - - - - - (success) H H H H H (success) T から始まって サクセスする確率 H から始まって サクセスする確率 8 click

Example 5.6. 正四面体 正四面体（ABCD）で虫(A Bug)が乱歩 頂点 A からスタート [ AIME 1985] 正四面体（ABCD）で虫(A Bug)が乱歩 頂点 A からスタート 次の頂点をランダムに選んで進む（確率 ） A D 正四面体を 真上から見た図 B C

: 歩目に 頂点 A にいる確率 Answer EX5.6 正四面体 ABCD 上で乱歩。 ちょうど 7歩目に頂点 A にいる確率は?

5. Recursions さっきの を解こう 公比 の等比級数 とおくと より

5. Recursions 写像 constant homogeneous recursion of degree k constant inhomogeneous recursion of degree k characteristic equation(特性方程式)

Proof Theorem 5.1. 複素数 に対して が を 満たすとき、またその時に限り は を満たす が を満たす 　　　満たすとき、またその時に限り は を満たす Proof が を満たす これは が を満たすことと同値

Theorem 5.2. 2つの写像 　　　が を満たす とき、その線形結合 は を満たす Proof

Proof Theorem 5.3. もし が異なる特性根 を 持つならば、 を満たす全ての は の形で書ける 持つならば、 を満たす全ての は の形で書ける Proof が を満たすことはTheorem5.1. , Theorem5.2. より言える 逆に が を満たすとき が上の形で書ける （どんな初期値に対しても が存在する）

Proof Theorem 5.3. もし が異なる特性根 を 持つならば、 を満たす全ての は の形で書ける ファンデルモンドの行列式 持つならば、 を満たす全ての は の形で書ける Proof ファンデルモンドの行列式 一意に定まる

Theorem 5.4. もし が異なる特性根 を 持ち、それらの重複度が ならば、 を満たす全ての は次の線形結合の形で 書ける

Theorem 5.5. 写像 が を満たすならば、 を満たす 、 を満たす を用い と書ける

Example 5.7. 正八角形 正八角形 (ABCDEFGH) 頂点をカエル（A Frog） が歩く 頂点 E に来ると歩くのをやめる [ IMO 1979] 正八角形 (ABCDEFGH) 頂点をカエル（A Frog） が歩く 頂点 E に来ると歩くのをやめる : ちょうど 歩目で頂点 E に到達する 歩道 (walk) の数 A H IMO : International Mathematical Olympiad B G C F D E

Solution Outline EX5.7 正八角形上で、頂点A から始まり 歩目で 頂点E に はじめて 到達する歩道の数 は? 歩目に ちょうど A ～ H にいる歩道の数 ～ とする ( 対称性よりH = B, G = C, F = D ) A H B G C F D E

Solution Outline EX5.7 正八角形上で、頂点A から始まり 歩目で 頂点E に はじめて 到達する歩道の数 は? Theorem 5.3 より 　　　　　　　　　　　　　　　　　　　　　　と書ける 特性方程式 特性根

Solution Outline EX5.7 正八角形上で、頂点A から始まり 歩目で 頂点E に はじめて 到達する歩道の数 は? より H B G C F D E

Solution Outline EX5.7 正八角形上で、頂点A から始まり 歩目で 頂点E に はじめて 到達する歩道の数 は? A H B G C F D E