(나) 정보화시대에 살고 있는 우리는 모든 정보가 비트 수열로 변환되어 처리된 다는 것을 알고 있다. 컴퓨터에 비트 수열의 상태로 자료가 저장되고, 휴대폰을 통한 음성도 비트 수열 상태로 전송된다. 예를 들어, 8개의 축구팀이 있다면 각 각의 팀을 000, 001, 010, 011, 100, 101, 110, 111의 총 3개의 비트로 표현할 수 있다.
철수는 확률변수 의 값을, 현옥은 확률변수 의 값을 알고 있으며, 철수와 현옥 모두 와 의 비트 수열 표현 방법도 알고 있다. 현옥은 확률변수 의 값을 알기 원한다. 이를 위해 철수와 현옥은 서로 메시지를 일정 회수만큼 교환 한다. 메시지 전송이란 어느 한 사람이 다른 사람에게 비트 수열을 보내는 것을
8 서강대학교 수시(1)
8. 서강대학교 수시(1)
뜻한다. 단, 메시지 하나의 비트수는 정해져 있지 않으나, 메시지 보내기의 횟수 가 정해지면, 전송되는 비트의 총합의 최소화를 목표로 한다.
현옥이가 확률변수 를 알기 위해 총 회의 메시지를 전송하는 것을 허용할 때, 보내져야 하는 메시지들의 비트수의 총합의 최솟값을 하자. 회수
이 결정되면, 철수와 현옥 사이에 오고 가는 메시지의 방법이 정해지며, 이는 철수와 현옥에게 모두 공개된다. 예를 들어, 총 2회의 메시지가 허용된다면, 첫 번째 메시지와 두 번째 메시지가 각각 의미하는 것을 철수와 현옥 모두가 안다.
[1] 집합 를 개의 원소로 이루어진 집합으로부터 중복을 허락하여 개를 뽑아 만든 모든 중복집합들의 모임이라고 하자. 집합 와 아래의 집합 는 일대일 대응 관계에 있다. 이에 대해 논술하라(ⓐ 참조).
｛ ⋯ ∣ ⋯ 는 양의 정수 ⋯ ｝
[2] 위 [1]의 집합 와 집합 사이의 일대일 대응 관계를 이용하고, 또 집합 와 일대일 대응 관계에 있는 다른 구체적 대상의 예를 찾아서, 이들을 이용하여 ⓑ 의 을 구하는 문제에 대하여 논술하라.
[3] 현옥이 에서 축구 경기를 보다가 잠시 전화를 받기 위해 집에서 나갔다. 이 때 철수가 현옥의 집을 방문한다. 이 순간 축구 시합이 끝나고, 결과적으로 현 옥은 시합한 두 팀의 이름만 알고, 철수는 이긴 팀만 안다고 가정하자. 현옥은 어느 팀이 이겼는지를 철수로부터 알고자 한다. 총 개의 축구팀이 있다고 가 정하자. 단 한 번의 메시지 전송이 허용된다면, 철수는 당연히 이긴 팀 이름을 현옥에게 알려주어야 한다. 그런데 총 개의 팀이 있으므로 개의 비트수 로 모든 팀을 표현할 수 있기에 이다. 여기서 는 실수 보다 크거나 같은 최소의 정수를 나타낸다. 그렇다면 메시지를 전송하는 것이 2 회 가능하다고 할 때, 첫 번째와 두 번째 메시지의 전송 방향과, 와
를 비교하여 그 효율성에 관하여 논술하라.(힌트 : 철수와 현옥 모두 각각의 팀이 어떤 비트 수열로 표현되는지 알고 있다.)
제시문 분석
• 제시문 (가)에서는 일대일 대응관계를 이용하여, 원소의 개수를 세기가 곤란한 집합의 경우, 원소의 개수를 세기가 보다 쉬운 다른 유한집합을 생각하여 해결 할 수 있음을 말하고 있다.
• 제시문 (나)에서는 정보가 비트수열의 상태로 저장, 전송되는 상황을 예를 들어 제시하며, 두 사람 사이의 메시지 전송 시 비트의 총합의 최소화를 목표로 함을 언급하여 문제 상황을 설정하고 있다. 문자를 2회 만에 전송할 때 사용되는 비 트 수의 효율성을 계산하는 능력을 평가하는 문제이다.
논제 분석
• [1]은 중복조합의 경우의 수를 일대일 대응관계에 있는 집합의 원소의 개수를 이용하여 구할 수 있는가 하는 문제이다. 즉 서로 다른 개 중에서 중복을 허락 해서 개를 택하는 경우의 수는
⋯ ⋯ 는음이아닌정수
의 원소의 개수와 같으며 이는
⋯ ⋯ 는양의정수
의 원소의 개수와 같음을 일대일 대응관계를 이용하여 보일 수 있는가 하는 문제이다.
• [2]에서는 중복조합을 계산하는 방법을 구체적 대상을 이용해서 설명할 수 있는 가 하는 문제이다. 중복조합은 명칭은 조합이지만 실제로는 같은 것이 있는 순 열을 계산하는 방법과 같다. 즉, 개의 구분자 와 개의 ○를 일렬로 세우 는 경우의 수와 일대일 대응관계에 있음을 설명할 수 있는 지를 묻는 문제이다.
• [3]은 문자를 전송할 때 사용되는 비트 수의 최솟값이 전송횟수에 따라 어떻게 달라지는지를 묻는 문제이다. 제시문 (나)와 연결하여 생각해야 문제를 해결할 수 있다.
8. 서강대학교 수시(1)
배경지식 쌓기
• 중복조합
집합 에서 중복을 허용하여 6개를 추출하는 문제를 생각해 보자.
o o o l o o l o l o o o l o o o l l o o o o o o 위의 표에서 첫 번째 칸은 A를 3개, B를 2개, C를 1개 선택한 경우이고, 두 번째 칸은 A를 0개, B를 3개, C를 3개 선택한 경우이고, 세 번째 칸은 A를 0개, B를 0 개, C를 6개 선택한 경우이다. 위의 사실에서 서로 다른 3개를 구분하려면 구분자 '1'이 2개 필요하고 선택된 6개는 o로 표현할 수 있음을 알 수 있다. 그리고 그 경 우의 수는 ooooooll을 일렬로 배열하는 경우의 수와 같다.
위의 사실을 일반화하면, 서로 다른 개 중에서 중복을 허락해서 개를 택하는 경우의 수는 개의 구분자 와 개의 ○를 일렬로 세우는 경우의 수와 같음을 알 수 있다.
따라서 그 경우의 수는
로 계산할 수 있다.
이는
로 표현할 수 있다. 이것은 개의 위치 중에
개를 뽑아 구분자 를 위치시키는 것에 해당하기도 한다.
풀 어 보 기 풀어보기
1. 다음 식에 대하여 주어진 조건에 알맞은 정수해의 개수를 구하시오.
① ≥
② ≥
③ ≥
기 기 기 기 기 기 기 기 기 기 기 자료 자료 자료 자료 자료 자료 자료 자료 자료 자료 자료
읽 기 자료
읽 읽 읽 읽 읽 읽 읽 읽 읽 읽 읽 읽 읽
• 똑같아 보이는 무한집합이라도 서로 수준이 다르다.
무한집합에서 자연수 전체의 집합 과 일대일 대응이 되는 집합을 셀 수 있는 무한집합, 즉 가산집합(countable set)이라고 한다. 그러면 셀 수 없는 무한집합도 존재할까?
자연수 전체의 집합과 실수 전체의 집합 사이에는 일대일 대응을 정의할 수 없다. 왜냐하 면 먼저 자연수 전체 집합의 원소 개수와 0부터 1 사이의 모든 실수의 개수에 대해 비교해 보자. 만약 두 집합사이에 일대일 대응관계가 성립하는 함수가 존재한다고 가정해보자. 그러면 1, 2, 3, …에 대응하는 순서대로 다음과 같은 소수를 나열할 수 있다. 이 때, 각 자리 수는 0과 9 사이의 자연수이고, 유한소수는 무한소수 표현을 쓰는 것으로 한다. (예를 들면 0.6은 0.599999…로 쓴다.)
이제 위 그림의 대각선을 따라서 과 다른 자연수 을 고르고, 와 다른 자연 수 를, 와 다른 를 차례대로 골라서 다음과 같은 수 을 만든다.
⋯⋯ (즉, ⋯⋯)
새로 생겨난 는 위에 나열된 ①, ②, ③, ④, …의 소수 중 그 어느 것과도 일치 하지 않는다. 왜냐하면 이므로 ①과 은 소수 첫째 자리가 다른 수이기 때문 에 같은 소수가 될 수 없다. 또, 이므로 ②와 은 소수 둘째 자리가 다른 수 이기 때문에 같은 수가 되는 것은 불가능하다. 같은 이유로 와 위에 배열된 모든 소수는 같지 않다. 이는 자연수와 일대일대응에서 탈락된 소수가 있음을 보여준다.
그러므로 0과 1 사이의 실수 전체 집합과 자연수 전체 집합은 일대일대응이 될 수 없다. 이로써 자연수보다 0과 1 사이의 실수가 훨씬 많다는 것을 알 수 있다. 0과 1 사이의 실수 전체 집합의 원소 개수와 실수 전체 집합의 원소 개수가 같음을 보일 수도 있다.
이와 같이 자연수와 일대일 대응을 만들 수 없는 무한집합도 존재하고 이를 셀 수 없는 무한집합, 즉 비가산집합(uncountable set)이라 한다. 따라서 실수 전체의 집합
은 비가산무한집합이다.
8. 서강대학교 수시(1)
개요 짜기
답안 작성
예시답안 예시답안 예시답안 예시답안 예시답안 예시답안 예시답안 예시답안 예시답안 예시답안
풀어보기
1. 서로 다른 3개 중에서 중복을 허용하여 15개를 선택하는 문제와 같다. 즉, 을 선택하지 않은 경우, 이고, 두 번 선택한 경우 이다.
중복조합을 이용하면 2개의 구분자 과 15개의 0을 나열하는 경우의 수와 같으므 로
개이다.
2. , ≥ 이므로, , , 이라 고 하면 의 음이 아닌 정수해의 개수와 같으므로
개의 경 우가 있다.
3. , ≥ 이므로 , 이라고 하면
의 음이 아닌 정수해를 찾는 경우의 수와 같으므로 91개의 경우를 찾을 수 있다.
논제 1 집합 를 개의 원소로 이루어진 집합으로부터 중복을 허락하여 개를 뽑아 만든 모든 중복 집합들의 모임이라고 하자. 이 때 서로 다른 개의 원소 를 각각 ⋯라고 하자. ⋯를 선택하지 않으면, 에 대응시키 고, 한 번 뽑았을 때 에 대응시키고, ⋯, 번 뽑았을 때, 에 대응시키면, 집합 A와 집합
⋯ ⋯ 는 음이 아닌 정수
는 일대일 대응관계에 있다.여기서 에 대응시키면, ⋯
⋯ ⋯ 는 양의 정수
가 된다. 따라서 집합 와 집합 는 일대일 대응이다. 이것은 집합 와 집합 가 일대일 대응 관계에 있음을 의미한다.논제 2 A, B, C가 주어졌을 때, 중복을 허용해서 4개를 선택하는 경우를 다음 과 같이 생각해 보자. A, BB, C를 과 같이 생각할 수 있다. 즉, 서로 다른 세 가지를 구분하려면 ‘’이 두 개 필요하고 각각의 개수는 의 개수로 표현할 수 있다.
따라서 서로 다른 개 중에서 중복을 허락해서 개를 택하는 경우의 수는 개의 구분자 ‘ ’와 개의 ‘’을 일렬로 세우는 경우의 수와 일대일 대응관계에 있음 을 알 수 있다.
8. 서강대학교 수시(1)
따라서 그 경우의 수는 같은 것을 포함하는 순열의 수로써
로 계산할
수 있다. 그런데
로 표현할 수 있다.
이것은 집합 의 원소의 개수가
임을 의미한다.
논제 3 현옥이는 시합한 두 팀의 이름을 이미 알고 있고 그것을 비트로 표 현한 이진법의 수를 이미 알고 있고 철수는 이긴 팀의 이진법 표현을 알고 있다는 것이 가정이다. 만약에
이라고 하자. 시합한 두 팀은 서로 다른 팀이므로 비트 수가 다른 ≤ ≤ 번째 비트가 반드시 존재한다.따라서 현옥이는 번째 비트수를 질문하면 되고 철수는 그것을 한 비트(0 또는 1)로 답하면 된다. 그런데
이므로 까지의 수를 표현하기 위한따라서 현옥이는 번째 비트수를 질문하면 되고 철수는 그것을 한 비트(0 또는 1)로 답하면 된다. 그런데