整数の問題(自作問題1-(11))

この記事の所要時間: 212

問題.

自作問題集の1-(11), 整数の問題です.

問題. 

\(M\)を非負整数, \(n\)を自然数とする. \(\displaystyle\frac{(2^{M+1}n)!}{n!}\)は2で何回割り切れるか.

2で割り切れる回数を直接数え上げることはできないので, いくつかの整数の積として表し数えていきます.

解答例.

\(N\)を自然数として, \(\displaystyle \frac{(2N)!}{N!}\)が2で何回割り切れるかを調べると,
\begin{align*}
\frac{(2N)!}{N!} &= \frac{(2N)\cdot(2N-1)\cdots2\cdot 1}{N\cdot(N-1)\cdots 2\cdot 1}\\
&= (2N-1)(2N-3)\cdots1\cdot\frac{2N}{N}\cdot\frac{2N-2}{N-1}\cdots\frac{4}{2}\cdot\frac{2}{1}\\
&= (2N-1)(2N-3)\cdots1\cdot2^N
\end{align*}
\((2N-1)(2N-3)\cdots1\)は奇数なので, \(\displaystyle \frac{(2N)!}{N!}\)は2で\(N\)回割り切れる.
今, 与えられた式は
\begin{align}
\frac{(2^{M+1}n)!}{n!} = \frac{(2^{M+1}n)!}{(2^Mn)!}\cdot\frac{(2^Mn)!}{(2^{M-1}n)!}\cdots \frac{(2n)!}{n!}
\end{align}
と変形でき, 右辺の各項\(\displaystyle \frac{(2^{k+1}n)!}{(2^kn)!}\)は2で\(2^kn\)回割り切れる整数なので, (1)の右辺は2で
\begin{align*}
2^Mn+2^{M-1}n+\cdots+2n+n = (2^{M+1}-1)n
\end{align*}
回割り切れる.
従って, \(\displaystyle \frac{(2^{M+1}n)!}{n!}\)は2で\((2^{M+1}-1)n\)回割り切れる.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加