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)

풀이 준비중.