재밌는 문제 - 중등KMO 2021 1번

 

 

풀이)

Step1)  \(A(st, s, t)=A(st-s, s, t) \) 임을 보이자. 

\(y_i=x_i+1 \) 이라 하면, \(y_1\geqslant y_2\geqslant ...\geqslant y_s\geqslant 0 \) 을 만족하고, 

\(y_1-y_s\leqslant t \) 도 만족한다. 또한,  \(y_1+y_2+...+y_s=st-s \) 이므로 이러한 쌍의 개수는

\(A(st-s, s, t) \) 와 같아진다.

 

Step2) \(A(st, s, t)=A(st-t, s, t) \) 임을 보이자

순서쌍 (\(x_1, x_2, ..., x_s)\)가 조건을 만족할 때, 순서쌍 \((x_2, x_3, ..., x_s, x_1-t)\) 가 항상 해가 됨을 보이자. 

우선, \(x_2\geqslant x_ 3 \geqslant ...\geqslant x_s \geqslant x_1-t\)가 성립한다. 

또한, \(x_1+...+x_s=st\leqslant sx_1\) 이므로, \(x_1-t\geqslant0\)이다. 

마지막으로 \(x_2-(x_1-t)=(x_2-x_1)+t\leqslant t\) 이므로 세 조건을 모두 만족한다.

따라서 일대일 대응이 성립하므로, \(A(st, s, t)=A(st-t, s, t)\)가 성립한다.