Larsif님 논술 문제 관련하여.

Question

http://orbi.kr/0002602799위 글에 있는 문제 이야기입니다.원래는 풀이 전체를 파일로 만들어서 올려야 하겠지만, 벌써 5시쯤인 관계로 간단하게 먼저 적어 봅니다.1의 (1)의 의미는 아마 다들 이해하셨겠지만, 어떻게 증명할지 헤매고 있으시겠지요. 그런데 증명해야 하는 것을 잘 살펴보면, n이 2 이상의 자연수일 때 성립하는 명제입니다. 따라서 n=2에서 시작하여 수학적귀납법을 이용할 수 있을 겁니다.n=2일 때의 증명은 f의 이계도함수가 0보다 크거나 같다는 사실을 잘 이용하고,(다시말해 미분과 관련된 것을 이용하라는 것이지요. 미분과 그래프의 성질을 철저하게 연관시켜서 이해하고 있는 분이라면 쉬울 겁니다) 람다_1 + 람다_2 = 1이라는 것을 잘 이용하면 됩니다. 일반적으로, 람다_1 + 람다_2 = 1이라는 등식이 성립할 경우, 풀이과정에 왼쪽 등식의 좌변이 나오면 우변으로 고치는 건 잘 하지만, 거꾸로 우변을 좌변으로 변형하는 것을 잘 떠올리기 힘듭니다. 제가 n=2일 때를 증명할 때는 위의 등식의 우변을 좌변으로 변형하는 것을 사용했었습니다.그 다음에는 n=k일 때 성립할 때 n=k+1일 때 성립한다는 것을 증명해야 하는군요. 그런데 그렇게 하려고 하니 람다_1 부터 람다_n까지의 합이 1이라는 것이 걸리는군요. 그럼에도, 수학적귀납법은 가능합니다. 수직선 위의 n개의 점 x_i에 질량 m_i가 있을 때 무게중심을 구하는 방법(다시말해 가중평균을 구하는 방법이면서, 이는 이산확률분포에서 평균을 구하는 것과도 관련이 있죠)을 내분점을 여러 번 이용하여 구할 수 있습니다. 그 방법을 여기에 이용하면 됩니다. 1의 (2) 또한 수학적귀납법으로 가능하기는 합니다. 다만 이게 괜찮은 방법인지 확신은 들지 않고, 다른 분들이 더 좋은 풀이를 알려 주기를 기대합니다.일단 수학적귀납법으로 푸는 것을 이야기하겠습니다. n=2일 때는 x_1 log(x_1) + ( 1 - x_1 ) log( 1 - x_1 ) ≥ x_1 log(y_1) + ( 1 - x_1 ) log( 1 - y_1 )을 증명해야 하죠. 몇 번 이야기했었지만, 변수가 두 개일 때를 잘 다룰 수 있는 방법을 우리는 모릅니다. 그러니 하나씩 고정하고 생각해 보아야 합니다. 즉, [ x_1을 0 이상 1 이하의 어떤 수로 고정해 두고, 임의의 y_1 (단, y_1 도 0 이상 1 이하)에 대하여 증명을 한 다음에, x_1을 0 이상 1 이하의 다른 수로 바꾸어 고정해도 마찬가지로 성립한다 ] 와 같은 식으로 증명을 해 나가자는 거지요.위에서 설명한 전략에 따라, x_1를 a, y_1을 z로 고친 뒤, 0 이상 1 이하의 어떠한 실수 a에 대하여도 a logz + (1-a) log(1-z)의 0 ≤ z ≤ 1에서의 최댓값이 a loga + (1-a) log(1-a)임을 증명하면 됩니다. 그런 다음, n=k일 때 성립하면 n=k+1일 때 성립하는 것을 증명할 때는, 1의 (1)에서 n=k일 때 성립하면 n=k+1일 때 성립하는 것을 증명한 것과 거의 같은 방법으로 했었습니다.1의 (3)은 의외로 간단합니다. 일단 기댓값은 y_i p_i의 총합이지요. 즉 y_i p_i의 총합이 p_i log( 1 / p_i )의 총합보다 크거나 같음을 보이면 됩니다. 부등식에서 서로 이항해 버리면 p_i log(p_i)의 총합이 p_i ( - y_i )의 총합보다 크거나 같음을 보이면 됩니다. 이 때, 1의 (1), 1의 (2), 제시문 중에서 단서를 찾아내어야 합니다. 일단 형태가 1의 (2)와 비슷해 보이니까 이를 이용해서 p_i log(p_i)의 총합보다 작거나 같은 [ p_i z_i의 총합 ] 을 찾을 수 있겠네요. 다만 z_i의 총합이 1이어야 하는데, 주어진 제시문 (나)를 어찌어찌하면 z_i를 잘 만들어낼 수 있을 겁니다. 그런 다음에, p_i z_i의 총합보다는 p_i w_i의 총합이 작고, 다시 p_i w_i의 총합보다는 p_i u_i의 총합이 작고... 와 같은 식으로 진행하면서 최종적으로 p_i ( - y_i ) 가 나오면 됩니다.2는 발상을 확 전환하여 풀 수 있습니다. Prefix code라는 대상이 조금 생소하지요? 왜 생소한가 하면, 보통 우리는 숫자를 보면 '오른쪽에서 왼쪽으로' 진행하면서 생각하기 마련이지만, 여기서는 '왼쪽에서 오른쪽으로' 진행하면서 생각해야 합니다. 그렇다면, 우리가 알고 있는 수학에서 정녕 '왼쪽에서 오른쪽으로' 진행하면서 생각하는 것이 없었는지 생각해 볼 필요가 있지요. 있습니다. 바로 소수가 그렇지요.그렇다면, Prefix code를 아예 이진법으로 표시한 소수로 생각해 볼 수 있습니다. 가령 코드 00은 0.00이고, 코드 10은 0.10이고, 코드 111은 0.111이고... 와 같은 식이지요. 이제 Prefix code의 특징을 잘 생각해 봅시다. 코드 00이 있을 때 코드 0011이 있으면 안 된다는 것을 어떻게 이해할 수 있을까요? 더 나아가, 코드 00이 있을 때 있으면 안 되는 코드는 어떤 것일까요?우선, 코드 00이 있다면 결국 코드 00 뒤에 임의의 숫자배열을 붙여 놓은 코드(0011, 001, 000101, ...)는 있으면 안 됩니다. 이를 '이진법으로 표시한 소수'로 생각한다면, 0.00 초과 0.01 미만의 이진수와 대응하는 코드는 있으면 안 된다는 것으로 표현할 수 있습니다.이를 일반화한다면, 어떤 코드 X_i가 있고, 코드 X가 이진법으로 표시한 소수 d_i에 대응하며 코드 X의 자리수가 y_i라면, d_i 초과 d_i + 2^( - y_i ) 미만의 소수에 대응하는 코드는 있으면 안 됩니다. 이를 다르게 생각하면, 코드 X와 d_i 이상 2^( - y_ i ) 미만이라는 구간이 서로 대응한다고 할 수 있겠지요. 그런데, 코드 X 외의 다른 코드는 d_i 이상 2^( - y_ i ) 미만의 소수와 대응하지 않으므로, 서로 다른 코드에 대응되는 구간은 겹치는 부분이 없습니다.그러면서, 어떤 코드이든지 그 코드가 대응하는 구간은 0 이상 1 미만이라는 구간에 포함됩니다. 즉, Prefix 코드로 나타낸 각각의 코드에 대응되는 각각의 구간들의 길이의 총합이 1 미만이어야 한다는 것이겠죠.(각각의 구간들의 교집합이 없으므로) 바로 앞의 문장이 증명하고자 하는 것입니다.

나카렌 · Accepted Answer

지금 보니, 위에서 서로 다른 코드에 대응되는 구간의 교집합이 공집합이라는 명제의 증명이 엄밀하지 못합니다. 귀류법을 써서 증명할 수 있는데, 아래에 댓글로 써 놓겠습니다.

나카렌 · Answer

코드 X_1이 이진법으로 표시한 소수 d_1에 대응하며 X_1의 자리수가 y_1이고, X_2는 d_1에 대응하며 자리수는 y_2라고 하겠습니다. 그리고 위에서 말한 방법에 의하여 코드 X_1에 대응되는 구간을 I_1, X_2에 대응되는 구간을 I_2라 하고, 두 구간의 교집합이 공집합이 아니라고 가정합시다.

이 때, y_1 = y_2라면 두 구간의 교집합은 반드시 공집합이어야 하므로, y_1 과 y_2가 같지 않은 경우입니다. 이 때 d_1 < d_2라고 두어도 일반성을 잃지 않습니다. 그 다음, 구간 I_1과 I_2의 교집합 내의 한 원소를 u라고 하면, u는 d_1 이상의 수이면서 d_2 이상의 수입니다. 즉, d_1 이상 u 이하의 수는 구간 I_1에 포함됩니다. 마찬가지로 d_2 이상 u 이하의 수는 구간 I_2에 포함됩니다. 따라서 d_2는 구간 I_1에 포함됩니다.

그런데 X_1, X_2가 Prefix Code라면, X_2와 대응하는 소수는 X_1과 대응하는 구간에 존재할 수 없습니다. 이에서 모순이 발생하였으므로, 귀류법에 의하여 X_1과 대응하는 구간 I_1, X_2와 대응하는 구간 I_2의 교집합은 공집합입니다.

Yoonaul · Answer

ㅠㅠ나카렌님 내일 블루투쓰로 제 문제좀 풀어주십셔;;

Larsif님 논술 문제 관련하여.

최근 게시글 · 더보기

오르비 캐스트