|
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
|