2023학년도 카이스트 면접 수학 기출문제_2

일반전형 문제 2 

다음 그림과 같이 정사각형 타일들이 일렬로 (무한히) 배열되어 있다. 각 타일의 꼭짓점을 '교차점'이라 하자. 개미는 교차점 $A$에서 출발하여 타일의 변 위를 다음 규칙에 따라 움직인다.

각 교차점에 도달할 때마다 개미는 그 교차점에 연결된 세 변의 방향 중 하나를 똑같은 확률로 임의로 골라 다음 교차점으로 이동한다. (예시: 그림의 파란색 화살표 방향들이 해당 교차점에서 개미가 이동할 수 있는 방향이다.)

이 규칙을 따르면, 개미가 $n$회의 움직임을 시행할 때, 일어날 수 있는 모든 경우의 수는 $3^n$이다,

(1) 개미가 총 $2n$회의 움직임을 시행한다고 가정하자. 개미가 $m$회 $0\leq m\leq n)$의 서쪽 방향 움직임을 시행하면서, $2n$번째 도달하는 교차점이 $A$와 일치하는 경우의 수는 몇 가지인가?(2점)

(2) 개미가 총 $2n$번째 도달하는 교차점이 출발점 $A$와 일치하였을 때, 서쪽 방향 움직임을 $m$회 $0\leq m\leq n)$ 시행했을 조건부 확률을 $P_{n,m}$이라 하자. 주어진 자연수 $n$에 대해, 이 조건부 확률 $P_{n,m}$을 최대화하는 $m$의 값을 $f(n)$이라 하자. (만약 최대화하는 $m$이 여러 개 존재한다면, 이들 중 가장 작은 값을 택한다,) 이때, $\displaystyle{\lim_{n\rightarrow\infty}\frac{f(n)}{n}}$의 값을 구하시오.(3점)

풀이

이 문제는 자연수와 관련된 문제이므로 자연스럽게 수열을 떠올리면 된다. 수학 문제를 해결하는 방법은 크게 두 가지가 있다. 연역과 귀납법이 있다. 모법 답안은 대부분 연역적으로 답을 찾아가는 과정을 보여준다. 하지만 이런 답안을 쉽게 찾기는 쉽지 않다. 이럴 때 귀납적으로 추론을 해 보면 의외로 쉽게 실마리를 찾을 수 있다. 이 문제와 같이 수열과 관련된 문제는 더더욱 귀납적 추론이 유용하다.

a) $n=1$일 때, 세 가지 경우가 있다. 방향을 나타내면 아래와 같다.

• 1) 상하 2) 좌우 3) 우좌

b) $n=2$일 때, 

• 1) 상하상하
• 2) 좌우상하 3) 좌상우하 4) 좌상하우 5)  상좌우하 6) 상좌하우 7) 우좌상하 8) 우상좌하 9) 상우좌하 10) 상하좌우 11) 우상하좌 12) 상우하좌 13) 상하우좌 
• 14) 좌좌우우 15) 좌우좌우 16) 좌우우좌 17) 우좌좌우 18) 우좌우좌 19) 우우좌좌

위에서 $n$이 정해지면 $2n$개 가운데 서쪽으로 이동하는 횟수와 동쪽으로 이동하는 횟수가 같아야 제자리로 되돌아 옴을 쉽게 알 수 있다. 좌우가 같은 개수이라야 한다. 아래와 같이 셋으로 분류할 수 있다.

• 1) 좌우가 없을 때, ${}_4 C_0=1$
• 2) ~ 13) 좌우가 하나씩 있을 때, ${}_4 C_1\times{}_3C_1=12$
• 14) ~ 18) 좌우가 둘씩 있을 때, ${}_4 C_2\times {}_2C_2=6$

이제 조건부 확률을 계산해 보자.

$$P_{2,0}=1/19, \;\;P_{2,1}=12/19\;\;P_{2,2}=6/19$$

 

(1) $2n$번째 도달하는 교차점이 출발점과 일치한다면 서쪽과 동쪽으로 움직인 횟수가 서로 같아야 한다. 즉 서쪽으로  $m$회 움직였으므로 동쪽으로도 $m$회 움직여야 한다. 따라서 $2n$번의 시행 가운데 서쪽과 동쪽으로 움직이는 때를 $m$번 씩 고르는 경우의 수는 ${}_{2n}C_{m}\cdot {}_{2n-m}C_{m}$이다. 나머지 $2n-2m$은 수직 방향(북이나 남)이고 자동으로 정해진다. 

따라서 정답은 ${}_{2n}C_{m}\cdot {}_{2n-m}C_{m}$이다.

(2) 조건부 확률 $P_{n,m}$은 경우의 수 ${}_{2n}C_{m}\cdot {}_{2n-m}C_{m}$에 비례한다.

$$P_{n,m}=\frac{{}_{2n}C_{m}\cdot {}_{2n-m}C_{m}}{\displaystyle{\sum_{k=0}^{n}} {}_{2n}C_{k}\cdot {}_{2n-k}C_{k}}$$

즉, $f(n)$은 경우의 수 ${}_{2n}C_{m}\cdot {}_{2n-m}C_{m}$를 최대로 만드는 $m$의 값이다.

이웃한 두 항의 대소관계를 알아보자.

${}_{2n}C_{m}\cdot {}_{2n-m}C_{m}$와 ${}_{2n}C_{m+1}\cdot {}_{2n-(m+1)}C_{m+1}$

\begin{split}{}_{2n}C_{m}&=\frac{2n(2n-1)\cdots(2n-m+1)}{m!}=\frac{(2n)!}{m!(2n-m)!}\\{}_{2n-m}C_{m}&=\frac{(2n-m)(2n-m-1)\cdots(2n-2m+1)}{m!}=\frac{(2n-2m)!}{m!(2n-2m)!}\\ \therefore {}_{2n}C_{m}\cdot {}_{2n-m}C_{m}&=\frac{(2n)!}{m!m!(2n-2m)!}\end{split}

마찬가지로

\begin{split}{}_{2n}C_{m+1}\cdot {}_{2n-(m+1)}C_{m+1}&=\frac{(2n)!}{(m+1)!(m+1)!(2n-2m-2)!}\\&={}_{2n}C_{m}\cdot {}_{2n-m}C_{m}\cdot \frac{(2n-2m)(2n-2m-1)}{(m+1)^2}\end{split}

$$\therefore \frac{{}_{2n}C_{m+1}\cdot {}_{2n-(m+1)}C_{m+1}}{{}_{2n}C_{m}\cdot {}_{2n-m}C_{m}}= \frac{(2n-2m)(2n-2m-1)}{(m+1)^2}$$

위에 있는 이웃하는 두 항의 비를 생각하자.

$1$보다 크면 ${{}_{2n}C_{m+1}\cdot {}_{2n-(m+1)}C_{m+1}}>{{}_{2n}C_{m}\cdot {}_{2n-m}C_{m}}$이고

$1$보다 작으면 ${{}_{2n}C_{m+1}\cdot {}_{2n-(m+1)}C_{m+1}}<{{}_{2n}C_{m}\cdot {}_{2n-m}C_{m}}$이다.

1. $\displaystyle{m+1 \leq 2n-2m-1 \Rightarrow m\leq \frac{2n-2}{3}}$일 때:

   $(m+1)^2 \leq (2n-2m-1)^2<(2n-2m)(2n-2m-1)$이므로,

   ${{}_{2n}C_{m+1}\cdot {}_{2n-(m+1)}C_{m+1}}<{{}_{2n}C_{m}\cdot {}_{2n-m}C_{m}}$이다.

• $\displaystyle{m+1 \geq 2n-2m \Rightarrow m\geq \frac{2n-1}{3}}$일 때:

   $(m+1)^2 \geq (2n-2m)^2>(2n-2m)(2n-2m-1)$이므로, 

   ${{}_{2n}C_{m+1}\cdot {}_{2n-(m+1)}C_{m+1}}>{{}_{2n}C_{m}\cdot {}_{2n-m}C_{m}}$이다.

따라서 구하는 $m$의 최댓값 $f(n)$은 다음 부등식을 만족시킨다.

$$\frac{2n-2}{3}<f(n)<\frac{2n-1}{3}$$

$$\therefore \lim_{n\rightarrow\infty}\frac{f(n)}{n}=\frac{2}{3}$$