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

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개 이상의 공이 들어갈까요?

 

 

댓글 19

  • 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