본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대48. 개미집 속의 개미
수학동아 2020.12.01 10:01 조회 1596

 

위의 그림과 같이 수형도 모양으로 주어진 개미집이 있다. 이때, 가장 아래 놓인 점 O을 시작으로 각 점은 모두 그 위로 d개의 점들과 연결되어 있다. 주어진 그림은 d=2인 경우이다. 이때, 점 O가 있는 곳을 1층이라 하고, 그 위에 있는 d개의 점을 2층이라 하며 반복적으로 3층, 4층 등을 정의하자. 이때, n층에 도달하면 개미가 땅 밖으로 나온다고 한다.

 

 

개미는 점 O에서는 2층의 d개의 점 각각으로 \frac{1}{d}의 확률로 움직이며, 2층부터 n-1층의 점 중 하나에 도달하면 위의 층의 연결된 d개의 점 각각으로 p의 확률로 움직이며 아래 층에 연결된 점으로 1-dp의 확률로 움직인다. 여기서 p<\frac{1}{d}인 양수다. 

 

 

이때 1층에서 시작하여 개미가 지상으로 나오는데 걸리는 시간을 T라 하고, T의 기댓값을 f_n(p)하자. 

 

 

 

문제1 f_{d,n}(p)의 값은 p가 증가함에 따라 감소하는지 여부를 설명하고 이를 증명하여라. 

 

 

 

문제2 어떤 양수 p_0, c_1, c_2, c_3, c_4, c_5가 존재하여 모든 n에 대해 다음이 성립함을 증명하여라. 

p<p_0이면 f_n(p)>e^{c_1n}  

p=p_0이면 c_2n^2\leq f_n(p)\leq c_3n^2  

p>p_0이면 c_4n\leq f_n(p)\leq c_5n

 

 

 

문제3 앞선 결과가 좀 더 일반적인 수형도에서도 성립할까? 예를 들어, 위의 각 점이 위로 2개 또는 3개의 점들과 연결되는 상황이라면 문제2의 결과가 성립할까? 성립하지 않는다면 어떤 결과가 성립할까? 혹은 더 일반적인 그래프들로 이 결과를 확장할 수 있는지 생각해 보아라.

 

※ 1번 문제는 파스칼 친구가 풀었습니다. 3번 문제의 풀이까지 완성되면 교수님께 최종 검토 요청드리겠습니다!

  •  
    수좋학 Lv.5 2020.12.01 21:13

    저는 증가한다 생각합니다.이유는 P가 증가하면 그만큼 확률도 증가합니다.

    예1):만약 P가 \frac{1}{3}이고 d2일때 위에 부등식은 성립합니다.P< \frac{1}{d}가 성립합니다.

    그러면 나갈 확률이(2층부터) 1 - dp라고 하는데 대입시키면 확률이 \frac{1}{3}이 됩니다.하지만 점점 수를 늘닐수록 확률이 감소합니다.

    그리고 4를 d에 대입하고, \frac{1}{4}을 P대입 하지 않는한 밑으로 내려갈 확률이 더 커진다.

     

    P = \frac{1}{d} > P

    \sum_{g=d+2}^{\infty } \frac{1}{g} > 1-dp

     

     

    댓글 작성하기 좋아요0 댓글수1
    •  
      Sin X Lv.5 2020.12.01 22:07

      위로 올라갈 확률이 증가하기 때문에 걸리는 시간의 기댓값이 감소할 것입니다.

      좋아요0
  •  
    수좋학 Lv.5 2020.12.02 08:17

    하지만 1-dp수식은 밑으로 내려갈 확률이고,p는 올라갈 확률이니

    p < 1-dp관계식이 성립합니다.

    그리고 위 풀이에 오류가 있었습니다.

    \sum_{g=d+2}^{\infty }\frac{1}{g} > 1-dp가 아니라

    \sum_{g=d+2}^{\infty }\frac{1}{g} > p입니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    수좋학 Lv.5 2020.12.02 08:24

    하지만 \frac{x}{y} >p라고 가정한뒤

    y \geq 2라면 p > 1-dp가 됩니다.

    예로 \frac{2}{5}가 p일때는 \frac{1}{5}가 내려갈 확률이고,\frac{2}{5}가 올라갈 확률입니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      Sin X Lv.5 2020.12.02 08:46

      그건 확률이 올라가기 때문에 시간이 감소한다는 직관적인 해석일 뿐인것 같습니다.

      f_{n,d}(p)를 식으로 표현한후 증가또는 감소함을 보여야 할것 같습니다.

      좋아요0
  •  
    Sin X Lv.5 2020.12.02 10:46

    \sum_{k=0}^{\infty} \binom{n+k-2}{k}{(dp)^{n+k-1}}{(1-dp)^k}({n+2k-1})

    이런 형태로 나오는것 같습니다.

    댓글 작성하기 좋아요2 댓글수12
    •  
      수좋학 Lv.5 2020.12.02 14:20

      그러내요.

      좋아요0
    •  
      수좋학 Lv.5 2020.12.02 14:32

      위 식은 제가 이해가 안됩니다(저 초등학생이에요......)

      하지만 제 생각은 위 문제 1번은 f_{d,n}(p)가 올라가는 시간의 기댓값이고 p가 증가하냐에 따라 시간이 감소하냐,증가하냐를 묻는것이니까,

      제 풀이는 1-dp \geq p라는 생각입니다.

      이유는 위에서 말했드시 \sum_{g=d+2}^{\infty }\frac{1}{g}>p라는 풀이이고요,

      하지만\frac{y}{x}=p < \frac{1}{d}라고 p를 풀이한뒤,y \geq 2라면

       1-dp< p라고 생각합니다.

      \therefore대부분 증가하지만,가끔식 \frac{y}{x}=p < \frac{1}{d},y \geq 2이런 모양이 나타나면 오히려 감소한다는 풀이입니다.

      맞나요?

      좋아요0
    •  
      Sin X Lv.5 2020.12.02 14:42

      위로 올라갈 확률은 p가 아닌 dp입니다. 그리고 1번은 직관적으로 봐도 당연히 위로 올라가는 확률은 p가 커짐에 따라 증가하므로 올라가는 시간의 기댓값은 감소합니다.

      저는 기댓값에 관한 식을 구해본것입니다.

      좋아요0
    •  
      Sin X Lv.5 2020.12.02 15:30

      실제로  \sum_{k=0}^{\infty} \binom{n+k-2}{k}{(dp)^{n+k-1}}{(1-dp)^k}({n+2k-1})가 발산하지 않는것으로 보아 맞는식인것 같네요.(발산하지 않는다고 맞는건 아니지만)

      시간이 되면 풀이도 올려보겠습니다.

      좋아요0
    •  
      수좋학 Lv.5 2020.12.02 16:01

      근데 여기서

      개미는 점 O에서는 2층의 d개의 점 각각으로 \frac{1}{d}의 확률로 움직이며, 2층부터 n-1층의 점 중 하나에 도달하면 위의 층의 연결된 d개의 점 각각으로 p의 확률로 움직이며 아래 층에 연결된 점으로 1-dp의 확률로 움직인다. 여기서 p<\frac{1}{d}인 양수다. 라고 말했는데 자세이 보면 아래 층에 연결된 점으로 1-dp확률로 움직인다 되어있으니까 오히려 대부분 증가한다 생각하는데 식은 제대로 못 세우겠습니다.좀 식을 만들어 주세요.

      좋아요0
    •  
      수좋학 Lv.5 2020.12.02 16:03

      확실이 sinX님이 저보다 훨씬 더 수학을 잘하시네요.

      좋아요0
    •  
      Sin X Lv.5 2020.12.02 16:14

      저 잘 못해여 

      그리고 식을 유도한 방법은 위방향으로 가는 시행이 n-1번 이상있고, 아래방향으로 가는 시행의 횟수에 따라 분류하여 무한급수의 합으로 표현한것입니다.

      좋아요0
    •  
      파스칼 Lv.7 2020.12.03 07:54

      n=2, p=0.000000001, d=2일 때 식이 틀린 듯합니다.

      식을 어떻게 구하셨나요?

      좋아요0
    •  
      파스칼 Lv.7 2020.12.03 08:20

      제가 구한 식은

      1+\sum_{k=2}^{n-1}((\sum_{i=0}^{k-2}\frac{(\frac{1}{dp}-1)^{i}}{(dp)})+(\frac{1}{dp}-1)^{k-1})입니다

      좋아요0
    •  
      Sin X Lv.5 2020.12.03 08:41

      음.. 저랑 다르게 나오셨네요 구한 과정을 한번 올려볼테니 틀린부분 알려주세요

      좋아요0
    •  
      Sin X Lv.5 2020.12.03 09:22

      아 2층에서 1층으로 갔다가 다시 1층에서 2층으로 가는 경우도 dp라고 해버렸네요... 다시 구해 보겠습니다.

      좋아요0
    •  
      수좋학 Lv.5 2020.12.03 09:31

      내가 여기서 가장 수학 못하는듯........

      너무 식 스케일이 다릅니다......

       

      좋아요0
  •  
    수좋학 Lv.5 2020.12.03 09:31

    근데 결론이 모에요?

    댓글 작성하기 좋아요0 댓글수0
  •  
    수좋학 Lv.5 2020.12.03 09:32

    어렵내.......

    힘들다.....

    댓글 작성하기 좋아요0 댓글수0
  •  
    Sin X Lv.5 2020.12.03 09:57

    \sum_i \sum_j dp^{i+n-2}(1-dp)^{i+j}(n+2(i+j-1))({n-2}H{i})이 나오는것 같습니다 제가 지금 사진 업로드가 안되서 유도 과정은 될때 올리겠습니다.

    댓글 작성하기 좋아요0 댓글수4
    •  
      Sin X Lv.5 2020.12.03 09:57

      파스칼님 이거 값 넣어서 맞는지 확인 부탁드립니다

      좋아요0
    •  
      파스칼 Lv.7 2020.12.03 22:48

      시그마 아래에 i, j를 써놓으셨는데 몇부터 몇까지 더하는 건지 잘 모르겠습니다. 또한 마지막에 n-2Hi에서 H가 혹시 중복조합 기호인가요?

      i=0, j=0 부터 더한다면 마찬가지로 n=2, p=0.000000000000000001, d=2일 때 기댓값이 1보다 많이 크게 나오는 것 같습니다.

      기댓값을 구하기 가장 쉬운 경우가 n=2일 때 dp에 상관없이 기댓값은 1이라는 부분인 듯하여 이것을 이용하고 있습니다.

      좋아요0
    •  
      Sin X Lv.5 2020.12.04 00:04

      저는 up down 쌍을 추가하는 경우가 있다고 가정하고 세운 식이기 때문에 n=2를 넣으면 식에 모순이 0H꼴의 모순이 나오는 것을 알수가 있습니다.

      그리고 중복조합 기호이고 각각 0 부터 더한 갓입니다.

      식을 검증할려면 n=2 이외의 경우르 해봐야 할것 같습니다.

      좋아요0
    •  
      파스칼 Lv.7 2020.12.04 08:03

      아 n-2Hi가 n-(2Hi)가 아니라 (n-2)Hi였군요. i,j는 각각 무한까지 더한다는 것이겠죠? 간단히.. n=3 d=2 p=0.25에서 기댓값이 4가 되어야 하는데 식에 따르면 4를 초과하는 듯합니다. 아래쪽에 1번 풀이 쓰면서 제가 f_n,d(p)를 구한 방법도 언급해 놓았습니다.

      좋아요0
  •  
    파스칼 Lv.7 2020.12.03 23:19

    1번 풀이입니다. p가 증가함에 따라 기댓값은 감소함을 증명하였습니다.

    a_n(d, p)를 n층에 도달한 뒤 n+1층에 도달할 때까지 시간의 기댓값이라고 정의합니다. 먼저 n=1일 때 a_n(d,p)=1입니다. 또한 확률변수로써 a_n(d,p)를 생각해보면, 확률 dp로 1이며 확률 1-dp로 1+a_(n-1)(d,p)+a_n(d,p)가 되므로 a_n(d, p)=(1-dp)(1+a_{n-1}(d,p)+a_n(d,p))+dp에서 a_n=(\frac{1}{dp}-1)a_{n-1}+\frac{1}{dp}를 얻습니다. 이때 f_d, n(p)=\sum_{k=1}^{n-1}a_k(d,p)로 쓸 수 있습니다. 또한 모든 d, p와 2 이상의 정수 k에 대하여 a_k(d,p)는 1보다 크며, 이는 a_n=(\frac{1}{dp}-1)a_{n-1}+\frac{1}{dp}에서 (\frac{1}{dp}-1)a_{n-1}가 양수이고 dp<1에서 1/dp>1이기 떄문입니다.

    일정한 d,n(단, n>2)의 조건에서 0<p<q<1/d일 때 f_d,n(p)>f_d,n(q)임을 보이겠습니다.

    1) k=1일 경우 a_k(d, p)=1=a_k(d, q)입니다.

    2) a_k(d, p)\geqa_k(d, q)라 가정합니다. 이때 모든 d, p와 2 이상의 정수 k에 대하여 a_k(d,p)는 0보다 크므로, a_{k+1}(d,p)=(\frac{1}{dp}-1)a_{k}(d,p)+\frac{1}{dp}> (\frac{1}{dq}-1)a_{k}(d,p)+\frac{1}{dq}\geq (\frac{1}{dq}-1)a_{k}(d,q)+\frac{1}{dq}=a_{k+1}(d,q)입니다. 즉, 1)에 의해 모든 2 이상의 k에 대해 a_{k}(d,p)> a_{k}(d,q)가 성립합니다.

    1), 2)에 의해, 일정한 d,n(단, n>2)의 조건에서 0<p<q<1/d일 때 f_{d,n}(p)=\sum_{k=1}^{n-1}a_k(d,p)=1+a_2(d,p)+\sum_{k=3}^{n-1}a_k(d,p)>1+a_2(d,q)+\sum_{k=3}^{n-1}a_k(d,p)\geq 1+a_2(d,q)+\sum_{k=3}^{n-1}a_k(d,q)=\sum_{k=1}^{n-1}a_k(d,q)=f_{d,n}(q)입니다. 즉 일정한 d,n(단, n>2)의 조건에서 0<p<q<1/d일 때 f_d,n(p)>f_d,n(q)입니다.

    댓글 작성하기 좋아요0 댓글수2
    •  
      수좋학 Lv.5 2020.12.04 08:18

      와,대박!!!!!

      즉 1번문제는 1주일도 안돼 해결????

      좋아요0
    •  
      최기자 Lv.4 2020.12.19 13:26

      김다인 멘토의 검토 결과 잘 풀었다고 합니다.^^

       

      수고했어요~!

      좋아요0
  •  
    Integral Lv.2 2020.12.07 12:45 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      Integral Lv.2 2020.12.07 12:54

      1번 풀이입니다^^

      좋아요0
    •  
      최기자 Lv.4 2020.12.19 13:26

      김다인 멘토의 검토 결과입니다.^^

       

      직관적인 감을 바탕으로 계산해주셨네요! n이 2 이하이면 어떻게 될지 궁금합니다^^ 또한 무한합을 기반으로 한 서술에서는 이 무한합이 잘 정의된다 (수렴한다)는 사실을 보여줘야함을 명심해주세요. 마지막으로 이러한 아이디어를 통해서 충분히 간결한 풀이를 찾을 수 있다는 점을 알려드립니다! 좀 더 힘내보세요!
       

      좋아요0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911