こんにちは。今回は今回は一橋大の2025前期大問1についてみていきます。
問題
正の整数 \(n\) に対し、 \(n\) の正の約数の個数を \(d(n)\) とする。たとえば、 \(6\) の正の約数は \(1,2,3,6\) の4個なので、 \(d(6)=4\) である。また、
$$f(n)=\frac{d(n)}{\sqrt{n}}$$
とする。
(1) \(f(2025)\) を求めよ。
(2) 素数 \(p\) と正の整数 \(k\) の組で \(f(p^k)\le f(p^{k+1})\) を満たすものを求めよ。
(3) \(f(n)\) の最大値と、そのときの \(n\) を求めよ。
考え方
「約数の個数」に関する整数問題です。本問は「約数の個数」についてゴリゴリに深掘る問題なので、約数の数え方を知らないと門前払いされてしまいます。逆に、約数がきちんと数えられさえすれば(2)あたりまではスルスル解き進められます。(3)は骨太な難問ですが解き切れれば爆アドです。
ということで、まずは約数の数え方について簡単に復習してみます。
まずは題意で与えられた \(d(6)\) の数え方について考えます。\(6=2 \times 3\) の4個の約数(1,2,3,6) について、2を約数に含まないものは(1,3)で2個、2を約数に含むものは(2×1,2×3)の2個であり、これらは等しく3の約数(1,3)の個数に等しい状況です。すなわち、
$$d(2^1 \times 3^1)=(1+1)\times d(3^1)=2\times 2=4$$
これを拡張します。\(n\) が素因数 \(p\) で \(k\) 回割り切れるとき、 \(n\) は \(p\) と互いに素な正の整数 \(m\) を用いて \(n=p^k m\) と表せます。 このとき、\(n\) の約数のうち \(p\) で \(l\) 回(\(0\le l\le k\))だけ割り切れるものの個数はすべて等しく \(d(m)\) であるため、
$$d(p^km)=(k+1)d(m)$$
が成立します。
最後にこれを一般化します。(\(p_1,p_2,…,p_k\)) を相違な \(k\) 個の素数、(\(q_1,q_2,…,q_k\))を1以上の整数として、 \(n=p_1^{q_1}p_2^{q_2}…p_k^{q_k}\) と素因数分解できるとき、 \(n\) の約数の個数は、
\(d(n)=d(p_1^{q_1}p_2^{q_2}…p_k^{q_k})=(q_1+1)(q_2+1)…(q_k+1)\)
と表せます。上式は「約数の個数」絡みの整数問題では必須級の公式なので、丸暗記しておくのが安牌かと思います。
本問ではこの公式をブンブンに振り回して解き進めていくことになります。
(1)
公式にブチ込んで計算します。
$$f(2025)=\frac{d(3^4\times 5^2)}{\sqrt{3^4\times 5^2}}=\frac{(4+1)(2+1)}{45}=\frac{1}{3}$$
(2)
公式にブチ込んで同値変形します。
$$f(p^k)\le f(p^{k+1})$$
$$\Leftrightarrow \frac{k+1}{\sqrt{p^k}}\le \frac{k+2}{\sqrt{p^{k+1}}}$$
$$\Leftrightarrow \sqrt{p} \le \frac{k+2}{k+1}=1+\frac{1}{k+1}$$
\(k\) は1以上の整数なので、
$$\sqrt{p}\le 1+\frac{1}{1+1}=1.5$$
$$\Rightarrow p \le 1.5^2=2.25$$
が必要で、これを満たす素数は \(p=2\) に絞られます。このとき、与式は
$$\sqrt{2}\le \frac{k+2}{k+1} \Leftrightarrow (\sqrt{2}-1)k\le 2-\sqrt{2} \Leftrightarrow k\le \sqrt{2} \Leftrightarrow k=1$$
と同値変形できるため、求める組は、(p,k)=(2,1) と求まります。
本番ではここまで記述できれば十分だと思います。
(3)
ここからが本題です。(3)だけで大きな難所が3か所くらいあります。険しい道のりですが頑張っていきましょう。
まずはゴールの確認をします。(3)のゴールは、「\(f(n)\) の最大値とそのときの \(n\) を求める」です。求めるものが２つありますが、\(n\) さえわかれば相方の \(f(n)\) は自動的に求まるっぽいので、実質的なゴールは「\(f(n)\) の最大値を与える \(n\) を求める」になります。コレを念頭に考察していきます。
(2)までの流れを踏まえると、\(n\) は素因数分解された形で表した方が見通しがよさそうなので、ちょっと気が重いですが頑張って素因数分解してみましょう。
\(n\) が \(k\) 種の相違な素数(\(p_1,p_2,…,p_k\))および1以上の整数(\(q_1,q_2,…,q_k\))を用いて\(n=p_1^{q_1}p_2^{q_2}…p_k^{q_k}\) と表される場合を考えると、 \(f(n)\) は
$$f(n)=\frac{(q_1+1)(q_2+1)…(q_k+1)}{\sqrt{p_1^{q_1}p_2^{q_2}…p_k^{q_k}}}$$
と表すことができます。この表式をじっくり眺めてみると、
$$f(n)=\frac{q_1+1}{\sqrt{p_1^{q_1}}}\frac{q_2+1}{\sqrt{p_2^{q_2}}}…\frac{q_k+1}{\sqrt{p_k^{q_k}}}$$
と分割できることに気づきます。各 \(\frac{q_k+1}{\sqrt{p_k^{q_k}}}\) は \(f(p_k^{q_k})\) に等しいため、
\(f(n)=f(p_1^{q_1}p_2^{q_2}…p_k^{q_k})=f(p_1^{q_1})f(p_2^{q_2})…f(p_k^{q_k})\)
と記述することができます。この式の持つ意味は大きく、複数種の素因数の積が単一の素因数の積で考察できるようになります。ここにきてようやく取っ掛かりが見えてきました。この表式に辿り着くまでが第1関門です。
(2)の結果が使えそうな表式が得られたので、このタイミングで(2)で得られた結果について深掘ってみましょう。(2)で得られた結果は、
$$f(p^k)\le f(p^{k+1}) \Rightarrow p=2 \space かつ \space k=1$$
というものでした。コレの対偶をとると、
$$p \ge 3 \space または \space k\ge 2 \Rightarrow f(p^k)\ge f(p^{k+1}) $$
と同値変形できます。この式を上手に解釈できるか否かが第2の関門になります。式中には変数が(p,k)の2種類登場しており、この手の関数の挙動をみるときは、「1文字だけ動かして、それ以外固定する」が鉄則なので、まずはpを固定して考えます。
p=2のとき、
$$f(2^1)\le f(2^2),\space f(2^2)\ge f(2^3)\ge f(2^4)\ge …$$
となることから、\(f(2^k)\) の最大値は\(f(4)\) であることがわかります。
次にp>2 の場合を考えます。この場合は、
$$f(p^1)\ge f(p^2)\ge …$$
となるため、p>2を固定した場合の \(f(p^k)\) の最大値は \(f(p^1)\) となります。
最後に、p>2を固定してkを動かしてみます。すると、
$$f(p^k)=\frac{k+1}{\sqrt{p^k}}\le \frac{k+1}{\sqrt{3^k}}=f(3^k)$$
となることから、kを固定してp>2を動かした場合の \(f(p^k)\) の最大値は \(f(3^k)\) となります。
以上をまとめると、(2)の結果から下記3つの知見が得られます。(p>2)
$$f(2^k)\le f(2^2)$$
$$\space f(p^k)\le f(p)$$
$$\space f(p^k)\le f(3^k)$$
ここまでの情報を整理するのが第2関門です。もう既に疲労困憊です。
これまで集めた情報をヒントに数列 \(f(n)\) を最大化することを考えてみます。
まず、\(n\) がもつ素因数に対応して下記の場合分けして考えていきます。
(I) n=1 の場合
(II) n>1 かつ n が素因数2を持たない場合
(III) n>1 かつ nが素因数を2のみ持つ場合
(IV) n>1 かつ nが2を含む相違な素因数を2個以上もつ場合
以上4通パターンでf(n)の最大値を個別に求めていきます。コレが最終関門です。ここにきて4通りの場合分けとか正気の沙汰とは思えませんが、心を無にして頑張っていきましょう。
まず(I)ですが、この場合は \(f(n)=f(1)=1\) です。
次に(II)ですが、このとき \(n\) は 3以上の素数 {\(p_k\)}により\(n=p_1^{q_1}p_2^{q_2}…p_k^{q_k}\) と表され、
$$f(n)=f(p_1^{q_1})f(p_2^{q_2})…f(p_k^{q_k})$$
$$\le f(3^{q_1})f(3^{q_2})…f(3^{q_k})=f(3^{q_1+q_2+…+q_k})$$
$$\le f(3^1) =\frac{2}{\sqrt{3}}$$
となるため、(II)の場合の最大値はf(3)ということになります。
次に(III)の場合について、この場合は \(n=2^q\) の形式で表せ、
$$f(n)=f(2^q) \le f(2^2)=\frac{2+1}{\sqrt{2^2}}=\frac{3}{2}$$
ゆえ、(III)の場合の最大値はf(4)となります。
最後に(IV)の場合を考えます。この場合、(\(p_2,p_3,…,p_k\)) を3以上の相違なk-1個の素数として\(n=2^{q_1}p_2^{q_2}…p_k^{q_k}\) と表せばよく、このとき
$$f(n)=f(2^{q_1})f(p_2^{q_2})…f(p_k^{q_k})$$
$$\le f(2^2)f(3^{q_2})…f(3^{q_k})=f(2^2)f(3^{q_2+q_3+…+q_k})$$
$$\le f(2^2)f(3^1)=f(12)=\frac{3}{\sqrt{3}}$$
ゆえ、(IV)の場合の最大値はf(12)=f(4)f(3)です。
ここまで来れば99割方勝ち確です。得られた4つの値 f(1),f(3),f(4),f(3)f(4) のうち最大のものが求める最大値になりますが、f(3)>1,f(4)>1、f(1)=1であることから、この中で最大なのはf(3)f(4)=f(12)で確定です。
以上より、f(n)はn=12で最大値f(12)=√3をとることがわかります。
お疲れ様でした。
答案例
(\(p_1,p_2,…,p_k\)) を \(p_1<p_2<…<p_k\) を満たす \(k\) 個の素数、(\(q_1,q_2,…,q_k\))を1以上の整数として、 \(n=p_1^{q_1}p_2^{q_2}…p_k^{q_k}\) と素因数分解できる場合を考える。このとき、 \(n\) の約数の個数は、
$$d(n)=d(p_1^{q_1}p_2^{q_2}…p_k^{q_k})=(q_1+1)(q_2+1)…(q_k+1) \tag{1}$$
と表せる。
(1)
(1)式より、
$$f(2025)=\frac{d(3^4\times 5^2)}{\sqrt{3^4\times 5^2}}=\frac{(4+1)(2+1)}{45}=\frac{1}{3}$$
(2)
$$f(p^k)\le f(p^{k+1}) \tag{2}$$
(1)式を用いて(2)式を変形すると、
$$f(p^k)\le f(p^{k+1})$$
$$\Leftrightarrow \frac{k+1}{\sqrt{p^k}}\le \frac{k+2}{\sqrt{p^{k+1}}}$$
$$\Leftrightarrow \sqrt{p} \le \frac{k+2}{k+1}=1+\frac{1}{k+1} \tag{3}$$
\(k\) は1以上の整数なので、
$$1+\frac{1}{k+1}\le 1+\frac{1}{1+1}=1.5$$
が満たされる。従って(3)式より、
$$(3) \Rightarrow p \le 1.5^2=2.25 \Rightarrow p=2$$
が必要である。\(p=2\) のとき、
$$(2) \Leftrightarrow \sqrt{2}\le \frac{k+2}{k+1} \Leftrightarrow (\sqrt{2}-1)k\le 2-\sqrt{2}\Leftrightarrow k\le \sqrt{2} \Leftrightarrow k=1$$
と同値変形できる。以上より、求める組は、
$$(p,k)=(2,1)$$
である。
(3)
(I) \(n=1\) のとき、\(f(n)=f(1)=1\) である。
(II) \(n>1\) のとき、\(n=p_1^{q_1}p_2^{q_2}…p_k^{q_k}\) の形式で表現できる。
(II-I) \(p_1=2,k=1\) のとき、(2)の結果から、
$$f(n)=f(2^{q_1})\le f(2^2)=\frac{2+1}{\sqrt{2^2}}=\frac{3}{2}$$
(II-II) \(p_1=2,k\ge 2\) のとき、
$$f(n)=f(2^{q_1}p_2^{q_2}…p_k^{q_k})$$
$$=\frac{(2+1)(q_2+1)…(q_k+1)}{\sqrt{2^{q_1}p_2^{q_2}…p_k^{q_k}}}$$
$$=\frac{2+1}{\sqrt{2^{q_1}}}\frac{q_2+1}{\sqrt{p_2^{q_2}}}…\frac{q_k+1}{\sqrt{p_k^{q_k}}}$$
$$=f(2^{q_1})f(p_2^{q_2})…f(p_k^{q_k})$$
と変形でき、(2)式より
$$f(2^{q_1})\le f(2^2),\space f(p_l^{q_l})\le f(3^{q_l}) \space (2\le l\le k)$$
であることから、
$$f(n)\le f(2^2)f(3^{q_2})f(3^{q_3})…f(3^{q_k})=f(2^2)f(3^{q_2+q_3+…+q_k})$$
$$\le f(2^2)f(3^1)=f(12)=\frac{(2+1)(1+1)}{\sqrt{12}}=\frac{3}{\sqrt{3}}$$
(II-III) \(p_1>2\) のとき、
$$f(n)=f(p_1^{q_1}p_2^{q_2}…p_k^{q_k})=f(p_1^{q_1})f(p_2^{q_2})…f(p_k^{q_k})$$
$$\le f(3^{q_1})f(3^{q_2})…f(3^{q_k})=f(3^{q_1+q_2+…+q_k})$$
$$\le f(3^1)=\frac{1+1}{\sqrt{3}}=\frac{2}{\sqrt{3}}$$
以上より、\(f(n)\) は \(n=12\) で最大値 \(f(12)=\sqrt{3}\) をとる。
コメント