sub sub

- 1.1 The Tower of Hanoi
 다른곳에서도 워낙 많이 나오기 때문에, 머 특별히 눈에 뛰는것은 없다. 단지 T(n)의 상한과 하한을 잡아서 T(n)을 계산하는(빅오와 오메가로 세타 구하는것처럼) 얘기가 나온다.

 - 1.2 Lines in the Plane
 두가지가 나온다. 첫째가 평면에서 n개의 직선으로 최대로 나눌수 있는 부분과, 둘째는 이를 응용한 직선을 구부려서 평면을 최대로 나누는 부분이다.
 첫째의 경우 작은것을 봤을때 L(n) = 2^n이라고 생각하기 쉬운데, 조금만 더해보면 아니라는 것을 알수 있고, 평행한 직선이 없는 경우가 최대가 될수 있다는 것을 이용하면 L(n) = L(n-1) + n 임을 알수 있다. 그리고 이의 클로즈폼을 구할때, unfolding 또는 unwinding이라는 개념을 이용해서 구하는데, 이는 'T(n)의 식의 T(n-1)을  T(n-2)..T(1)로 대체시킴으로서 구하는 방법이다. 이를 통해 T(n) = 1 + 2 + ... + n + 1 = S(n) + 1임을 알수있다.
 그리고 클로즈폼의 정의에 대해서 나오는데, 1 + 2 + ... + n 같은 경우는 되지 않고(길이가 가변이므로) n(1+ n)/2 나 n!등은 클로즈폼으로 생각한다.
 둘째는 직선을 구부리는 것은 직선 2개를 교차시켜서 교점에서 한영역으로만 직선을 그려준것과 같다. 그리고 이는 2개의 직선으로 만드는 영역에서 2개를 잃어 버린다. 구부린 직선으로 최대를 만들때 구부러진 부분이 항상 다른 직선들 밖에 있는게 최대가 되므로 결국 2n개 만큼 적다고 생각하면 된다. 따라서 Z(n) = L(2n) - 2n이 되고, close form은 2n^2 - n + 1이 된다.
 
 첫째와 둘째에서 n을 아주 크게 하면 L(n) = 1/2n^2, Z(n) = 2n^2로서, 두번째가 첫번째보다 4배나 크다는 것을 알수 있다. 즉 무한한 직선으로 평면을 나누는 것보다, 이를 구부리면 4배 정도 더 많이 평면을 나눌 수 있다.

 - 1.3 The Josephus Problem
 몇번을 봐도 아직도 했갈리는 문제인듯. 처음 설명은 쉬운편이지만, 뒤로 가면서 생략이 많이 되어 있는 느낌을 많이 받았다.ㅋ

 처음에 J(n) = n/2라고 생각하지만, 조금 해보면 아니라는 것을 알수 있다. 그리고 J(n)이 홀수 라는 것을 알수 있다(짝수는 처음에 다 죽으니까). 즉 2n과 2n+1로 나누면(원을 그려서 생각해보면)

 여기서 만족하지 않고, closed form을 구하면, p10의 테이블을 보면, 2의 승수가 중요한 역활을 한다.
n = 2^m + l  (0<= l < 2^m) => J(n) = 2l + 1
이를 induction으로 증명해보면

 이제 쉽게 풀수 있는 방법을 생각해보자. 이전에서 봤듯이 2가 중요한 역활을 한다는 것을 알수 있다. 2진법으로 표현해보면

  위의 예를 생각해보면 J(n)을 알면 n을 구할수 있다고 생각할수 있는데 안되는 경우도 있다.
(ex) J(1011)2) = 111 이다. 이경우는 복구 안된다. 최고차항 바로 다음에 0이 있는 경우)
 
 J를 반복해보면 J(k) = k이 되는 경우가 있다. 이때 최초의값의 1의개수를 r(n)이라고 하면, k = 2^r(n) - 1이 된다. 이는 뒤에 일반화할때 쓰인다.

 최초에 우리는 J(n) = n/2라고 가정했다(틀렸음). 그럼 이게 맞는 경우는 언제가 되는지 알아보자.

 일반화 하자. 어렵다..ㅡㅜ
(1.8) 처럼 다른 상수를 사용할 수 있다.

 (기존의 식은 a = 1, b = -1, r = 1) (1.12)를 보면 f(n) = A(n)a + B(n)b + C(n)r  (1.13) 으로 표현할수 있다. 이는 또 A(n) = 2^m, B(n) = 2^m - 1 - l, C(n) - l  (1.14)로 표현할 수 있다. (1.13) 과 (1.14)는 induction으로 증명하는 것은 어렵지 않지만, 계산하는 것은 힘들다(A(n),B(n),C(n) 구하는것).

 repatoire method를 이용한다. 특정 값을 선택하고, 이것들을 결합하는 것은 좋은방법이다. 이것은 점화식을 푸는데 놀랍도록 효과적인 방법이다(책에서ㅋ). 반성하자 예전에 봤을때 이해했는데 로그를 안남겨서..ㅡㅜ 이고생을 하다니.ㅋㅋ
 우선 a만을1로 하고 b = r = 0 이되도록 하면A(n)에 대한 값을 구할수 있다. 그다음 f(n) = 1, f(n) = n 등의 특수한 값을 설정하여 a, b, c를 거기에 해당하도록 맟추면 3개의 식을 얻을수 있다. 이것으로 A(n), B(n), C(n)을 구하면 된다. 그러면 f(n) 을 쉽게 구할 수 있다. ㅋ


 비트 시프트에 대한 일반화. 여기서는 증명하지 않고 그냥 계속 보여줬다.ㅋ

더 일반화 시킴 변환전의 진법과 변환후의 진법이 다들수도 있음

- Exercises
Warmups
1. step2가 잘못됬다고 생각했는데, 해답을 보니 n = 2 일때가 잘못됬다고 나와있네.ㅋ 맞는 예기인듯.ㅋ

2. n개를 옮기기 위해서는 우선 n-1개를 B로 옮기고, 1개를 가운데 막대에 옮기고, B에 있는 n-1개를 다시 A로 옮기고, 가운데 막데에 있는 1개를 B로 옮긴후, A에 있는 n-1개를 B로 옮겨야 한다. f(n) = 3f(n) + 2이다. closed form은 다 풀어서 할려고 했는데, 양변에 1을 더하면 쉽게 3^n-1임을 알수 있다. 그리고 f(n)/2번 옮겼을때, 모든 원판이 가운데 막대에 있다.(약간 생각해봐야 할듯)

3. 무슨말인지..ㅡㅜ

4. 아니다. 이동에 아무 제약이 없으므로 시작점과 끝점을 어디에 두더라도 상관없다(시작점과 끝점이 같으면 안움직여도 된다)

5. 서로다른 원은 최대 2군데에서 모이기 때문에 이전에 상태(원3개로 나눈 평면 개수)를 모두 2개로 나눌수 없다. 최대 14개로 나눌수 있다.

6. 최초 몇번을 시도하면, 직선을 하나를 추가하면, 무조건 경계가 없는 평면을 2개 더생성한다. 그러므로 최대로 평면을 나눈것에서 2n을 빼면 되므로, f(n) = L(n) - 2n 이된다. clsoed form은 1/2n^2 - 3/2n + 1 이 된다.

7. step1을 증명하지 않았다.

Homework exercises

8. 해보면, Q(0) = a, Q(1) = b, Q(2) = (1+b)/a, Q(3) = (a+b+1)/(ab), Q(4) = (1+a)/b
Q(5) = a, Q(6) = b,... 여기서 Q(0)과 Q(5) Q(1)과 Q(6)이 같다는 것을 알수 있다. 그리고 점화식은 기존의 n-1과 n-2에 의해 결정되므로, 위의 값이 반복된다.

9.
a. P(n)에서 사실이면 X(n)을 X(1)에서X(n-1)까지의 평균으로 잡으면 P(n)의 우변이
((X(1)+...X(n-1))/(n-1))^n 이 된다. 그리고 좌우 양변에 X(n)으로 나누면 증명할 수 있다.
b. 쉬운데 외 삽질했지?? 수업시간에 해서 그런가. 우선은 수식쓰기 힘드니까 n짜리 2개로 표현하고, 이를 각 P(n)을 적용한다. 그다음 ^n을 빼고 나온값을 2개의 곱으로 생각해서 P(2)를 적용하면 된다.
c. step1 P(2)가 참이므로, P(1)이 참이 된다.
    step2 2m까지 참이라고 하면(m+1 <= 2m)  b에 의해 2m+2가 참이 되고, a에 의해 2m+1이 참이된다. 따라서 2(m+1)도 참이 된다.

10. 순환된다고 보면된다. A, B, C 막대라고 가정
Q(n)은 쉽게 생각할 수 있다. 우선 n-1개를 C로 보내고(R(n-1)),1개를 B로 보내고, C에서 B로  n-1개로 보내면 된다.(R(n-1))
Q(n) = 2R(n-1) + 1   (E10.1)
R(n)은 우선B에서 A로 n-1개를 보내고(R(n-1)), B에서 C로 1개를 보내고, A에서 B로 n-1개르 보내고(Q(n-1)), C에서 A로 1개를 보내고, B에서 A로 n-1개를 보내면(R(n-1)) 된다.
R(n) = R(n-1)+1+Q(n-1) + 1 + R(n-1) = Q(n) + Q(n-1) + 1    (by E10.1)

11. A에서 C로 옮긴다.
a. 우선 제일큰거 2개를 빼놓고, B로 옮긴다음 2개를 연속해서 C로 옮기고, 나머지를 B에서 C로 옮기면 된다.
f(2n) = 2f(2n-2) + 2

b. 젤 밑에 2개를 빼고는 2번씩 움직이므로 원래 모양을 유지한다.
A에서 C로 2n-2개를 옮기고, 1개를 B로 그다음 C에서 B로 2n-2개로 옮기고 A에서 C로 1개를 옮기고, B에서 A로 2n-2개를 옮기고, B에서 C로 1개를 옮기고, A에서 C로 2n-2를 옮기면 된다.
f(2n) = 4f(2n-2) + 3

12
우선 젤 큰것들을 나두고 A에서 B로, A에서 C로 젤 큰것들을 옮기고, B에서 C로 나머지를 옮기면 된다.
A(m(1),...,m(n)) = 2A(m(1),...m(n-1)) + m(n)

만약 순서를 생각하면, 예외적은 것을 제외하고, (m(n) = 1, n =1)하고는 A(..)로 젤큰거 빼고 C옮긴후, 젤큰거를 A에서 B, C에서 A로 A(..)로 옮기고, B에서 C로 젤큰거를 옮기고, 나머지를 순서가 바뀌지 않게 옮기면 된다.

13. 우선 지그재그 하나에 직선 3개가 있다. 모든 재약이 없다면 L(3n)이 될것이다. 그러나 지그재그직선당는 3개의 직선에서 없는 부분이 있으므로 이것을 생각하면 4식 빼야 한다. 그리고 한 지그재그 직선마다 2개의 직선이 평행하므로 하나의 교차를 빼야 한다. 그러므로 ZZ(n) = L(3n) - 5n = 9/2n^2 - 7/2n + 1 이된다.
 해답의 설명은 잘 이해가 안간다. 대충 그렇게 될거라는것은 생각할수 있지만..ㅡㅜ

14. 잘이해 안간다. 해답을 보니 그럴거 같기도 한다. @,.@

15.
f(2) = 2, f(3) = 1 이 된다. 그이후부터는 J의 재귀를 그대로 쓰면 되므로
f(2n) = 2f(n) - 1, f(2n+1) = 2f(n) + 1 (n > 1)
그리고 이를 처음 몇개를 써보면
n = 2^m + 2^(m-1) + k 라고 하면 f(n) = 2k + 1 이된다. (m은 최대한 큰수)

16. lepartorie method 아직 잘은 이해 안감.ㅡㅜ

Exam problems