#1. 중심이 $O$인 원 위에 서로 다른 세 점 $A$, $B$, $X$가 있고 세 점 $A$, $B$, $O$는 한 직선 위에 있지 않다. 삼각형 $ABO$의 외접원을 $\Omega$라 할 때, 선분 $AX$, $BX$는 원 $\Omega$와 각각 점 $C(\ne A)$, $D(\ne B)$에서 만난다. 점 $O$가 삼각형 $CXD$의 수심임을 보여라.
풀이.
$\angle OCX=\angle ABO=90^\circ - \angle X$이므로 $CO\perp DX$, 마찬가지로 $DO\perp CX$입니다.
따라서 $O$는 $\triangle CXD$의 수심입니다. $\blacksquare$
(참고) $AB$와 $CD$가 antiparellel 관계이므로, $O$는 $\triangle ABX$의 외심인 동시에 $\triangle 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\leq k\leq 333)$
풀이. 먼저 다음 세 수열을 생각해봅시다.
$x_n=\textbf{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\geq a_{t+1}-3>d\cdot b_{t+1}-3\geq 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$는 조건을 만족합니다. $\blacksquare$
#3. 집합 $S$는 평면 상의 $2024$개의 점들로 구성되어 있고, 이 점들 중 어느 세 점도 한 직선 위에 있지 않다. 집합 $S$에 속하는 두 점을 지나는 직선 $l$이 다음 조건을 만족하면 $l$을 '약한 균등 직선'이라 하자.
(조건) 직선 $l$이 평면을 두 개의 부분으로 나눌 때, 한 부분은 $S$의 원소 중 정확히 $1010$개의 점을 포함하고 다른 부분은 정확히 $1012$개를 포함한다. (단, 각 부분은 $l$ 위의 어떤 점도 포함하지 않는다고 하자.)
집합 $S$의 두 점을 지나는 직선들 중 약한 균등 직선의 개수를 $w(S)$라 하자. $w(S)$가 가질 수 있는 값 중 가장 작은 것을 구하여라.
답. $\boxed{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$개 이상 존재합니다. $\square$
그러면 자연스럽게 나쁜 점의 개수를 세는 것이 다음 목표가 됩니다.
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$는 무조건 색칠된 영역에 들어가게 되어 모순입니다. $\square$
따라서 나쁜 점은 최대 $1$개이며, $|S|-1$개 이상의 나머지 점들은 각각 적어도 $2$개 이상의 약한 균등 직선을 가집니다. 이를 일종의 그래프로 생각하면(두 점을 이은 직선이 약한 균등 직선일 경우 변으로 연결합니다), 모든 점의 차수가 $2$ 이상이므로 변의 개수가 $|S|-1$개 이상임이 보장됩니다. 따라서 약한 균등 직선은 적어도 $|S|-1$개 이상 존재합니다.
실례는, 정$2023$각형과 중심으로 구성된 집합입니다. $\blacksquare$
#4. 다음 조건을 만족하는 최고차항의 계수가 $1$인 $k$차 정수 계수 다항식 $f(x)$가 존재하는 가장 작은 양의 정수 $k(\geq 2)$를 구하여라.
(조건) 임의의 두 정수 $m,n$에 대하여, $f(m)-f(n)$이 $31$의 배수이면 $m-n$은 $31$의 배수이다.
답. $\boxed{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{cases} 0 & k\mid p-1 \\ -1 & k \nmid p-1 \end{cases}$$
pf. 모든 원소들을 원시근의 거듭제곱으로 표현하면 등비급수로 계산 가능합니다. $\square$
이를 이용하면 $k\mid p-1$일 때는 $\displaystyle\sum_{i=0}^{p-1} f(i)^{\frac{p-1}{k}}$를 계산하여 모순을 쉽게 보일 수 있습니다. 남은 경우인 $4$차 함수는 조금 더(?) 잘해주면 됩니다.
적당한 평행이동을 통해 $f(x)=x^4+ax^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$은 당연히 모순입니다. $\blacksquare$
#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{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\geq a_{k+3}, a_{k+1}\leq 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}} \leq\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$ 미만임을 확인할 수 있습니다. $\blacksquare$
#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{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\phi(n)=\sum_{n=1}^{2024}\sum_{n\mid m}\phi(n)=\sum_{m=1}^{2024}\sum_{n\mid m}\phi(n)=\sum_{m=1}^{2024} m$입니다.
비슷하게, $\displaystyle\sum_{n=1}^{2024} \lfloor\frac{1012}{n}\rfloor\phi(n)=\sum_{m=1}^{1012} m$입니다. 이를 대입하면 답이 나옵니다. $\blacksquare$
(*) $\left\lfloor\displaystyle\frac{\lfloor\frac{n}{p}\rfloor}{q}\right\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_{\phi}(\lfloor\frac{2024}{n}\rfloor) $$
$$=2\sum_{n=1}^{2024}(-1)^{n-1}\sum_{m=1}^{\lfloor2024/n\rfloor} \phi(m)$$
$$ =2\sum_{n=1}^{2024}(-1)^{n-1}\sum_{m=1}^{\lfloor2024/n\rfloor} \sum_{d\mid m} d\mu(\frac{n}{d})$$
$$=2\sum_{nde \leq 2024} (-1)^{n-1} d \mu(e) $$
$$=2\sum_{ne \leq 2024} (-1)^{n-1}\mu(e)\sum_{d=1}^{\lfloor\frac{2024}{ne}\rfloor}d = 2\sum_{ne \leq 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{cases}1 & n=1 \\ -2 & n=2 \\ 0 & n\geq 3\end{cases}$ 입니다.
pf. 첫번째는 자명하고, 뫼비우스 반전 $H$가 곱산술함수라는 사실을 이용해 소수의 거듭제곱에 대해서만 계산하면 됩니다. $\square$
따라서 계산을 계속하면, 준식은
$$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$$
입니다. $\blacksquare$
#7. 예각삼각형 $ABC$의 수심을 지나고 점 $A$를 지나지 않는 직선 $l$이 직선 $BC$와 점 $P(\ne B,C)$에서 만나고, 점 $A$를 지나고 $l$과 수직인 직선이 삼각형 $ABC$의 외접원과 점 $R(\ne A)$에서 만난다. 점 $A,B$에서 $l$에 내린 수선의 발을 각각 $A',B'$이라 하고, 점 $A'$을 지나고 직선 $BC$와 수직인 직선을 $l_1$, 점 $B'$을 지나고 직선 $CA$와 수직인 직선을 $l_2$라 하자. 두 직선 $l_1$과 $l_2$의 교점을 $l$에 대하여 대칭시킨 점을 $Q$라 할 때, $\angle PQR=90^\circ$임을 보여라.
풀이.
직선 $AA'$과 $BC$의 교점을 $T$라 하겠습니다. 각 계산을 해보면
$$\angle QB'A'=\angle Q'B'A'=\angle A'AC=\angle RBT$$
$$\angle QA'B'=\angle Q'A'B'=90^\circ-\angle P=\angle RTB$$
이므로 $\triangle QB'A' \sim \triangle RBT (AA)$입니다.
여기서 $BB' \parallel TA'$이므로 $B'A'/B'P=BT/BP$이고, 따라서 $\triangle B'QP\sim\triangle BRP$가 성립합니다.
나선 닮음의 성질에 따라 $\triangle PBB'\sim \triangle PRQ$이고, $\angle PQR=\angle PB'B=90^\circ$입니다. $\blacksquare$
(참고) 이렇듯 적절한 닮음을 찾아 비례 관계나 나선 닮음으로 확장시키는 아이디어가 계속 출제되고 있습니다.
#8. 칠판에 $10$개의 수 $1,2,\cdots,10$이 적혀있고, 나현이는 다음과 같은 시행을 반복한다.
(시행) 칠판에 적혀있는 $10$개의 수 중 서로 약수와 배수의 관계가 아닌 두 수를 골라 지우고 이 두 수의 최대공약수와 최소공배수를 칠판에 적는다.
칠판에 적혀있는 $10$개의 수 중 임의의 두 수가 약수와 배수의 관계를 이루면 이 시행은 그만둔다. 나현이는 위의 시행을 최대 몇 번 할 수 있겠는가?
답. $\boxed{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)$).
이때 다음 성질들이 성립합니다.
- 중간 시행 과정과 무관하게, 최종 시행 결과는 열들을 잘 재배열했을 때 각 행이 정렬된 상태이다.
- $4$차 표에서 $10$열과 나머지 간의 시행은 최대 $6$번이다.
- $3$차 표에서 $8,9$열과 나머지 간의 시행은 최대 $7$번이다.
- $4$차 표에서 게임을 진행할 때, ($10$열을 제외한 열끼리의 시행 횟수) $+$ ($10$열과 나머지 열 간의 not $3$-majorize 시행 횟수) $\leq$ ($3$차 표에서의 최대 시행 횟수)이다.
- $3$차 표에서 게임을 진행할 때, ($8,9$열끼리 혹은 나머지 열끼리의 시행 횟수) $+$ ($8,9$열과 나머지 열 간의 not $2$-majorize 시행 횟수) $\leq$ ($2$차 표에서의 최대 시행 횟수)이다.
- $2$차 표에서 가능한 시행 횟수는 최대 $8$번이다.
하나씩 증명해봅시다.
1. 시행을 할 때마다 각 행 별로 inversion 수가 감소하므로, 결국에는 모든 행이 정렬된 상태로 종료되어야 합니다. $\square$
2. $4$차 표에서의 $10$열과 다른 열을 교환할 경우, $10$열이 이미 $7$의 지수가 앞서므로 뒤쳐지는 지수도 존재해야 합니다(두 열이 majorize 관계에 있지 않아야 하기 때문입니다). 시행 결과 $10$열의 아래 세 성분 중 적어도 한 항은 증가하게 됩니다. $10$열에는 무조건적으로 최소공배수만 쓰이므로, 1번에 따라 $10$열의 최종 상태는 $(1,1,2,3)$입니다. 아래 세 성분의 합이 $0$에서 $6$으로 변하므로, 최대 $6$번만 선택됩니다. $\square$
3. 2번과 마찬가지로 증명할 수 있습니다. $3$차 표에서 $8,9$열은 $(1,0,0),(1,0,1)$에서 $(1,1,2),(1,2,3)$으로 변하게 됩니다. 성분의 합의 차이를 보면 최대 $7$번입니다. $\square$
4. $4$차 표에서 게임을 진행할 때 아래 세 행이 어떻게 변하는지 살펴봅시다. $10$열을 제외한 열끼리 시행하는 경우에는, $7$의 지수가 둘 다 $0$이므로 $3$차 표에서 시행하는 것과 완전히 동일합니다. $10$열을 선택하여 시행하는 경우에는, not $3$-majorize인 경우에만 $3$차 표에서 유의미한 시행이 됩니다. 또한, $4$차 표에서 게임이 종료되었을 때에는 $3$차 표에서 또한 더 이상 시행을 할 수 없는 상태가 됩니다. ($\because$ not-majorize 관계의 두 열은 성분을 확장해도 not-majorize 관계입니다) 따라서 4번의 부등식이 성립합니다. $\square$
5. $3$차 표에 대해서 4번의 논리를 똑같이 적용하면 됩니다. $\square$
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$번의 시행이 가능합니다. $\square$
이 사실들을 이용하면, 먼저 4번에 의해
($4$차 표 시행 횟수)$=$ ($10$열을 제외한 열끼리의 시행 횟수)$+$ ($10$열과 나머지 열 간의 시행 횟수)
$\leq$ ($10$열과 나머지 열 간의 $3$-majorize 시행 횟수)$+$ ($3$차 표에서의 최대 시행 횟수)입니다.
5번에 의해
($3$차 표 시행 횟수)$=$ ($8,9$열끼리 혹은 나머지 열끼리의 시행 횟수) $+$ ($8,9$열과 나머지 열 간의 시행 횟수)
$\leq$ ($8,9$열과 나머지 열 간의 $2$-majorize 시행 횟수) $+$ ($2$차 표에서의 최대 시행 횟수)입니다.
따라서 ($10$열과 나머지 열 간의 $3$-majorize 시행 횟수)을 $N_1$, ($8,9$열과 나머지 열 간의 $2$-majorize 시행 횟수)를 $N_2$, ($2$차 표에서의 최대 시행 횟수)를 $N_3$, ($4$차 표 시행 횟수)를 $N$이라 하면
$$N\leq N_1+N_2+N_3$$
입니다. 2번에 의해 $N_1\leq 6$, 3번에 의해 $N_2 \leq 7$, 6번에 의해 $N_3\leq 8$이므로 $N\leq 21$입니다.
이제 실례를 찾아봅시다. 가장 간단하게 생각할 수 있는 실례는 아래 행부터 순서대로 정렬하는 것입니다. 그런데 이렇게 해보면 $21$번이 나오지 않고, $18$번 정도에서 종료됩니다. 어떻게 해봐도 시행 횟수가 더 늘어나지 않아서, 부등식의 상한을 조금 더 낮춰보기로 했습니다. 각 부등식의 등호조건은 성분들의 합이 $1$씩 증가할 때 성립하는데, 실제로 $18$번의 실례를 살펴보면 그렇지 않음을 알 수 있습니다. 따라서 다음을 보여봅시다.
Claim 1. $N_1\leq 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\leq 4$입니다. $\square$
Claim 2. $N_2\leq 6$
pf. 비슷한 이유로 성립합니다. $N_2=7$, 즉 모든 변화가 majorize하며 정확히 $1$씩 증가한다 가정하고 최종 상태에서 역산해보면 금방 모순이 도출됩니다. $\square$
따라서 $N\leq4+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)\rightarrow(5,7) \rightarrow(3,6) \rightarrow(3,5) \rightarrow(4,6) \rightarrow(4,5) \rightarrow(5,7) \rightarrow(6,7) $($8$번)
$ \rightarrow(5,9) \rightarrow(6,9) \rightarrow(7,9) \rightarrow(4,8) \rightarrow(6,8) \rightarrow(7,8) $ ($6$번)
$ \rightarrow(5,10) \rightarrow(7,10) \rightarrow(8,10) \rightarrow(9,10) $ ($4$번) $\blacksquare$
P.S. 사지방에서 글 쓰는 게 쉽지 않다는 걸 깨달았습니다.
'MO' 카테고리의 다른 글
| 2024 FKMO Day 1 풀이 (0) | 2024.03.25 |
|---|---|
| 2023 KMO 고등부 2차 풀이 (1) | 2023.11.05 |
| 2023 FKMO Day 1 풀이 (1) | 2023.06.17 |
| 2023 FKMO DAY2 풀이 (0) | 2023.03.27 |
