본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대22. 쿠폰 수집가 문제의 일반화
수학동아 2018.10.01 10:32 조회 1930

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

 

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

 

문제1

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

 

문제2

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

 

문제3

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

 

문제4

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

 

 

  •  
    math Lv.2 2018.10.01 16:04

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

    댓글 작성하기 좋아요2 댓글수1
  •  
    B.C.I.수학장 Lv.5 2018.10.01 16:25

    (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
  •  
    B.C.I.수학장 Lv.5 2018.10.01 16:57

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

    댓글 작성하기 좋아요0 댓글수3
    •  
      김우현 기자 Lv.5 2018.10.02 09:21

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

      좋아요0
    •  
      아인수타인 Lv.12 2018.10.15 00:34

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

      좋아요0
    •  
      김우현 기자 Lv.5 2018.12.19 17:42

      반드시 숫자일 필요는 없어요. 아래 표현을 잘 관찰해보세요!smiley

      "어떤 자연수 n에 대해, 함수 \small f(n)=1+2+3+\small \cdots+n을 시그마 기호(\small \sum)로 나타내면  \small f(n)=\sum_{k=1}^{n} k다"

      좋아요0
  •  
    B.C.I.수학장 Lv.5 2018.10.01 21:01

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    B.C.I.수학장 Lv.5 2018.10.02 23:34

    진전이 있을 지는 모르겠지만 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
  •  
    CoderLab Lv.4 2018.10.03 21:21

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

    댓글 작성하기 좋아요0 댓글수3
    •  
      B.C.I.수학장 Lv.5 2018.10.03 21:53

      네....

      좋아요0
    •  
      CoderLab Lv.4 2018.10.04 20:34

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

      좋아요0
    •  
      B.C.I.수학장 Lv.5 2018.10.04 20:41

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

      좋아요0
  •  
    아인수타인 Lv.12 2018.10.11 20:49

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

    댓글 작성하기 좋아요0 댓글수2
    •  
      B.C.I.수학장 Lv.5 2018.10.11 21:33

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

      좋아요0
    •  
      아인수타인 Lv.12 2018.10.13 00:48

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

      좋아요0
  •  
    CoderLab Lv.4 2018.10.18 19:37

    통계학을 막 시작한 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
    •  
      CoderLab Lv.4 2018.10.18 19:41

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

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

      좋아요0
    •  
      B.C.I.수학장 Lv.5 2018.10.18 22:57

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

      좋아요0
    •  
      CoderLab Lv.4 2018.10.19 12:00

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

      -\sum시그마 올림-

      좋아요0
  •  
    B.C.I.수학장 Lv.5 2018.10.31 22:52

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

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

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

    댓글 작성하기 좋아요0 댓글수0
  •  
    CoderLab Lv.4 2018.11.15 22:15
    확인요청중

    <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 댓글수5
    •  
      CoderLab Lv.4 2018.11.16 22:52

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

      좋아요0
    •  
      CoderLab Lv.4 2018.12.05 22:18

      여러분~ 체크해주세요!

      좋아요0
    •  
      B.C.I.수학장 Lv.5 2018.12.07 22:23

      전 모르겠어요 :{

      좋아요0
    •  
      CoderLab Lv.4 2018.12.08 11:41

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

       

      좋아요0
    •  
      김우현 기자 Lv.5 2018.12.28 10:11

      친구들의 관심아 모여라! (기웃)

      좋아요0
  •  
    CoderLab Lv.4 2019.05.29 16:34

    마지막 글이 5개월 전이군요..

    제발 관심을 가져주세요!

    댓글 작성하기 좋아요1 댓글수0
  •  
    cjmoon Lv.6 2019.09.22 09:38 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수1
    •  
      cjmoon Lv.6 2019.11.09 07:50

      공개

      1번문제, 들어간다. 안들어간다해서 50%활룔. 즉 2n번 던지면 평균적으로 들어간다.

      2번문제, 2^{d}n

      3번문제, 2nm

      4번문제, 2^{d}nm

      1번,3번은 자신이 있는데 2번, 4번은 조금 자신이 없네요.

      좋아요0
  •  
    CoderLab Lv.4 2019.09.25 16:48
    확인요청중

    함께 의견을 나눠주세요!

    다시 정리해보죠. 2번문제입니다.


    일단 n개의 바구니에 d개의 공을 던진다고 하면, 그 경우의 수는 \binom{n}{d}가 됩니다. 자, 한 바구니를 기준으로 두면 그 바구니로 들어갈 경우의 수는 d개네요. 그럼 한 바구니로 들어갈 확률은 \frac{d}{\binom{n}{d}}가 될겁니다. 결국

    \sum_{k=1}^{n}\frac{d}{\binom{n}{k}}이 되지 않을까요?


    그럼 기댓값은 n\sum_{k=1}^{n}\frac{d}{\binom{n}{k}}이 될텐데요. 확신은 못하겠습니다.

     

    댓글 작성하기 좋아요0 댓글수3
    •  
      c언어 Lv.2 2019.09.26 15:23

      아직 왠지는 잘 모르겠지만 시그마님이 추축하신 것이 틀린것 같습니다 ㅠㅠ

       

      n =10, d = 10을 대입하면 바로 되니까 1이 되어야 하는데 시그마님처럼 계산을 하면 127정도가 나오네요....그리고 프로그램에 여러 수를 넣어 보니 추측한것보다 훨씬 값이 작게 나옵니다

       

      그리고 d=1 을 대입했을때 1번답과 같게 나오고 n=d일때는 1이 나와야 하는걸 더 생각해 보면 좋을것 같아요

      좋아요0
    •  
      CoderLab Lv.4 2019.09.28 09:34

      저도 뭔가 이상하다는 느낌이 들었는데, 불행히도 그 예상이 적중했네요.....

      좋아요0
    •  
      CoderLab Lv.4 2019.09.28 09:39

      할 수 있는 것만 수정해 볼게요.


      1. \frac{d}{\binom{n}{d}}가 아니라 \frac{1}{\binom{n}{d}}로 수정합니다.

      2. 확률들을 더하는 것에서 \sum을 사용하면 안됩니다. 이 부분은 어떻게 해야할 지 감이 오지 않네요

      좋아요0
  •  
    c언어 Lv.2 2019.09.25 17:52

    지금 생각해 보니까 프로그래밍으로 답과 풀이를 구할 수는 없지만 대강 확인을 할 수 있을 것 같습니다!

    지금은 조금 바빠서 이번주안에는 한번 만들어서 2번, 3번을 확인해 보겠습니다

    댓글 작성하기 좋아요0 댓글수0
  •  
    c언어 Lv.2 2019.09.26 14:57

    일단 1번을 만들어서 수학장님이 푼것과 비교를 해보았습니다!

    프로그램 설명 : python의 랜덤함수를 이용해서 공을 n개의 바구니에 넣는 경우를 시뮬레이션해보았습니다. 그렇게 모든 바구니의 공수가 1개 이상될때까지 반복한후 이때의 던진 횟수를 카운트하였습니다. 시행을 100000번정도 해본후 나온 횟수의 평균값을 구해보니 이론적으로 구한 값과 소수점 첫째자리까지는 같네요!

    n=20 인 경우로 해본 것이고 이론적인 값은 수학장님이 구한 공식을 계산한 경우입니다

    실험한 값은 프로그래밍으로 총 100000번 돌렸을때 평균적인 값입니다

    /resources/comment/2019/09/8930694165b65a71f5afdf1ccca98fc8.py

    /resources/comment/2019/09/c9069037dbec2aeb9286b1eaa7989a0c.txt

     

    p.s) 제 닉과 같이 c언어로 진행을 해보려 하였는데, 2,4번에 겹치지 않고 랜덤한 수를 뽑아야 되는거에서 c는 지원하는 함수를 찾을 수 없어서 python으로 프로그래밍을 만들었습니다 ㅠㅠ

     

    댓글 작성하기 좋아요0 댓글수1
    •  
      c언어 Lv.2 2019.09.26 14:59

      지금은 시행을 100000번만 돌렸는데 시간이 된다면 백만번이나 50만번정도 돌리고, n의 값에 따라서 정리해서 추가로 올리겠습니다

      좋아요0
  •  
    c언어 Lv.2 2019.09.27 17:12

    혹시나 잘 쓸수 있는 사람이 있을까 올립니다

    프로그램으로 1번문제, 2번문제 data값입니다

    /resources/comment/2019/09/927f7de77dd8c546cf1bfcddb80339a3.txt

    /resources/comment/2019/09/638be276167d5b299c89e3d8b89c31a3.txt

    제가 2번 여러가지 예측을 해봤는데 data값이랑 다르네요 ㅠㅠ

     

    댓글 작성하기 좋아요0 댓글수1
    •  
      c언어 Lv.2 2019.09.27 17:13

      txt파일 들어가 보니까 한글이 다 깨졌던데 왼쪽에 n,d에 따른 결과 값이라 생각하시면 됩니다!

      좋아요0
  •  
    cjmoon Lv.6 2019.09.28 08:25 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수0
  •  
    cube120 Lv.5 2019.09.28 14:39

    일단 c언어 님이 올려주신 자료를 토대로 함수를 예상해보았습니다. 아래 그림에서 검은색 점이 실제계산값, 곡선이 제가 예상한 함수입니다.

    곡선은 아래서부터 순서대로 d=n-1, d=n-2, d=n-3, d=n-4, d=n-5일 때의 그래프이고, 식은

    2+\frac{1}{n-1},   2+\frac{1}{n-1}+\frac{3}{n-2},   2+\frac{1}{n-1}+\frac{3}{n-2}+\frac{4}{n-3}2+\frac{1}{n-1}+\frac{3}{n-2}+\frac{4}{n-3}+\frac{5}{n-4}2+\frac{1}{n-1}+\frac{3}{n-2}+\frac{4}{n-3}+\frac{5}{n-4}+\frac{5}{n-5} 입니다.

    위 그래프에서 보면 d=n-1, d=n-2인 경우 실제 계산값과 거의 정확히 일치하는 것을 볼 수 있습니다. (참고로 d=n-1인 경우에는 식이 1+1/(n-1)이 나오는 것을 유도 할 수 있습니다.)

    그러나 d=n-3 부터는 조금씩 오차가 있어서, 저 식이 맞는지는 잘 모르겠습니다.

    댓글 작성하기 좋아요0 댓글수2
    •  
      c언어 Lv.2 2019.09.28 16:16

      d=  n-1일때의 식을 가지고 어떤 규칙으로 n-2,n-3 ... 일때의 식을 유추하였는지 알 수 있을까요...?

      그리고 그래프를 그릴때 n,d의 값이 각각 무었이었나요? 많은 경우를 한다고 횟수를 만번밖에 안해서 오차가 좀 큽니다ㅠㅠ. 알려주신다면 그 30개정도의  경우만 한다면 회수를 늘려서 더 정확하게 값을 낼 수 있을거 같아요!

      좋아요0
    •  
      cube120 Lv.5 2019.09.28 21:04

      일단 d=n-1일 때의 식만 계산한 것이고, d=n-2 부터는 말 그대로 가능해보이는 모든 함수를 대입해봐서 찾았습니다. 그래서 저 식이 틀릴수도 있다고 한 것이고요.

      그리고 그래프에서 점의 n값은 x좌표와 같습니다. 예를 들어, 빨간색 그래프의 가장 왼쪽 점은 (n,d)=(3,1)입니다.

      좋아요0
  •  
    c언어 Lv.2 2019.09.30 15:09

    cube120님이 d=n-k일때의 경우로 생각해서 예상되는 그래프도 그려서 이 경우에 한해서 더 정확한 값을 찾아 보았습니다.

    /resources/comment/2019/09/484a996baa2e97d5f93f2a9dc6edef95.txt

    현재 값이 나온 d=1, d=n-1의 실제값과 비교를 해본 결과 오차가 0.002 이내로 나오는 것 같습니다.

    지금 d=n-2인 경우를 일반화 하기 전에 n=4,d=2의 정확한 값을 구하려고 하는데 힘드네요ㅠㅠ

    cube120님의 식처럼 a_1/n + a_2/(n-1) + a_3/(n_2) + ... 의 꼴로 나올거 같기는 한데.... 

    댓글 작성하기 좋아요0 댓글수1
    •  
      cube120 Lv.5 2019.10.02 17:10

      저도 n=4,d=2일 때의 값을 구해보고 있는데, 잘 안되네요. 혹시 추가로 얻어진게 있으면 알려주세요. ㅎㅎ

      그리고 c언어로 기댓값을 한번 구해봤는데, 10^6번씩 100번 실행해봤더니 값의 평균으로는 대략 3.8152325가 나오네요. 아래 사진은 모든 결과값을 나타낸 겁니다.

      좋아요0
  •  
    파스칼 Lv.7 2020.03.05 00:45
    확인요청중

    2번 답을 점화식의 형태로 내겠습니다.

    우선 \binom{a}{b}에서 a또는 b가 음수이면 이 값을 0으로 정의할 것을 밝힙니다.n개의 바구니 중 빈 바구니가 m개일 때, 공 d개를 던지는 과정을 한 번 실행하여 빈 바구니가 m-k개인 상태가 될 확률은 \frac{\binom{n-m}{d-k}\binom{m}{k}}{\binom{n}{d}}입니다. 즉, f(n,m,d)를 n개 바구니 중 m개가 빈 상황에서 d개의 공을 매번 던질 때 공을 던지는 횟수의 기댓값으로 정의하면 아래와 같은 점화식이 나옵니다.f(n,1,d)=\frac{\binom{n}{d}}{\binom{n-1}{d-1}}f(n,m,d)=\frac{\frac{\binom{n-m}{d}}{\binom{n}{d}}+\sum_{k=1}^{min(m,d)}[\frac{\binom{n-m}{d-k}\binom{m}{k}}{\binom{n}{d}}(f(n,m-k,d)+1)]}{1-\frac{\binom{n-m}{d}}{\binom{n}{d}}}

    댓글 작성하기 좋아요0 댓글수1
    •  
      김다인(멘토) Lv.5 2021.11.22 01:47 비밀댓글
      비밀 댓글이 등록 되었습니다!
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911