使三项式系数为奇数的唯一k值

0.1110

任给自然数m,n，试证明：有且只有一个自然数\(k\in [0,\min(m,n)]\)，使得三项式系数\[\left(\begin{split}m+n-k\ \ \ \\m-k,n-k,k\end{split}\right)=\frac{(m+n-k)!}{k!(m-k)!(n-k)!}\]是奇数.

northwolves

$\frac{(m+n-k)!}{k!(m-k)!(n-k)!}$=$\frac{m!(m+n-k)!}{k!(m-k)!m!(n-k)!}$=$C_{m+n-k}^mC_m^k$

测试了几个$100>=m>=n>=k>=0$,似乎结论是对的

mathe

我们可以将n-k,m-k,k写成二进制数.
由于n! 中含有2的次幂为\([\frac n2]+[\frac n4] + [\frac n8]+...\)
本题结果为奇数表示n-k,m-k,k三者进行二进制相加时，所有比特位上都没有进位，也就是说三者中每个比特位都最多只有一个数是1.
我们可以对比特位从低到高进行数学归纳法证明。
如果我们设k的二进制表示为$k_{t-1}k_{t-2}...k_0$, 并且即$k^{(h)}=k_{h-1}k_{h-2}...k_0$,也就是k的最低h位构成的二进制数。
类似可以定义$n^{(h)},m^{(h)}$，而且很显然$(n-k)^{(h)}=n^{(h)}-k^{(h)} (mod 2^h)$等
于是，我们首先容易计算所有合法的$k_0$
显然在$n_0=m_0=1$时，$k_0=1$,不然$k_0=0$
然后计算$k_1$时，我们只需要判断$(n-k^{(1)})_1$和$(m-k^{(1)})_1$，只有两者都是1时,$k_1$才能够是1，不然，必然是0.
同样确定$k_1$以后，我们就已经确定了$k^{(2)}$
所以同样可以根据$(n-k^{(2)})_2$和$(m-k^{(2)})_2$是否同时为1，唯一确定$k_2$到底取1还是0.
上面过程一直下去，显然能够合法取到的k是唯一的。我们还需要证明的是上面这个过程构造的k必然不大于m和n,而这个结论也很容易证明。只要依次归纳证明
$m^{(h)} \ge k^{(h)}$即可，这个不难。
所以这样的k是存在而且唯一的。

现在这个过程也给了一种从n,m计算k的有效方法。
比如n=26, m=29，它们的二进制表示分别为11010和11101
由于$n_0=0, m_0=1$, 所以$k_0=0$, $n-k^{(1)}=26, m-k^{(1)}=29$
      $(n-k^{(1)})_1=1,(m-k^{(1)})_1=0$, 所以$k_1=0$, $n-k^{(2)}=26, m-k^{(2)}=29$
      $(n-k^{(2)})_2=0,(m-k^{(2)})_2=1$, 所以$k_2=0$, $n-k^{(3)}=26, m-k^{(3)}=29$
      $(n-k^{(3)})_3=1,(m-k^{(3)})_3=1$, 所以$k_3=1$, $n-k^{(4)}=18, m-k^{(4)}=21$，它们二进制表示分别为10010,10101
      $(n-k^{(4)})_4=1,(m-k^{(4)})_4=1$, 所以$k_4=1$, $n-k^{(5)}=2, m-k^{(5)}=5$，它们二进制表示分别为00010,00101
由于余下高比特位都已经是0了，计算结束，得到k的二进制表示为11000，也就是k=24.
计算结果这时$\frac{(n+m-k)!}{(n-k)!(m-k)!k!}=55221075$的确是奇数。

   

northwolves

Triangle T(n,k) = n AND k, 0<=k<=n, bitwise logical AND, read by rows.

gxqcn

一个奇偶性问题，最后居然用到二进制，最终还涉及到位运算，神奇！
如果搁在计算机兴起之前的时代，若想到此类方法，岂不要先做大量铺垫？

hujunhua

一个很有诱惑性的变量替换：
将`m-k,n-k`用`m,n`代替，得到如下结论：
对于任意自然数`m,n`, 存在唯一的自然数`k`, 使得`\left(\begin{split}k+m+n\\\ \ k,\ m,\ n\ \ \end{split}\right)=\D\frac{(k+m+n)!}{k!m!n!}`为奇数。
错在哪里？

曹半

hujunhua 发表于 2022-11-29 18:39
一个很有诱惑性的变量替换：
将`m-k,n-k`用`m,n`代替，得到如下结论：
对于任意自然数`m,n`, 存在唯一的 ...

`m’=m-k,n’=n-k,k=m@n\to k=(m’+k)@(n’+k)`
得到一个关于`k`的方程，在不清楚算符“@”的情况下，无法断言这个方程有解、无解，更不能断言有唯一解。

hujunhua

约定`[x]_2`表示整数`x`的二进制表示。`[x]_2^i`表示`[x]_2`第`i`位（从低到高）。
约定 `\text{IntExp}_2[x]`表示整数`x`中含因子2的重数。
我们有公式\[\text{IntExp}_2[n!]=\left[\frac n2\right]+\left[\frac n4\right] +\left[\frac n8\right]+\cdots+\left[\frac n{2^i}\right]+\cdots\tag{1}
\] 及不等式\[\left[\frac{a_1+a_2+\cdots+a_t}{b}\right]\ge\left[\frac{a_1}b\right]+\left[\frac{a_2}b\right]+\cdots+\left[\frac{a_t}b\right]\tag{2}\]
三项式系数为奇数等价于\[\text{IntExp}_2[(m+n-k)!]=\text{IntExp}_2[(m-k)!]+\text{IntExp}_2[(n-k)!]+\text{IntExp}_2[k!]\tag{3}
\]将公式(1)代入等式(3)，由不等式(2)得\[
\left[\frac{m+n-k}{2^i}\right]=\left[\frac{m-k}{2^i}\right]+\left[\frac{n-k}{2^i}\right]+\left[\frac{k}{2^i}\right]\tag{4}
\]\[\to [m+n-k]_2^i=[m-k]_2^i+[n-k]_2^i+[k]_2^i\tag{5}
\]可见上式右边3个比特位最多只有一个是1，相加不产生进位. 那么任取右边2项相加，自然也不会产生进位，故\[
\to\begin{split} [m]_2^i&=[m-k]_2^i+[k]_2^i\\ [n]_2^i&=[n-k]_2^i+[k]_2^i\end{split}\tag{6}
\](6)上下两式相乘立得\[[m]_2^i \& [n]_2^i=[k]_2^i\tag{7}\]上面的推导过程一步步都是可逆的，所以这样的k是存在而且唯一的。

比如n=26, m=29，二进数表示分别是11010和11101，所以`k=[11000]_2=24,m-k=5,n-k=2,m+n-k=31`

计算结果$\frac{31!}{2!5!24!}=55221075$的确是奇数。

hujunhua

7#的问题现在有更正了。
`\left(\begin{split}k+m+n\\\ \ k,\ m,\ n\ \ \end{split}\right)=\D\frac{(k+m+n)!}{k!m!n!}`为奇数的充要条件是\[[k+m+n]_2^i=[k]_2^i+[m]_2^i+[n]_2^i\]所以对于给定的正整数`m,n`, 存在`k`满足上式的充要条件是\([m+n]_2^i=[m]_2^i+[n]_2^i\)，即\[[m]_2^i\&[n]_2^i=0\]满足这个条件，那么小于`\max(m,n)`的`k`共有`2^l`个（`l`是`[m]_2^i=[n]_2^i=0`的位数）。

0.1110

感谢mathe老师，胡俊华老师：
不曾想此题轻易地被“二进制”+“位运算”证明并扩展了！
不由想到年前的：
《宿南澳岛》
云舒云卷海天清
潮落潮生岛月明
大浪淘沙淘不净
无名小贝也晶莹