OMC215


Online Math Contest

2024-03-23

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

A

문제

\(1 \leq a \leq 1000, 1 \leq b \leq 1000\)인 정수 \(a, b\)에 대해,

\[\frac{a^2 - 1001a + 1001^2}{b^2 - 1001b + 1001^2}\]

가 최댓값을 가질 때의 \(a + b\)로써 가능한 값들의 총합을 구하세요.

해설

\[\frac{a^2 - 1001a + 1001^2}{b^2 - 1001b + 1001^2} \leq \frac{\mathrm{max} \{a^2 - 1001a + 1001^2 \} }{\mathrm{min} \{ b^2 - 1001b + 1001^2 \} }\]

이므로, 등호가 성립하는 것은 \(a = 1, 1000\)이면서 \(b = 500, 501\)일 때이므로, 구하는 답은

\[(1 + 500) + (1 + 501) + (1000 + 500) + (1000 + 501) = 4004\]

B

문제

\(100 \times 100\)의 격자판이 있습니다. \(N\)개의 칸을 골라 깃발을 각 칸에 1개씩 두었을 때, 다음이 성립했습니다.

\(N\)으로 가능한 최댓값을 구하세요.

해설

전체 격자판을 \(1 \times 3, 3\times 1\)의 연속된 칸들 \(A\)로 분할하면, 각 \(A\)마다 배치할 수 있는 깃발은 많아야 \(2\)개입니다. (해설 원문의 그림 참고)
따라서, 가능한 \(N\) 의 최댓값은 \(1 + 3333 \times 2 = 6667\)개입니다.

C

문제

\(10^5\)의 약수이면서 \(3\)으로 나눈 나머지가 \(1\)인 것의 총합을 구하세요.

해설

\(10^5 = 2^5 \tiems 5^5\)의 약수는 \(2^a \times 5^b \ (a, b \in \{ 0, 1, 2, 3, 4, 5 \} ) \)로 나타낼 수 있습니다.

\[2^a \times 5^b \equiv (-1)^{a + b} \mod 3 \]

이므로 약수 \(2^a \times 5^b\)를 \(3\)으로 나눈 나머지가 \(1\)인 것은 \(a, b\)의 합이 짝수인 것과 같습니다.
따라서 구하는 총합은

\[(2^0 + 2^2 + 2^4)(5^0 + 5^2 + 5^4) + (2^1 + 2^3 + 2^5)(5^1 + 5^3 + 5^5) = 150381\]

D

문제

\(AB \Vert BC\)인 사다리꼴 \(ABCD\)가 있습니다. 변 \(AD\) 위에 점 \(X\)를, 선분 \(AC\)위에 점 \(Y\)를, 변 \(BC\)위에 점 \(Z\)를 잡았을 때, 다음이 성립했습니다.

\[AB = 1001, BC = 3004, CD = 2001, \ AX = 3, XD = 997, AY : YC = 1 : 3\]

꺾은선 \(XYZ\)(= 선분 \(XY\)와 선분 \(YZ\)를 이은 것)가 사다리꼴 \(ABCD\)를 \(2\)등분할 때, 선분 \(BZ\)의 길이를 구하세요.

해설

변 \(BC\)위의 점 \(P\)가 있어서, 선분 \(XP\)가 사다리꼴 \(ABCD\)의 넓이를 \(2\)등분 하는 경우를 생각해봅시다.
구체적으로는 \(BP = 1999\)를 만족하는 점입니다.
삼각형 \(XYZ, XPZ\)는 넓이가 같으므로 \(XZ \Vert YP\)가 성립합니다. 따라서 직선 \(XY\)와 변 \(BC\)의 교점을 \(Q\)라 두면 \(PQ : PZ = YQ : YX = YC : YA = 3 : 1\)입니다.
여기서 \(CQ = 3AX = 9\)인 것으로부터 \(BQ = 2995\)이므로, \(BP = 1999\)인 것을 이용하면 \(PQ = 996\)임을 알 수 있습니다.

이상으로부터 \(PZ = 332\)이며, \(BZ = BP - PZ = 1667\)입니다.

E

문제

\(999\)또는 \(1001\) 중 적어도 한 쪽으로 나누어 떨어지는 양의 정수를 좋은 수라 부르겠습니다.
양의 정수 \(n\)에 대해, \(n\)이하의 좋은 수의 개수를 \(f(n)\)이라 할 때, 다음의 값을 구하세요:

\[f(1) + f(2) + … + f(999999)\]

해설

\(999 = p, 1001 = q\)라 하고, \(S = f(1) + f(2) + … + f(pq)\)라 합시다.
좋은 수 \(a\)에 대해 \(1 \leq a \leq pq\)를 만족하는 것들 전체의 집합을 \(A\)라 합시다. \(p, q\)는 서로소이므로, \(\vert A \vert = p + q -1\)입니다.
여기서 \(a \in A\)에 대해, \(n\)이하의 좋은 수로써 \(a\)가 존재하는 \(1 \leq n \leq pq\)인 \(n\)은 \(pq + 1 -a\)개 만큼 있습니다.
즉 \(a \in A\)는 \(pq + 1 - a\)만큼 \(S\)의 값에 기여하므로,

\[\begin{align} S & = \sum_{a \in A} (pq + 1 - a) \nonumber \\ & = (pq + 1) \vert A \vert - \sum_{a \in A} a \nonumber \\ & = (pq + 1)(p + q -1) - (\sum_{k = 1}^q pk + \sum_{k = 1}^p qk - pq) \nonumber \\ & = (pq + 1)(p + q -1) - \frac{pq}{2}(p + q) \nonumber \\ & = 1000000 \times 1999 - 999999 \times 1000 = 999001000 \nonumber \end{align}\]

F

문제

\[\angle{ABD} + \angle{ACD} = 180^{\circ}\]

인 볼록 사각형 \(ABCD\)에서, 그 \(2\)개의 대각선의 교점을 \(E\)라 뒀을 때,

\[AE = 61, BE = 47, CE = 21, DE = 51\]

이 성립했습니다. 변 \(AD\)의 길이를 구하세요.

해설

각도에 대한 다음의 식으로부터 \(\angle{ABD} \geq \angle{CAD}\)이므로, 삼각형 \(ABE\)의 외접원과 변 \(AD\)는 \(A\)가 아닌 점에서 다시 만난다는 것을 알 수 있습니다.

\[\angle{ABD} = 180^{\circ} - \angle{ACD} = \angle{CAD} + \angle{ADC} = \angle{CAD}\]

이 교점을 \(F\)라고 하면,
\[\angle{AFE} = 180^{\circ} - \angle{ABD} = \angle{DCE}\]

인 것으로부터, \(F\)는 삼각형 \(CDE\)의 외접원 위에 있음을 알 수 있습니다.
따라서 방벽 정리에 의해 다음이 성립합니다.

\[AF \times AD = 61 \times 82 = 5002, DF \times AD = 51 \times 98 = 4998\]

따라서 \(AD^2 = AF \times AD + DF \times AD = 10000\)인 것으로부터, \(AD = 100\)입니다.

G

문제

\(1, 2, …, 20\)으로 구성된 순열 \(a_1, a_2 …, a_{20}\)에서 \(1\)이상 \(20\)이하의 임의의 정수 \(i, j\)에 대해 \(a_ia_j \leq ij + 20\)이 성립하는 것은 몇 개 있을까요?

해설

지문의 조건에 부합하는 집합 \(a_1, …, a_{20}\)을 좋은 집합이라고 합시다.
좋은 집합에 대해 \(a_p = 20\)인 \(1 \leq p \leq 20\)을 정하고, 지문의 부등식에 대해 \(j = p\)라고 두면

\[20a_i = a_ia_p \leq ip + 20 \leq 20(i + 1)\]

이므로 모든 정수 \(1 \leq i \leq 20\)에 대해 \(a_i \leq i + 1\)일 필요가 있습니다.

\(a_i = i + 1\)일 때 주어진 부등식에 의해, \((i + 1)^2 \leq i^2 + 20\)이므로, \(i = 1, 2, …, 9\)일 핑요가 있습니다.
이상으로부터 다음의 조건이 \(A\)가 좋은 집합이기 위한 필요조건이 됩니다. 이 조건을 만족하는 \(A\)가 좋은 집합임을 알 수 있습니다.

\[a_i \begin{cases} i + 1 \ (i = 1, 2, …, 9) \\ i \ (i = 10, 11, …, 20) \end{cases}\]

따라서 이 조건을 만족하는 \((a_1, a_2, …, a_{20})\)인 집합의 수를 구하면 됩니다. \(a_1\)부터 순서대로 정해가면 \(a_9\)까지 각각 2가지, \(a_{10}\)부터 \(a_{20}\)까지 1가지 경우가 있으므로, 구하는 순열의 개수는 \(2^9 = 512\)개 입니다.

H

문제

정 \(3n\)각형에서, 그 정점들만으로 이루어진 집합을 \(S_n\)이라고 합시다.
다음의 조건을 만족하는 관계 \(f : S_n \rightarrow S_n\)의 개수를 \(a_n\)이라고 합시다:

이 때, 다음의 값을 소수 \(100003\)으로 나눈 나머지를 구하세요:

\[a_{100000} - \sum_{n = 1}^{99999}(6n + 5)a_n\]

해설

\(a_1 = 2, a_2 = 40\)입니다. 이후 \(n \geq 3\)이라 둡니다.
정 \(3n\)각형의 정점을 시계방향으로 \(A_1, …, A_n, B_1, …, B_n, C_1, …, C_n\)이라 합시다. 지문의 조건을 만족하는 관계 \(f\)를 좋은 관계라고 부르겠습니다.
좋은 관계는 일대일 함수입니다. 어떤 \(1 \leq i \leq n\)에 대해 \(\{ f(A_i), f(B_i), f(C_i) \} = \{ A_n, B_n, C_n \} \)이 성립하므로, \(i\)가 \(n\)과 같은가에 따라 경우를 나눠 생각해봅시다.

이상으로부터 다음의 점화식을 구할 수 있습니다.

\[a_n = 2a_{n - 1} + 24(n - 1)a_{n - 2} + 6(n - 1)a_{n - 1}\]

이를 변형해 다음의 식을 얻습니다.

\[a_n - 6na_{n - 1} = -4(a_{n - 1} - 6(n - 1)a_{n - 2})\]

위 식과 \(a_1 = 2, a_2 = 40\) 인 것으로부터 수열 \( \{ a_{n = 1} - 6(n + 1)a_n \} \)은 초항이 \(16\), 공비가 \(-4\)인 등비수열이 됩니다.
따라서 \(a_{n + 1} - 6(n + 1)a_n = (-4)^{n + 1}\)이므로, 다음과 같이 계산할 수 있습니다.

\[\begin{align} a_{100000} - \sum_{n = 1}^{99999}(6n + 5)a_n & = a_{100000} - \sum_{n = 1}^{99999}(a_{n + 1} - a_N - (-4)^{n + 1}) \nonumber \\ & = a_1 + \sum_{n = 1}^{99999} (-4)^{n + 1} \nonumber \\ & = 2 + \frac{1}{5} (16 + 4^{100001}) \nonumber \\ & \equiv 2 + \frac{1}{5}(16 + \frac{1}{4}) \ (\mathrm{mod} \ 100003) \nonumber \\ & \equiv \frac{21}{4} \ (\mathrm{mod} \ 100003) \nonumber \\ & \equiv 25006 \ (\mathrm{mod} \ 100003) \nonumber \end{align}\]

기하는 어렵다

다른거 하다 오느라 30분 정도 늦기도 했고, 본인이 약한 기하문제들이 많아서 1문제 밖에 못 풀었다…

진짜 더 열심히 해야지.

« PREV NEXT »
© 2024 SeokguKim   •  Base Theme  Moonwalk