2024 FKMO Day 1 풀이

#1. 양의 홀수 $a,b,c,d$에 대하여, 이 중 어느 두 개를 골라도 서로소라고 하자. 양의 정수 $n$에 대하여

$$f(n)=\left[\frac{n}{a}\right]+\left[\frac{n}{b}\right]+\left[\frac{n}{c}\right]+\left[\frac{n}{d}\right]$$

이라 할 때, 다음 등식을 증명하여라. (단, $[x]$는 $x$를 넘지 않는 가장 큰 정수)

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

 

풀이. 지수의 기우성이 변하지 않는 범위에서 자유롭게 식 변형을 할 수 있습니다.

$$\sum _{n=1}^{abcd}(-1{)}^{f(n)}=\sum _{n=1}^{abcd}(-1{)}^{\left[\frac{n}{a}\right]+\left[\frac{n}{b}\right]+\left[\frac{n}{c}\right]+\left[\frac{n}{d}\right]}=\sum _{n=1}^{abcd}(-1{)}^{n-a\left[\frac{n}{a}\right]+n-b\left[\frac{n}{b}\right]+n-c\left[\frac{n}{c}\right]+n-d\left[\frac{n}{d}\right]}=\sum _{n=1}^{abcd}(-1{)}^{n\mathrm{\%}a+n\mathrm{\%}b+n\mathrm{\%}c+n\mathrm{\%}d}$$

$$=(\sum _{i=0}^{a-1}(-1{)}^i)(\sum _{i=0}^{b-1}(-1{)}^i)(\sum _{i=0}^{c-1}(-1{)}^i)(\sum _{i=0}^{d-1}(-1{)}^i)=1◼$$

 

 

 

#2. 양의 정수 $n(\ge 2)$에 대하여 $2n$개의 사탕이 있다. 갑은 이 $2n$개의 사탕 모두를 $4n$개의 상자 $B_1,\cdots ,B_{4n}$에 나누어 넣는다. 을은 갑이 각 상자에 넣은 사탕의 개수를 확인한 후에, 다음 조건을 만족하도록 $4n$개의 상자 중 정확히 $2n$개의 상자 $B_{k_1},\cdots ,B_{k_{2n}}$을 골라 그 안에 있는 사탕을 모두 가져간다.

(조건) 각 $i=1,2,\cdots ,2n$에 대하여 $k_i-k_{i-1}$은 $1$ 또는 $3$이며, $k_{2n}=4n$이다. (단, $k_0=0$)

갑은 을이 선택하지 않은 $2n$개의 상자에 들어있는 사탕을 모두 가져간다. 갑과 을이 각자 최대한 많은 사탕을 가져가기 위하여 모두 최선의 전략을 사용한다면, 갑은 몇 개의 사탕을 가져갈 수 있겠는가?

 

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

풀이. 갑의 전략: 짝수번째 상자에 사탕을 하나씩 넣습니다. 을은 기우성을 번갈아가며 상자를 선택하기 때문에, 정확히 절반의 상자를 뽑게 됩니다.

 

을의 전략: (조건)은 다음과 같이 간단히 정리할 수 있습니다.

"$0$에서 시작해, $1$과 $3$을 $n$번씩 더하며 $4n$까지 선택합니다."

이렇게 $2n$번 뛰어서 만들어지는 형태들을 경로라 부릅시다. 

 

Lemma. 임의의 짝수 $2k(1\le k<2n)$에 대해, 두 개의 경로를 잘 골라 $2k$번째 상자는 둘 다 지나지 않고, 나머지 칸들은 두 경로 중 적어도 하나가 지나도록 할 수 있다.

pf. $1$과 $3$을 번갈아가며 잘 배치하면 됩니다.

$k=2t$라면 $(3,1,3,\cdots ,1,\mathbf{\text{3}},3,1,\cdots ,3,1,1),(1,1,3,1,\cdots ,3,\mathbf{\text{1}},3,3,1\cdots ,3)$로 설정(굵은 표시가 $2t-1$번째),

$k=2t+1$라면 $(1,1,3,\cdots ,1,\mathbf{\text{3}},3,1,\cdots ,3),(3,1,3,1,\cdots ,\mathbf{\text{3}},3,1,\cdots ,3,1,1)$로 설정(굵은 표시가 $2t+1$번째) $◼$

(경로가 사실상 유일하기 때문에, 직접 그려보시면 바로 찾을 수 있습니다)

 

$2n$개의 사탕을 배치할 경우, 짝수번째 상자가 $2n$개이므로 사탕 개수가 한 개 이하인 짝수번째 상자를 찾을 수 있습니다. 그 상자에 Lemma를 적용할 경우, 두 경로 중 하나는 전체 사탕의 절반 이상을 지나게 됩니다. $◼$

 

 

 

#3. 다음 조건을 만족하는 가장 작은 양의 실수 $p(\le 1)$을 구하여라.

 

(조건) 실수 $x_1,x_2,\cdots ,x_{2024},y_1,y_2,\cdots ,y_{2024}$에 대하여

• $0\le x_1\le x_2\le \cdots \le x_{2024}\le 1$
• $0\le y_1\le y_2\le \cdots \le y_{2024}\le 1$
• ${\displaystyle \sum _{i=1}^{2024}{x}_i={\displaystyle \sum _{i=1}^{2024}{y}_i=2024p}}$이면

부등식 ${\displaystyle \sum _{i=1}^{2024}{x}_i(y_{2025-i}-y_{2024-i})\ge 1-p}$가 성립한다. (단, $y_0=0$)

 

답. $\boxed{{\displaystyle {\displaystyle \frac{\sqrt{5}-1}{2}}}}$

풀이. Mixing Variable 문제입니다. (등호는 자명히 전부 $p$일 때입니다)

최종식이 $\{x_i\}$와 $\{y_i\}$에 대한 일차식이므로, 나머지 변수들을 전부 고정하고 $x_i$와 $x_{i+1}$(혹은 $y_i$와 $y_{i+1}$)를 조정한다고 했을 때 두 값을 최대한 모으거나 최대한 벌리는 것이 최적입니다. 만약 수열 $x_i$에 $0$과 $1$ 사이의 서로 다른 값이 두 개 이상 존재할 경우 이 과정을 통해 값을 단조감소시킬 수 있습니다. 따라서, 저희는 $\{x_i\}$와 $\{y_i\}$가 각각 $(0,a,1)$, $(0,b,1)$($0<a,b<1$)로만 구성되어 있다고 가정해도 무관합니다. 

 

이렇게 가정할 경우 주어진 식이 매우 간단히 표현되기 때문에, 적절히 경우를 나누어 계산을 통해 문제를 해결할 수 있습니다. 그 복잡한 계산 과정을 여기에 담는 건 그닥 의미가 없다고 생각되어 넣지 않겠습니다. (aops에 어떤 분이 계산해 놓으신 듯 합니다) 개인적으로 좋은 문제라 생각하진 않습니다.  $◼$