자연계열 1번

[가] 현대는 디지털 시대이다. 이는 연속적인 것을 다루는 아날로그 방식의 사고에서 이산적인 사고로 전환하였음을 의미한다. 그런데 이산적이라는 것은 유한하거나 무한수열과 같이 자연수의 집합과 일대일 대응 관계에 있는 대상들을 다루는 것을 의미한다. 오늘날 이산수학은 대학에서 컴퓨터과학, 그 밖의 공학이나, 통계학, 확률론 그리고 OR 등을 공부하고자 하는 학생들에게 필수과목이 되고 있다.

그런데 이산수학에서 가장 기초적이며 중요한 것 중 하나는 유한집합의 원소의 갯수를 세는 것이다. 이를 위해서는 ⓐ주어진 유한집합과 일대일 대응 관계에 있으면서(따라서 두 집합은 갯수가 같다), 보다 세기가 쉬운 다른 유한집합(들)을 생각하여 이를 해결해내는 것이 보통이다. 그런데 두 개의 집합 $\displaystyle C,D$ 가 일대일 대응이라는 것은 $\displaystyle C$에서 $\displaystyle D$로의 (또는 $\displaystyle D$에서 $\displaystyle C$로의) 전단사 함수가 존재한다는 것으로, 간단히 말하자면 하나의 집합에서 다른 집합으로의 함수가 존재하고 또 이의 역함수가 존재하는 것과 같다. ⓐ에 대한 예를 들자면 ⓑ $\displaystyle k$ 개의 원소로 이루어진 집합으로부터 중복을 허락하여 $\displaystyle n$개를 뽑아 만든 모든 중복집합의 갯수 $\displaystyle M(k,n)$ 을 구하는 문제를 생각할 수 있다(여기서 중복 집합에 있어서는 동일한 원소라 하더라도 서로 다르게 보나, 원소들의 순서는 고려하지 않는다). 가령 두 개의 원소로 이루어진 집합 $\displaystyle \{r,s\}$ 에서 중복을 허락하여 순서를 고려하지 않고 세 개를 뽑아 만든 중복집합은 다음과 같이 네 가지임을 알 수 있으므로 $\displaystyle M(2,3)=4$ 이다.$\displaystyle \{r,r,r\},\ \{r,r,s\},\ \{r,s,s\},\ \{s,s,s\}$

[나] 현재 정보화시대에 살고 있는 우리는 모든 정보가 비트 수열로 변환이 되어 처리된다는 것을 알고 있다. 컴퓨터에 비트 수열의 상태로 자료가 저장되고, 휴대폰을 통한 음성도 비트 수열 상태로 전송된다. 예를 들어, 8개의 축구팀이 있다면 각각의 팀을, 000, 001, 010, 011, 100, 101, 110, 111의 총 3개의 비트로 표현할 수 있다.

철수는 확률변수 $\displaystyle X$의 값을, 현옥은 확률변수 $\displaystyle Y$의 값을 알고 있으며, 철수와 현옥 모두 $\displaystyle X$와 $\displaystyle Y$의 비트 수열 표현 방법도 알고 있다. 현옥은 확률변수 $\displaystyle X$의 값을 알기 원한다. 이를 위해 철수와 현옥은 서로 메시지를 일정 회수만큼 교환한다. 메시지 전송이란 어느 한 사람이 다른 사람에게 비트 수열을 보내는 것을 뜻한다. 단, 메시지 하나의 비트수는 정해져 있지 않으나, 메시지 보내기의 회수가 정해지면, 전송되는 비트수의 총합의 최소화를 목표로 한다.

현옥이가 확률변수 $\displaystyle X$를 알기 위해 총 $\displaystyle m$회의 메시지를 전송하는 것을 허용할 때, 보내져야 하는 메시지들의 비트수의 총합의 최소값을 $\displaystyle C_{m}(X,Y)$ 라고 하자. 회수 $\displaystyle m$이 결정되면, 철수와 현옥 사이에 오고 가는 메시지의 방법이 정해지며, 이는 철수와 현옥 모두에게 공개된다. 예를 들어, 총 2회의 메시지 전송이 허용된다면, 첫 번째 메시지와 두 번째 메시지가 각각 의미하는 것을 철수와 현옥 모두가 안다.