HMMT 2022년 11월 General 9번 문제
자연수 $n$ 에 대해서 다음 값
\[\mathcal{L} = \mathrm{lcm} (1, 2, ... , n) \times \left ( \frac{1}{1} + \frac{1}{2} + ... + \frac{1}{n} \right)\]이 45의 배수가 될 경우, quixotic 하다고 부른다. 이 경우, 10번째로 작은 quixotic 자연수를 구하시오.
배수인지를 확인하는 문제의 경우, 소수의 제곱꼴로 나오는 수들로 각각 배수인지를 확인하는 것이 더 편하다. 소수의 배수인지를 확인하는 것이 소수의 특징을 사용할 수 있기 때문이다.
이제 $n$을 고정시키자. 45를 소인수분해 하면 $3^2 \times 5$이다. 따라서 위의 값이 5의 배수를 만족하기 위해서 필요한 조건과 $3^2$의 배수를 만족하기 위해 필요한 조건을 구한 뒤, 두 조건을 모두 만족하는 값을 찾도록 하자.
위의 값을 추가로 정의한 값에 따라 변형하면,
\[\mathcal{L} = \sum_{i=0}^{i=k_p} { \sum_{k \in S_p^i} {\mathrm{lcm}(1, 2, ... , n) \frac{1}{k}}}\]가 된다. 특징을 살펴보면, $M_n$은 $p^{k_p}$의 배수이지만, $p^{k_p+1}$의 배수가 아니라는 점이다. 이 특징을 이용하면, 위의 식에서 상당 부분을 제거할 수 있다. $\frac{1}{k}$의 $k$가 $p^{k_p}$의 배수가 아닌 이상, $\frac{\mathrm{lcm}(1, 2, … , n)}{k}$ 값은 항상 $p$의 배수가 될 수밖에 없다. 그렇기 때문에, $\mathcal{L}$이 $p$의 배수인지 보기 위해서는 $i=k_p$인 부분에서 그 내부의 값이 $p$의 배수인지 확인하면 된다.
$p=5$이고, $S_p^{k_p}$의 경우의 수는 $\{1\}, \{1, 2\}, \{1, 2, 3\}, \{1, 2, 3, 4\}$가 될 수 있다. 각 경우에 대해서 5의 배수가 되는지 확인해 보자.
즉, $\mathcal{L}$가 p의 배수가 되기 위해서는 $S_p^{k_p}$가 $\{1, 2, 3, 4\}$가 되어야 한다. 다시 말하면, $p$진법으로 $n$을 적었을 때 가장 최고자리 숫자가 4여야 한다.
이번에는 $p=3$인 경우이다. 하지만 9는 3의 제곱이기 때문에, $S_p^{k_p}$뿐만 아니라, $S_p^{k_p-1}$도 보아야 한다. 그 이유는 위 식에서 $i=k_p-1$일 때에는 $p$의 배수임을 보장할 수 있지만, $p^2$의 배수인지는 보장할 수 없기 때문이다.
이제 확인해 보아야 할 집합은 $S_p^{k_p}$와 $S_p^{k_{p-1}}$이 되고 총 경우의 수는 6가지 이다.
위 중에서 분모가 9의 배수가 되는 경우는 (5) 케이스 뿐인데, 이 경우는 3진법으로 n을 적을 때, 가장 최고자리 수가 21여야 한다.
이 둘의 경우를 모두 종합해서 두 조건을 모두 만족하는 경우를 확인해 보자.
이 두 조건의 교집합을 하면, 21~23, 500~624가 된다. 따라서 10번째로 조건을 만족하는 작은 수는 506이 된다.