문제는 https://arca.live/b/math/23435496
사람 10000명이 있다.
그리고 서로 다른 100개의 주머니가 있다. 각각 1번 주머니, 2번 주머니, ... , 100번 주머니라고 하자.
그리고 N번째 주머니에는 N이라는 표시가 붙은 빨간공과 파란공이 각각 10000개씩 있다. N-빨간공, N-파란공이라고 하자.
이제 각각의 사람이
1번~100번 주머니까지, 각 주머니에서 공을 꺼내서 가져가는데
N번 주머니에 대해, 다음의 행동 중 하나를 한다.
1. N-빨간공 1개 가져가기,
2. N-파란공 1개 가져가기.
3. N-빨간공과 N-파란공 각각 1개씩 가져가기.
이때, 두 사람 A, B에 대해,
A가 가져간 공들로 N번째 항에 N번째 공이 놓이게 만든 나열 (1-공, 2-공, 3-공, ..., 100-공)들 중에
B가 가져간 공들로 만들 수 있는 나열이 존재할 때,
A와 B가 서로 완전히 겹치게 가져간 경우가 있다고 하자.
그리고 10000명의 전원이 공을 가져갔는데, 임의의 서로 다른 두 사람이 서로 완전히 겹치게 가져간 경우가 없었다.
좀 더 풀어서 설명하자면,
임의의 서로 다른 두 사람 A, B에 대해,
A가 가진 공들로 N번째 항에 N번째 공이 놓이는 유한 수열 a=(1-공, 2-공, 3-공, ..., 100-공)을 만들었을 때, B가 가져간 공들로는 이와 똑같은 수열 a를 만들 수 없다. 즉, B는 1-공, 2-공, ..., 100-공들 중 가져가지 않은 공이 존재한다.
(가령, A가 모든 주머니에서 빨간공만을 가져갔다고 해보자. 그러면, B가 가져간 공들로는 N-빨간공만으로 이루어진 수열을 만들 수 없다. 즉, B는 1~100번의 주머니 중 어느 하나 이상의 주머니에서 빨간공을 가져가지 않았다. )
그러면 이제 임의의 사람 A에 대해, h(A)=(1번~100번의 주머니들 중 A가 1개의 공만 꺼낸 주머니의 개수)라고 하고, u(A)=2^(-h(A))라고 하자. 그러면 다음을 증명하라.
모든 사람 A에 대해, u(A)의 합은 1이하이다. 즉, (A는 10000명의 사람들) ∑2^(-h(A)) ≤1
===================================================================
사람 숫자를 2명 이상으로 제한하는 경우, 주머니 1개에 대해서 성립하는 것은 자명합니다.
이제 n 개의 주머니에 대해 성립한다고 가정하고, 주머니가 n+1 개인 경우에 성립하는 것을 보이도록 하겠습니다.
n+1 개째의 주머니에서 빨간 공 1개만을 가져간 사람의 집합을 A = { A_1, A_2, ... A_a }
파란 공 1 개를 가져간 사람의 집합을 B = { B_1, B_2, ..., B_b }
두 색깔의 공 모두를 가져간 사람을 C = { C_1, C_2, ..., C_c } 라고 하고,
전체 사람의 집합 A∪B∪C = { A_1, A_2, ..., A_a, B_1, B_2, ..., B_b, C_1, C_2, ..., C_c } 중 서로 완전히 겹치는 경우는 없다고 하면
A∪B = { A_1, A_2, ..., A_a, C_1, C_2, ..., C_c } 중에 서로 완전히 겹치는 사람이 없는데, 이들은 n+1번째 주머니에서는 모두 겹치므로, n번째 주머니까지에서 서로 완전히 겹치지 않아야 합니다.
따라서 1~n 까지의 주머니만을 볼 때 ∑2^(-h(A)) + ∑2^(-h(C)) ≤1
그런데 A에 속하는 사람들은 n+1의 주머니에서 1개만을 꺼냈으므로, ∑2^(-h(A)) 의 실제 값은 1~n 까지의 주머니만을 볼 때의 값의 1/2 입니다. 따라서 2∑2^(-h(A)) + ∑2^(-h(C)) ≤1
마찬가지로 2∑2^(-h(B)) + ∑2^(-h(C)) ≤1
고로 2∑2^(-h(A)) + ∑2^(-h(C)) + 2∑2^(-h(B)) + ∑2^(-h(C)) ≤2
2∑2^(-h(A)) + 2∑2^(-h(B)) + 2∑2^(-h(C)) ≤2
∑2^(-h(A)) + ∑2^(-h(B)) + ∑2^(-h(C)) ≤1
따라서 주머니가 n 개인 경우에 성립한다면 n+1인 경우에도 성립합니다. (증명끝)
