ノリの悪い日記

古今東西の映画、ポピュラー音楽、その他をいまここに交錯させながら随想します。

陥没地帯 (24)

高校数学 整数問題 花

ペンステモン。

f:id:noriharu-katakura:20201103225718j:plain

ヤブカンゾウかなあ。

f:id:noriharu-katakura:20201103230355j:plain

【問】
\text{(1)} k を自然数とする。 m を m = 2^k とおくとき、 0 \lt n \lt m をみたす整数 n について、二項係数 _m \mathrm{C}_{n} は偶数であることを示せ。

\text{(2) } 以下の条件をみたす自然数 m をすべて求めよ。

条件: 0 \leq n \leq m をみたすすべての整数 n について二項係数 _m \mathrm{C}_n は奇数である。

【解】
はじめに:
記述を簡単にするために、次の関数 \phi を以下のように定義して使用する。

定義:
自然数 n を素因数分解したとき、素数 2 の指数を \phi(n) で表す。
例:
\phi(40) = \phi(2^3 \times 5) = 3
\phi(5) = 0

\text{(1)}
\displaystyle{\begin{align} _{2^k} \mathrm{C}_{n} &= \frac{2^k(2^k-1)\cdots (2^k-n+1)}{n!} \\&= \frac{2^k}{n} \cdot\frac{(2^k-1)\cdots (2^k-n+1)}{(n-1)!}\end{align}}

これから、

\displaystyle{n\cdot_{2^k} \mathrm{C}_{n} = 2^k \cdot _{2^k-1} \mathrm{C}_{n-1}}

となるが、

n = 2^{\phi(n)}p ( pは正の奇数)

とおくと、

2^{\phi(n)} \leq 2^{\phi(n)}p \lt 2^k

から

\phi(n) \lt k

となるので、 _{2^k} \mathrm{C}_{n} は偶数である。

\text{(2)}
n = 0, m の場合には、

_m \mathrm{C} _0 = _m \mathrm{C} _m = 1

で _m \mathrm{C} _n は任意の自然数 m で奇数になる。そこで、任意の 0 \lt n \lt m で 「 _m \mathrm{C} _n が奇数になる」ことを考える。

そうすると、

\displaystyle{_{m} \mathrm{C}_{n} = \frac{m(m-1)\cdots (m-n+1)}{n!}}

と表したとき、 _m \mathrm{C} _n が奇数になることと、上式の分母、分子の素因数 2 が約分されてすべて消えることは同値であることがわかる。

このことから、任意の 0 \lt n \lt m で「

\displaystyle{\sum_{k=1}^{n} \phi(m-k+1) = \sum_{k=1}^{n} \phi(k) }

である」ことは _m \mathrm{C} _n が奇数であることと同値である。

さらに上の条件と、任意の 0 \lt n \lt m で、「

\phi(m - n + 1) = \phi(n)

が成立する」(★) ことは同値である。

(以下その証明)
★ が必要条件であること:
n = 1 のとき \phi(m) = \phi(1) =0 だから成立する。
n=1, 2, \cdots, k のとき \phi(m-n+1) = \phi(n) が成立すると仮定すれば、 n = k+1 のとき

\phi(m-k) = \phi(k)

となって成立する。

★ が十分条件であること:
明らか。
(証明終わり)

そこで、 m の条件を求めるために、まず ★ の条件が成立するとする。

任意の 0 \lt n \lt m を

n = 2^{\phi(n)}p
( p は正の奇数)

と表せば、★の条件から、

m-n+1 = 2^{\phi(n)}q
( q は正の奇数)

と書けるので、

m+1 = 2^{\phi(n)}(p+q)

となり、これを

m +1 = 2^{\phi(m+1)}r
( r は正の奇数)

と比較すれば、 p + q は奇数同士の和で偶数なので、任意の 0 \lt n \lt m で、

\phi(m+1) > \phi(n)

となる。ここで、上の正の奇数 r が r \gt 1 だと仮定すると、

n = 2^{\phi(m+1)}

を満たす n がとれて、任意の 0 \lt n \lt m で、

\phi(m+1) > \phi(n)

であることと矛盾するので、 r = 1 である。

以上から、★ の条件が成り立つとき、 k を任意の自然数として、 m は、

m = 2^k - 1

で表されることが必要である。


逆に m = 2^k - 1 ( k は任意の自然数) であるとき、★ の条件が成立することを示す。

\phi(m - n + 1) = \phi(2^k - n)

であるが、任意の 0 \lt n \lt m を

n = 2^{\phi(n)}p
( p は正の奇数)

と表すと、 \text{(1)} で調べたように、 \phi(n) \lt k である。したがって、

\phi(2^k - n) \\ = \phi(2^{\phi(n)}(2 ^{k-\phi(n)}-p))

とできるが、 p は奇数であることから、

\phi(m - n + 1) \\ = \phi(2^k - n) \\ = \phi(2^{\phi(n)}(2 ^{k-\phi(n)}-p)) \\ = \phi(2^{\phi(n)}) \\ = \phi(n)

となって、★ が成立するに十分である。


以上から、問題の条件と

k を任意の自然数として、

m = 2^k - 1

と表せることは同値である。
//