◆愛知県 Y.M.Ojisan さんからの解答
【問題１】
予想は正しい。
∵ ｍ＝２t−１ t≧３において
2mＣm-1≡３ mod ８である。――――（１）
一方 2mＣm-1 ≧８ であるから
2mＣm-1＝２k−１≡７ mod ８ であり３にはならない。
（１）の証明
ｍ＝２t−１においてのみ2mＣm-1は奇数である。
従って、2mＣm-1 mod ２3 を考えるときは
１〜２ｍの数の 素因数中の奇数項のmod ２3のみ考慮すればよい。
さて、１〜２p 中の２0×奇数のものに関してのmod ８は
１、３、５、７、１、３、５、７。。。。。１、３、５、７
と４個ずつの繰り返しである。
ところで １×３×５×７≡１ mod ８であるから
それらの積も≡１ mod ８である。
これは１〜２p 中の ２pｰ3×奇数 のものまで同じである。
２p-2×奇数のものに関して奇数部のmod ８は １、３の２項である。
２p-1×奇数のものに関して奇数部のmod ８は １のみである。
２p×１のものに関しての奇数部のmod ８は １のみである。
従って ｐ≧２において
｛（２p）！の奇数因数部｝≡３ mod ８ である。 ―――(２)
| 2mＣm-1＝ | (２t+1−２)！ (２t−２)！２t！ |
＝ | ２t+1！ ２t！２t！ |
× | ２t(２t−１) ２t+1(２t+1−１) |
と恒等変形できる。
２の倍数を消去して mod 8を考えると ｔ≧３のとき （２）を適用すると、
| 2mＣm-1≡ | 3 3×3 |
× | 1×7 1×7 |
≡３ mod ８ |
である。因みにｔ＝２のとき
| 2mＣm-1≡ | 3 3×3 |
× | 1×3 1×7 |
≡７ mod ８ |
である。
【感想】
「データ圧縮符号の構造に関する研究」として、実用と結びつくということでとても興味深く思いました。
◆茨城県 こんにちは さんからの解答
私はm≠2t-1のとき2mCm-1は偶数となることを示します。
当然、2mCm-1は奇数である2k-1にはなりえません。
【解答】
【補題１】
| n!の素因数分解したときのpの指数は | i=1 |
[ | n pi |
]となる。 |
【証明】
n!の指数は
i=1 |
{i*(piで割り切れてpi+1で割り切れない1以上n以下の自然数の個数)} |
| = | i=1 |
{i*([ | n pi |
]-[ | n pi+1 |
])} |
| = | i=1 |
{(i-(i-1))*[ | n pi |
]} |
| = | i=1 |
[ | n pi |
] |
証明終
【補題２】
α、βを実数とすると[α+β]-([α]+[β])=0,1となる。
【証明】
αとβは、0≦γ,δ＜1なる実数γとδを用いて、
α=[α]+γ、β=[β]+δと書ける。
α+β=[α]+[β]+γ+δ、0≦γ+δ＜2より
0≦γ+δ＜1のとき[α+β]=[α]+[β]、
1≦γ+δ＜2のとき[α+β]=[α]+[β]+1
よって[α+β]-([α]+[β])=0あるいは1となる。
証明終
【補題３】
自然数Nをs進法で表す(もちろんsは2以上の自然数)。
| N= | i=0 |
(ai*si)となります。 |
| このとき、ahはah= | [ | N sh |
]-s[ | N sh+1 |
] |
【証明】
| N sh | ={ | h-1 i=0 |
(ai*si)}/sh+{ | i=h |
(ai*si)}/sh |
| 0≦ | h-1 i=0 |
(ai*si)≦ | h-1 i=0 |
{(s-1)*si}=(s-1)* | sh-1 s-1 |
=sh-1＜shより |
| [ | N sh | ]= | h i=h |
(ai*si-h) | =ah+ | i=h+1 |
(ai*si-h) |
| 同様に[ | N sh+1 | ]= | i=h+1 |
(ai*si-h-1) |
| s*[ | N sh+1 | ]= | i=h+1 |
(ai*si-h) |
| よってa | h | =[ | N sh |
]-s[ | N sh+1 |
]となる。 |
証明終
【補題４】
nとrを0≦r≦nなる自然数とする。
nとrをp進法で表す。
| n= | i=0 |
(bi*pi)、r= | i=0 |
(ci*si)、n-r= | i=0 |
(di*si)、 |
ある0以上の整数hに対してbh＜ch+dh となるとき、
nCrはpで割り切れる。
【証明】
補題３より
| b | h | =[ | n ph |
]-p[ | n ph+1 |
]、c | h | =[ | r ph |
]-p[ | r ph+1 |
]、d | h | =[ | n-r ph |
]-p[ | n-r ph+1 |
] |
問題の条件bh＜ch+dhに代入すると
| [ | n ph | ]-p[ | n ph+1 |
]＜([ | r ph |
]-p[ | r ph+1 |
])+([ | n-r ph |
]-p[ | n-r ph+1 |
]) |
| [ | n ph | ]-[ | r ph |
]-[ | n-r ph |
]＜p([ | n ph+1 |
]-[ | r ph+1 |
]-[ | n-r ph+1 |
]) |
ここで補題２より
| [ | n ph+1 |
]-[ | r ph+1 |
]-[ | n-r ph+1 |
]=0あるいは1である。 |
| [ | n ph+1 |
]-[ | r ph+1 |
]-[ | n-r ph+1 |
]=0と仮定すると |
| [ | n ph |
]-[ | r ph |
]-[ | n-r ph |
]＜0となる。 |
これは補題２の
| [ | n ph |
]-[ | r ph |
]-[ | n-r ph |
]=0あるいは1に反する。 |
| よって[ | n ph+1 |
]-[ | r ph+1 |
]-[ | n-r ph+1 |
]=1である。 |
| nCr= | n! r!(n-r)! |
を素因数分解したときのpの指数は補題1より |
i=1 |
([ | n pi |
]-[ | r pi |
]-[ | n-r pi |
]) |
| 補題２より[ | n pi |
]-[ | r pi |
]-[ | n-r pi |
]=0あるいは1だから |
i=1 |
([ | n pi |
]-[ | r pi |
]-[ | n-r pi |
])≧[ | n ph+1 |
]-[ | r ph+1 |
]-[ | n-r ph+1 |
]=1 |
よってnCrはpで割り切れることがわかる。
証明終
さて、冒頭のm≠2t-1のとき、2mCm-1は偶数となることを示す
mが偶数のとき、m-1とm+1は奇数である。
2mを2進数で書くと20の桁は0、m-1、m+1の20の桁は1
よって補題４より2mCm-1は偶数である。
mが奇数のとき、mの一番下の桁は1である。
よって、m-1の20の桁以外の桁とmの20の桁以外の桁は一致する。
ここでm≠2t-1であることを思い出そう。
よって、mを2進数で表す。
| m= | i=0 |
(ei*2i) |
すると、eh-1=0、eh=1となる自然数hが存在する。
| 2m= | i=0 |
(ei*2i+1)= | i=1 |
(ei-1*2i) |
| m-1= | i=1 |
(ei*2i) |
m+1を2進数で表すと
| m+1= | i=1 |
(fi*2i) |
2m,m+1,m-1の2hの桁はそれぞれ、0,fh,1
よって、fhの値が0であろうが1であろうが、
0=eh-1＜1+fh=eh+fhが成立する。
よって、補題４より2mCm-1は偶数であることが示された。
解答終
【コメント】
Y.M.Ojisan さんからの解答とあわせて、
2mCm-1=2k-1となるのは
m=1あるいはm=3の場合に限られることが示されます。
よって、ひさおさんの予想は正しいことが示されました。
◆東京都 ぽこぺん さんからの解答
Y.M.Ojisan さんの mod 8 で考えた見事な証明を見ているうちに，（１）の別証を思いつきました。
Pascal の三角形を mod 8 で考えると，2N の段（下図の青色）はきれいな形をしています。
N≧2 のときには，1, 4, 6, 4, 1 の間に 2N-2 - 1 個の 0 が入った形になるのです。
この証明は簡単ですが，たとえば母関数を使ったものは下記の【注】のようになります。
問題の m = 2t-1 の段（ピンク色）の中央付近は，m = 2t の段の中央付近の値から計算できます：
m = 2t の中央の 6 に対して，6 を挟む直上の行中央の 2 つの項は等しいから，共に 3 か，共に 7 となるしかありません。
しかし，7 の場合は上図のように右端が 1 にならないので適しません。
そこで中央の 2 項は 3 と決まり，その上の行では a+b≡3 (mod 8) となります。
ここで t≧3 のときには a≡0 となることが次のように証明できるので，b≡3 となるわけです。
実際，m = 2n-1 (奇数) のとき，2mCm は
| (4n-2)(4n-3)…(2n) (2n-1)(2n-2)…1 |
= | (奇数)×2n (n-1)! |
ここで，分母の (n-1)! に含まれる 2 の最大指数は
| [ | n-1 2 |
] + [ | n-1 4 |
] + [ | n-1 8 |
] + [ | n-1 16 |
] + … |
(2t-2-1) +(2t-3-1)+ … +(21-1)
= 2t-1 - t
= n - t
となります。
したがって，m = 2t-1 のとき，2mCm に含まれる 2 の最大指数は
n - (n - t) = t となり，
t≧3 のとき 2mCm ≡ 0 (mod 8) となることがわかります。
【注】
2 つの同じ次数の整数係数多項式
f(x) = Σak xk，g(x) = Σbk xk の係数の間に
ak ≡ bk (mod n) の関係があるとき，
f(x) ≡ g(x) (mod n) と定義する。
このとき，mod 8 で
(1+x)4 = 1 + 4x + 6x2 + 4x3 + x4
(1+x)8
＝ (1 + 4x + 6x2 + 4x3 + x4)2
≡ 1 + 4x2 + 6x4 + 4x6 + x8
＝ (1+x2)4
であることに注意すると，
(1+x)16
≡ {(1+x2)4}2
＝ (1+x2)8
≡ (1+x4)4
(1+x)32
≡ {(1+x4)4}2
＝ (1+x4)8
≡ (1+x8)4
…
などとなる。
【感想】
青色の行のような美しい性質は有名でなかったように思います。
初めて気づきました。
◆東京都 ぽこぺん さんからの解答
Pascal の三角形による証明がうまくいったのに気を良くして，
2mCm-1 が奇数 ⇔ m = 2t-1 (t = 1, 2, …)
についても考えてみました。
再び mod 8 で Pascal の三角形を作ると，
2N の段は 1，4，6，4，1 が間に 2N-2-1 個の0 を挟んで並んでいます。
(上記の注参照)
このとき，Pascal の三角形の性質から，明らかに
0≦n＜2N のとき，
C(2N + n, r) ≡ 偶数 (n＜r＜2N)
C(2N + n, r) ≡ 奇数 (r = n, 2N)
であることがわかります。
(式で書くよりも，下図の例 (N=4) を見れば一目瞭然ですね)
さらに，n の範囲を 4 つに分けて，
0 ≦n＜1・2N-2 のとき，
C(2N + n, r) ≡ 1 (r = n, 2N)
1・2N-2≦n＜2・2N-2 のとき，
C(2N + n, r) ≡ 5 (r = n, 2N)
2・2N-2≦n＜3・2N-2 のとき，
C(2N + n, r) ≡ 7 (r = n, 2N)
3・2N-2≦n＜4・2N-2 のとき，
C(2N + n, r) ≡ 3 (r = n, 2N)
に注意すれば，まとめて全部証明できてしまいました。