18 Quantos números inteiros entre 1 e 10.000 têm soma dos dígitos igual a 12 ?
Passo 1
O enunciado pede: “Quantos inteiros entre
e
têm soma dos dígitos igual a
?” O conteúdo aqui é combinatória de soluções inteiras não negativas com restrição de máximo por variável (cada dígito vai de
a
). Vamos modelar cada número como um vetor de dígitos e usar estrelas-e-barras
inclusão-exclusão para contar as soluções.
Passo 2
Qualquer inteiro de
a
(que cobre
a
) pode ser escrito como quatro dígitos
, com
e queremos
O caso
tem soma de dígitos igual a
, então não entra no total.
Passo 3
Primeiro contamos sem considerar o teto
. O número de soluções não negativas de
é, por estrelas-e-barras,
Passo 4
Agora corrigimos pelo fato de cada
não poder exceder
. Para um dígito fixo
violar, teríamos
. Definindo
, a soma passa a ser
cujo número de soluções não negativas é
Como há
escolhas de qual dígito viola, o total de soluções inválidas (com pelo menos um
) é
Não há interseção de dois dígitos violando simultaneamente, pois isso exigiria soma mínima
.
Passo 5
Subtraindo as soluções inválidas do total sem teto, obtemos o número desejado: