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.