2021 IMO Problem 6 [대수/조합]

문제: \(2\) 이상의 양의 정수 \(m\)에 대하여 정수들의 유한집합 \(A\)의 부분집합 \(B_1, B_2, ..., B_m\)은  

         각각의 \(k=1, 2, ..., m\)에 대하여 \(B_k\)의 모든 원소의 합이 \(m^k\)이다. 

         이 때, \( n(A)\geq m/2 \)임을 증명하여라.

 

 

2021 국제수학올림피아드 마지막 문제이다. 짧지만 풀기 어려운 문제다.

 

hint 1) 

\(m^1, m^2, ... , m^k\)를 보니 왠지 \(m\)진법이 떠오른다. 

 

hint 2)

더블카운팅을 이용해보자. 

 

풀이)

\(A=\left\{a_1, a_2, ..., a_n \right\}\)라고 하자.  

\(B_k\)는 원소의 합이 \(m^k\)이므로, 다음과 같이 표현 가능하다.

$$ m^k=\sum_{i=1}^{n}c_{ki}a_i, \quad c_{ki}\in \left\{ 0, 1\right\} $$

이제 \(m^1\)부터 \(m^m\)을 통해 구성하는 서로 다른 값을 세보자.  

\(m\)진법 표현의 유일성에 의해, 정확히 \(m^m\)개의 서로 다른 값을 갖는다. 

이들을 \(m\)진법 식으로 표현하면, 

$$  M=\sum_{j=1}^{m}\lambda _jm^j ,  \quad 0\leq \lambda _j\leq m-1  $$

위 식을 첫번째 식에 대입하여 정리하면, 

$$ M=\sum_{j=1}^{m}\lambda _jm^j=\sum_{j=1}^{m}\lambda _j\left ( \sum_{i=1}^{n}c_{ji}a_i \right )
= \sum_{i=1}^{n}\left ( \sum_{j=1}^{m}\lambda _jc_{ji} \right )a_i=\sum_{i=1}^{n}s_ia_i $$

이다. 이 때, \(s_i=\sum_{j=1}^{m}\lambda _jc_{ji}\leq m(m-1) \)이므로

\(  \sum_{i=1}^{n}s_ia_i \)가 만들 수 있는 서로 다른 값의 개수는 최대 \((m(m-1)+1)^n\)개가 된다.

(\(a_i\)들은 고정되어 있고, \(s_i\)를 0부터 \(m(m-1)\)들 중에 선택하여 값들을 생성할 수 있으므로..)

따라서 다음 부등식이 성립한다. 

$$ m^m < (m(m-1)+1)^n  < m^{2n}  \rightarrow \quad n>m/2 $$ 

증명 끝.