Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

덴치 문제..푼 결과

2005.10.11 10:56

박기현 조회 수:4542 추천:337

좀 야매로 때려맞췄습니다;;
머리가 복잡해져서 중간에 실수한게 있을수도 있구.. 또 아이디어 자체가 틀린것일수도 있지만..

올려 봅니다.



Define: Discrete Function Eo[n,k]

=> n명에서 k명을 방법 1로 뽑을 경우의 평균 시행 횟수

Define: Discrete Function En[n,k]

=> n명에서 k명을 방법 2로 뽑을 경우의 평균 시행 횟수


Eo[n,k] =
먼저 각각의 경우의 확률을 보면

     ┳ 0명 뽑힐 확률 2*1/2^n
     ┣ 1명 뽑힐 확률 2*C(n,1)/2^n
     ┣ 2명 뽑힐 확률 2*C(n,2)/2^n
     :
     ┣ k명 뽑힐 확률 2*C(n,k)/2^n
     :
     ┗ [n/2] 명 뽑힐 확률 [x]는 x보다 작은 최대 정수

C(n,k) = (k) = n!   을 의미함
     (n) ━━━━
       k!(n-k)!

이는 Geomatric이므로 각각의 역수가 평균이 된다. 즉

Eo[n,k] = 2^n/2*C(n,k) = 2^(n-1) / C(n,k)       {Eo함수}

한편 En[n,k]는 1~k까지 뽑히면 뽑는 상황의 상태가 변한다. 다시 보면


En[n,k]  ┳ 0명 뽑힘 ━ 상태유지
     ┣ 1명 뽑힘 ━ En[n-1,k-1]
     ┣ 2명 뽑힘 ━ En[n-2,k-2]
     :
     ┣ k명 뽑힘 ━ En[n-k,0]
     :
     ┗ 상태유지

가 된다. 즉 상태가 변화할 확률은 1명 뽑힐 확률 + 2명 ... k명 뽑힐 확률로 다음과 같다.

k         △
∑ C(n,i)/ 2^(n-1) = Sump(n,k)     (- Sum of Probabilities)
i=1

이 상태가 되었을 때 앞으로의 평균 시행 횟수를 Ea[n,t]라고 하면 En[n,k] 는 다음과 같이 쓸 수 있다.

En[n,k] = 1/Sump(n,k) + Ea[n,t] - 1       {1}

이것은 Geomatric에서 일정 수 Ea를 더한 만큼 가게 되며 Ea값이 n, k에 의해서만
바뀌기 때문게 가능한 가정이다.

12줄 위의 그림에서 Ea를 구해 보면, 평균은 각각의 확률 * 각각의 시행 평균 / 전체 확률 이 되므로

     k
     ∑ (En[n-i,k-i] + 1) * C(n,i)/ 2^(n-1)
     i=1
Ea[n,k] = ━━━━━━━━━━━━━━━━━━━━      {2}
         Sump(n,k)

가 된다. +1항은 k 이하의 사람이 뽑혀 En으로 내려갈 때 뽑힐 때 셋 횟수를 더한 값이다.
위 식에서 2^(n-1) 항은 소거되고, 새 함수를 정의하여

k     △
∑ C(n,i) = Sumc(n,k)
i=1

로 한 후, Ea를 {1}식에 대입하여 정리하면

     ┏ k               ┓
     ┃ ∑ (En[n-i,k-i] + 1) * C(n,i) ┃ + 2^(n-1) - Sumc(n,k)
     ┗ i=1              ┛
En[n,k] = ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
         Sumc(n,k)


     ┏ k            ┓
     ┃ ∑ En[n-i,k-i] * C(n,i) ┃ + 2^(n-1)
     ┗ i=1           ┛
    = ━━━━━━━━━━━━━━━━━━━━      {En함수}
         Sumc(n,k)

가 된다.

En의 initial condition 을 살펴보면, 정리 전 식에서 i = k일 때 평균(En[n-i,k-i] + 1)이 1이 되므로

En[n,0] = 0     (n=자연수)

이 된다.

------------------------------------------------------------------------------------------------

Problem 1-1:

답 : Eo[10,3] = 512/120

Problem 1-2:

답 : En[10,3] ≒ 7.54794 (풀이는 맨 아래에)

Problem 1-3:

En'[10,4] ┳ 0명 뽑힘 ━ 상태유지
     ┣ 1명 뽑힘 ━ En[9,2]
     ┣ 2명 뽑힘 ━ En[8,1]
     ┣ 3명 뽑힘 ━ En[7,0]
     ┣ 4명 뽑힘 ━ En[4,1]
     :
     ┗ 상태유지

상태변화는 1~4명 뽑혔을 때까지에서 일어나며 변화 확률은 Sump(10,4)가 된다. 위와 같은 방법으로
Ea'를 구하면

      ┏ 3                    ┓
      ┃ ∑ (En[10-i,3-i] + 1) * C(10,i)/ 2^(9) ┃ + (En[4,1] + 1) * C(10,4)/ 2^(9)
      ┗ i=1                   ┛
Ea'[10,4] = ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
         Sump(10,4)

      ┏ 3                ┓
      ┃ ∑ (En[10-i,3-i] + 1) * C(10,i) ┃ + (En[4,1] + 1) * C(10,4)
      ┗ i=1               ┛
     = ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
         Sumc(10,4)

가 되며 이를 {1}식에 ' notation사용하여 대입하면

      ┏ 3                ┓
      ┃ ∑ (En[10-i,3-i] + 1) * C(10,i) ┃ + (En[4,1] + 1)*C(10,4) + 2^9 - Sumc(10,4)
      ┗ i=1               ┛
En'[10,4] = ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
         Sumc(10,4)

      ┏ 3             ┓
      ┃ ∑ En[10-i,3-i] * C(10,i) ┃ + En[4,1]*C(10,4) + 2^9
      ┗ i=1            ┛
     = ━━━━━━━━━━━━━━━━━━━━━━━━━━━━
         Sumc(10,4)

가 된다.

답 : En'[10,4] ≒ 4.52179

Problem 2-1:

답: En[n,3] = 얼마 안되므로 재귀로 표현할 수 있다.

Problem 2-2:

답: En[n,k] = 지금 방법으로는 표현 불가, n,k를 알면 알고리즘으로 사용 가능


--------------------------------------------------------------------------------------------------

Algorithm for Calculating En[n,k]

     ┏ k            ┓
     ┃ ∑ En[n-i,k-i] * C(n,i) ┃ + 2^(n-1)
     ┗ i=1           ┛
En[n,k] = ━━━━━━━━━━━━━━━━━━━━
         Sumc(n,k)


En[n,0] = 0

이며 이를 C 함수로 나타내면 다음과 같다.

double En(int n, int k) {
int i;
double s1, s2;

/* 이 부분은 n, k가 초기에 정상적으로 입력되었다고 가정할 때 주석처리가 가능하다
if(n<2*k+1 || k<0 || n<3 ) {
cout << "잘못된 숫자 입력n";
return 0;
}
*/

if(k==0)
return 0;
else {
s1 = expi(2,n-1); // (exponent for integer - expi(int a, int b) 는 double a^b를 리턴)
s2 = 0;
for(i=1;i<=k;++i) {
s1 += En(n-i,k-i)*C(n,i); // C(int a,int b) 는 int a!/[ b! * (a-b)! ]를 리턴
s2 += C(n,i);
}
}
return s1/s2;
}

double expi(int a, int b) {
int i;
double s = a;
for(i=1;i<b;++i)
s *= a;
return s;
}

int C(int a, int b) {
int i;
int s1, s2;

/* 이 부분은 a, b가 초기에 정상적으로 입력되었다고 가정할 때 주석처리가 가능하다
if(a<b) {
cout << "잘못된 숫자 입력n";
return 0;
}
*/

s1 = 1;
s2 = 1;
for(i=0;i<b;++i) {
s1 *= a-i;
s2 *= i+1;
}
return s1/s2;
}

-----------------------------------------------------------------------

답을 위해 작성한 main 함수

#include<iostream>

using namespace std;

double En(int n, int k);
double expi(int a, int b);
int C(int a, int b);

void main()
{
cout << En(10,3) << endl;
cout << ( En(9,2)*C(10,1) + En(8,1)*C(10,2) + En(4,1)*C(10,4) + expi(2,9) )/( C(10,1)+C(10,2)+C(10,3)+C(10,4) ) << endl;
}

--------------------------------------------------------------------------

결과창

7.54794
4.52179
Press any key to continue


........................................................................................
■ 박기현: c코드의 En함수에서 주석처리된 if 구문에서 n<3은 필요도 없고 En[2,0]때문에 맞지도 않는군요.. 수정해야겠습니다. (pl2115@hotmail.com) -[10/13-01:38]-
........................................................................................
■ 송홍엽: 고생했다... 정답을 검토할동안 조금만 기다려다오.. (hy.song@coding.yonsei.ac.kr) -[10/14-20:46]-
번호 제목 글쓴이 날짜 조회 수
공지 논문에 영어작문 주의사항 몇 가지 송홍엽 2008.05.22 8615
공지 젊은 학부생 여러분에게... 송홍엽 2008.11.20 5891
공지 우리학과 대학원생 모두에게 (특히, 박사과정들에게) 하고싶은 말입니다. 송홍엽 2014.01.20 6526
87 학위논문 작성에 관한 조언 file 송홍엽 2014.01.25 1941
86 2013년 12월 31일 오후에 작성한 글: 새해는 시속 1400키로의 속도로 달려온다. file 송홍엽 2014.01.17 2240
85 [펀글] 한겨레 2011.12.23. 정봉주 유죄판결은 법적 착시현상 송홍엽 2011.12.25 2263
84 [퍼온글] 외국계 기업, `출신대 간판` 안 본다 송홍엽 2011.12.15 3662
83 [펀글] 영문이력서 작성법 송홍엽 2011.03.27 5333
82 [펀글] 왜 우린 이런거 못만드냐고... 송홍엽 2010.05.09 2817
81 [펀글] 프로그램 설계시 좋은 코딩 습관 송홍엽 2009.12.27 4969
80 [펀글]프로운동선수의 대학학업 병행하기 송홍엽 2009.12.17 2833
79 [퍼온글] 수학의 힘 -- 동아일보 컬럼 2008.12.18 송홍엽 2008.12.18 3645
78 [퍼온글] 해석학적 극한의 의미 송홍엽 2008.12.18 3922
77 [퍼온글] FM방식 개발한 암스트롱 송홍엽 2008.09.24 3905
76 움직이는 글자 태그 송홍엽 2008.09.04 3771
75 [펀글]수학의 open problems 모음. 송홍엽 2008.07.30 6267
74 김정한 교수의 '창의적 수학교육' [1] file 송홍엽 2008.06.20 5998
73 수학사 바로잡기 (3) - 월간 과학동아 2008년 7월호 강석기 기자의 글 송홍엽 2008.06.20 4177
72 수학사 바로잡기 (2) 송홍엽 2008.06.03 7702
71 수학사 바로잡기 (1) - 오일러의 36명 장교문제와 조선시대 최석정 (수정본 - 일부 오류 수정) [1] file 송홍엽 2008.06.03 6327
70 [펀글] 전화기를 최초로 발명한 사람은 누구인가 송홍엽 2008.05.23 6391