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\%a+ n\%b + n\%c + n\%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 \quad \blacksquare$$

 

 

 

#2. 양의 정수 $n(\geq 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{n}$

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

 

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

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

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

 

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

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

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

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

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

 

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

 

 

 

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

 

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

• $0\leq x_1\leq x_2\leq\cdots\leq x_{2024}\leq 1$
• $0\leq y_1\leq y_2\leq\cdots\leq y_{2024}\leq 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})\geq 1-p$가 성립한다. (단, $y_0=0$)

 

답. $\boxed{\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에 어떤 분이 계산해 놓으신 듯 합니다) 개인적으로 좋은 문제라 생각하진 않습니다.  $\blacksquare$