OMC217

Online Math Contest

2024-04-11

대회 링크
https://onlinemathcontest.com/contests/omc217

A

문제

\(x\)에 대한 \(2\)차 방정식 \(x^2 2nx + 6n - 57 = 0\)이 정수해를 가지는 양의 정수 \(n\)의 총합을 구하세요.

해설

판별식을 \(D\)라고 하면, \(D/4 = n^2 - 6n + 57\)인 것으로부터, 이것이 제곱수가 되는 \(n\)을 모두 구하면 됩니다.
\(D/4\)를 음이 아닌 정수 \(m\)을 이용해 \(m^2\)로 나타내면, 조건은

\[(m + n - 3) (m - n + 3) = 48\]

로 변형할 수 있습니다. \(m + n - 3\)과 \(m - n + 3\)의 홀짝이 일치한다는 점을 주의해서 곱이 \(48\)이 되는 2개의 쌍을 찾는 것으로, \((m, n)\)의 쌍으로 가능한 것들은 \((7, 2), (7, 4), (8, 7), (13, 14)\)가 있고, 구하는 합은 \(27\)입니다.

B

문제

넓이가 \(768\)인 삼각형 \(ABC\)의 내부에 점 \(P\)를 잡았을 때, 다음을 만족했습니다.

\[AB : BC : CA = \vert \triangle{ABP} \vert : \vert \triangle{BCP} \vert : \vert \triangle{CAP} \vert = 3 : 4 : 5\]

\(BP\)의 길이를 구하세요.
(단, \(\vert \triangle{XYZ} \vert\)는 삼각형 \(XYZ\)의 넓이를 나타냅니다.)

해설

조건으로부터, 직선 \(AB, BC, CA\)와 점 \(P\)와의 거리는 모두 같으므로, \(P\)는 삼각형 \(ABC\)의 내심입니다. 또, \(AB = 3x, BC = 4x, CA = 5x\)라고 두면,

\[AB^2 + BC^2 = CA^2\]

가 성립하므로, \(\angle{B} = 90^{\circ}\)입니다. 따라서,

\[768 = \frac{1}{2} AB \times BC = 6x^2\]

인 것으로부터, \(x = 8\sqrt{2}\)입니다. 따라서,

\[AB = 24\sqrt{2}, BC = 32\sqrt{2}, CA = 40sqrt{2}\]

입니다. 여기서, \(P\)에서 변 \(AB, BC, CA\)에 내린 수선의 발을 각각 \(D, E, F\)라 하면, 사각형 \(BDPE\)는 직사각형이 되며, 특히 \(PD = PE\)이므로 정사각형이 됩니다. 또한, \(P\)가 내심인 것을 생각하면,

\(AD = AF, CE = CF\)

가 각각 성립하므로,

\[BP = \sqrt{2}BD = \sqrt{2} \times \frac{BD + BE}{2} = \frac{(AB - AD) + (BC - CE)}{\sqrt{2}} = \frac{AB + BC - CA}{\sqrt{2}} = 16\]

입니다.

C

문제

\(S = \{1, 2, …, 9000\}\)라고 둡시다.
임의의 \(S\)의 공집합이 아닌 부분집합 \(T\)에 대해, \(T\)의 모든 원소들의 곱을 \(3\)으로 나눈 나머지를 \(f(T)\)라 합시다.
\(T\)가 \(S\)의 공집합이 아닌 부분집합 전체를 움직일 때, \(f(T)//)의 평균은 서로소인 두 양의 정수 \(a, b\)를 이용해 \(\frac{b}{a}\)와 같이 나타낼 수 있습니다.
\(b\)를 소수인 \(2999\)로 나눈 나머지를 구하세요.

해설

\(T \subset S\)에 \(3\)의 배수가 포함될 때, \(f(T) = 0\)이 됩니다.
그리고 \(T \subset S\)에 \(3\)의 배수가 포함되지 않을 때를 생각해 봅시다. 이 때 다음이 성립합니다.

• \(T\)에 \(3\)으로 나눠 \(2\)가 남는 수가 짝수 개 있다면 \(f(T) = 1\), 홀수 개 있다면 \(f(T) = 2\).

따라서,

\[A = _{3000}C_0 + _{3000}C_2 + … + _{3000}C_{3000}, B = _{3000}C_1 + _{3000}C_3 + … + _{3000}C_{2999}\]

라고 두면, \(f(T) = 1\)인 \(T \subset S\)의 개수 \(n_1\), \(f(T) = 2\)인 \(T \subset S\)의 개수 \(n_2\)는 각각

\[n_1 = 2^{3000}A - 1, n_2 = 2^{3000}B\]

로 나타낼 수 있습니다. 여기서, 다음의 보제가 성립합니다.

보제. \(A = B = 2^{2999}\)

이항정리로부터,

\[2^{3000} = (1 + 1)^{3000} = A + B, 0 = (1 - 1)^{3000} = B - A\]

가 각각 성립하므로, 이들 \(2\)개의 식을 연립하여 풀면 위의 결과가 됩니다.

보제로부터, 구하는 평균은 다음과 같이 계산할 수 있습니다.

\[\frac{1 \times n_1 + 2 \times n_2}{2^{9000} - 1} = \frac{3 \times 2^{5999} - 1}{2^{9000} - 1}\]

이 때, 소수 \(p\)가 \(3 \times 2^{5999} - 1\)과 \(2^{9000} - 1\)을 나눌 수 있다고 가정합니다. 즉,

\[3 \times 2^{5999} \equiv 2^{9000} \equiv 1\]

이 성립하는 것으로 봅시다. 이 때ㅡ \(2^{9000} -1\)은 홀수이므로, \(p\)는 홀수인 소수입니다. 또한,

\[3 \equiv \frac{1}{2^{5999}} \equiv \frac{2^{9000}}{2^{5999}} \equiv 2^{3001}\ (\mathrm{mod}\ p)\]

가 성립합니다. 따라서,

\[27 = 3^3 \equiv (2^{3001})^3 = 8 \times 2^{9000} \equiv 8\ (\mathrm{mod}\ p)\]

인 것으로부터, \(p = 19\)입니다. 한편으로, 페르마의 소정리에 의해 \(3 \times 2^{5999} - 1\)과 \(2^{9000} - 1\)은 모두 \(19\)로 나누어 떨어집니다. 또한, 지수 리프팅 보조정리에 의해 \(2^{9000} - 1\)은 \(19^2\)로 나누어 떨어지지 않는 것을 확인할 수 있으므로,

\[b = \frac{3 \times 2^{5999} - 1}{19}\]

입니다. 이를 \(2999\)로 나눈 나머지는 \(2211\)입니다.

D

문제

삼각형 \(ABC\)와 그 내부의 점 \(P\)가 다음의 조건을 만족합니다.

\[\angle{PBC} : \angle{CAP} : \angle{ABP} : \angle{PAB} : \angle{BCP} = 1 : 2 : 3 : 4 : 5\]

이 때, \(\angle{PCA}\)의 크기는 서로소인 두 양의 정수 \(a, b\)를 이용해 \(\frac{a}{b}\)도로 나타낼 수 있습니다.
\(a + b\)를 구하세요.

해설

\(\angle{PBC} = x\)라고 두고, 선분 \(BC\)에 대해 \(A\)와 대칭인 점을 \(A’\)라고 합시다.

\[\angle{BA’C} + \angle{CPB} = (4x + 2x) + (180^{\circ} - 5x - x) = 180^{\circ}\]

이므로, \(4\)개의 점 \(A’, B, C, P\)는 같은 원 위에 있습니다.
따라서 \(\angle{PBA’} = \angle{PA’B} = 5x\)이므로 \(BP = A’P\)임을 알 수 있습니다. 이로부터 직선 \(PD\)는 \(BA’\)의 수직이등분선이므로, \(AB = AA’\)이고, 삼각형 \(ABA’\)는 정삼각형입니다.
따라서, \(\angle{ABA’} = 8x = 60^{\circ}\)인 것으로부터 \(x = 7.5^{\circ}\)임을 구할 수 있으므로,

\[\angle{PCA} = 180^{\circ} - 7.5^{\circ} \times 15 = 67.5^{\circ}\]

가 되며, 구하는 답은 \(137\)입니다.

E

문제

양의 정수 \(n\)에 대해, \(n\)의 양의 약수들 중 음이 아닌 정수 \(k\)를 이용해서 \(2^k\)의 꼴로 나타낼 수 있는 것들의 총합을 \(f(n)\)이하고 합시다.
또한, \(g(n) = -1000n + \sum_{k - 1}^nf(k)\)라고 정의합시다.

양의 정수 \(n\)이 \(2^{1000} \leq n \leq 2^{1001}\)을 만족하며 움직일 때, \(g(n)\)으로 가능한 \(37\)번째로 큰 값을 소수인 \(997\)로 나눈 나머지를 구하세요.

해설

\(2^k\)를 약수로 가지는 \(1\)이상 \(n\)이하의 정수의 개수을 \(C_{n, k}\)라고 나타내면,

\[\sum_{k = 1}^nf(k) = \sum_{k = 0}^{\infty}2^kC_{n, k}\]

입니다. 여기서 \(C_{n, k} = \left \lfloor \frac{n}{2^k} \right \rfloor\)인 것으로부터, 양의 정수 \(x, y\)에 대해 \(x \% y\)로 \(x\)를 \(y\)로 나눈 나머지를 나타내면,

\[2^kC_{n, k} = n - n\%2^k\]

입니다. \(2^{1000} \leq n < 2^{1001} - 1\)인 경우에는 \(C_{n, k} > 0\)인 \(k\)의 범위는 \(0 \leq k \leq 1000\)이므로,

\[g(n) = -1000n + \sum_{k = 0}^{1000}(n - n \% 2^k) = n - \sum_{k = 0}^{1000}n \% 2^k\]

임을 알 수 있습니다.
여기서, \(n\)의 \(2\)진법 표기를 \(b_{1000}b_{999}…b_0\)이라 둡시다. 이 때 \(n \% 2^0 = 0\)이고, \(k \geq 1\)일 때는

\[n \% 2^k = \sum_{i = 0}^{k - 1}2^ib_i\]

가 되므로,

\[\sum_{k = 0}^{1000}n \% 2^k = \sum_{k = 0}^{1000}2^k(1000 - k)b_k\]

가 됩니다. 이로부터, \(b_{1000} = 1\)인 것에 주의하면,

\[g(n) = n - \sum_{k = 0}^{1000}n \% 2^k = 2^{1000} - \sum_{k = 0}^{999}2^k(999 - k)b_k\]

임을 알 수 있습니다.
여기서, \(\sum_{k = 0}^{999}2^k(999 - k)b_k\)의 각 항의 \(b_k\)의 계수는 \(k\)에 대해 (\(k = 999\)를 제외하고) 단조 비감소하게 됩니다. 또한,

\[\sum_{k = 0}^42^k(999 - k) < 2^5(999 - 5), \sum_{k = 0}^12^k(999 - k) < 2^2(999- 2)\]

가 각각 성립하므로, \(g(n)\)으로써 가능한 \(37\)번째로 큰 값은

\[2^{1000} - (2^5(999 - 5) + 2^2(999 - 2)) = 2^{1000} - 35796\]

이며, 이를 \(997\)로 나눈 나머지는 페르마의 소정리에 의해 \(112\)가 됩니다.

붙임. 마지막의 유도과정과 마찬가지로 생각해서, \(n - 2^{1000}\)이 충분히 작은 범위에서는 \(g(n)\)이 단조 감소하는 것을 알 수 있습니다.

F

문제

양의 실수 \(x, y, z\)가

\[\frac{x}{x + \sqrt{y}} + \frac{y}{y + \sqrt{z^2}} + \frac{z}{z + \sqrt{x^3}} = 1\]

을 만족할 때, \(z\)로써 가능한 값의 최댓값은 서로소인 두 양의 정수 \(p, q\)를 이용해 \(\frac{q}{p}\)로 나타낼 수 있습니다.
\(pq\)의 양의 약수의 개수를 구하세요.

해설

양의 실수 \(X, Y, Z\)에 대해,

\[X = \frac{x}{x + \sqrt{y}}, Y = \frac{y}{y + \sqrt{z^2}}, Z = \frac{z}{z + \sqrt{x^3}} = 1\]

로 나타냅시다. 산술 - 기하 평균의 관계로부터,

\[\begin{align} \frac{1}{z} & = \left( \frac{\sqrt{y}}{x} \right)^6 \left( \frac{z}{y}\right)^3 \left( \frac{\sqrt{x^3}}{z} \right)^4 \nonumber \\ & = \left( \frac{1 - X}{X} \right)^6 \left( \frac{1 - Y}{Y} \right)^3 \left( \frac{1 - Z}{Z} \right)^4 \nonumber \\ & = \frac{(Y + Z)^6}{X^6} \frac{(Z + X)^3}{Y^3} \frac{(X + Y)^4}{Z^4} \nonumber \\ & = \frac{1}{X^6Y^3Z^4} \left(\frac{Y}{5} \times 5 + \frac{Z}{7} \times 7\right)^6 \left(Z +\frac{X}{5} \times 5\right)^3 \left(\frac{X}{7} \times 7 + Y\right)^4 \nonumber \\ & \geq \frac{1}{X^6Y^3Z^4} \left(12 \sqrt[12]{\frac{Y^5}{5^5} \times \frac{Z^7}{7^7}}\right)^6 \left(6 \sqrt[6]{Z \times \frac{X^5}{5^5}}\right)^3 \left(8 \sqrt[8]{\frac{X^7}{7^7} \times Y}\right)^4 \nonumber \\ & = \frac{2^{27} \times 3^9}{5^5 \times 7^7} \nonumber \end{align}\]

여기서 실제로 등호를 성립시키는 \(x, y, z\)가 존재하는 것으로부터, 구하는 답은 \(28 \times 10 \times 6 \times 8 = 13440\)이 됩니다.

비기너 디비전이 아니면 역시 어렵다

수학이 특기는 아니고 문과다 보니 역시 비기너 디비전이 아니면 2문제가 고작인가 싶다.

더 잘하고 싶지만 지금은 이게 최선.