2017 Benelux MO 풀이

수올문제 자료집을 돌다가 그나마 풀만한 문제들이 보여서 풀어보았다.

나한테 풀리는 걸 보면 그렇게 변별력이 있는 문제들은 아니거나, 사풀 유도가 굉장히 악랄하거나.

1, 2, 3, 4-(a)를 풀었고, 4-(b)는 아직 푸는 중이다.

문제 링크(한국어)

---

Spoiler Alert!

This section is intentionally left blank.

---

1. 다음을 만족하는 \(f : \mathbb{Q}^{+} \to \mathbb{N}\)을 모두 구하여라.

$$ \forall x, y \in \mathbb{Q}^{+}, \quad f(xy) \cdot \gcd \left( f(x)f(y), f(\frac{1}{x})f(\frac{1}{y}) \right) = xyf(\frac{1}{x})f(\frac{1}{y}) $$

*\(P(a,b)\) : \(x\)에 \(a\), \(y\)에 \(b\)를 대입함으로써 얻어지는 사실. 수올러들은 대놓고 쓰나보다.

1) \(P(1,1)\) : \(f(1) = 1\)

2) \(n\)은 자연수.

\(G(n) := \gcd \left( f(n), f(\frac{1}{n}) \right) \)

- \(P(n,1)\) : \(f(n) \cdot G(n) = n f(\frac{1}{n})\)

- \(P(\frac{1}{n},1)\) : \(f(\frac{1}{n}) \cdot G(n) = \frac{1}{n} f(n)\)

$$ \therefore \frac{f(n)}{f(\frac{1}{n})} = \frac{n}{G(n)} = nG(n) \implies G(n) = 1 \land f(\frac{1}{n}) = \frac{f(n)}{n} $$

3) \(p, q\)는 서로소인 자연수.

\(H(p,q) := \gcd \left( f(a)f(\frac{1}{b}), f(b)f(\frac{1}{a}) \right)\)

\(P(p, \frac{1}{q})\) : \(f(\frac{p}{q}) H(p,q) = \frac{p}{q}f(q)f(\frac{1}{p}) = qf(1/p)f(1/q)\) (by 2)

이 때, 역시 2)에 의해 H(p,q)의 값을 구할 수 있다.

$$ H(p,q) = \gcd \left( p f(\frac{1}{p})f(\frac{1}{q}) , q f(\frac{1}{p})f(\frac{1}{q}) \right) = f(\frac{1}{p})f(\frac{1}{q}) \gcd(p,q) = f(\frac{1}{p})f(\frac{1}{q}) $$

이걸 그대로 위 식에 대입하면 \(f(\frac{p}{q}) = p\)가 된다. 즉, \(f\)는 유리수를 기약분수로 나타냈을 때 분자. \({}_{\blacksquare}\)

---

2. 문제 설명은 너무 귀찮으니 생략.

답 : \(n\)이 짝수면 후수가, \(n\)이 홀수면 선수가 이긴다.

\(n\)이 짝수인 경우, 후수는 선수가 하는 짓을 그대로 따라하면 된다. 이 동작이 매번 가능함은 자명하고, 선수, 후수가 만드는 그래프의 크기도 같다. 선수가 먼저 시작했기 때문에 선수의 그래프가 먼저 포화되어 버린다. 따라서 후수의 승.

\(n\)이 홀수인 경우는 반대로 선수가 아무 점이나 잡고 하나 연결한 뒤, 그 점을 없다고 치고 후수의 동작을 그대로 따라하면 된다.

엄밀하게 쓰는 방법은 모르겠다.

09.30) 사풀이었음을 확인했다. 당연히 후수가 저렇게 놀아줄 리가 없다... 솔루션에서 답만 본 상태. 실제로 선수가 이기는 경우는 \(n\)이 \(4k+3\)일 때 뿐이다.

---

3.

무려 기하 문제...!

열심히 그림을 그리려 했지만 지오지브라가 미숙하다. 그냥 입으로 때울 수 있는 난이도이니 입으로. 혹시나 이 문제를 풀지 못했다면 손으로 그리면서 따라오자. 점이 2개밖에 등장하지 않는다.

결국 주어진 문제는 각 ACB의 이등분선이 선분 DA와 평행함과 동치이다.

그리고 (각 B) = (각 C)이므로 AB의 중점 E를 잡으면 사각형 EBCD는 등변사다리꼴이 되어 ED와 BC가 평행하다.

각 ACB를 \(2\alpha\)라고 하자. 결국은 (각 CAD) = \(\alpha\)를 보이면 된다.

그런데 ED가 BC와 평행하고 E가 AB의 중점이므로, AC와 ED의 교점 F 또한 AC의 중점이 된다.

마침 D가 직각이다! 따라서 F는 직각삼각형 ACD의 외심이 되고, 삼각형 AFD가 이등변삼각형이므로 

(각 AFE) = 2(각 CAD) = (각 ACB) = \(2\alpha)가 되어 증명종료.

---

4.

n by n grid에 \(n^2\)개의 서로 다른 정수를 쓰는데, 행 열별로 gcd가 모두 달라야 한다.

(a) 이 수에는 적어도 \(2n^2\) 이상의 정수가 존재한다.

(b) 모든 수가 \(2n^2\)이하이도록 그리드를 채울 수 있는 \(n\)을 모두 구하여라.

(a) 

행 / 열별로 나온 \(\gcd\) 중 가장 큰 \(\gcd\)는 적어도 \(2n\)이상이다.

그 행 / 열에 적힌 수들은 전부 '\(2n\) 이상의 어떤 수'의 배수여야 하므로, 그 중 최댓값은 아무리 작아도 \(2n^2\) 이상이다.

(b)

풀이 준비중.