A maioria dos problemas de contagem, nas provas e fora delas, se resolve com um número pequeno de movimentos usados de novo e de novo. As fórmulas dos capítulos anteriores são só metade do trabalho; a outra metade é perceber qual movimento o problema está pedindo. Este capítulo reúne os nove movimentos que resolvem a maior parte dos problemas. Cada um é descrito nas mesmas cinco partes: o que é, por que funciona, o sinal no enunciado que o chama, um exemplo e a armadilha que costuma pegar as pessoas. No fim há uma rotina para atacar qualquer problema, uma lista de armadilhas clássicas e duas rodadas de prática.
Ao final você vai conseguir
- Reconhecer pelo enunciado qual movimento de contagem o problema precisa.
- Usar com segurança o complementar, o bloco, os espaços e "escolher os lugares primeiro".
- Perceber uma contagem em excesso e dividir por ela, ou separar em casos quando uma restrição afeta outra.
- Seguir uma rotina fixa para montar qualquer problema de contagem.
- Evitar as armadilhas clássicas: contagem dupla, ordens internas esquecidas, itens iguais contra itens diferentes.
O que é. Antes de qualquer fórmula, troque de lugar dois dos itens escolhidos num resultado e pergunte se o resultado mudou.
Por que funciona. Arranjos contam resultados ordenados e combinações contam grupos; a única diferença entre eles é se uma troca gera um resultado novo. O teste faz exatamente essa pergunta.
Quando usar. Sempre, como primeiro passo. Palavras como presidente, primeiro, posição, senha, pódio apontam para ordem; palavras como comissão, grupo, equipe, conjunto, bilhete, mão de cartas apontam para ausência de ordem.
Exemplo. Escolher 2 representantes de turma com funções iguais entre 30 alunos: trocar os dois dá a mesma dupla, então C(30, 2) = 435. Escolher um representante e um vice: a troca dá um resultado novo, então A(30, 2) = 870.
A armadilha. A palavra "escolher" não quer dizer combinação. "Escolher um presidente e um tesoureiro" é arranjo.
O que é. No método das casas, preencha as posições com condições antes das livres.
Por que funciona. O princípio multiplicativo precisa que cada etapa tenha um número fixo de opções. Uma posição livre tem o mesmo número de opções aconteça o que acontecer; uma restrita pode não ter, se as livres já gastaram o que ela precisa.
Quando usar. "Não pode começar com 0", "precisa terminar em vogal", "precisa ser ímpar", "o primeiro lugar fica com…".
Exemplo. Anagramas de LIVRO que começam e terminam por vogal: as pontas primeiro, I e O em 2 ordens; depois as 3 consoantes no meio, 3! = 6. Total 12.
A armadilha. Duas restrições que disputam os mesmos itens (o último algarismo par e o primeiro diferente de 0) não podem ir as duas primeiro. Aí use o macete 3.
O que é. Divida os resultados em casos separados, conte cada um e some.
Por que funciona. O princípio aditivo: se todo resultado cai em exatamente um caso, o total é a soma dos casos.
Quando usar. Quando uma escolha muda o número de opções de outra (o último algarismo é 0 ou não?), ou quando o próprio enunciado lista casos ("4 ou 5 dígitos", "exatamente 2 ou exatamente 3").
Exemplo. Pares de 3 algarismos distintos: terminando em 0, 9 · 8 = 72; terminando em 2, 4, 6 ou 8, 8 · 8 · 4 = 256. Total 328.
A armadilha. Os casos não podem se sobrepor e precisam cobrir tudo. Confira com um exemplo pequeno que nenhum resultado pertence a dois casos.
O que é. Conte tudo, conte o que você não quer, e subtraia.
Por que funciona. Todo resultado tem a propriedade ou não tem, então desejados = total − indesejados. Compensa quando o lado indesejado é um caso simples.
Quando usar. "Pelo menos um", "nem todos", "não lado a lado", "algum algarismo repetido".
Exemplo. Senhas de 4 dígitos com pelo menos um dígito repetido: todas as senhas, 10⁴ = 10 000, menos as com todos os dígitos distintos, 10 · 9 · 8 · 7 = 5040. Total 4960.
A armadilha. O contrário de "pelo menos um" é "nenhum", não "exatamente um".
O que é. Itens que precisam ficar juntos são colados num bloco, contado como um único item; depois se multiplicam as ordens internas do bloco.
Por que funciona. Toda ordem com os itens juntos é exatamente uma ordem do bloco entre os outros, vezes uma ordem dentro do bloco.
Quando usar. "Juntos", "lado a lado", "um ao lado do outro", "em sequência sem separar".
Exemplo. Anagramas de PERNAMBUCO com as vogais E, A, U, O juntas, em qualquer ordem: o bloco mais P, R, N, M, B, C são 7 itens, 7! = 5040, vezes 4! = 24 dentro do bloco: 120 960.
A armadilha. Esquecer as ordens internas, ou multiplicá-las quando a ordem dentro do bloco é fixa ("juntas e nessa ordem").
O que é. Para manter alguns itens separados, posicione primeiro os outros; depois ponha os itens que devem ficar separados nos espaços entre eles, no máximo um por espaço.
Por que funciona. m itens em fila deixam m + 1 espaços (contando as duas pontas). Itens postos em espaços diferentes nunca se encostam.
Quando usar. "Nunca dois lado a lado", "nunca juntos", para mais de dois itens, quando o complementar exigiria inclusão–exclusão.
A armadilha. Esquecer as duas pontas como espaços, ou usar os espaços para itens que só precisam ficar longe de um item específico.
O que é. Conte como se tudo fosse diferente e ordenado, e depois divida por quantas vezes cada resultado real foi contado.
Por que funciona. Se todo resultado real foi contado o mesmo número m de vezes, a contagem verdadeira é a contagem bruta dividida por m. É exatamente daí que vêm o k! das combinações, o a!b! das letras repetidas e o n das mesas circulares.
Quando usar. Itens iguais, giros de um círculo, grupos sem nome, ou uma condição simétrica como "A antes de B" (exatamente metade de todas as ordens).
Exemplo. Em quantas ordens de chegada de 6 corredores a Ana chega antes da Bia? Trocar as duas forma pares entre cada ordem e uma em que a Bia chega antes: 6!/2 = 360.
A armadilha. Dividir só funciona quando todo resultado foi contado o mesmo número de vezes. Em "pelo menos um homem" escolhendo "o" homem primeiro, uma comissão com um homem é contada uma vez e uma com dois homens duas, então nenhuma divisão única conserta.
O que é. Decida quais posições um tipo de item vai ocupar (uma combinação de posições) e depois preencha cada tipo de posição.
Por que funciona. Um resultado fica determinado por onde vai cada tipo e pela ordem dentro de cada tipo; as duas escolhas são etapas.
Quando usar. Sequências com um número fixo de um símbolo, itens que mantêm uma ordem fixa entre si, caminhos mínimos num quadriculado.
Exemplo. Anagramas de CAPITULO em que as vogais A, I, U, O aparecem nessa ordem (não necessariamente juntas): escolha os 4 lugares das vogais, C(8, 4) = 70; elas entram na ordem fixa, 1 modo; as 4 consoantes preenchem o resto, 4! = 24. Total 1680, que é 8!/4!, como o macete 7 também diz.
A armadilha. Escolher os lugares é combinação (os lugares formam um conjunto); preenchê-los é permutação dos itens, a não ser que os itens sejam iguais ou tenham ordem fixa.
O que é. Todo problema em que itens iguais são repartidos entre caixas diferentes é k estrelas e n − 1 barras: C(n + k − 1, k).
Por que funciona. Itens iguais não têm identidade, então uma repartição fica determinada por quantos vão para cada caixa, que é uma fila de estrelas e barras.
Quando usar. Balas, moedas ou votos iguais; repetição permitida e ordem ignorada; soluções inteiras de x + y + z = s.
Exemplo. 10 votos iguais entre 3 candidatos, cada candidato pode não receber nenhum: C(12, 2) = 66 apurações possíveis.
A armadilha. Se os itens são diferentes (10 pessoas diferentes votando), cada item escolhe sua caixa: 3¹⁰, não estrelas e barras.
| Passo | Pergunte |
|---|---|
| 1 | O que exatamente é um resultado? Escreva um, como exemplo concreto. |
| 2 | A ordem importa (teste da troca)? Os itens podem se repetir? Os itens são diferentes ou iguais? |
| 3 | Há restrições? Preencha-as primeiro, ou separe em casos. |
| 4 | O contrário é mais simples? Então conte o complementar. |
| 5 | Contei algum resultado mais de uma vez? Divida, ou repense o método. |
| 6 | Confira com uma versão menor que dê para listar à mão. |
| Errado | Certo | Por quê |
|---|---|---|
| "pelo menos um homem": escolher o homem, depois o resto | todos menos nenhum homem | comissões com vários homens são contadas várias vezes |
| dois juntos: 5! para 6 pessoas | 5! · 2! | a ordem interna do bloco foi esquecida |
| 10 pessoas diferentes votam em 3 candidatos: C(12, 2) | 3¹⁰ | eleitores diferentes não são estrelas iguais |
| 3 prêmios iguais para 10 pessoas: A(10, 3) | C(10, 3) | prêmios iguais não têm ordem |
| 6 pessoas em 3 duplas sem nome: 90 | 90/3! = 15 | grupos sem nome não podem ser ordenados |
| "e depois" contado com + | · | etapas se multiplicam, casos separados se somam |
Uma rodada de 10 perguntas
Acerte quantas conseguir. Os erros voltam no final, numa rodada de revisão.
Saber um macete é metade do caminho; a outra metade é ver quando ele serve. Cada pergunta é um problema e o que ele pede. Escolha o macete que resolve. Uma resposta errada mostra o macete certo e uma frase sobre por que ele funciona ali. As perguntas vêm numa ordem nova a cada rodada.
Uma rodada de 10 perguntas
Acerte quantas conseguir. Os erros voltam no final, numa rodada de revisão.
Cada exercício é criado na hora, então uma rodada nova nunca é igual. O computador escolhe a resposta primeiro e monta a pergunta em volta dela, trabalhando com frações exatas, por isso o gabarito está sempre certo. As respostas são lidas de forma exata: 0,75, 3/4 e 6/8 contam como o mesmo número (quando a forma irredutível é pedida, 6/8 só recebe um lembrete). Uma resposta errada mostra a resolução linha por linha, na ordem em que a lição faz; o número novo de cada linha aparece colorido.
Ideias-chave
- Teste da troca primeiro: um resultado novo depois da troca quer dizer que a ordem importa.
- Posições restritas primeiro; quando as restrições competem, separe em casos e some.
- "Pelo menos um" e "não juntos" costumam ser o total menos o contrário.
- Juntos: um bloco, vezes suas ordens internas. Separados: posicione os outros e use os m + 1 espaços.
- Conte como se tudo fosse diferente e ordenado, depois divida por quantas vezes cada resultado foi contado.
- Escolha primeiro os lugares de um tipo de item; itens iguais em caixas são estrelas e barras.
- Escreva um resultado concreto antes de contar, e confira o método num caso pequeno.