2009年 日本数学オリンピック本選 第３問 解答例
$${k}$$を$${2}$$以上の整数、$${n_1, n_2, n_3}$$を正の整数、$${a_1, a_2, a_3}$$を$${1}$$以上$${k-1}$$以下の整数とする。
$${b_i = a_i \displaystyle\sum^{n_i}_{j=0}k^j (i = 1, 2, 3) }$$
とおく。$${b_1b_2=b_3}$$であるとき、$${(n_1, n_2, n_3)}$$の組としてありうるものをすべて求めよ。
考え方：
問題文が少しややこしいですが、
要は$${k}$$進法ですべての位が同じになる２つの数をかけて、
やはりすべての位が同じになる条件を調べます。
掛け算を筆算の形で書いてみると、
例えば$${b_1, b_2}$$どちらの桁数も十分大きいとき
$$
\begin{array}{cccc}
&\cdots &a_2&a_2\\
\times & \cdots &a_1&a_1\\ \hline
\cdots & A & B & a_3 \\
\cdots & B & a_3 & \\
\cdots & a_3 & & \\
\vdots& && \\ \hline
\cdots &a_3 & a_3 & a_3
\end{array}
$$
と書けます。これを覆面算のように埋めていってみましょう。
この時、$${a_1a_2}$$は大きくても$${k}$$進法で２桁であることに注意しておきます。
$${B=0}$$がわかるので、$${a_1a_2}$$の１桁目と２桁目の和は$${k}$$になります。
次に$${A=0}$$になる必要がありますが、
くりあがりを考えると$${A = B+1}$$となるため、
これはあり得ません。
よって、どちらかは２桁以下であることがわかります。筆算は
$$
\begin{array}{cccc}
&\cdots &a_2&a_2\\
\times & &a_1&a_1\\ \hline
\cdots & A & 0 & a_3 \\
\cdots & 0 & a_3 & \\ \hline
\cdots &a_3 & a_3 & a_3
\end{array}
$$
のようになります。
さらに$${A=a_3}$$となる条件を調べていくと解が絞れていけます。
このような筆算を用いた形式で解答を記述するのも可能だと思いますが、
多項式の形に書き直して以下の解答例としました。
解答例：
$${n_1 \leqq n_2}$$としても一般性を失わない。
(i) $${n_1 = 1, n_2=1}$$のとき、
$${b_1b_2 = a_1a_2(k+1)^2 < k^4}$$
であるから、$${n_3 = 2, 3}$$である。
$${n_3 = 2}$$とすると$${a_1a_2 < k}$$が必要であり、
条件から$${a_1a_2 = a_3}$$を得るが、これは条件を満たさない。
$${n_3 = 3}$$のとき、例えば$${a_1=a_2 =5, a_3=4, k= 7}$$が条件を満たすので、
$${(n_1, n_2, n_3) = (1, 1, 3)}$$は解である。
(ii) $${n_2 \geqq 2}$$のとき、
条件より$${a_1a_2 \equiv a_3 (\text{mod } k)}$$なので
$${0}$$以上の整数$${c}$$を用いて$${a_1a_2 = ck + a_3}$$とおける。
$${a_1 \leqq k-1, a_2 \leqq k-1}$$より$${c \leqq k-1}$$となる。
すると、
$$
\begin{align*}
b_1b_2 & = a_1a_2(1 + k + \cdots + k^{n_1})(1 + k + \cdots + k^{n_2}) \\
& \equiv a_1a_2 + 2a_1a_2k (\text{mod } k^2 )\\
& \equiv a_3 + (2a_3 + c)k (\text{mod } k^2 )
\end{align*}
$$
となる。
これが$${b_3 = a_3 + a_3k + a_3k^2 \cdots}$$と一致するので、
$${a_3 + c = k}$$ を得る。
(ii-i) さらに$${n_1 = 1}$$のとき、
$$
\begin{align*}
b_1b_2 & = (a_3+ck)(1 + k)(1 + k + \cdots + k^{n_2})\\
& \equiv a_3 + (2a_3 + c)k + (2a_3 + 2c)k^2 (\text{mod } k^3)\\
& \equiv a_3 + a_3k + k^2 (\text{mod } k^3)\\
\end{align*}
$$
となる。一方、
$$
b_1b_2 = b_3 \equiv a_3 + a_3k + a_3k^2 (\text{mod } k^3)
$$
であるから、$${k^2}$$の係数を比較すると$${a_3 = 1}$$となり、
$${a_3 + c = k}$$より$${c = k - 1}$$を得るが、
$${a_1a_2 = ck + a_3 = k^2 - k + 1 > (k-1)^2}$$となり矛盾。
(ii-ii)$${n_1 \geqq 2}$$のとき、
$$
\begin{align*}
b_1b_2 & = (a_3+ck)(1 + k + \cdots + k^{n_1})(1 + k + \cdots + k^{n_2})\\
& \equiv a_3 + (2a_3 + c)k + (3a_3 + 2c)k^2 (\text{mod } k^3)\\
& \equiv a_3 + a_3k + (a_3 + 1)k^2 (\text{mod } k^3)\\
\end{align*}
$$
となり、$${a_3 = a_3+1}$$が必要となり矛盾。
以上より$${n_2 \geqq 2}$$なる解はない。
よって答え$${(n_1, n_2, n_3) = (1, 1, 3)}$$
コメント：
途中で$${a_1=a_2 =5, a_3=4, k= 7}$$という解を示しています。
これは例えば以下のように求められます：
$${a_1a_2(k+1)^2 = a_3(k^3 + k^2 + k +1)}$$より
$${a_1a_2(k+1) = a_3(k^2 +1) (1)}$$を得て、
$${a_1a_2 = ck + a_3}$$を代入して
$${ck^2 + (c+a_3)k + a_3 = (c+1)k^2 +a_3 = a_3(k^2 +1)}$$
となるので、$${c+1 = a_3}$$より$${k = 2a_3 -1}$$を得ます。
これを(1)に代入すると$${a_1a_2 = 2a_3^2 - 2a_3 + 1}$$となります。
右辺に正の整数を代入していって、
それが$${k}$$より小さい２数の積で表されるようなものを探したとき、
$${a_3=4}$$の時に$${a_1a_2 = 2a_3^2 - 2a_3 + 1 = 25}$$となって見つかります。
お知らせ：
少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
間違いなど見つけましたら是非お教えください。
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)