|
essa foi uma quest�o da obm-u, n�o?
existe um resultado, que sai facilmente por indu��o
que mostra que o n�mero de combina��es de valores a1, a2, ..., a[k] > 0
inteiros tq:
a1 + a2 + ... + a[k] = n � Binomial(n-1,
k-1).
no caso do problema temos a1, ..., a10 e a
restri��o extra 0 < a1, ..., a10 < 7.
o inteiro 7 s� pode aparecer uma vez, pois se
aparecer 2 vezes teremos somado 14 com apenas dois elementos e precisar�amos
somar 6 com o resultado de 8 dados, o que � imposs�vel.
ent�o precisamos contar o n�mero de vezes em que o
7 aparece
temos 10 posi��es para colocar o 7 e depois
precisamos de 9 inteiros somando 13, use a f�rmula acima... 10*Binomial(12,
8)
elimine o caso em que aparece um 8 na sol., depois
repita para o caso 9, 10 e 11.
a id�ia da sol. oficial do problema � parecida (e
mais elegante do que o racioc�nio acima):
- contar as solu��es que incluam um
n�mero >= 7 � equivalente a contar as 10 vezes as
solu��es de
a1' + a2' + ... + a10' = 14, com
a[i]' > 0, isso porque podemos tirar 6 do inteiro >= 7 e ficar com um
inteiro > 0, multiplicamos por 10 porque a posi��o do inteiro >= 7 �
qualquer uma das 10 poss�veis.
[ ]'s
|