Resumo da opera:
Escreva n e p em base 2, e compare seus digitos. Se TODOS os digitos
binarios de n forem maiores que os de p, C(n,p) eh impar. Senao (isto eh, se
houver algum digito 0 em n na mesma posicao de algum digito 1 em p), entao
C(n,p) eh par.
Exemplos:
n=47=10
p=24= 11000
Como tem aquele segundo digito do n que perde para o digito
correspondente de p, entao C(47,24) eh par.
n=46=101110
p=10= 1010
Como todos os digitos de n ganham dos de p, entao C(46,10) eh impar.
---///---
Para demonstrar:
IDEIA 1: Monte um triangulo de Pascal apenas com i (impar) e p (par).
i
ii
ipi
ipppi
iippii
ipipipi
Por exemplo, aqui em cima dah para ver que o triangulo que aparece nas 4
primeiras linhas se repete duas vezes nas linhas 5-8 (e o espaco que sobra
no meio eh preenchido com p). Note que este fenomeno vai se repetir: o
triangulo das linhas 1-8 eh copiado duas vezes nas linhas 9-16, e o buraco
eh preenchido com numeros pares. Em ASCII pobre, esta recorrencia eh uma
coisa mais ou menos assim (T eh o triangulo que se repete):
|\
|T\
|\ pp |\
|T\ p |T\
Se o primeiro digito binario de p for maior que o de n, estamos no triangulo
de p's no meio, deu par. Senao, a repeticao de triangulos diz que voce pode
jogar fora o primeiro digito de n (andando 2^k linhas para cima), jogar fora
o primeiro digito de p (andando 2^k colunas para a esquerda ou nao,
dependendo se este digito eh 0 ou 1), e recomecar o processo com os novos
numeros... Ou seja, comparando o novo primeiro digito de cada um... e assim
por diante.
IDEIA 2: Este papo todo eh um caso particular do Teorema de Lucas. Uma
demonstracao muito facil de ler estah em:
http://www.math.hmc.edu/funfacts/ffiles/30002.4-5.shtml
(Ele usa um caso particular, mas eh obvio que o argumento funciona em
geral.)
Abraco,
Ralph
2010/11/20 Fernando Oliveira fet...@gmail.com
C(n,p) = n! / (n-p)!p!
Conte os fatores de 2 em n!, (n-p)! e p!. Se o número de fatores de 2 for
maior no numerador, o número é par, se for igual, é ímpar.
Ex: C(36, 24) = 36! / 24!12!
(pegando a parte inteira das divisões)
fatores de 2 em 36!: 36/2 + 36/4 + 36/8 + 36/16 + 36/32 = 18 + 9 + 4 + 2 +
1 = 34
fatores de 2 em 24!: 24/2 + 24/4 + 24/8 + 24/16 = 12 + 6 + 3 + 1 = 22
fatores de 2 em 12!: 12/2 + 12/4 + 12/8 = 6 + 3 + 1 = 10
Como 34 22 + 10, o número é par.
Fernando
