◆山梨県 Footmark さんからの解答。
【答え】
ｎ＝２q−１ (ｑは２≦ｑの整数)
【考察】
Ａ＝nＣm*n-mＣk
| ＝ | ｎ！ ｍ！ｋ！{ｎ−(ｍ＋ｋ)}！ |
| ＝ | ｎ！(ｍ＋ｋ)！ ｍ！ｋ！{ｎ−(ｍ＋ｋ)}！(ｍ＋ｋ)！ |
| ＝ | ｎ！ {ｎ−(ｍ＋ｋ)}！(ｍ＋ｋ)！ | * | (ｍ＋ｋ)！ ｍ！ｋ！ |
Ｂ＝m+kＣm
| ＝ | (ｍ＋ｋ)！ ｍ！ｋ！ |
ここで、Ａ と Ｂ の偶奇が一致することと、Ａ＋Ｂ が偶数であることとは同等ですから、
Ａ＋Ｂ
| ＝ | (ｍ＋ｋ)！ ｍ！ｋ！ | [ | ｎ！ {ｎ−(ｍ＋ｋ)}！(ｍ＋ｋ)！ | + １ ] |
が，いかなる ｍ,k に対しても常に偶数でなければなりません。
| 右辺の積の左側の | (ｍ＋ｋ)！ ｍ！ｋ！ | は、 |
ですから、積の右側が偶数に、つまり
| ｎ！ {ｎ−(ｍ＋ｋ)}！(ｍ＋ｋ)！ | が、常に奇数でなければなりません。 |
ｍ＋ｋ＝ｐ (当然ｐは０≦ｐ≦ｎ)とすると、
| ｎ！ {ｎ−(ｍ＋ｋ)}！(ｍ＋ｋ)！ | ＝ | ｎ！ (ｎ−ｐ)！ｐ！ | ＝nＣp |
問題は、いかなる ｐ においても常に nＣp が奇数になる ｎ を探すことになります。
パスカルの三角形では、横１行のすべての値が奇数である段を探すことです。
１番上に 0Ｃ0＝１ を加え、奇数を●(色着き含む)、偶数を○ で表したパスカルの三角形は以下のとおりです。
この三角形で、横１行のすべての値が奇数なのは、１番上の●を頂点にして●(色着き含む)の線でできる三角形の底辺です。
明らかに、底辺は ２q 段目に当たります。（ｑは１≦ｑの整数）
ところが、１番上には 0Ｃ0＝１ を加えてますし、また ２≦ｎ です。
∴ ｎ＝２q−１ (ｑは２≦ｑの整数)
【Ｐ・Ｓ】
とても、面白い問題だと思います。
◆茨城県 小川 康幸 さんからの解答。
問題を一般化して一般の素数pで考える。
A=nCm*n-mCk，B=m+kCk とおきます。
任意の0以上の整数m、kに対して、
Aがpで割り切れる。⇔ Bがpで割り切れる。
となるような、n≧m+kとなるような自然数を求める。
【答え】
n=pf*t-1
ただし、fは0以上の整数、tはp-1以下の自然数
【解答】
まず、pで割り切れない自然数xに対して、xp-1≡1 (mod p)となる。
証明は、割り切れる？part2を参照ください。
一方、xがpで割り切れるとき、
xp-1≡0 (mod p)
A、B共にpで割り切れないとき、
Ap-1-Bp-1≡1-1≡0 (mod p)
A、B共にpで割り切れるとき、
Ap-1-Bp-1≡0-0≡0 (mod p)
よって、Ap-1-Bp-1≡0 (mod p)となるような、nを求めればよい。
A=nCm+k*B と書けるので、
0≡Ap-1-Bp-1
≡Bp-1*(nCm+kp-1-1)
Bはpで割り切れないこともあるので、
nCm+kp-1-1がpで割り切れる。
nCm+kp-1≡1 (mod p)
つまり、0≦j≦nを満たす任意のjに対して、nCjがpで割り切れない事が必要十分条件です。
ここで、記号の定義をします。
自然数dに対して、dが、phで割り切れ、ph+1で割り切れないとき、
h=l(d)と書くことにする。
ただし、dがpで割り切れないとき、h=0と考える。
また、このとき、d=ph*s
sはpで割り切れない自然数と書ける。
0以上の整数fを、f=l(n+1)とおく、
すると、n+1は、n+1=pf*t
tはpで割り切れない自然数と書ける。
ここで、次のことが言える。
【１】
t＞pとなるとき、
はpで割り切れる。
【証明】
tがpで割り切れないので、1．が言えた。
証明終
【２】
t＜pとなるとき、任意の0≦j≦nとなるjに対して、nCjはpで割り切れない。
(tはpと互いに素なので、t=pとはならない)
【証明】
j≧1のとき
| nCj= | (pf*t-1)*(pf*t-2)*･･･(pf*t-j) 1*2*･･･*j | となる。 |
1≦r≦jなる任意のrに対して、
r≦j＜pf*t＜pf+1だから、l(r)＜f+1、
よってl(r)≦fとなる。
v=l(r)とすると、r=pv*w、wはpで割り切れない自然数と書ける。
v＜fのとき、
pf*t-pv*w=pv*(pf-v*t-w)
pf-v*t-w≡-w (mod p)
だから、
pf-v*t-wはpで割り切れない。
l(pf*t-r)=v=l(r)
v=fのとき、pf*w=r≦j≦pf*t-1＜pf*t
よって、w＜tとなる。
pf*t-pv*w=pf*(t-w)
1≦t-w＜pだからt-wはpで割り切れない
l(pf*t-r)=v=l(r)
よって、
l(nCj)
| = | j r=1 | {l(pf-r)}- | j r=1 | l(r) |
| = | j r=1 | l(r)- | j r=1 | l(r) |
| =0 |
nCjはpで割り切れない。
j=0のとき、nC0=1は明らかに、pで割り切れない。
よって、題意は言えた。
証明終わり。
よって、0≦j≦nを満たす任意のjに対して、nCjがpで割り切れないnは、
0以上の整数fと、p-1以下の自然数tによって、
n=pf*t-1とかく事が出来るnに限ります。
解答終わり
【おまけ】
このとき、
nCm*n-mCk=nCm+k*m+kCkだから、
l(nCm)+l(n-mCk) =l(nCm+k)+l(m+kCk)となる。
l(nCm)=l(nCm+k)=0となるので、
l(n-mCk)=l(m+kCk)
となる。
同様にして、l(n-kCm)=l(m+kCm)
よって、m+kCk=m+kCmより
l(n-mCk)
=l(m+kCk)
=l(n-kCm)
=l(m+kCm)
さらに、n-mCk=n-mCn-m-k
n-kCm=n-kCn-k-mから、
l(n-mCk)
=l(m+kCk)
=l(n-kCm)
=l(m+kCm)
=l(n-mCn-m-k)
=l(n-kCn-k-m)
が言えます。