2013/7/11 Artur Costa Steiner <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.