Técnica de contagem: contagem por casos

A análise combinatória é uma ferramenta muito útil que consegue resolver uma variedade enorme de problemas de contagem através da contagem indireta. Mas nem sempre dá para ser tão elegante: o jeito é partir para o trabalho braçal e contar na raça. Contou a mesma coisa duas vezes ou esqueceu de alguma ocorrência? Zerou a questão.

Apresento aqui um método bem prático e útil para lidar com essas complicações: a contagem por casos.

Pré-requisitos

Não precisamos de muitos artifícios da análise combinatória — se precisássemos, não estaríamos estudando contagem por casos! —. Mais precisamente, nada além do princípio fundamental da contagem.

O que é contagem por casos?

Enquanto brincava um pouco no Alcumus, do Art of Problem Solving, um tópico me chamou a atenção: casework counting. Não há nada fora do normal e você provavelmente já usou em algum momento, mas é muito interessante ver como a técnica pode ser aplicada em vários contextos. O esquema geral é o seguinte:

1 - Divida o problema em casos, que devem englobar todas as ocorrências possíveis;
2 - Para cada caso, conte as ocorrências diretamente ou por análise combinatória;
3 - Verifique se há intersecções entre os casos;
4 - Some as ocorrências contadas em cada caso, tomando cuidado com as intersecções.

No vídeo abaixo, Richard Rusczyk demonstra a contagem por casos na prática:

Se inglês não for sua praia, sem problemas, veremos a seguir como resolver o primeiro problema do vídeo e aplicar a estratégia.

Exemplo simples - Contando caminhos

Considere o diagrama abaixo:

Queremos saber quantos caminhos distintos podemos tomar para ir de A até B.

• 1 - Divida o problema em casos, que devem englobar todas as ocorrências possíveis.

Não importa qual seja o caminho, ele inevitavelmente deve passar por X, Y ou Z. Temos aí nossos 3 casos bem definidos que abrangem todos os caminhos possíveis.

• 2 - Para cada caso, conte as ocorrências diretamente ou por análise combinatória.

- Passando por X: De A até X temos 3 possibilidades, depois mais 2 de X até B. Pelo princípio fundamental da contagem, temos 3 * 2 = 6 caminhos.

- Passando por Y: De A até Y temos 1 possibilidade, depois mais 4 de Y até B. Pelo princípio fundamental da contagem, temos 1 * 4 = 4 caminhos.

- Passando por Z: De A até Z temos 2 possibilidades, depois mais 5 de Z até B. Pelo princípio fundamental da contagem, temos 2 * 5 = 10 caminhos.

• 3 - Verifique se há intersecções entre os casos.

Um caminho não pode ligar A até B passando por mais de um ponto intermediário, seja ele X, Y ou Z. Assim, temos certeza de que não contamos um mesmo caminho mais de uma vez.

• 4 - Some as ocorrências contadas em cada caso, tomando cuidado com as intersecções.

Nossa resposta é, portanto, 6 + 4 + 10 = 20 caminhos.

Outro exemplo - Números especiais

(American Mathematics Competitions 2005) Quantos números de 3 dígitos satisfazem a propriedade de que o dígito do meio é a média aritmética do primeiro e último dígitos?

• 1 - Divida o problema em casos, que devem englobar todas as ocorrências possíveis.

Vemos que o primeiro e último dígitos dependem diretamente do dígito do meio, então podemos montar casos referentes a ele:

- O dígito do meio é 1: Os números são 111 e 210, totalizando 2.
- O dígito do meio é 2: Os números são 123, 321, 222 e 420, totalizando 4.
.
.

Ok, não é muito prático. É basicamente uma solução de "força bruta" — testar ou procurar ocorrências uma por uma —, só que mais organizada. Consegue visualizar uma maneira de diminuir os casos ou uma propriedade que torne a contagem mais eficiente?

Note que, se o dígito do meio é a média aritmética dos outros 2 dígitos, então a soma desses dígitos deve ser par. Afinal, um número ímpar dividido por 2 não resulta em um inteiro. Isso nos limita a simplesmente 2 casos:

- Caso 1: O primeiro e o último dígito são ímpares;
- Caso 2: O primeiro e o último dígito são pares.

Qualquer outro caso é impossível nas condições especificadas, pois par + ímpar = ímpar.

Isso nos permite acrescentar uma nova observação: se um problema pode ser dividido de formas diferentes, opte por aquela com menos casos e/ou que permita uma contagem mais fácil.

• 2 - Para cada caso, conte as ocorrências diretamente ou por análise combinatória.

Ao invés de contar um por um, outra vantagem é que agora podemos usar o princípio fundamental da contagem:

- Caso 1: Temos 5 possibilidades para o primeiro dígito (1, 3, 5, 7, 9) e novamente 5 para o último. Portanto, há 5 * 5 = 25 números.

- Caso 2: Temos 4 possibilidades para o primeiro dígito (2, 4, 6, 8) e mais 5 para o último (contando com o zero). Portanto, há 4 * 5 = 20 números.

• 3 - Verifique se há intersecções entre os casos

É bem interessante ver que efetivamente separamos os números pares dos ímpares, então não há intersecção.

• 4 - Some as ocorrências contadas em cada caso, tomando cuidado com as intersecções.

Nossa resposta final é 25 + 20 = 45 números.

Problemas de treino

• Problema 1 - Quantos números naturais menores que 1000 contêm o dígito 3 pelo menos duas vezes?

• Problema 2 - Quantas vezes o número 1 aparece na lista dos naturais de 50 a 600?

• Problema 3 - (MathCounts 2009) Isaac escreveu os inteiros de 1 até 104, incluindo os extremos. Quantos dígitos ele escreveu?

• Problema 4 - (American Mathematics Competitions 2006) Um inseto está posicionado em um vértice de um cubo e se move ao longo de suas arestas de acordo com a seguinte regra: em cada vértice, o inseto escolherá percorrer uma das três arestas a partir desse vértice. Cada aresta tem uma probabilidade igual de ser escolhida, e todas as escolhas são independentes. Qual é a probabilidade de que, após sete movimentos, o inseto terá visitado cada vértice exatamente uma vez? 

• Problema 5 - (MathCounts 2007) Usando cada um dos dígitos do conjunto S = {1, 2, 3, 4} exatamente uma vez e zero ou mais sinais de adição ("+"), quantos totais distintos podem ser obtidos? Nenhum dígito pode ser usado como uma potência, raiz etc. Apenas adição é válida. Quando n dígitos são escritos próximos uns aos outros, eles representam um número de n dígitos, não o produto de n fatores. Quatro desses totais são 1234, 55 = 12 + 43, 127 = 123 + 4 e 37 = 31 + 2 + 4.

• Problema 6 - (MathCounts 2009) Qual é o maior inteiro n tal que \(3^n\) é um divisor de \(1 \times 3 \times 5 \times ... \times 97 \times 99\)?

Fontes

Casework - AoPSWiki
Casework Counting - Part 1
Casework Counting - Part 2