OMC213 A - D

Online Math Contest

2024-03-15

Online Math Contest

앳코더를 요새 열심히 하던 중에 프로그래밍이 아닌 수학만으로 비슷하게 경쟁하는 Online Math Contest에 대해 알게 되었다.
꽤나 흥미진진한 문제가 가득.

평소에 앳코더 해설 번역하듯 이것도 해설을 번역해도 되는가 여쭤봤더니 괜찮다는 답변이 왔다.
그런 관계로 이번 대회 OMC213(for beginners)의 문제와 해설을 번역해 보았다.

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

A

문제

어떤 마을에 주민이 $9 \times 10^{11}$명 있고, 각각 서로 다른 $12$자리(제일 앞자리는 $0$이 아닌) 고유번호가 부여되어 있습니다.
이 마을에서는 다음 조건을 만족하는 서로 다른 두 사람의 주민 둘에 대해서만, 서로 친구가 될 수 있습니다.

• 두 사람의 고유번호를 $10$진법으로 합했을 때, 자릿수 올림이 발생하지 않는다.

마을 주민 $U$군의 고유번호는 $808080808080$입니다. $U$군과 친구가 될 수 있는 주민은 몇 명 일까요?

해설

우선, 제일 앞자리는 $1$이어야만 합니다. 남은 $8$에 대해서는 각각 $0, 1$의 2가지 경우가 있으며, 그 이외의 $0$에 대해서는 각각 $10$가지의 경우가 존재하므로, 구하는 답은

$$1 \times 2^5 \times 10^6 = 32000000$$

B

문제

실수 $a$가 있습니다. 아래의 $3$개의 직선으로 $xy$좌표평면을 분할했을 때, 삼각형이 생기지 않았습니다.

$$y = x - 8,\ 3x - 2y = 6,\ y = ax + 2$$

이 때, $a$로써 가능한 값들의 총합을 서로소인 두 양의 정수 $p, q$를 이용해 $\frac{p}{q}$로 나타낼 수 있습니다. $p + q$의 값을 구하세요.

해설

$3$개의 직선이 삼각형을 이루지 않을 때, $3$개의 직선이 하나의 교점에서 만나든지, $2$개의 직선이 평행한 경우입니다.

• 전자의 경우: $y = ax + 2$가 $y = x - 8,\ 3x - 2y = 6$의 교점인 $(-10, -18)$을 지나므로, $a = 2$이다.
• 후자의 경우: $y = ax + 2$가 $y = x - 8$과 평행하다면 $a = 1$, $3x - 2y = 6$과 평행하다면 $a = \frac{3}{2}$이다.

따라서, 구하는 총합은 $\frac{9}{2}$이며, 답은 $11$입니다.

C

문제

$2$이상 $25$이하의 양의 정수 $n$에 대해, 다음 조건을 만족하는 것들의 총합을 답하세요.

• $n - 1$이하의 모든 양의 정수 $k$에 대해, $kn$은 제곱수가 아니다.

해설

$n$을 소인수분해했을 때 모든 지수가 $1$인 경우, 명백히 조건을 만족합니다.
반대로, 그렇지 않을 경우 $n$은 $2$이상의 제곱수인 양의 정수 $m$을 약수로 가지며, 이 때 $\frac{n}{m} \times n = \frac{n^2}{m}$이 제곱수가 되므로, 조건을 만족하지 못합니다.

따라서, 문제의 조건을 만족하는 $n$은

$$2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23$$

이며, 총합은 $188$입니다.

D

문제

$0$이상 $999$이하의 정수의 묶음 $(a, b, c)$중에서, $a + b + c$($10$진법으로) 계산했을 때 자릿수 올림이 발생하는 것은 몇 개 있습니까?

해설

자릿수 올림이 발생하지 않는 묶음 $(a, b, c)$의 수를 세어 봅시다.

$a$의 $1$의 자리, $10$의 자리, $100$의 자리를 각각 $A_0, A_1, A_2$라고 하고, 마찬가지로 $B_0, B_1, B_2, C_0, C_1, C_2$를 정의합니다.
$a + b + c$를 계산했을 때 자릿수 올림이 발생하지 않는다는 것은 다음과 동치입니다.

$$A_i + B_i + C_i \leq 9\ (i = 0, 1, 2)$$

$i$의 값에 상관없이 위의 식을 만족하는 $0$이상 $9$이하의 정수의 묶음 $A_i, B_i, C_i$는 $_{12} C_3$개 있습니다.
따라서 자릿수 올림이 발생하지 않는 $(a, b, c)$의 수, 즉, $0$이상 $9$이하의 정수의 묶음 $(A_0, B_0, C_0, A_1, B_1, C_1, A_2, B_2, C_2)$는 $(_{12} C_3)^3$개 만큼 있습니다.

따라서 자릿수 올림이 발생하는 $(a, b, c)$의 수는 다음과 같습니다.

$$1000^3 - (_{12}C_3)^3 = 989352000$$

처음은 3문제 정도

처음 참가하느 것이기도 했고 쫄렸던게 있어서 레이팅 반영 없이 참가했다.
문제들은 연습삼아 본 것들 비슷하게 수학적 관찰을 꽤 요구하는 편.

대회 시간 내에는 적당히 3문제 푼 다음 D번을 보기만 하고 지나갔지만, 다음엔 더 열심히 해봐야지.