(解いてみた その2) IMO2019 Problem 4
解いてみた No.2 は先日あったというIMOのProblem 4.からです。(選手のみなさんお疲れ様でした)
本当はテストが間近にあるのでこんなの解いてる暇は無いんですけどね・・・つい気になってしまった。
問題.2
以下をみたす正の整数の組$ (k,n) $をすべて求めよ:
$ k! = (2^{n} -1)(2^{n} -2)(2^{n} -4) \cdots (2^{n} - 2^{n-1}) $
解答
以下の議論において, $ m\in \mathbb{N} $が素数$ p $で割り切れる最大の回数を$v_p (m)$ で表すこととする。
次の補題を示す。
補題.1
$P_{j} := \displaystyle\prod_{i=1}^{3^{j} }(2^{i} - 1) $ ($ j=1,2,\cdots $)とおく。このとき, 任意の$ j $に対して $v_3(P_j) \leq \dfrac{3^{j+1}}{4} - \dfrac{5}{4} $
(証明)
$ (2^{i} -1) $が$3$で割れるのは$ i $が偶数であるときだから,
$\displaystyle\prod_{i=1}^{\frac{3^{j}-1}{2}}(4^{i} -1) = (2^{2} -1)(2^{4} -1)\cdots (2^{3^{j}-1} -1)$ の$3$で割れる回数を見れば良い。各$ i=1,2,\cdots ,\frac{3^{j}-1}{2}$に対して, $4^{i} -1$ が$ 3 $で割れる回数は, LTE Lemma より
$ v_3(4^{i} -1 ) = v_3(4-1) + v_3(i) = 1+v_3(i) $
なので, これの総和の$\displaystyle\sum_{i=1}^{\frac{3^{j} -1}{2}} (1+v_3(i)) = \dfrac{3^{j}-1}{2} + v_3\left( \left( \dfrac{3^{j}-1}{2} \right) ! \right)$ が$v_3( P_j )$に等しい。$v_3 \left( \left( \dfrac{3^{j}-1}{2} \right) ! \right)$ は, Legendreの定理より次のように評価される。
$ v_3 \left( \left( \dfrac{3^{j}-1}{2} \right) ! \right) = \displaystyle\sum_{i=1}^{\infty} \left\lfloor \dfrac{\frac{3^{j} -1}{2}}{3^{i}} \right\rfloor \leq \displaystyle\sum_{i=1}^{j-1} \dfrac{\frac{3^{j} }{2}}{3^{i}} = \displaystyle\sum_{i=1}^{j-1} \dfrac{3^{j-i}}{2} = \dfrac{1}{2} \cdot \dfrac{3}{2}(3^{j-1} -1) = \dfrac{3^{j}}{4} -\dfrac{3}{4} $
以上より $ v_3(P_j) \leq \dfrac{3^{j} -1}{2} + \dfrac{3^{j}}{4} - \dfrac{3}{4} = \dfrac{3^{j+1}}{4} - \dfrac{5}{4} $ となる。
(証明終)
右辺の $( 2^{n} -1 )(2^{n} -2)(2^{n} - 4)\cdots (2^{n} - 2^{n-1})$は,
$2^{\frac{n(n-1)}{2}}\displaystyle\prod_{i=1}^{n}(2^{i} -1)$と書ける。これを$f_n$とおく。まず, $ k! $が$2$で$\dfrac{n(n-1)}{2}$ 回割れなければならないので、Legendreの定理より $\displaystyle\sum_{i=1}^{\infty} \left\lfloor \dfrac{k}{2^{i}} \right\rfloor = \dfrac{n(n-1)}{2}$
$ 3^{j-1} \leq n < 3^{j} $となるような $ j $ が, $ n $ に対して一意に取れることに注意する。明らかに $ \dfrac{f_n}{2^{\frac{n(n-1)}{2}}} $は$ P_j $の約数であるから,$ v_3(f_n) = v_3\left( \dfrac{f_n}{2^{\frac{n(n-1)}{2}}}\right) \leq v_3(P_{j+1})$
を満たす。補題1より, $v_3(f_n) \leq v_3(P_{j}) \leq \dfrac{3^{j+1}}{4} - \dfrac{5}{4} $
を得る。 $ v_3(k!) = v_3(f_n) $ であるから, $v_3(k!)$ も同じ不等式を満たさねばならず, $v_{3}(k!) = \displaystyle\sum_{i\geq 1}\left\lfloor \dfrac{k}{3^{i}} \right\rfloor$ である。
したがって,
$\displaystyle\sum_{i\geq 1}\left\lfloor \dfrac{k}{3^{i}} \right\rfloor \leq \dfrac{3^{j+1}}{4} - \dfrac{5}{4} $ と $\displaystyle\sum_{i\geq 1}\left\lfloor \dfrac{k}{2^{i}} \right\rfloor = \dfrac{n(n-1)}{2} < \dfrac{3^{j}(3^{j} -1)}{2}$
を同時に満たす$ j $に限定される。
$ j\geq 2$であるとする。
2式目より, ガウス記号を$\lfloor x\rfloor \leq x$で評価すると $ \dfrac{n(n-1)}{2} < \displaystyle\sum_{i\geq 1}\dfrac{k}{2^{i}} = k$となる。
よって, $ k> \dfrac{n(n-1)}{2} \geq \dfrac{3^{j-1}(3^{j-1}-1 )}{2} \geq 3^{2j-3} >1 $ であるから,
$ \displaystyle\sum_{i\geq 1} \left\lfloor \dfrac{3^{2j-3}}{3^{i}} \right\rfloor = \dfrac{3^{2j-3}-1}{2} < \displaystyle\sum_{i\geq 1} \left\lfloor \dfrac{k}{3^{i}} \right\rfloor \leq \dfrac{3^{j+1}}{4} - \dfrac{5}{4}$ となる。*1
$ 3^{j-2} = J $とすると, $ \dfrac{3^{2j-3} -1}{2} = \dfrac{3J^{2} -1}{2} < \dfrac{9}{4}J - \dfrac{5}{4} = \dfrac{3^{j+1}}{4} - \dfrac{5}{4} $ である。真ん中を整理すると
$ 3(2J^2 -3J +1) <0 $となる。左辺は$ 3(J-1)(2J-1) $であって, $j\geq 2$としたから $ J\geq 1 $である。よって, この不等式は成立し得ないので$ j\geq 2 $は不適。$ j=1 $とすることで, $1\leq n< 3$となるので $ n=1,2 $が必要。
元の式の右辺に代入して
$(2^{1} - 2^{0}) = 1$, $(2^{2} -2^{1})(2^{2} -2^{0}) = 6$ より,
$ (k,n) = (1,1), (3, 2) $ のみ。
コメント
（急いで書いてきたのでちょっとミスあるかもね）
階乗の入る不定方程式は個人的に難しいイメージがあります・・・。まあ, Legendreの定理とか使うものは結構限られると思いますが。$ a^{n} - b^{n}$の形を見たらやはりLTEなのですね。IMOの問題は次のリンクから見れます。
