2023 IOI 교육생 선발 면접 문제 - 2번

문제

무한한 격자판이 있다고 하자.

각 셀은 0 또는 1의 상태를 가질 수 있다.

각 셀은 단위 시간 마다 다음 규칙에 따라서 상태가 바뀐다.

• $t$ 시간에 어떤 셀의 위치를 $(r,c)$ 라고 할 때 $(r+1,c)$와 $(r,c+1)$ 위치의 셀이 모두 $1$ 이면 $t+1$시간에 $(r,c)$ 셀의 상태는 1이다.
• $t$ 시간에 어떤 셀의 위치를 $(r,c)$ 라고 할 때 $(r+1,c)$ 또는 $(r,c+1)$ 위치의 셀이 $0$ 이면 $t+1$시간에 $(r,c)$ 셀의 상태는 0이다.

초기에 상태가 1인 셀들이 유한하다고 할 때, 시간이 충분히 흐른다면 모든 셀들의 상태가 0이 됨을 보이시오.

예시 : 빨간색으로 색칠된 칸은 상태가 1인 셀을 나타낸다.

증명

$t$ 시간에 1인 셀의 개수를 $n_t$, 초기에 1인 셀의 개수를 $m=n_0$, 각 셀의 상태를 $s(r,c)$ 라고 하자.

그리고 다음과 같은 3가지 타입의 셀들을 생각해보자.

$$\begin{align}
s_a(r,c) &= s(r+1,c) \cdot s(r,c+1) \\
s_b(r,c) &= s(r+1,c) \cdot (1- s(r,c+1)) \\
s_c(r,c) &= (1- s(r+1,c) ) \cdot s(r,c+1)
\end{align}$$

• $s_a(r,c)$ : 오른쪽, 아래 셀 모두가 1인 셀들을 나타낸다.
• $s_b(r,c)$ : 아래 셀이 1이고 오른쪽 셀이 0인 셀들을 나타낸다.
• $s_c(r,c)$ : 아래 셀이 0이고 오른쪽 셀이 1인 셀들을 나타낸다.

그리고 시간 $t$에 $s_a(r,c)=1$인 셀의 개수를 $a_t$, $s_b(r,c)=1$인 셀의 개수를 $b_t$, $s_c(r,c)=1$인 셀의 개수를 $c_t$ 라고 하자.

이제 우리는 $a_t, b_t, c_t, n_t$ 간의 관계를 따질 것이다.

 

(아래가 1인 셀의 개수 + 오른쪽이 1인 셀의 개수)에 대해 생각해보자.

좀더 형식적으로는 $L= \{ (r,c) | s(r+1,c)=1 \; \forall \; r,c \}, \; R= \{ (r,c) | s(r,c+1)=1 \; \forall \; r,c \}$ 라고 할때 $|L|+|R|$을 나타낸다.

 

1. 자명하게 $|L|+|R| = n_t+n_t = 2n_t$ 이 성립한다.
2. 다음을 보자.
   (1) $ s_a(r,c)=1 \lor s_b(r,c)=1 \lor s_c(r,c)=1 $ 가 거짓인 경우 : $(r,c) \notin L, (r,c) \notin R$ 이다.
   (2) $ s_a(r,c)=1 \lor s_b(r,c)=1 \lor s_c(r,c)=1 $ 가 참인 경우 :
       (a) $s_a(r,c)=1$가 참인 경우 $(r,c) \in L, (r,c) \in R$ 이다.
       (b) $s_b(r,c)=1$ 가 참인 경우 $(r,c) \in L, (r,c) \notin R$ 이다.
       (c) $s_c(r,c)=1$ 가 참인 경우 $(r,c) \notin L, (r,c) \in R$ 이다.
       (참고) $s_a(r,c)=1, s_b(r,c)=1, s_c(r,c)=1 $ 중 어느 두개도 동시에 참일 수 없으므로 세 명제에 대해 진리집합들은
       서로 독립집합이다.
   
   (1)과 (2)의 (a), (b), (c) 에 의해 $|L|+|R| =  2a_t + b_t + c_t$ 이 성립한다.

1. 의 직관적인 이해를 위한 그림

2. 의 직관적인 이해를 위한 그림

 

1. 와 2. 에 의해 $a_t + \frac{b_t + c_t}{2} = n_t$ 이 성립한다.

그런데 문제의 규칙에 따라서 $a_t = n_{t+1}$ 도 성립한다.

 

그러므로 $n_t \geqslant n_{t+1} $ 가 성립하고, $n_t > 0$이면 $n_t>n_{t+1}$ 또한 성립한다.

($n_t > 0$ 인 경우 $ b_t + c_t  > 0$인 것은 어렵지 않게 증명이 가능하다.)

 

$n_0=m$이고 $n_t > 0 \Rightarrow n_t>n_{t+1}$ 이므로 충분히 큰 $t$에 대해 $n_t=0$ 이라는 것은 수학적 귀납법으로 보일 수 있다.