Deje $m$ ser un entero positivo. Dado $m$, quiero encontrar la más grande $n$, $1\leq n\leq m$, tal que $$m+n\elegir n $$ es impar. Hay alguna norma de teoremas o resultados? Cualquier referencia? Gracias!
Respuestas
¿Demasiados anuncios?
Anthony Shaw
Puntos
858
Kummer del Teorema, una prueba de que se da en esta respuesta, en el caso de $p=2$ dice
Si, al agregar $m$ $n$ en binario, no hay ningún lleva, a continuación, $\binom{m+n}{n}$ será impar.
Por lo tanto, el mayor $n\le m$, será el binario " -complemento de $m$ (trunca el tamaño de $m$).
Por ejemplo, si $m=5=101_{\text{two}}$,$n=10_{\text{two}}=2$. $$ \binom{5+3}{3}=56\qquad\binom{5+4}{4}=126\qquad\binom{5+5}{5}=252 $$ Si $m=10=1010_{\text{two}}$,$n=101_{\text{two}}=5$.
Tenga en cuenta que si $m=2^k-1$, entonces, los'complemento de $m$ truncado para el tamaño de $m$$0$. Por lo tanto, no es $1\le n\le m$, de modo que $\binom{m+n}{n}$ es impar.
Leg
Puntos
14825
Si $\dbinom{m+n}n$ es impar, esto significa que el mayor poder de $2$ dividiendo $\dfrac{(m+n)!}{m!n!}$. Esta está dada por $$\sum_{k=1}^{\infty} \left(\left\lfloor \dfrac{m+n}{2^k}\right\rfloor - \left\lfloor \dfrac{m}{2^k}\right\rfloor - \left\lfloor \dfrac{n}{2^k}\right\rfloor\right)$$ Por lo tanto, tenemos $$\left\lfloor \dfrac{m+n}{2^k}\right\rfloor = \left\lfloor \dfrac{m}{2^k}\right\rfloor + \left\lfloor \dfrac{n}{2^k}\right\rfloor$$ para todos los $k$.
Si $m = \sum_{l=0}^t a_l2^l$$n = \sum_{l=0}^t b_l2^l$, luego tenemos $$\left(\sum_{l=k}^t (a_l+b_l)2^{l-k}\right) + \sum_{l=0}^{k-1} \lfloor(a_l+b_l)2^{l-k} \rfloor = \sum_{l=k}^t (a_l+b_l)2^{l-k}$$ for all $k$. This means we need $a_l b_l = 0$ for all $l \in \{0,1,2,\ldots,t\}$.
Michael Lang
Puntos
1
Uno puede demostrar por inducción, ver, por ejemplo, esta respuesta, que todos los $(2^a-1)$th fila del triángulo de Pascal consiste enteramente impar de entradas, es decir, $2^a-1 \choose k$ es extraño que todos los $a,k$.
Ahora para fija $m$, $2^a-1$ el mayor número de este formulario $\lt 2m$ y cada una de las $n$ tal que $m+n \gt 2^a-1$ podemos usar ${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$ a realizar reducciones de $m+n \choose n$ para finalmente llegar al $\sum[{2^a-1 \choose k_i - 1} + {2^a-1 \choose k_i}]$. Cada $k_i \geq 0$, ya que existen en la mayoría de las $n$ sustracciones involucrados. La suma es par, porque cada individuo plazo es impar y hay un número par de términos. Vemos que, de hecho,$m+n=2^a-1$, porque sabemos $2^a-1 \choose k$ a un ser extraño.
Por ejemplo, para $m=5$, el primer número menos de $10$ de este formulario es $7$. Entonces $n=2$, $7 \choose 2$ es extraño, y cada una de las $5+n\choose n$ $n \gt 2$ es incluso por la reducción anterior argumento.
Para $m=2^a-1$, el primer número menos de $2*(2^a-1)$ de este formulario es $2^a-1$ sí. Entonces $n=0$, $m \choose 0$ es extraño, y cada una de las $m+n\choose n$ $n \gt 0$ es nuevo aun. Pero $n=0$ está excluido, por lo que no $m=2^a-1$ tiene una solución válida. También se puede ver, que el resto de los casos tienen solución.
DiGi
Puntos
1925
También puede utilizar Lucas del teorema. En este contexto, se dice que si las representaciones binarias de $m+n$$n$$(b_r\ldots b_0)_{\text{two}}$$(c_r\ldots c_0)_{\text{two}}$, respectivamente, entonces
$$\binom{n+m}n\equiv\prod_{k=0}^r\binom{b_k}{c_k}\pmod 2\;.$$
Las únicas posibilidades para $\binom{b_k}{c_k}$$\binom01=0$$\binom00=\binom10=\binom11=1$, lo $\binom{n+m}n$ es impar si y sólo si no hay ninguna $k$ tal que $b_k<c_k$. Supongamos que hay un $k$. Elija el más pequeño; a continuación, el binario expansiones de $m$ $n$ ambos tienen un $1$ en esa posición. Por lo tanto, queremos que el mayor $n\le m$ que no tienen un $1$ en su binario de expansión en cualquier posición en la que $m$$1$, y eso es simplemente el complemento de cadena de bits. En particular, si $2^k\le m<2^{k+1}$, $n=2^{k+1}-1-m$.
Rob
Puntos
101
Un experimento rápido sugiere es $n=2^e-m-1$ donde $2^e$ es la menor potencia de 2 mayor que $m$. Que esta $n$ $\binom{m+n}{n}$ impares de la siguiente manera rápida de Lucas teorema, utilizando el hecho de que $m+n = 2^e-1 = 2^{e-1}+2^{e-2}+\cdots+1$. Que no hay mayor $n$ funciona de la siguiente manera a partir de la fórmula habitual de la máxima potencia de un primer dividir un factorial después de señalar $m+n \ge 2^e$ pero $m,n < 2^e$.
