Seja {A_n} a quantidade de seqüências com 4 números escolhidos de 1 a n
tais que a diferença positiva seja maior ou igual a 2 (n>=4).
Seja {B_n} a quantidade de seqüências com 3 números escolhidos de 1 a n
tais que a diferença positiva seja maior ou igual a 2 (n>=3).
Seja {C_n} a quantidade de seqüências com 2 números escolhidos de 1 a n
tais que a diferença positiva seja maior ou igual a 2 (n>=2).
Para sabermos quanto vale A_(n+1), devemos dividir nossa contagem em duas
partes:
i) escolher 4 números dentre os que vão de 1 a n tais que a diferença
positiva seja maior ou igual a 2. Isto pode ser feito de A_n maneiras.
ii) escolher o (n+1) como um número obrigatório a constar no nosso conjunto
de 4. Após isso, escolher 3 números entre os que vão de 1 a (n-1), cuja
diferença positiva seja maior ou igual a 2. Isto pode ser feito de B_(n-1)
maneiras.
Podemos escrever: A_(n+1) = A_n + B_(n-1) (n>=4).
Analogamente teremos: B_(n+1) = B_n + C_(n-1) (n>=3).
Pensando de maneira similar, temos também: C_(n+1) = C_n + (n-1) (n>=2).
Temos três séries telescópicas. Resolvendo e lembrando que a soma das
colunas do triângulo de Pascal é o número binomial localizado na diagonal à
direita do último elemento do somatório, obteremos:
C_n = binomial (n-1,2) = (n-1).(n-2)/2!
B_n = binomial (n-2,3) = (n-2)(n-3)(n-4)/3!
A_n = binomial (n-3,4) = (n-3)(n-4)(n-5)(n-6)/4!
Em quinta-feira, 11 de julho de 2013, Lucas Prado Melo escreveu:
> 2013/7/11 Artur Costa Steiner <steinerar...@gmail.com <javascript:_e({},
> 'cvml', 'steinerar...@gmail.com');>>
>
>> Não consegui achar uma forma de resolver isto sem recorrer a um
>> computador.
>>
>> Com os inteiros de 1 a 100, quantos conjuntos de 4 elementos podemos
>> formar de modo que a diferença positiva entre dois elementos do conjunto
>> seja maior ou igual a 2?
>>
>
> Utilizando da seguinte identidade:
>
> sum_{0 <= k <= n} kCm = (n+1)C(m+1)
>
> , onde xCy é o numero de combinações de x objetos, y a y,
>
> podemos obter uma expressão para o valor procurado.
>
> Em vez de considerar as posições, consideremos a posição inicial x e as
> diferenças d1, d2 e d3, de modo que os números selecionados sejam x, x+d1,
> x+d1+d2, x+d1+d2+d3.
>
> Se fixarmos k = d1+d2+d3, de quantas formas podemos selecionar uma tripla
> (d1, d2, d3)? Basta fazer uma combinação completa de k-6 em 3 pedaços e
> então adicionar a cada um dos 3 pedaços o +2 pra respeitar a restrição de
> ser >= 2. O número de triplas é portanto (k-6 + 2)C2.
>
> Fixado k, podemos selecionar a posição inicial de 100-k-1 formas.
>
> Assim o número total de formas é
> sum_{6 <= k <= 99} (100 - k - 1) (k-6 +2)C2.
>
> Para nos "livrarmos" do "k" no fator podemos fazer o seguinte:
>
> (99 - 3 - (k-3)) (k-4)C2 = 96 (k-4)C2 - (k-3) (k-4)C2 = 96 (k-4)C2
> - 3 (k-3)C3
>
> E assim a expressão pode ser obtida da identidade mostrada no início com
> algumas manipulaçõezinhas algébricas.
>
>
> --
> []'s
> Lucas
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antivírus e
acredita-se estar livre de perigo.
