2024 KMO 고등부 2차 풀이

#1. 중심이 $O$인 원 위에 서로 다른 세 점 $A$, $B$, $X$가 있고 세 점 $A$, $B$, $O$는 한 직선 위에 있지 않다. 삼각형 $ABO$의 외접원을 $\mathrm{\Omega }$라 할 때, 선분 $AX$, $BX$는 원 $\mathrm{\Omega }$와 각각 점 $C(\ne A)$, $D(\ne B)$에서 만난다. 점 $O$가 삼각형 $CXD$의 수심임을 보여라.

 

풀이. 

$\mathrm{\angle }OCX=\mathrm{\angle }ABO={90}^{\circ }-\mathrm{\angle }X$이므로 $CO\perp DX$, 마찬가지로 $DO\perp CX$입니다.

따라서 $O$는 $\mathrm{△}CXD$의 수심입니다. $◼$

 

(참고) $AB$와 $CD$가 antiparellel 관계이므로, $O$는 $\mathrm{△}ABX$의 외심인 동시에 $\mathrm{△}CXD$의 수심이 됩니다.

 

 

 

 

 

#2. 양의 정수의 수열 $\{x_n\}$에 대하여 $x_1=2$이고 각각의 양의 정수 $n$에 대하여 $x_{n+1}-x_n\in \{0,3\}$이면 $\{x_n\}$을 '개구리 수열'이라 하자. 다음 조건을 만족하는 실수 $d$를 모두 구하여라.

(조건) 두 개구리 수열 $\{a_n\}$, $\{b_n\}$에 대하여, $a_n=1000b_n$인 양의 정수 $n$이 존재하면 $a_m=d\cdot b_m$인 양의 정수 $m$이 존재한다.

 

답. $3k+1(k\in \mathbb{Z},0\le k\le 333)$

풀이. 먼저 다음 세 수열을 생각해봅시다.

$x_n=\mathbf{\text{min}}(3n-1,1000),y_n\equiv 2,z_n\equiv 5(n>1)$

$\{x_n\}$과 $\{y_n\}$, $\{x_n\}$과 $\{z_n\}$을 확인해보면 $d$는 $1000$ 이하의 $3k+1$꼴 양의 정수여야 함을 알 수 있습니다.

 

이제 임의의 $1000$ 이하의 $3k+1$꼴 양의 정수인 $d$가 (조건)을 만족하지 않는다고 가정해봅시다.

$1$과 $1000$은 자명하게 성립하니, $d\ne 1,1000$라고 가정합시다.

$a_1/b_1=1$, $a_n/b_n=1000$이므로 $a_t/b_t<d$, $a_{t+1}/b_{t+1}>d$인 $t$가 존재합니다.

 

그러면 $a_t\ge a_{t+1}-3>d\cdot b_{t+1}-3\ge d\cdot b_t-3$이 성립하고, 정리하면

$d\cdot b_t-3<a_t<d\cdot b_t$입니다.

 

이때 개구리 수열은 편차가 $3$의 배수이므로, 개구리 수열의 모든 항은 항상 $3k+2$꼴입니다. 그러면 직전 부등식에서 세 항이 모두 $3k+2$꼴이므로, 이웃한 $3k+2$꼴 정수 사이에 또 다른 $3k+2$꼴 정수가 있다는 뜻이 되어 모순입니다.

 

따라서 $d$는 조건을 만족합니다. $◼$

 

 

 

 

 

#3. 집합 $S$는 평면 상의 $2024$개의 점들로 구성되어 있고, 이 점들 중 어느 세 점도 한 직선 위에 있지 않다. 집합 $S$에 속하는 두 점을 지나는 직선 $l$이 다음 조건을 만족하면 $l$을 '약한 균등 직선'이라 하자.

(조건) 직선 $l$이 평면을 두 개의 부분으로 나눌 때, 한 부분은 $S$의 원소 중 정확히 $1010$개의 점을 포함하고 다른 부분은 정확히 $1012$개를 포함한다. (단, 각 부분은 $l$ 위의 어떤 점도 포함하지 않는다고 하자.)

 

집합 $S$의 두 점을 지나는 직선들 중 약한 균등 직선의 개수를 $w(S)$라 하자. $w(S)$가 가질 수 있는 값 중 가장 작은 것을 구하여라.

 

답. $\boxed{{\displaystyle 2023}}$

풀이. 편의상 $1011=n$으로 두겠습니다. 즉 평면 상에 $2n+2$개의 점이 있으며, 약한 균등 직선은 평면을 각각 $n-1$개, $n+1$개의 점으로 분할합니다.

 

기본적인 아이디어는 직선을 회전시키는 과정에서 중간값 정리를 적용하는 것입니다.(잘 알려진 발상입니다)

 

다음을 만족하는 $S$의 원소 $X$를 나쁜 점이라 부르겠습니다: 임의의 $X$가 아닌 $S$의 원소 $Y$에 대해, 직선 $XY$는 평면을 정확히 $n$개의 점으로 분할합니다.

 

Claim 1. $S$의 원소 $X$가 나쁜 점이 아니면, $X$를 지나는 약한 균등 직선이 $2$개 이상 존재한다.

pf. $X$가 나쁜 점이 아니므로, $X$가 아닌 $S$의 원소 $Y$를 잡아 직선 $XY$가 평면을 $n$개씩 분할하지 않게 할 수 있습니다.

 

만약 양쪽 평면의 점 개수가 $4$개 이상 차이 나면, 이 상태에서 직선을 $X$를 중심으로 ${180}^{\circ }$ 회전시키며 직선의 오른쪽 영역에 있는 점의 개수를 살펴봅시다. 이 값은 최대 $1$씩 변하며, $n-2$ 이하에서 $n+2$ 이상까지 변해야 합니다. 따라서 그 과정에서 점의 개수가 정확히 $n-1$개인 순간과 $n+1$개인 순간이 존재합니다. 즉, $X$를 지나는 약한 균등 직선이 $2$개 이상 존재합니다.

 

그렇지 않다면, 현재 직선은 평면을 각각 $n-1$개, $n+1$개로 분할하고 있는 상태입니다. 여기서 직선을 조금만 회전시켜 양쪽이 $n-1,n+2$개로 나뉘도록 해봅시다. 이 상태에서 다음 점을 만날 때까지 계속 회전시켜 봅시다. 이때 양쪽의 점 개수는 $(n-2,n+2)$ 또는 $(n-1,n+1)$개로 나뉘게 됩니다. 전자의 경우 위 문단의 논리를 그대로 적용할 수 있고, 후자의 경우에는 새로운 약한 균등 직선을 하나 찾은 것입니다. 어떤 경우든 $X$를 지나는 약할 균등 직선이 $2$개 이상 존재합니다. $◻$

 

그러면 자연스럽게 나쁜 점의 개수를 세는 것이 다음 목표가 됩니다.

 

Claim 2. $S$의 원소 중 나쁜 점은 최대 $1$개이다.

pf. 아니라 가정하고, $S$의 두 나쁜 점 $A,B$와 이들을 지나는 직선 $l$을 잡습니다. 직선 $l$은 $A$에 의해 두 부분으로 나뉘게 되는데, $B$가 포함된 부분을 '뒤', 포함되지 않은 부분을 '앞'이라 정의하겠습니다. 이제 $A$를 중심으로 $l$을 회전시켜 보겠습니다. 나쁜 점의 정의에 따라 $l$은 $S$의 또 다른 점을 지나는 임의의 순간에 평면을 정확히 $n$개씩 분할해야 합니다. 이렇게 되기 위해서는, $l$을 회전하는 과정에서 $S$의 원소들이 $l$의 앞과 뒤에 번갈아가며 닿아야 합니다. (직접 그려보시면 쉽게 알 수 있습니다) 이 성질이 $B$에 대해서도 똑같이 성립해야 하는데, 이 과정에서 모순이 발생합니다.

 

$l$을 $A$를 중심으로 시계방향으로 회전했을 때 처음으로 $l$의 앞과 닿는 점을 $P$라 합시다. ($B$가 $l$의 뒤에 있으므로 그 다음은 앞에서 만나야 합니다) 이제 $l$을 $B$를 중심으로 시계방향으로 회전시킬 때 처음 만나는 점 $Q$가 존재하는데, $A$가 $B$에 대해서 '앞'에 있었으므로 $Q$는 $B$에 대해서 '뒤'에 있어야 합니다. 하지만 $P$의 정의상 색칠된 영역에는 $S$의 원소가 존재할 수 없으며, $Q$의 정의에 따라 $Q$는 무조건 색칠된 영역에 들어가게 되어 모순입니다. $◻$

 

따라서 나쁜 점은 최대 $1$개이며, $|S|-1$개 이상의 나머지 점들은 각각 적어도 $2$개 이상의 약한 균등 직선을 가집니다. 이를 일종의 그래프로 생각하면(두 점을 이은 직선이 약한 균등 직선일 경우 변으로 연결합니다), 모든 점의 차수가 $2$ 이상이므로 변의 개수가 $|S|-1$개 이상임이 보장됩니다. 따라서 약한 균등 직선은 적어도 $|S|-1$개 이상 존재합니다.

 

실례는, 정$2023$각형과 중심으로 구성된 집합입니다. $◼$

 

 

 

 

 

#4. 다음 조건을 만족하는 최고차항의 계수가 $1$인 $k$차 정수 계수 다항식 $f(x)$가 존재하는 가장 작은 양의 정수 $k(\ge 2)$를 구하여라.

(조건) 임의의 두 정수 $m,n$에 대하여, $f(m)-f(n)$이 $31$의 배수이면 $m-n$은 $31$의 배수이다.

 

답. $\boxed{{\displaystyle 7}}$

풀이. $p=31$로 둡시다. $f(x)=x^7$이 성립하므로, $6$ 이하의 차수에 대해서만 확인해보면 됩니다. ($7$과 $p-1$이 서로소이므로, $x$를 원시근의 거듭제곱으로 표현했을 때 모든 수를 표현합니다.) 

 

$f({\mathbb{Z}}_p)={\mathbb{Z}}_p$을 반증하는 가장 간단한 방법은 불변량을 이용하는 것입니다.

단순히 함수들을 더한다고 생각하면, ${\displaystyle \sum _{i=0}^{p-1}{x}^k}$의 값이 필요합니다.

 

Lemma. $$\sum _{i=0}^{p-1}{x}^k\equiv \{\begin{array}{ll}0& k\mid p-1\\ -1& k\nmid p-1\end{array}$$

pf. 모든 원소들을 원시근의 거듭제곱으로 표현하면 등비급수로 계산 가능합니다. $◻$

 

이를 이용하면 $k\mid p-1$일 때는 ${\displaystyle \sum _{i=0}^{p-1}f(i{)}^{\frac{p-1}{k}}}$를 계산하여 모순을 쉽게 보일 수 있습니다. 남은 경우인 $4$차 함수는 조금 더(?) 잘해주면 됩니다.

 

적당한 평행이동을 통해 $f(x)=x^4+a{x}^2+bx$로 둡시다. 이때 ${\displaystyle \sum _{i=0}^{p-1}f(i{)}^8}$과 ${\displaystyle \sum _{i=0}^{p-1}f(i{)}^9}$을 계산해 $x^{30}$의 계수를 보면 $a,b$가 $p$의 배수임을 확인할 수 있습니다. $f(x)=x^4$은 당연히 모순입니다. $◼$

 

 

 

 

 

#5. 임의의 양의 실수 $a_1,a_2,\cdots ,a_{99}$에 대하여 부등식

$$\sum _{k=1}^{99}\frac{a_{k+1}}{a_k+a_{k+1}+a_{k+2}}<M$$

을 만족하는 가장 작은 실수 $M$을 구하여라. (단, $a_{100}=a_1,a_{101}=a_2$)

 

답. $\boxed{{\displaystyle 49}}$

풀이. 실례는 $0$과 $1$을 번갈아 배치하면 됩니다.

계산값이 크기의 대략 절반이니, 항을 두 개씩 묶어보면 다음과 같은 관찰을 할 수 있습니다.

$$\frac{a_{k+1}}{a_k+a_{k+1}+a_{k+2}}+\frac{a_{k+2}}{a_{k+1}+a_{k+2}+a_{k+3}}<\frac{a_{k+1}}{a_{k+1}+a_{k+2}}+\frac{a_{k+2}}{a_{k+1}+a_{k+2}}=1$$

 

이렇게 끝났으면 좋았으나, $99$가 홀수이기 때문에 항이 하나 남습니다. 따라서 한 그룹은 3개로 묶어 처리를 해주어야 합니다. 이때 $a_k\ge a_{k+3},a_{k+1}\le a_{k+4}$인 $k$를 찾을 수 있습니다.(귀류법으로 쉽게 보일 수 있습니다)

그러면 이러한 $k$에 대해

$$\frac{a_{k+1}}{a_k+a_{k+1}+a_{k+2}}+\frac{a_{k+2}}{a_{k+1}+a_{k+2}+a_{k+3}}+\frac{a_{k+3}}{a_{k+2}+a_{k+3}+a_{k+4}}\le \frac{a_{k+1}}{a_{k+3}+a_{k+1}+a_{k+2}}+\frac{a_{k+2}}{a_{k+1}+a_{k+2}+a_{k+3}}+\frac{a_{k+3}}{a_{k+2}+a_{k+3}+a_{k+1}}=1$$

이므로 전체 합이 $49$ 미만임을 확인할 수 있습니다. $◼$

 

 

 

 

 

#6. 양의 정수 $n$에 대하여 $f(n)$을 $n$ 이하의 양의 정수 중 $n$과 서로소인 것의 개수라 하자. 예를 들어, $10$과 서로소인 $10$ 이하의 양의 정수는 $1,3,7,9$이므로 $f(10)=4$이다. 양의 정수 $n$에 대하여 $g(n)=\lfloor \frac{2024}{n}\rfloor$라 할 때, 다음 식의 값을 구하여라. (단, $\lfloor a\rfloor$는 $a$를 넘지 않는 최대 정수)

$$\sum _{n=1}^{2024}(1-(-1{)}^{g(n)})f(n)$$

 

답. $\boxed{{\displaystyle 2\cdot {2012}^2}}$

풀이 1. 앞항을 간단히 정리해봅시다. 결국 $g(n)$이 홀수일 때만 살아남으므로, $g(n)$을 $2$로 나눈 나머지로 표현할 수 있습니다. 정확히, $(1-(-1{)}^{g(n)})=2(g(n)-2\lfloor \frac{g(n)}{2}\rfloor )=2(\lfloor \frac{2024}{n}\rfloor -2\lfloor \frac{1012}{n}\rfloor )$입니다. (*)

 

그런데 ${\displaystyle \sum _{n=1}^{2024}\lfloor \frac{2024}{n}\rfloor \varphi (n)=\sum _{n=1}^{2024}\sum _{n\mid m}\varphi (n)=\sum _{m=1}^{2024}\sum _{n\mid m}\varphi (n)=\sum _{m=1}^{2024}m}$입니다.

비슷하게, ${\displaystyle \sum _{n=1}^{2024}\lfloor \frac{1012}{n}\rfloor \varphi (n)=\sum _{m=1}^{1012}m}$입니다. 이를 대입하면 답이 나옵니다. $◼$

 

(*) $\lfloor {\displaystyle \frac{\lfloor \frac{n}{p}\rfloor }{q}}\rfloor =\lfloor {\displaystyle \frac{n}{pq}\rfloor }$가 성립합니다.

 

풀이 2. 이렇게도(?) 풀 수 있습니다. 곱산술함수의 특성을 이렇게까지도 이용해볼 수 있습니다.

함수 $f$에 대해 ${\displaystyle \sum _{k=1}^{n}f(k)=S_f(n)}$이라 정의합시다.

$$\sum _{n=1}^{2024}(1-(-1{)}^{g(n)})f(n)=2\sum _{n=1}^{2024}(-1{)}^{n-1}{S}_{\varphi }(\lfloor \frac{2024}{n}\rfloor )$$

$$=2\sum _{n=1}^{2024}(-1{)}^{n-1}\sum _{m=1}^{\lfloor 2024/n\rfloor }\varphi (m)$$

$$=2\sum _{n=1}^{2024}(-1{)}^{n-1}\sum _{m=1}^{\lfloor 2024/n\rfloor }\sum _{d\mid m}d\mu (\frac{n}{d})$$

$$=2\sum _{nde\le 2024}(-1{)}^{n-1}d\mu (e)$$

$$=2\sum _{ne\le 2024}(-1{)}^{n-1}\mu (e)\sum _{d=1}^{\lfloor \frac{2024}{ne}\rfloor }d=2\sum _{ne\le 2024}(-1{)}^{n-1}\mu (e)S_{id}(\lfloor \frac{2024}{ne}\rfloor )$$

$$=2\sum _{k=1}^{2024}{S}_{id}(\lfloor \frac{2024}{k}\rfloor )\sum _{d\mid k}(-1{)}^{d-1}\mu (\frac{k}{d})$$

 

Fact. $h(n)=(-1{)}^{n-1}$은 곱산술함수입니다. 또한, 뫼비우스 반전함수 $H(n)=\{\begin{array}{ll}1& n=1\\ -2& n=2\\ 0& n\ge 3\end{array}$ 입니다.

pf. 첫번째는 자명하고, 뫼비우스 반전 $H$가 곱산술함수라는 사실을 이용해 소수의 거듭제곱에 대해서만 계산하면 됩니다. $◻$

 

따라서 계산을 계속하면, 준식은

$$2\sum _{k=1}^{2024}{S}_{id}(\lfloor \frac{2024}{k}\rfloor )H(k)$$

$$=2S_{id}(\lfloor \frac{2024}{1}\rfloor )-4S_{id}(\lfloor \frac{2024}{2}\rfloor )$$

$$=2\sum _{k=1}^{1012}((k+1012)-k)=2\cdot {2012}^2$$

입니다. $◼$

 

 

 

 

 

#7. 예각삼각형 $ABC$의 수심을 지나고 점 $A$를 지나지 않는 직선 $l$이 직선 $BC$와 점 $P(\ne B,C)$에서 만나고, 점 $A$를 지나고 $l$과 수직인 직선이 삼각형 $ABC$의 외접원과 점 $R(\ne A)$에서 만난다. 점 $A,B$에서 $l$에 내린 수선의 발을 각각 $A^{\prime },B^{\prime }$이라 하고, 점 $A^{\prime }$을 지나고 직선 $BC$와 수직인 직선을 $l_1$, 점 $B^{\prime }$을 지나고 직선 $CA$와 수직인 직선을 $l_2$라 하자. 두 직선 $l_1$과 $l_2$의 교점을 $l$에 대하여 대칭시킨 점을 $Q$라 할 때, $\mathrm{\angle }PQR={90}^{\circ }$임을 보여라.

 

풀이. 

직선 $A{A}^{\prime }$과 $BC$의 교점을 $T$라 하겠습니다. 각 계산을 해보면

$$\mathrm{\angle }Q{B}^{\prime }{A}^{\prime }=\mathrm{\angle }{Q}^{\prime }{B}^{\prime }{A}^{\prime }=\mathrm{\angle }{A}^{\prime }AC=\mathrm{\angle }RBT$$

$$\mathrm{\angle }Q{A}^{\prime }{B}^{\prime }=\mathrm{\angle }{Q}^{\prime }{A}^{\prime }{B}^{\prime }={90}^{\circ }-\mathrm{\angle }P=\mathrm{\angle }RTB$$

이므로 $\mathrm{△}Q{B}^{\prime }{A}^{\prime }\sim \mathrm{△}RBT(AA)$입니다. 

 

여기서 $B{B}^{\prime }\parallel T{A}^{\prime }$이므로 $B^{\prime }{A}^{\prime }/B^{\prime }P=BT/BP$이고, 따라서 $\mathrm{△}{B}^{\prime }QP\sim \mathrm{△}BRP$가 성립합니다.

나선 닮음의 성질에 따라 $\mathrm{△}PB{B}^{\prime }\sim \mathrm{△}PRQ$이고, $\mathrm{\angle }PQR=\mathrm{\angle }P{B}^{\prime }B={90}^{\circ }$입니다. $◼$

 

(참고) 이렇듯 적절한 닮음을 찾아 비례 관계나 나선 닮음으로 확장시키는 아이디어가 계속 출제되고 있습니다.

 

 

 

 

 

#8. 칠판에 $10$개의 수 $1,2,\cdots ,10$이 적혀있고, 나현이는 다음과 같은 시행을 반복한다.

(시행) 칠판에 적혀있는 $10$개의 수 중 서로 약수와 배수의 관계가 아닌 두 수를 골라 지우고 이 두 수의 최대공약수와 최소공배수를 칠판에 적는다.

 

칠판에 적혀있는 $10$개의 수 중 임의의 두 수가 약수와 배수의 관계를 이루면 이 시행은 그만둔다. 나현이는 위의 시행을 최대 몇 번 할 수 있겠는가?

 

답. $\boxed{{\displaystyle 18}}$

풀이. 먼저 서술의 편의를 위해 여러가지를 정의하도록 하겠습니다. 일단 각 수를 소인수분해 시 $2,3,5,7$의 지수로 이루어진 네 수의 순서쌍으로 표현하겠습니다. (ex. $12=(2,1,0,0)$) 이 수들을 모아 $4\times 10$ 표에 정리하도록 하겠습니다. 이때 아래(4행)에서부터 $7,5,3,2$의 지수입니다. 또한, $10$개의 수들을 사전 순으로 정렬하겠습니다. 즉 $7$의 지수, $5$의 지수, $3$의 지수, $2$의 지수 순으로 커지게 정렬합니다. 그 결과는 아래와 같습니다.

 

0	0	0	0	0	0	0	0	0	1
0	0	0	0	0	0	0	1	1	0
0	0	0	0	1	1	2	0	0	0
0	1	2	3	0	1	0	0	1	0

($1$열부터 $10$열까지 각각 $1,2,4,8,3,6,9,5,10,7$을 나타냅니다)

 

어떤 순서쌍 $a$가 $b$를 majorize한다는 것은, $a$의 모든 성분이 $b$의 성분보다 크거나 같음을 의미합니다. 본문에 있는 "약수와 배수의 관계"가 이에 해당됩니다. 시행을 할 경우, 두 열을 골라 왼쪽 열에는 최대공약수, 오른쪽 열에는 최소공배수를 적습니다. 이때 최대공약수는 두 순서쌍의 최솟값, 최소공배수는 두 순서쌍의 최댓값 연산으로 계산합니다. (이때 수들의 정렬 관계는 오로지 초기 상태를 위한 것이며, 시행 과정에서 정렬은 얼마든지 깨질 수 있습니다)

 

아래에서부터 $k$개의 행만 선택해 사전순 정렬한 표를 $k$차 표라 정의하겠습니다. 예를 들어 $3$차 표에서 게임을 진행한다는 것은 $7$의 지수를 무시하고 연산을 하겠다는 뜻입니다. 또한 $k$차 표에서 두 개의 열을 골라 시행을 하려 할 때, 만약 두 열의 하위 $k-1$개 성분이 majorize 관계이면 이를 $(k-1)$-majorize 관계, 아닐 경우 not $(k-1)$-majorize 관계라 정의하겠습니다. 예를 들어 9열과 10열을 $3$-majorize 관계입니다($(1,0,1)>(0,0,0)$). 

 

이때 다음 성질들이 성립합니다.

1. 중간 시행 과정과 무관하게, 최종 시행 결과는 열들을 잘 재배열했을 때 각 행이 정렬된 상태이다.
2. $4$차 표에서 $10$열과 나머지 간의 시행은 최대 $6$번이다.
3. $3$차 표에서 $8,9$열과 나머지 간의 시행은 최대 $7$번이다.
4. $4$차 표에서 게임을 진행할 때, ($10$열을 제외한 열끼리의 시행 횟수) $+$ ($10$열과 나머지 열 간의 not $3$-majorize 시행 횟수) $\le$ ($3$차 표에서의 최대 시행 횟수)이다.
5. $3$차 표에서 게임을 진행할 때, ($8,9$열끼리 혹은 나머지 열끼리의 시행 횟수) $+$ ($8,9$열과 나머지 열 간의 not $2$-majorize 시행 횟수) $\le$ ($2$차 표에서의 최대 시행 횟수)이다.
6. $2$차 표에서 가능한 시행 횟수는 최대 $8$번이다.

하나씩 증명해봅시다.

1. 시행을 할 때마다 각 행 별로 inversion 수가 감소하므로, 결국에는 모든 행이 정렬된 상태로 종료되어야 합니다. $◻$

2. $4$차 표에서의 $10$열과 다른 열을 교환할 경우, $10$열이 이미 $7$의 지수가 앞서므로 뒤쳐지는 지수도 존재해야 합니다(두 열이 majorize 관계에 있지 않아야 하기 때문입니다). 시행 결과 $10$열의 아래 세 성분 중 적어도 한 항은 증가하게 됩니다. $10$열에는 무조건적으로 최소공배수만 쓰이므로, 1번에 따라 $10$열의 최종 상태는 $(1,1,2,3)$입니다. 아래 세 성분의 합이 $0$에서 $6$으로 변하므로, 최대 $6$번만 선택됩니다. $◻$

3. 2번과 마찬가지로 증명할 수 있습니다. $3$차 표에서 $8,9$열은 $(1,0,0),(1,0,1)$에서 $(1,1,2),(1,2,3)$으로 변하게 됩니다. 성분의 합의 차이를 보면 최대 $7$번입니다. $◻$

4. $4$차 표에서 게임을 진행할 때 아래 세 행이 어떻게 변하는지 살펴봅시다. $10$열을 제외한 열끼리 시행하는 경우에는, $7$의 지수가 둘 다 $0$이므로 $3$차 표에서 시행하는 것과 완전히 동일합니다. $10$열을 선택하여 시행하는 경우에는, not $3$-majorize인 경우에만 $3$차 표에서 유의미한 시행이 됩니다. 또한, $4$차 표에서 게임이 종료되었을 때에는 $3$차 표에서 또한 더 이상 시행을 할 수 없는 상태가 됩니다. ($\because$ not-majorize 관계의 두 열은 성분을 확장해도 not-majorize 관계입니다) 따라서 4번의 부등식이 성립합니다. $◻$

5. $3$차 표에 대해서 4번의 논리를 똑같이 적용하면 됩니다. $◻$

6. 어차피 선택되지 않는 $(0,0)$을 제외하고 $2$차 표는 다음과 같이 구성됩니다.

0	0	0	0	1	1	2
1	1	2	3	0	1	0

아래 행은 결과적으로 $0,0,1,1,1,2,3$으로 정렬되어야 합니다. 위 행의 값에 따라 열들을 세 그룹으로 나누면, 시행 시 첫번째 그룹은 항상 아래 행의 숫자가 감소하며 마지막 그룹은 항상 아래 행의 숫자가 증가합니다. 첫번째 그룹은 아래 행 숫자의 합이 $5$만큼 감소해야 하고, 세번째 그룹은 아래 행 숫자의 합이 $3$만큼 증가해야 합니다. 따라서 최대 $8$번의 시행이 가능합니다. $◻$

 

이 사실들을 이용하면, 먼저 4번에 의해 

($4$차 표 시행 횟수)$=$ ($10$열을 제외한 열끼리의 시행 횟수)$+$ ($10$열과 나머지 열 간의 시행 횟수)

$\le$ ($10$열과 나머지 열 간의 $3$-majorize 시행 횟수)$+$ ($3$차 표에서의 최대 시행 횟수)입니다.

 

5번에 의해

($3$차 표 시행 횟수)$=$ ($8,9$열끼리 혹은 나머지 열끼리의 시행 횟수) $+$ ($8,9$열과 나머지 열 간의 시행 횟수)

$\le$ ($8,9$열과 나머지 열 간의 $2$-majorize 시행 횟수) $+$ ($2$차 표에서의 최대 시행 횟수)입니다.

 

따라서 ($10$열과 나머지 열 간의 $3$-majorize 시행 횟수)을 $N_1$, ($8,9$열과 나머지 열 간의 $2$-majorize 시행 횟수)를 $N_2$, ($2$차 표에서의 최대 시행 횟수)를 $N_3$, ($4$차 표 시행 횟수)를 $N$이라 하면

$$N\le N_1+N_2+N_3$$

입니다. 2번에 의해 $N_1\le 6$, 3번에 의해 $N_2\le 7$, 6번에 의해 $N_3\le 8$이므로 $N\le 21$입니다.

 

이제 실례를 찾아봅시다. 가장 간단하게 생각할 수 있는 실례는 아래 행부터 순서대로 정렬하는 것입니다. 그런데 이렇게 해보면 $21$번이 나오지 않고, $18$번 정도에서 종료됩니다. 어떻게 해봐도 시행 횟수가 더 늘어나지 않아서, 부등식의 상한을 조금 더 낮춰보기로 했습니다. 각 부등식의 등호조건은 성분들의 합이 $1$씩 증가할 때 성립하는데, 실제로 $18$번의 실례를 살펴보면 그렇지 않음을 알 수 있습니다. 따라서 다음을 보여봅시다.

 

Claim 1. $N_1\le 4$

pf. $10$열의 아래 세 성분은 $(0,0,0)$에서 $(1,2,3)$까지 커져야 합니다. 이때 majorize한 시행을 통해 성분이 변한다면, 모든 성분이 단조증가해야 합니다. 그러므로 등호조건에 따라 정확히 한 성분만 $1$ 커질려면, 나머지 성분은 일치해야 합니다. 이는 곧 나머지 두 성분은 표 상에서 $2$개 이상 존재해야 한다는 뜻이 됩니다. (예를 들어 $(1,0,1)$이 $(1,0,2)$로 변하려면, $2$행과 $3$행에 각각 $1$과 $0$이 $2$개 이상 존재해야 합니다) 그런데 $2$행에는 $2$가, $3$행에는 $2$와 $3$이 하나씩 밖에 없습니다. 따라서 $10$열의 아래 세 성분 중 어느 한 성분이 $1$보다 커지는 순간 더 이상 majorize한 시행이 아니게 됩니다. 이는 성분 합이 최대 $4$까지 커질 수 있다는 의미이며, 따라서 $N_1\le 4$입니다. $◻$

 

Claim 2. $N_2\le 6$

pf. 비슷한 이유로 성립합니다. $N_2=7$, 즉 모든 변화가 majorize하며 정확히 $1$씩 증가한다 가정하고 최종 상태에서 역산해보면 금방 모순이 도출됩니다. $◻$

 

따라서 $N\le 4+6+8=18$입니다.

 

실례는 쉽게 생각해서 아래 행부터 정렬하면 됩니다. 정확한 실례는 처음 표를 기준으로 다음 열을 순서대로 시행하면 됩니다.

0	0	0	0	0	0	0	0	0	1
0	0	0	0	0	0	0	1	1	0
0	0	0	0	1	1	2	0	0	0
0	1	2	3	0	1	0	0	1	0

$(2,5)\to (5,7)\to (3,6)\to (3,5)\to (4,6)\to (4,5)\to (5,7)\to (6,7)$($8$번)

$\to (5,9)\to (6,9)\to (7,9)\to (4,8)\to (6,8)\to (7,8)$ ($6$번)

$\to (5,10)\to (7,10)\to (8,10)\to (9,10)$ ($4$번) $◼$

 

 

 

P.S. 사지방에서 글 쓰는 게 쉽지 않다는 걸 깨달았습니다.