대한수학회 16번
정보의 양 측정하기
문제 출제자 : 이지운 KAIST 수리과학부 교수
이번 대한수학회 문제는 기존 문제와 성향이 조금 다릅니다. 새로운 분야 문제에 도전해 보세요. 출제자인 이지운 KAIST 교수님에 따르면 1번은 비교적 쉽고, 2~3번은 어렵다고 합니다. 특히 3번은 교수님도 쉬운 풀이법을 알지 못한다면서, 고등학교 수학 수준으로 해결할 수 있는지 궁금하다고 밝혔습니다. 그럼 문제 나갑니다.
양의 정수 에 대해 수열
을 생각합니다. 만약
이고
이면 수열
를 확률분포로 생각할 수 있습니다. 확률분포
에 대해 평균
와 분산
를 다음과 같이 정의합니다.
한편, 확률분포 를 통해 알 수 있는 정보의 양은 엔트로피
를 통해 측정할 수 있으며, 이는 다음과 같이 정의합니다.
(여기서 log는 자연로그를 의미하며, 인 경우
으로 생각함.)
문제 1. 주어진 에 대해 엔트로피의 최댓값과 최솟값을 구하세요.
문제2. 어떤 양수 과
이 존재해 모든 양의 정수
과 확률분포
에 대해 다음이 성립함을 보이세요. (가능하다면
과
의 최솟값도 구하세요.)
문제3. 어떤 양수 와
가 존재해 모든 양의 정수
과 확률분포
에 대해 다음이 성립함을 보이세요. (가능하다면
와
의 최솟값도 구하세요.)
*알립니다!
소문제 (1)번이 수학장, 구머 친구에 의해 해결 됐어요!
------------------------------------------------------------------------------
------------------------------------------------------------------------------
1번 최솟값 : 0
p_n이 1 미만일 때는 -log p_n이 양수가 되기 때문에 모두 0이고 하나만 1일 때 최솟값이 나옵니다
1번 문제 최댓값입니다. 일단, 이 명제부터 증명하겠습니다. 이걸 증명하면 됩니다. 제가 여러 가지 경우 넣어봤는데 대충 성립합니다. 어쩄든 이걸 증명하면, 최댓값은
이 됩니다. 왜냐하면,
을 정리하면
이게 최대가 되려면
이 최소가 되야 하는데, 위의 저 정리를 증명하면
일 때 최소가 되고, 그러면
이 됩니다.
결론 : 이걸 먼저 증명하자.(구머님이 증명해주심)
이게 설명을 잘 못해서 여러 분들이 오해를 하시는 것 같은데 최댓값은 이 아니라
입니다.(2018.4.15)
음...... 잘 안 풀리네요. 접근부터가 잘못된 걸까요?
라 하자.
이렇게 생각해 봅시다.
오랜만입니다. a>b의 가정 하에 증명하였습니다.
비슷한 방식으로 최솟값을 구하려면 하나에 값을 몰아주면 되겠네요.
최솟값은 맨 위에서 0이라고 구했습니다. 제 생각 증명해주셔서 감사합니다.
그런데 3번째 줄에서 4번째 줄로 가는 것이 이해가 잘 않되는데, 제 지식이 적은 탓(저는 오래 살지 않았습니다.) 인가요...
(1+1/x)^x가 증가함수이기 때문입니다.
주정훈 멘토에게 여쭤본 결과, 수학장 친구와 구머 친구의 풀이 모두 정답입니다!
수학장님, a^a x b ^ b = (a+b)^(a+b) x (a - b)^(a-b) 명제가 참인 것을 알겠어요.
이 명제를 통해서 p_1 , p_2 ... , p_M = 1/M 일 때 (p_1)^(p_1) x ... x (p_M)^(p_M) 최소인 사실을 어떻게 알 수 있나요? 부탁합니다앗!
2번 문제 식의 좌변에 있는 의 값을 구했습니다. 일단,
라고 합시다. 양변에 로그를 취해 주면
(물론 이떄 밑은 e입니다.)
즉, 우리가 알고 싶은 건 k값이므로 양변에 로그를 없애주면
이 됩니다.
제가 전에 쓴것을 바탕으로 가겠습니다.
이라는 것을 증명해야 합니다.
이고, 그래서
이 됩니다. 그러면,
인 분산의 차이는
입니다.
또, 의 차이는 아무리 적어도
입니다.
즉, 약 가 차이 입니다.
에서는 너무 작아서 지수는 상관없습니다.
즉, 을 증명해야 하고, 즉,
이면 성립하기 때문에 증명 끝.
여러분 p를 이렇게 나눠봅시다.
1. 이 0인 경우 2. 0이 아닌 경우
만약 1번 경우라면, M에서 1을 빼고 을 없앱니다. 그래도 h(p)과 m(p), V(p)의 값은 차이가 없습니다.
그래서 맨 끝의 수가 0이 아닌 수가 될 때까지 맨 끝의 수를 없앱니다.
저번에 말했다시피 입니다. 이
의 최솟값이
이므로
의 최댓값은
입니다.
즉, m(p)에 차수가 1 이상인 M이 들어가기만 한다면,(즉 상수가 아니라면) 과
이 존재합니다. 그런데, 우리가 아까 p 맨 끝의 0들을 모두 제거했기 때문에 m(p)는 상수가 나올 수가 없습니다.
최솟값은 좀 더 해봐야 알 것 같은데, 이 정도로 증명을 끝낼 수 있을까요? 맨 마지막 문장이 좀 애매하긴 한 것 같지만.... 반증이나 오류 발견하면 알려주세요.
우선, 수학장님이 구하신 의 값은
가 맞습니다.
또한, 의 값은
일 때 M으로 최댓값을 가집니다.
이때의 의 값은
이므로
이렇게 생각할 수도 있을까요?
이라는 것을 증명해야 합니다.
의 최댓값은 1/M으로 수학장님 말대로 입니다. 그리고 분산의 성질로
가 있습니다.
Mathdragon 님의 의견과 같이 으로 할 수 있습니다. 즉, 분산
이라고 할 수 있습니다.
이고,
입니다.
그래서 정리하면 이라는 것을 증명해야 합니다.
그리고, 이고,
이기면 됩니다.
를 이용한 풀이를 조금 수정하겠습니다. 그리고
은 매우 작은 수로 0.000000001 또는 0.000000000000000000001이 될 수 있습니다. 그런데 0은 아니기 때문에
은 무한대가 아닙니다.
먼저, 는 짝으로
만큼 바뀝니다.
,
이라고 합시다. 그러면 분산의 차이는 전의 댓글에 말했듯이
입니다. 그리고,
입니다. 그것의 차이는 적어도
입니다. 즉,
이라는 것을 증명해야 합니다.
으로 묶으면
이라는 식이 나옵니다. 아무리 차가 커도
이기 때문에
이라는 식을 증명해야 합니다. 그리고
항이 없는 이유는 차이에는 상수항이 사라지기 때문입니다. 전개해보면
입니다.
즉, 이여야 합니다. 이제
의 값을 정해봅시다. 그 값은 매우 크지만 상수입니다. 바로
입니다. 그러면
이라는 식이 나오게 됩니다. 그 식의 참은 당연합니다.
의 값은 큰 문제가 없습니다. 아무 양수 입니다.
그리고, ,
으로 바꾸면 반복되어서 결국 모든
에 대해 참입니다.
즉, 증명 끝.
e^2h(p)의 차를 정확하게 계산해 보시길 바랍니다
그러는 방법이 있나요??
저는 그것의 차이를 진짜보다 적게 하였습니다. 그래야 전체의 차이가 커지기 때문입니다. (분수이기 때문입니다.)
차이가 진짜보다 커야 부등식에 의미가 있는거 아닌가요?
그래서 차이를 진짜보다 크게 하였습니다.
아 그러네요 ㅋㅋ
"그리고, ,
으로 바꾸면 반복되어서 결국 모든
에 대해 참입니다."
이 부분이 조금 걸리네요. 저번에도 말했듯이, 은 무한소가 될 수 밖에 없습니다.
이 0이 아니라고는 하시지만, 무한소는 0에 무한히 가까운, 이것보다 작은 양수가 존재하지 않는 양수라고 할 수 있습니다. 만약
이 무한소가 아니라면,
보다 작은 양수가 항상 존재하게 되고, 그러면 모든 p에 대해 증명이 불가능합니다.
결국, 이 무한소일 수 밖에 없다는 건데,
입니다. 귀납적으로 증명하는 것보다는, 귀류법이나 직접 증명이 필요할 것 같습니다.
3을 풀으려면 이 무한대로 가는 경우는 없다고 증명해야 합니다. 그 이유는 무한이 아니기 한다면
가 큰 수여라도 문제가 참이기 때문입니다.
을 간단히 한다면
이 됩니다. 이것이 무한대가 되는 경우는 없습니다. 단,
에 0이 포함되어서
가 '정하기 불가' 상황이 될때를 제외한다면 말이죠. (
은 결정 불가입니다. 논쟁이 일고 있는 부분이지요.) 이때는 문제로 다시 돌아가야 하며, 엔트로피의 정의로 돌아가야 합니다. 문제에서
이면
은 0이라고 가정했습니다. 즉, 모든 0들은
이 0이고, 즉 엔트로피
는 유한하게 되고, 즉
가 유한하게 됩니다. 그 뜻은
는 언제나 무한이 도지 않고, 증명 끝.
3번 풀이이고, 순서는..거꾸로입니다.
M->무한일 때 p1=1, 나머지는 0일때 V(p),M(p)를 구해보면 무한-무한 꼴이 되지 않습니다.
전댓글에도 언급했던것 같은데..
A2가 무한이 될수 있습니다.
그리고 패르마님 답을 얻기 전에 일부 값들을 미리 대입해봐서 식이 성립하는지 확인하는 작업이 필요하신 것 같습니다.
그리고 무한이 되는 경우도 있지만 안되는 경우또한 존재하고, (위 예시처럼) 따라서 m이 무한으로 수렴하지 않는다는 논리를 사용할 수 없습니다.
그동안 패르마님 풀이를 꽤 많이 봤었는데, 패르마님은 아직 무한에 대한 정확한 개념이 부족한 것 같습니다..이 문제는 딱히 무한을 써서 푸는 문제가 아닌것 같으니 같이 다른 방법을 생각해봐요.
아 최솟값 0은 실수입니다...
M이 무한대로 가도 양의 정수가 된다면 A2도 무한대로 갈 수 있습니다. 즉, 성립합니다.
문제에서 A2가 어떤 양수라 하지 않았나요? 무한이 되면 안될것 같아요.(애초에 그런식으로 풀리면 문제의 의미가..)
M도 양수라고 했습니다. 그래서 M도 무한으로 가면 않됩니다.
하지만 A2가 정해져 있다면 그 A2를 넘어서는 M은 무한이 아니라도 잡을 수 있습니다. 다른 논리가 필요할 것 같습니다.
...A2는 정해지는 것이 아닙니다 그리고 엔트로피의 최댔값은 M이 무한 으로 가면 0 이 됩니다. 그 이유는 이 0 이 되기때문입니다.
?엔트로피 최댓값은 1/m이 아닌데.. 최댓값은 -log(1/m)=log m아닌가요?
패르마님 지금 전혀 문제를 잘못 이해하신것 같은데 A2 B2는 고정된 값입니다..M이 어떻게 되든 방정식이 성립하는 A2를 찾는 게 문제 2 3번입니다.
문제 2,3 번을 풀기 위해서는 엔트로피인 가 유한하다는 것을 증명해야 합니다. 귀류법을 씁시다. 즉,
가 무한할 수 없다는 것을 증명합시다.
#1. 에 0이 있지 않은 경우 (
이진 않습니다.)
이 경우에는 엔트로피는 유한합니다. 그 이유는 일때
은 1보다 작고, 1보다 작은 수들을 계속 곱하면 1보다 작으며, 1보다 작은 수에
를 붙이면 그 값은 음수가 되고, 절대로
가 되지 않기 때문입니다.
#2. 에 0이 있는 경우 (
이진 않습니다.)
이경우에는 수학적 귀납법을 씁시다. 먼저, 이 2이면 당연히 성립합니다. 또,
과 그 전때 일때 언제나 성립한다고 합시다. 그리고
이면서
에 0이 있다고 합시다. 그러면 무네에 의해서
안의 0항은 없는 듯 만듯이 됩니다. 그 이유는
이
이 0이면 0이라고 문제에서 말했기 때문입니다. 즉,
에서 있는 0은 빼도 괜찮습니다. 즉, 전의 것들은 언제나 성립하기 때문에 #2도 성립합니다.
또, 은 엔트로피가 계산불가입니다.( 최댓값이
이여서..)
문제에서 plogp=0, 즉 logp^p=0이라고 가정한다는 것은 p^p=e^0=1이라고 계산하라는 것과 같습니다.
//윗분 댓 확인
그래도 유한하지 않나요?? 그리고우리가 문제의 식을 만족하는 수를 찾으라는 것입니다. 유리가 정해서 고정된 값으로 먼들기 때뮨입니다.
뭐가 유한한가요? 그리고 문제의 식을 만족하라는 건 뭔 수를 의미하나요? 구체적으로 주어를 생략하지 말고 말해주세요.
그리고 각경우마다 그 경우를 만족하는 A2 B2을 찾는게 아니라 모든 경우를 만족시키는 A2 B2를 찾는 거에요.. 애초에 문제가 패르마님이 생각한 그런 문제면 아무나 다 풀수 있을 건데 내질 않겠죠.
아... 그렇군뇨
그런데 A2과 B2의 최솟값은 뭔가요?? 그 둘의 합이 최소인가요, 아니면 그 둘중 하나가 가장 작은 것인가요??
의 최댓값은
입니다. 그리고
의 최댓값은
이
일때, 즉,
입니다. 그 뜻은 모든
에 관해서, 그리고
에 관해서
을 만족하는
와
가 존재한다는 것을 증명해야 합니다. 그리고,
입니다. 이 분산의 최솟값은
입니다.
이고 다른
일때이지요. 그 이유는 1을 재외한 모든
에 대해
이기 때문에 그러면
가 최소가 되고
,즉
가 최대가 되지 않기 때문입니다. 즉,
인
를 택하고 그래서 분산의 최솟값이 0입니다. (다른풀이:(확실하지는 않음.) 분산은 언제나
입니다. 즉,
의 최솟값인 0이 분산의 최솟값입니다. 단,
입니다. ) 그렇기 때문에
이라는 식이 나오고, 즉
입니다. 그 뜻은
는 어떤 양수이고,
이기만 하면 성립한다는 것을 알 수 있습니다. 그렇기 때문에 3번의 반절은 성립합니다.
또, 최솟값은 는 1, 그리고
는 0이라는 것을 알 수 있습니다.
안 맞는 것일지도 모르지만, 귀납법적 증명을 하겠습니다. 시작은 전의 댓글과 같습니다. 확률분포는 짝으로 만큼 바귄다는 것과
으로 부터 시작합니다. 그때 필요한것은 이항정리입니다. 그것의 증명은 다음과 같습니다:
라는 등식을 먼저 증명해야 합니다. 그것의 증명은 다음과 같습니다.
이고,
이며,
이다. 우변=
이제 이항정리를 증명합시다. 입니다.
입니다.
이기때문에
이라고 할 수 있습니다. 이항정리로 하면 (
을 뺏습니다.)
입니다.즉,
의 차이는
입니다. 분산은
입니다. 즉, 분산의 차이는
입니다.
이라는 것을 증명해야 합니다.
이 양변으로 지위집니다. 이제
를 취하면 됩니다. 그러면
이 나옵니다.
이 최댓값은
이기 때문에 대입하면
이 나옵니다.
의 최솟값은
으로,
입니다. 즉,
의 최솟값은
이 나옵니다. 그래서 3번의 반절이 증명됬습니다.
3번 풀이입니다...
비슷한 방법으로 2번을 풀 수 있다고 생각합니다.
(
=
로 묶일 수 있는 것)을 이용합니다.
오류가 있다면 알려주시길 바랍니다.
여백 패르마 친구의 답변 확인 중! 출제하신 교수님의 스케쥴로 답변이 늦어질 수 있다는 점 양해 부탁드려요!!
흐힝 언제 출제자의 제 풀이의 의견이 나올까요?? 틀렸다고 해도 의견을 알려주세요!!
답변이 지연돼서 미안해요, 여백 패르마 친구!
주정훈 멘토에 따르면 풀이가 잘못됐으니 다시 풀어보라는 의견이에요!!
뭐가 잘못되었나요??
어느 한 곳이 틀렸다기 보다 다른 방법으로 접근해 보라는 의견을 주셨어요! 새로운 방법으로 증명해 보는 게 어떨까요?
패르마님 참고로 이항정리같은 기본적인 것들은 굳이 증명 안하셔도 될것 같아요..패르마님 증명을 계속 읽다보니 너무 세세한 것까지 증명을 하려고 하는 경향이 있는 것 같아요.
여윽시 구머님 힌트 주니까 금방 푸시네요....
사실 푼건 아니고 그 힌트를 증면한거에요..아직 힌트를 써먹진 않았죠.
(그리고 구머가 누구죠??)
예... 구머가 아닌 kid milli님 제가 이어가볼게요. 이라고 하자. 이 때 a는 M의 값에 따라 달라지는 수이다.
이므로, a값은 M이 1일 때 0부터 시작하여 점점 감소하다가 -1 이하에서 수렴한다. 힌트의 정리에 의해
인데,
이므로
이다. 그런데 여기서 잘 안 풀리는 게
이라는 수식이 성립하지 않기 때문에......
제가 q_n을 잘못 정의한 거 같네요 kid milli님이 정의하신대로 해볼게요
q_n을 1보다 적당히 큰 실수 a를 어떻게 잘 정의해서 q_k=(1/k^a)/(1/1^a+1/2^a+....+1/n^a)로 정의하면 될듯요
아래 파일은 의 증명입니다. 상수항이 없어서 맞는지는 잘 모르겠습니다.
/resources/comment/2020/01/f57ea0a984396e15eaed2c08ac630b39.pdf
문제가 되는 극한값은 -inf가 아니라 -cM 인 것 같습니다. a가 0+로 다가가면 분모는 절댓값이 무한으로 커지고 분자는 일정한 상수가 되니까요. 그러면 이 되어 여전히 a가 존재한다고 할 수 있습니다. (혹시 여기에 오류가 있으면 지적 부탁드려요!)
그리고 LEMMA1의 증명에서 설명이 부족했던 부분 : 일 때
임은 그래프를 그리면 자명하게 성립하기 때문에 풀이를 생략했습니다. 만약 그래프를 그리지 않고 증명하고싶다면 미분을 통해 증명하면 됩니다.
답 맞는 것 같은데 언제 검토해주시나요?
다시 검토 요청할게요!
검토도 많이 밀려 있고 마감 기간이라 신속하게 확인을 못했어요 미안해요~!
김다인 멘토가 다시 봤는데, 함수 f가 a=1에서 정의가 안된다고 합니다~!
1-log(a)<0임을 보이는 데에서 오류가 생겼네요. 모든 M에 대해서 1-log(a)<0이 되는 게 아니라, 충분히 큰 M에 대해서는 a<e여서 1-log(a)<0이 된다고 보시면 될 거 같습니다.
충분히 큰 M이라고 가정해도 풀이에 큰 문제가 없는 이유는 이유는 h_1(M)이 maximum 값이 아닌 M의 개수가 유한하기 때문입니다. 그러한 M 값들에서 h(M,p)의 upper bound를 잡을 수 있고, 이를 {h_1(M), M은 양의 정수}의 upper bound과 비교하면 더 큰 값이 {h(M,p)}의 upper bound가 되게 됩니다.
충분히 큰 M에 대해서 a<e인 이유는 a^M -> 3.512...로 converge하기 때문입니다. Step.2에서 이 사실을 먼저 증명한 뒤에 나머지 풀이를 이어나가면 논리적으로도 큰 문제는 없을 것으로 보입니다.
우선 전체적으로 좋은 흐름의 풀이입니다.
다만 Step1 단계에서 최소인 State가 존재한다는 것이 확보되어야 논리를 펼칠 수 있습니다. 정확히 min값을 가지고 있는 것이 존재하기 않고, 어떤 값으로 수렴할 수도 있습니다. 이 부분에 대해 부등식을 다른 방법으로 접근해 보는 것이 좋을 것 같습니다. 첨언을 하자면 의 형태가 증명이 더 잘 보일 것 같네요. (이 식의 좌항은 따로 이름이 있습니다.)
또한 Step2에서 아마 변수명을 중간에 잘못 사용한 것 같네요. 인
는 1뿐입니다.
이 부분들만 고치면 좋은 풀이가 될 것 같습니다.
답변 달아주셔서 감사합니다 ㅠㅠㅠ
Step1에서 min값이 존재하지 않을 수 있다는 건 생각하지 못했내요. 지금 간단하게 드는 생각은 log(0)을 0으로 본다는 문제의 가정을 사용하면 min값이 존재함을 보일 수도는 있을 것 같습니다. Step2 에서는 제가 중간에 풀이를 수정했는데, 그 부분을 깜빡하고 수정하지 않은 것 같습니다. 맨 처음에는 으로 했다가 a가 1로 수렴하게 되서
으로 바꿨습니다.
대한수학회 16번의 3번 문제 풀이입니다. Log sum inequality를 이용해서 증명해보았습니다.
풀이 과정에 오류가 있는 거 같으면 댓글 달아주세요!
/resources/comment/2022/04/5e779681a9c56a819a9f6bc5923b2b40.pdf
파일 크기가 커져서 깨지네요.
그리고 연습장까지 같이 업로드되서 풀이를 다시 올립니다.
/resources/comment/2022/04/e0ceb014aad11bd572327c31464fa5bf.pdf
/resources/comment/2022/04/6dddda588e221492277ee5e4d974de9a.pdf
안녕하세요~ 어셈블 멘토에게 확인 요청했습니다~ 조금만 기다려주세요~!
첫 번째 사진의 두 번째 페이지에서 를 얻은 이후에
가 아니라
로 넘어가는 게 맞는 것 같은데, 다행히 풀이 진행에는 상수 조금 바뀌는 것을 제외하면 영향이 없습니다.
라는 중간 변수를 잡아서
와
를 연결했네요 잘 풀었습니다!
앗 그러네요
감사합니다~
혹시 해결 딱지는 언제 붙나요?
해결 딱지는 출제자인 교수님의 검토가 끝나야 붙습니다. 지금은 대학생 멘토의 검토만 끝난 상황입니다!
넵 알겠습니다!