ノリの悪い日記

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

陥没地帯 (24)

ペンステモン。

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

ヤブカンゾウかなあ。

f:id:noriharu-katakura:20200628194500j: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

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