5 Recursions 朴大地.

Presentation on theme: "5 Recursions 朴大地."— Presentation transcript:

1 5 Recursions 朴大地

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22 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?

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

24 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対応 : ・ ・ ・

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

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

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

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

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

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

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

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

33 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

34 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

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

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

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

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

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

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

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

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

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

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

45 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

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

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

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

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