2013/7/11 Artur Costa Steiner <[email protected]>
> 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.
