(OBM) Combinatória

Para ser múltiplo de 3, um número deve ter a soma de seus algarismos igual a um múltiplo de 3.

A       B     C     D     E
9  *  10 * 10 * 10 * 10 = 90.000 números de cinco dígitos

Um a cada três números é divisível por 3. Logo, há 30.000 números múltiplos de 3 com 5 dígitos.

Desses, quantos não contém 6?

Há 8 possibilidades para o primeiro dígito (1, 2, 3, 4, 5, 7, 8, 9), e 9 possibilidades para os próximos 3 dígitos (0, 1, 2, 3, 4, 5, 7, 8, 9). A soma desses 4 dígitos vai resultar em um dos três grupos de algarismos:

1, 4, 7 -> então o último pode ser 2, 5 ou 8
2, 5, 8 -> então o último pode ser 1, 4 ou 7
3, 6, 9 -> então o último pode ser 3, 6 ou 9

Desse modo, a soma entre os cinco resultará em um múltiplo de 3. Como apenas um dos três casos acima ocorrem por vez, há 3 possibilidades para o último algarismo.

Temos então 8 * 9 * 9 * 9 * 3 = 17.496 números múltiplos de 3 que não contém 6.

Há 30.000 múltiplos de 3 e 17.496 múltiplos de 3 que não contém 6. O número de múltiplos de 3 que contém 6 é a diferença entre os dois anteriores, isto é, 12.504.