주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[대한수학회] 대22. 쿠폰 수집가 문제의 일반화

2018.10.01

같이 풀어볼까?

네이버밴드 구글플러스

대한수학회 10월 문제는 '쿠폰 수집가 문제'를 일반화한 문제입니다. 비교적 쉬운 1, 2번 문제부터 풀고 3, 4번 문제에 도전해 보세요!

 

바구니 \large n개가 있습니다. 공을 던져서 모든 바구니에 공이 들어가도록 하고 싶습니다. 던진 공은 바구니에 무작위로 들어가며, 각 바구니에 공이 들어갈 확률은 같습니다.

 

문제1

만약 한 번에 한 개의 공을 던진다면, 평균적으로 공을 몇 번 던져야 모든 바구니에 공이 들어갈까요?

 

문제2

만약 한 번에 공 \large d개를 던지고 \large d개의 공이 항상 서로 다른 바구니에 들어간다면, 평균적으로 공을 몇 번 던져야 모든 바구니에 공이 들어갈까요?

 

문제3

만약 한 번에 한 개의 공을 던진다면, 평균적으로 몇 번 공을 던져야 모든 바구니에 적어도 \large m개 이상의 공이 들어갈까요?

 

문제4

만약 한 번에 공 \large d개를 던지고 \large d개의 공이 항상 서로 다른 바구니에 들어간다면, 평균적으로 공을 몇 번 던져야 모든 바구니에 적어도 \large m개 이상의 공이 들어갈까요?

 

 

댓글 30

  • math 2018.10.01 16:04:32

    공이 바구니에 들어가지 않을 확률은 없죠?

    좋아요1 댓글수1
    • 수학장 2018.10.01 16:13:10

      있다면 언급이 됐겠죠?

      좋아요0
  • 수학장 2018.10.01 16:25:41

    (1번문제)평균적으로 공을 던지는 횟수는 \sum(공을 던진 횟수 k)x(k-1번 던졌을 땐 들어가지 않았고, k번 던졌을 떄 모든 바구니에 공이 들어갈 확률) 이렇게 구하면 될 것 같아요. 예를 들어 바구니가 2개라면 공을 2번 던져서 들어갈 확률 1/2, 3번 던져서 들어갈 확률 1/4, 4번 던져서 들어갈 확률 1/8, ...........) 즉 \sum_{n=2}^\infty \frac{n}{2^{n-1}}=3입니다.

    좋아요0 댓글수0
  • 수학장 2018.10.01 16:57:53

    일단 1번 문제는 빈 바구니가 k개 있을 때, 공이 빈 바구니에 들어갈 기댓값은 \frac{n}{k}입니다. 빈 바구니가 n개일 때, n-1일 때, n-2개일 때, ......, 2개일 때, 1개일 때의 기댓값을 모두 더하면 모든 바구니에 공이 들어갈 기댓값이 되므로 정답은 n\sum _{k=1}^n\frac{1}{k}입니다.

    좋아요0 댓글수2
    • 김우현 기자 2018.10.02 09:21:37

      주정훈 멘토가 잘 풀었다는 의견을 전달했습니다~. 2번까지 풀리면 출제자의 검토를 받도록 할게요!wink

      좋아요0
    • 아인수타인 2018.10.15 00:34:03

      근데요, \sum가 원칙적으로 위아래에 숫자가 있어야 하지 않나요? 1번에 걍 \sum만 있는 건 뭐죠???

      좋아요0
  • 수학장 2018.10.01 21:01:30

    2번 문제는 1\leq k \leq d를 만족하는 k(던졌을 때 채워지는 빈 통의 개수)와 빈 통의 개수 l과의 관계로 기댓값을 계산한 다음 경우의 수를 더하면 될 것 같습니다. 경우의 수가 너무 많을까요?

    좋아요0 댓글수0
  • 수학장 2018.10.02 23:34:53

    진전이 있을 지는 모르겠지만 2번 문제에서 던진 게 모두 채워진 바구니에 들어갈 확률을 F라고 하고, 던진 것 중 c개가 빈 바구니에 들어갈 확률을 E_c라고 하면 던졌을 때 c개가 빈 바구니에 들어갈 기댓값(여러번에 걸쳐서는 안 되고, 한 번에 c개가 들어가거나, 던진 공들이 모두 이미 채워진 통에 들어가다가 한 번에 들어갈 기댓값)은 \frac{E_c}{(1-F)^2}이고, 채워진 바구니의 개수가 f이면 F=\frac{f!(n-d)!}{n!(f-d)!} E_c=\frac{f!(n-f)!(n-d)!}{n!(n-f-c)!(f-d+c)!}입니다. 이쯤 되니 다른 방법으로 갈아타야 될 것 같네요...... 일단 전 이 방법대로 계속 하겠습니다. 2번 문제를 풀 다른 아이디어 있으면 같이 공유해주세요.

    좋아요0 댓글수0
  • 시그마 2018.10.03 21:21:33

    2번문제 공이 바구니에 들어가지 않을 확률은 없죠?

    좋아요0 댓글수3
    • 수학장 2018.10.03 21:53:50

      네....

      좋아요0
    • 시그마 2018.10.04 20:34:50

      그런데 2번문제에서 d=n이면  한방에 해결 되는데요, 이럴 수도 있는 거지요?♦

      좋아요0
    • 수학장 2018.10.04 20:41:28

      물론 d=n일 때 한 번에 다 들어가긴 하지만 여기서 구하라는 건 d가 특정한 수 일 때 구하라는 게 아니라 d에 대한 식을 세우라는 것이니까요.

      좋아요0
  • 아인수타인 2018.10.11 20:49:58

    그나저나 댓글이 넘 없네요...sad

    좋아요0 댓글수2
    • 수학장 2018.10.11 21:33:54

      그러게요.... 다들 국가수리과학연구소 문제에만 관심이 있고..... 이제는 그 문제에도 관심이 없는 듯하고... 다들 바쁘신가보네요...

      좋아요0
    • 아인수타인 2018.10.13 00:48:33

      또는 별다른 아이디어가 없을 수도요... (저도 그렇고요.)

      좋아요0
  • 시그마 2018.10.18 19:37:00

    통계학을 막 시작한 1人입니다. 베르누이 시행에 대해 알다가 얻게 된 따끈따끈한 아이디어입니다.

    1. 확률에 대한 생각

    일단 d개 중 1개가 들어갈 확률, 2개가 들어갈 확률,...,d개가 들어갈 확률을 모두 더해야 한다고 생각했습니다. 그래서 저 이름이기도 한\sum을 쓰기로 했습니다.                         그다음 식을 전개해 보았습니다.

          2. n번째 던졌을 때의 식 전개

    \sum_{k=1}^{d}까지는 생각해보았는데, 그다음 막혀서 한동안 댓글을 올리지 못했습니다. 그 후 베르누이 시행을 보며 식을 구해냈습니다. 일단 \binom{d}{k}을 써서 d번 던졌을때  k번 성공하는 모든 경우의 수를 따졌고, k번 성공하고 (d-k)번 실패하는 확률은 시그마까지 합해

     \sum_{k=1}^{d}\binom{d}{k}p^k(1-p)^d^-^k 

    가 되었습니다.

          3. n+1번째 던졌을 때의 식

    \sum_{k=1}^{d}\binom{d}{k}p^k(1-p)^d^-^k​​​​​​​ 조건부 확률을 이용해 겹치는 것까지 생각했습니다.

    조건부확률이란, n이 주어졌을때 a의 확률을 말하는 것입니다.(이미 다 아시겠지만)

    먼저 c개의 공이 실패할 확률을 Nop_c라 하면, 모든 공이 실패할 확률은

    p(Nop_d|p1)이라 할 수 있습니다.(p1은 곧 채워져 있는 바구니의 확률이기도 하기 때문에)

    그렇다면  실패할 확률의 평균은

    \sum_{c=1}^{d}p(Nop_c|p1)

    이 됩니다. 그럼 n+1번째로 던졌을때의 성공률은 

    1-\sum_{c=1}^{d}p(Nop_c|p1)

    이 됩니다.

          4.결론

    저 생각으로는 이렇게 하는 것도 나쁘지 않을거라 생각합니다. 그러나 제가 맨 처음 이야기했듯이 아직 서툽니다. 오류있으면 당장 알려주세요! 오타도 환영입니다!

    smileywinklaugh\sum시그마 올림smiley​​​​​​​winklaugh

                                               

         

    좋아요0 댓글수3
    • 시그마 2018.10.18 19:41:07

      오류가 없거나 증명에 방해가 되지않으면 좀더 파고들어 보겠습니다.

      (►추신: 국18문제 이후 복귀입니다! 18문제 저만 파고 있는 느낌인지라 많은 관심 부탁드려요!angel(깨알홍보!!) )

      좋아요0
    • 수학장 2018.10.18 22:57:36

      문자들 정리해주실 수 있나요?

      좋아요0
    • 시그마 2018.10.19 12:00:42

      d는 한번 던진 갯수, k는 성공하는 공의 수, c는 실패하는 공의 갯수, Nop은 실패할 확률입니다.

      -\sum시그마 올림-

      좋아요0
  • 여백 패르마 2018.10.28 19:16:07

    (3번 문제)

    풀이: p_{i}를 i번 던졌는데도 각각 상자에 m개의 공이 들어가지 못할 확률이라고 하자. , E_{m}(n)은 각 상자에 m개의 공이 들어가 있을 때까지 던져야 하는 평균 던지는 수라고 하면, E_{m}(n)=\sum_{i=0}^{}\infty p_{i}이다. 그리고, p_i=\frac{N_i}{n^i}라고 하자. 이때, N_i는 i번 던졌을 때 각 상자에 m개의 공이 들어가지 않을 경우의 수이다. 

    각 상자를 x_1, x_2, x_3,...,x_n이라고 하자. 이때 x_1= x_2= x_3=...=x_n=1이다. 그러면, (x_1+ x_2+ x_3+...+x_n)^i=n^{i}이다.  N_i(x_1+ x_2+ x_3+...+x_n)^i에서 지수가 m이상인 것을 모두 뺀 것이다. 각 상자에 m개 이상이 들어가면 안 되기 때문이다. P(x_1, x_2, x_3,...,x_n)이 다항식이거나 지수함수일때, \{P(x_1, x_2, x_3,...,x_n)\}을 m이상의 지수를 가진 항들이 빠진 식이라고 정의하자. 그러면, p_{i}=\frac{N_i}{n^i}=\frac{\{(x_1+x_2+...+x_n)^{i}\}}{n_i}이다. 

    S_{m}(t)=\sum_{k=0}^{m-1} \frac{t^{k}}{k!}라고 정의하자. 그리고, F=\exp(x_1+x_2+...+x_n)-(e^{x_1}-S_{m}(x_1))(e^{x_2}-S_{m}(x_2))...(e^{x_n}-S_{m}(t_n))이라고 정의하자. 여기에서  \exp(x_1+x_2+...+x_n)에서의 m이상의 지수는 빠졌음을 쉽게 알 수 있다. 즉, F=\{\exp(x_1+x_2+...+x_n)\}이다. 그리고, 태일러 급수로 e^{x}=1+x+\frac{x^{2}}{2!}+...+\frac{x_n}{n!}+...이다. 즉, F=\sum \{(x_1+x_2+..,+x_n)\}^{i}/i!이다. 또, E_{m}(n)=\sum \{(x_1+x_2+..,+x_n)^{i}\}/n^{i}이다. 즉, 1/i!을 1/n^i으로 바꿀 수 있는 공식이 필요하다. 

    Lemma (1)) \frac{1}{n_i}=n\int_{0}^{\infty }\frac{t^i}{i!}e^{-nt}dt이다. 

    pf(1)) 조금 뜬금없는 말일 수도 있지만, wolframalpha 에다가 integral o to inf t^(i) times e^(-nt) dt 라고 쳤더니, 답으로 n^{-i-1}\Gamma (i+1)이 나왔다. \Gamma (i+1)=i!이고, n^{-i-1}=\frac{1}{n^{i+1}}이다. 즉, n\int_{0}^{\infty }\frac{t^{i}}{i!}e^{-nt}dt=n\times \frac{1}{n^{i+1}}=\frac{1}{n^{i}}이다. ><

    <본 증명> 

     

    좋아요0 댓글수4
    • 여백 패르마 2018.10.28 19:16:45

      이건 3번 풀이입니다. 

      좋아요0
    • 시그마 2018.10.29 21:45:54

      패르마님! 저는 2번 끝나갑니다!

      아자아자!

      좋아요0
    • 수학장 2018.10.31 22:51:17

      비댓 좀 풀어주실 수 있나요? 솔직히 저 비밀댓글입니다.를 볼 때마다 답답하기도 하고요.... 한 달 지났으니까 정답이라면 저희들이 풀이를 본다 하더라도 상관 없을 것 같고요.... 만약 틀렸으면 저희들이 서로 틀린 점 지적해줄수도 있거든요...

      좋아요0
    • 여백 패르마 2018.11.11 16:11:22

      여러분!!!! 비댓 풀었습니다. 

       

      좋아요0
  • 수학장 2018.10.31 22:52:21

    2번 문제 힌트가 수학동아 잡지에 나왔는데

    "2번 문제는 먼저 빈 바구니를 하나 정한 뒤 이 바구니에 공이 들어가려면 평균적으로 공을 몇 번 던져야 할지 생각해보세요!"라고 하네요

    기댓값을 어떻게 구해야 하는지 식을 구하는 게 너무 헷갈리네요...

    좋아요0 댓글수0
  • 시그마 2018.11.15 22:15:03

    <2번문제>

    1번문제랑 비슷하게 접근할 수 있다.

    Lemma(1)

    바구니 x_k에 공이 들어갈 확률을 P_k라 하면 바구니에 들어갈 확률은 다음과 같다.

    P_k=\frac{1}{\binom{n}{d}}  평균으로는 P_k=\sum_{i=1}^{d}\frac{1}{\binom{n}{i}}

    <본문제>

    확률의 값인 P_k=\sum_{i=1}^{d}\frac{1}{\binom{n}{i}}의 기댓값을 구해야 하는데,

    그러면 이P_k=d\sum_{i=1}^{d}\frac{1}{\binom{n}{i}}가 된다.

     

    좋아요0 댓글수4
    • 시그마 2018.11.16 22:52:39

      여러분이 체크 부탁드립니다 

      좋아요0
    • 시그마 2018.12.05 22:18:13

      여러분~ 체크해주세요!

      좋아요0
    • 수학장 2018.12.07 22:23:48

      전 모르겠어요 :{

      좋아요0
    • 시그마 2018.12.08 11:41:52

      무엇을 모르겠다는 건가요?

       

      좋아요0