2023 FKMO DAY2 풀이

2023년 3월 26일 시행된 2023 FKMO DAY2에 대한 해설이다.

 

4. 다음 조건을 만족하는 양의 정수 $n$을 모두 구하여라.

    (조건) $2^n-1$은 $7$보다 큰 소인수를 갖지 않는다.

 

풀이. 위 문제를 해결하기 위해서는 $2^n-1$ 꼴의 수가 충분히 큰 소인수를 가진다는 것을 설명해야 한다. 이와 관련된 유명한 성질이 있다.

 

Claim. 소수 $p$에 대해 $2^p-1$의 소인수는 $pk+1$ 꼴이다.

pf. $2^p-1$의 각 소인수 $q$에 대한 위수 $r$을 생각해 보았을 때, $2^p-1$이 $q$로 나누어 떨어지므로 지수인 $p$가 $r$로 나누어 떨어져야 한다. 따라서 $r$은 $1$ 또는 $p$이며, 자연스럽게 $r=p$임을 알 수 있다. 이때 $2^{q-1}-1$ 또한 $q$의 배수이므로 지수인 $q-1$이 $r$로 나누어 떨어져야 하므로 결과가 도출된다.    $\blacksquare$

 

위 Claim을 이용하면 다음과 같은 논의를 해볼 수 있다.

(1) 만약 $n$이 $5$ 이상의 소인수 $p$를 가지면, $2^p-1$이 $pk+1$ 꼴 소인수를 가지며 배수인 $2^n-1$ 또한 가진다. $p\geq 5$일 때 그 $pk+1$ 꼴 소인수는 $7$보다 커야 한다. 따라서 $n$은 오직 $2$와 $3$만을 소인수로 가진다.

(2) 만약 $n$이 $8$의 배수이면, $2^8-1=255=3\times5\times17$가 $7$보다 큰 소수 $17$을 소인수로 가지므로 $2^n-1$ 또한 $17$의 배수이다. 따라서 $n$의 $2$-지수는 최대 $2$이다.

(3) 만약 $n$이 $9$의 배수이면, $2^9-1=511=7\times73$이 $7$보다 큰 소수 $73$을 소인수로 가지므로 $2^n-1$ 또한 $73$의 배수이다. 따라서 $n$의 $3$-지수는 최대 $1$이다.

 

$\therefore$ $n$은 $12$의 약수이며, 각각 시도해보면 $n=1,2,3,4,6$일 때 가능하다.

 

 

 

5. 주어진 양의 정수 $n$에 대하여 $n$개의 상자 $B_1, \cdots, B_n$이 있다. 다음과 같은 시행을 반복하여 상자에 공을 추가할 수 있다.

(시행) $1\leq i\leq j\leq n$을 만족하는 양의 정수 $i,j$를 선택하여 $i\leq k\leq j$를 만족하는 각 $k$에 대하여 상자 $B_k$에 공을 하나씩 추가한다.

 

양의 정수 $x_1,\cdots,x_n$에 대하여 $f(x_1,\cdots,x_n)$을 상자 $B_i$에 $x_i$개의 공이 들어있는 상태에서 시작하여 각 상자에 들어있는 공의 개수를 모두 3의 배수로 만들기 위해 필요한 시행의 횟수의 최솟값이라 하자. 이때 $f(x_1,\cdots,x_n)$이 가질 수 있는 값 중 가장 큰 값을 구하여라.

 

풀이. 편의상 각 항을 3으로 나눈 나머지로 생각할 수 있다. 문제를 풀기 전에, 구간 덧셈 시행을 더 쉽게 생각할 수 있는 재밌는 발상이 있다. 다음과 같은 새로운 수열을 정의하자.

$0\leq i\leq n$에 대해 $y_i=x_{i+1}-x_i$

이때 $x_0=x_{n+1}=0$으로 정의한다. 그러면 $(i, j)$에 대해 시행을 할 경우 $y_{i-1}$이 1 증가, $y_{j}$가 1 감소하며 나머지는 변하지 않는다. 즉, 각 시행은 $0\leq i<j\leq n$인 두 $i,j$를 골라 $y_i$를 1 증가, $y_j$를 1 감소시킨다.

 

이제 최소 시행 횟수에 접근하기 위해 다양한 생각을 해볼 수 있다.

Claim 1. 각 항은 덧셈만 이루어지거나 뺄셈만 이루어진다.

pf. 그렇지 않은 항 $x_j$가 있다고 가정하면, 어떤 $0\leq i<j<k\leq n$이 존재해 $(i, j), (j,k)$에서 시행이 이루어졌어야 한다. 그러나 이 둘은 $(i,k)$로 대체되어도 결과가 동일하며, 시행 횟수는 1 감소하였다.    $\blacksquare$

 

Claim 2. 각 항은 세 번 이상의 동일한 연산이 이루어지지 않는다.

pf. 어떤 항 $a_i$에 세 번 이상의 덧셈이 이루어졌다고 가정하자(뺄셈도 마찬가지다). 이때 $0\leq i<j\leq k\leq l\leq n$이 존재해 $(i,j),(i,k),(i,l)$에서 시행이 이루어졌어야 한다. 만약 $j\ne k$이면 이들을 $(j,k),(j,l)$, $j=k\ne l$이면 $(j,l)$, $j=k=l$이면 아무것도 안 한 것으로 대체할 수 있다.    $\blacksquare$

 

 따라서 각 항에는 최대 두 번의 연산이 덧셈이나 뺄셈이 이루어진다. 즉 $0$에는 시행을 할 필요가 없으며, $1$에는 뺄셈 한 번이나 덧셈 두 번, $2$에는 덧셈 한 번이나 뺄셈 두 번이 필요하다. 이 정보들을 시각적으로 편하게 바라보기 위해 다음과 같이 그래프를 설정하자. 어떤 두 $0\leq i<j\leq n$에 대해 $(i,j)$에 시행을 적용하였을 경우 두 점을 잇는다(여러 번 시행했을 경우 여러 번 잇는다, 물론 Claim 2에 의해 최대 2번 할 수 있다). Claim 2에 의해 각 점의 차수가 2 이하이므로, 이 그래프는 몇 개의 경로와 회로로 분할된다. 또한 Claim 1에 의해 이 그래프는 이분그래프이다. 따라서 그래프의 모든 회로는 짝수 회로이다. 먼저 짝수 회로의 경우, 짝수 번째 변들을 전부 홀수 번째 변들로 대체하였을 때 결과가 유지됨을 알 수 있다(즉 모든 홀수 번째 변들을 두 번씩 진행한 것으로, 모든 짝수 회로를 $2$-cycle로 분할해서 생각해도 된다). 경로의 경우 점이 $v$개일 때 변은 $v-1$개이다. 즉 $v-1$번의 시행으로 $v$개의 변수를 $0$으로 만들 수 있다는 뜻이다.

 

 이제 정량적인 계산을 위해 $2$-cycle의 개수를 $k$개, 나머지 경로들의 점 개수를 $n+1-2k=v_1+\cdots+v_t$라 하자. 이때 시행 횟수는 $2k+\displaystyle\sum_{i=1}^t (v_i-1)=2k+(n+1-2k)-t=n+1-t$이다. 이 식에 따르면 $t$가 최대화 될 때 시행 횟수가 최소화됨을 알 수 있다. $t$가 최대화될려면 각 경로의 점 개수가 최소여야 한다. 가장 쉽게 생각할 수 있는 경로는 선분이지만, 덧셈 연산이 뺄셈 연산보다 앞에서 이루어져야 한다는 제약 때문에 불가능한 반례가 존재한다. 그 다음으로 가장 쉽게 생각할 수 있는 예시가 점 3개로 이루어지 경로이다.

 

Lemma 1. 처음 수열이 어떻게 주어지더라도 $t\geq \lfloor \frac{n+1}{3}\rfloor$이 되게 그래프를 만들 수 있다.

pf. $0$들을 무시하고 $1$과 $2$를 나열하자. 만약 $2$ 뒤에 등장하는 $1$이 존재하면 한 번의 시행으로 둘을 모두 해결할 수 있다. 이 시행을 불가능할 때까지 반복하면, $1$과 $2$가 각각 왼쪽과 오른쪽에 분리된 형태로 남는다. 이때 $1$의 개수와 $2$의 개수는 mod $3$으로 합동이다. 이때, 두 번의 시행으로 같은 수 세 개를 해결할 수 있다($\because$ $i<j<k$에 대해 모두 $1$이면 $(i,j),(i,k)$, 모두 $2$이면 $(i,k),(j,k)$로 시행하면 된다). 이때 가능한 최종상태는 $1, 2$ 또는 $1, 1, 2, 2$이다. 전자는 $2$-cycle로 처리 가능하며, 후자는 점이 $4$개인 경로로 처리 가능함을 쉽게 확인할 수 있다. 가장 최악의 경우를 고려하기 위해 처음 시행을 무시하자($2,1$을 한 번으로 처리하는 과정은 각 수를 $0.5$번의 시행으로 해결하는 것으로 가장 최선이다). 이때 $n$을 $3$으로 나눈 나머지에 따라 만들어지는 경로 개수를 세어보면 명제에 제시된 바와 일치한다.    $\blacksquare$

 

Lemma 2. 앞쪽 절반이 $1$, 뒤쪽 절반이 $2$인 수열 $(y_i)$에 대해, $t =\lfloor\frac{n+1}{3}\rfloor$이다.

pf. 우선 모든 $1$이 $2$ 보다 앞에 있으므로 길이가 $2$인 경로가 등장할 수 없다. $0$ 또한 없으므로, 모든 경로의 길이는 $3$ 이상이어야 한다. 따라서 Lemma 1의 과정이 최선의 방법이며, 이때 정확히 주어진 $t$ 값을 가진다.    $\blacksquare$

 

따라서 답은 $(n+1)-\lfloor \displaystyle\frac{n+1}{3} \rfloor$이다.

 

 

 

6. 양의 정수 $n\geq 3$과 실수 $a_1, \cdots, a_n, b_1, \cdots, b_n$에 대하여 다음 부등식을 증명하여라.

$\displaystyle\sum_{i=1}^n a_i(b_i-b_{i+3}) \leq \displaystyle\frac{3n}{8} \sum_{i=1}^n ((a_i-a_{i+1})^2+(b_i-b_{i+1})^2)$

 

풀이. 우선 부등식을 살펴봤을 때, 각 수열을 평행이동이나 닮음변환해도 결과를 변화시키지 않는다는 사실을 알 수 있다.

 

이 사실을 기억한 채 부등식을 해결해보자. 부등식을 조금 더 자세히 살펴보면, 우변에 $n$이 곱해져있다. 양변이 동차식임에도 $n$이 계수로 붙은 것은, 우변에서 $a_i$의 공차가 일정할 때 좌변에서 $a_i$가 $n$에 대한 일차항 정도의 크기를 가질 수 있기 때문이다. 또한 $b_i$들을 관찰해보면 우변은 $1$ 차이, 좌변은 $3$ 차이의 변화량으로 구성되어 있다. 잘 생각해보면 $3$ 차이의 변화량은 연속한 $1$ 차이 변화량 세 개의 합으로 표현할 수 있으므로 두 항을 관련지을 수 있을 듯하다. 마지막으로 우변이 제곱의 합, 좌변이 곱들의 합으로 표현될 걸 보면 무난하게 AM-GM을 사용할 것으로 보인다.

 

먼저 좌변과 우변의 $b_i$ 변화량들을 동일하게 맞춰주기 위해 다음과 같은 코시 부등식을 떠올릴 수 있다.

$(1^2+1^2+1^2)((b_i-b_{i+1})^2+(b_{i+1}-b_{i+2})^2+(b_{i+2}-b_{i+3})^2)\geq (b_i-b_{i+3})^2$

이를 각 $i$에 대해 전부 더해주면, $9\displaystyle\sum_{i=1}^n (b_i-b_{i+1})^2 \geq \sum_{i=1}^n (b_i-b_{i+3})^2$이다.

편의상 $b_i-b_{i+3}=c_i$로 둘 때, 이 부등식을 참조하여 다음 부등식을 증명하면 충분함을 알 수 있다.

 

$\displaystyle\sum_{i=1}^n a_ic_i \leq \displaystyle\frac{3n}{8} \sum_{i=1}^n (a_i-a_{i+1})^2+\frac{n}{24}\sum_{i=1}^nc_i^2$

 

이제 AM-GM을 적용하기 더 편한 식이 되었다. 이때 식의 구조와 $a_i$가 $O(n)$ 정도의 크기임을 고려하면 다음과 같이 등호조건을 조절하는 것이 자연스럽다. 

 

$a_i c_i = 2 \times\sqrt{\frac{6}{n}}a_i\times \sqrt{\frac{n}{24}}c_i \leq \frac{6}{n} a_i^2 + \frac{n}{24}c_i^2$

이를 모든 $i$에 대해 더해주면, $\displaystyle\sum_{i=1}^n a_i c_i \leq \frac{6}{n}\sum_{i=1}^n a_i^2 + \frac{n}{24}\sum_{i=1}^n c_i^2$

 

따라서 다음을 보이면 충분하다.

$\displaystyle\frac{6}{n} \sum_{i=1}^n a_i^2 \leq \frac{3n}{8} \sum_{i=1}^n (a_i-a_{i+1})^2$, $16\displaystyle\sum_{i=1}^n a_i^2 \leq n^2 \sum_{i=1}^n (a_i-a_{i+1})^2$

 

결론부터 말하면, 이 부등식은 거짓이다(애초에 좌변을 발산시킬 수 있다). 그러나, 가장 처음에 언급했듯이 수열 $(a_n)$에 적절한 변환을 적용할 수 있고, 그렇게 하더라도 지금까지의 논의에 영향을 주지 않는다. 우리가 방금 얻어낸 부등식을 보았을 때 우변은 평행이동에 대해 불변이지만 좌변은 영향을 받는다. 따라서 우리는 수열을 적절히 평행이동시켜 좌변이 최소가 되게 만들 것이다. 변화량을 $x$로 잡고 이차식을 전개해 최소일 조건을 찾아보면, $x$가 수열의 평균이 되어야 함을 알 수 있다. 또한 수열을 평균만큼 평행이동 시켰을 때 얻어진 항들의 합이 0인 것을 쉽게 알 수 있다. 그러므로 우리는 다음을 보이면 충분하다.

 

$a_1+\cdots+a_n=0$일 때 $16\displaystyle\sum_{i=1}^n a_i^2 \leq n^2 \sum_{i=1}^n (a_i-a_{i+1})^2$이다.

 

우리는 이 부등식을 코시 부등식을 이용하여 증명할 것이다(그게 가장 자연스러운게, 제곱의 합이 제곱의 합 이상임을 증명할 수 있는 가장 쉬운 방법이다). 그러므로 우리는 공차의 적절한 가중치 합이 단일항 $a_i$가 되도록 가중치를 설정해야 한다.

 

실패한 접근

이때 수열의 합이 0인 사실을 적극적으로 활용하기 위해 다음과 같이 Abel Sum의 형태를 생각해볼 수 있다.

$1(a_1-a_2)+2(a_2-a_3)+\cdots+(i-1)(a_{i-1}-a_i)=a_1+a_2+\cdots+a_{i-1}-(i-1)a_i$

마찬가지로 $(-1)(a_{n-1}-a_n)+(-2)(a_{n-2}-a_{n-1})+\cdots+-(n-i)(a_i-a_{i+1})=a_n+\cdots+a_{i+1}-(n-i)a_i$이므로 두 식을 더하면 우변이 $((a_1+\cdots+a_n)-a_i)-(n-1)a_i=-n a_i$로 원하는 결과와 가깝다. 이때 코시 부등식을 적용하는 과정에서 가중치의 제곱 합이 최소가 되게 하기 위해서는 두 식이 절반씩($n/2$) 항들을 나눠가지는 경우가 최선이다. 이때의 가중치 제곱 합을 계산해보면 최대 $2\displaystyle\sum_{i=1}^{\lfloor n/2 \rfloor} i^2\leq 2\frac{1}{6}\frac{n}{2}(\frac{n}{2}+1)(n+1)=O(\frac{n^3}{12})$이다. 이를 모든 $i$에 대해 더해주면 거의 비슷한 부등식이 나오는데, 좌변의 계수가 $16$이 아니라 $12$로 나온다. (실패)

 

 

 다른 방법을 찾아보자. 직접적으로 단일항을 만들 수 없다면, 다른 꼴을 만든 후 계산했을 때 결과적으로 단일항의 제곱 합과 같아야 한다. 우변을 가지고 코시 부등식을 적용하는 방법 중, 위에서 수열 $(b_i)$에 적용한 방법을 생각해볼 수 있다. 사실 이 부등식은 다음과 같이 일반화할 수 있다.

$k^2 \displaystyle\sum_{i=1}^n (a_i-a_{i+1})^2 \geq \sum_{i=1}^n (a_i-a_{i+k})^2$

 

이를 $1\leq k<n$에 대해 모두 더할건데, 이때 $k$가 절반보다 클 경우에는 절반보다 작은 반대 방향의 차이를 고려해 코시 부등식의 계수를 설정한다. 이를 적용하면 다음과 같은 결과가 나온다.

$O(\displaystyle\frac{n^3}{12})\sum_{i=1}^n (a_i-a_{i+1})^2 \geq \sum_{k=1}^{n-1}\sum_{i=1}^n (a_i-a_{i+k})^2=2(n-1)\sum_{i=1}^n a_i^2-2\sum_{1\leq i<j\leq n} a_ia_j=(2n-1)\sum_{i=1}^n a_i^2 - (\sum_{i=1}^n a_i)^2 = O(2n)\sum_{i=1}^n a_i^2 $

따라서 $\displaystyle\sum_{i=1}^n a_i^2 \leq O(\frac{n^2}{24}) \sum_{i=1}^n (a_i-a_{i+1})^2$으로 증명하려는 부등식보다 강한 부등식이다(물론 실제로 더 강한지 확인해봐야 한다. 독자는 꼭 해보길 바란다).

 

 

 

P.S. 4, 5번은 무난했고, 6번이 예상치 못한 부등식이었다. 내가 부등식을 잘하지 않아 객관적인 난이도는 잘 모르겠다. 쉽다고 생각하진 않는데, 부등식을 잘한다면 무난하게 풀 수도 있을 듯하다. 아직 DAY 1 문제를 보지 않았는데, 생각보다 4번 정수가 너무 쉽게 출제되었다. 5번은 무난한 중간 난이도 조합이라 생각한다. 전체적인 난이도를 보았을 때 평균보다 약간 쉬운 셋인 것 같다.