[HORIZON] 전구의 불은 켜질까?

https://horizon.kias.re.kr/30621/

 

 

HORIZON의 12월 퍼즐이 재밌어 보여서 풀어봤다. 크리스마스 트리의 전구를 삼각형 모양으로 배치하고, 맨 아래층의 켜짐/꺼짐 상태로부터 맨 위층이 켜질지 꺼질지 예측하는 것이다.

 

https://horizon.kias.re.kr/30621/

 

전구는 위 그림처럼 아래 두 전구가 다르면 꺼지고 같으면 켜진다. 곰곰이 생각해보니 홀짝성 문제임을 알 수 있었다. (짝, 짝)이거나 (홀, 홀)이면 켜지고, 그 외에는 꺼진다. 즉, 합이 짝이면 켜지고 합이 홀이면 꺼진다.

 

문제는 다음과 같다. 2049층짜리 트리를 만들고, 1층 전구 상태를 원주율에 따라 결정한다. 1층의 n번째 전구는 원주율 소수점 아래 n번째 자리 숫자가 홀수이면 끄고 짝수이면 켠다. 이 트리의 맨 윗층 전구는 켜질까, 꺼질까?

 

---

 

원주율의 모든 숫자를 다 이용하도록 문제를 만들지는 않았을 것이다. 분명히 불변량 비슷한 무언가가 있을 것이다. 그리고 왜 하필 2049일까. 분명히 $2^n$과 연관이 있을 것이라 생각했다. 어차피 mod 2로 생각하는 것이니 0이면 켜지고 1이면 꺼지는 것으로 볼 수 있다. 이제 트리의 1층 전구 상태를 아래와 같이 두면,

 

$$
a_1 \vert a_2 \vert \cdots \vert a_n
$$

 

그 윗층은 아래와 같고,

 

$$
a_1+a_2 \vert a_2+a_3 \vert \cdots \vert a_{n-1}+a_n
$$

 

그 윗층은 아래와 같다.

 

$$
a_1+2a_2+a_3 \vert a_2+2a_3+a_4 \vert \cdots \vert a_{n-2}+2a_{n-1}+a_n
$$

 

계수가 파스칼의 삼각형이 된다. 따라서 꼭대기 층의 값은 아래와 같다.

 

$$
\sum_{k=0}^{n-1} \begin{pmatrix}n-1 \\ k\end{pmatrix} a_{k+1}
$$

 

주어진 n이 2049이므로 2049층의 값은 아래와 같다.

 

$$
\sum_{k=0}^{2^{11}} \begin{pmatrix}2^{11} \\ k\end{pmatrix} a_{k+1}
$$

 

처음에는 파스칼의 삼각형에 나오는 모든 숫자들이 양 끝을 빼고 짝수일까 생각했는데, 찾아보니 아니었다. 하지만 매의 눈으로 관찰하니 $2^n+1$ 층은 양 끝을 빼고 모두 짝수임이 보였다. 즉, 아래를 증명하면 되는 문제였다.

 

[Lemma] $m$이 1 이상의 정수일 때, $\begin{pmatrix}2^m \\ k\end{pmatrix}$는 $0<k<2^m$인 정수 $k$에 대해 짝수이다.

 

이 Lemma가 참이라면 2049층 트리 1층의 가운데는 꼭대기에 영향을 주지 못한다. 어차피 짝수가 곱해지기 때문이다. 양 끝의 합의 홀짝성에 의해서 꼭대기 층이 결정된다. 그런데 원주율의 소수점 아래 1번째는 1이고 2049번째는 7이다. 따라서 합은 8이고 꼭대기 전구는 켜진다.

 

아래는 Lemma의 증명이다.

 

$\begin{pmatrix}2^m \\ k\end{pmatrix}$는 아래와 같이 쓸 수 있다.

$$
\begin{pmatrix}2^m \\ k\end{pmatrix} = \frac{(2^m)!}{k! (2^m-k)!}
$$

이 값은 양의 정수이므로, 분모와 분자를 각각 소인수 분해했을 때 분모의 각 소인수에 대해 분자는 그 소인수의 지수가 분모보다 크거나 같아야 한다. 따라서 분자의 2의 지수가 분모의 2의 지수보다 큼을 보이면 된다. 우선 분자는 $(2^m)!$이므로 2의 지수는 아래와 같다.

$$
\frac{2^m}{2} + \frac{2^m}{4} + \cdots + \frac{2^m}{2^m} = 2^m-1
$$

분모 중 $k!$의 2의 지수를 따져보면,
$1, 2, ..., k$ 중 2의 배수는 최대 $k/2$개 있고,
$1, 2, ..., k$ 중 4의 배수는 최대 $k/4$개 있고,
$1, 2, ..., k$ 중 8의 배수는 최대 $k/8$개 있다.

 

이 과정을 통해 $k!$의 2의 지수는 아래 값보다 클 수 없음을 알 수 있는데,

$$
\frac{k}{2} + \frac{k}{4} + \frac{k}{8} + \cdots
$$

$k\neq0$이라는 조건에 의해 이 값은 $k$보다 작으므로, $k!$의 2의 지수는 최대 $k-1$이다. 같은 이유로, $k\neq2^m$이라는 조건에 의해 $(2^m-k)!$의 2의 지수는 최대 $2^m-k-1$이다. 따라서 분모의 2의 지수는 최대 $2^m-2$가 되어 분자보다 작으므로

$$
\begin{pmatrix}2^m \\ k\end{pmatrix} = \frac{(2^m)!}{k! (2^m-k)!}
$$

는 $0<k<2^m$에 대해서 항상 짝수이다.