Contagem dupla é uma ferramenta para resolver problemas, ou partes deles, muito frequente em problemas onde queremos provar que algum valor está dentro de uma cota. Até certo ponto, o nome é autoexplicativo: vamos contar algo duas vezes, mais precisamente, vamos contar a mesma coisa de duas maneiras diferentes.
Visualizar como essa ideia pode ser útil é mais fácil em um problema, porém podemos adiantar que geralmente o objetivo é calcular algo de um primeira forma, depois de uma maneira diferente, e igualar tais valores.
Exemplo 1: 24 estudantes participam de um curso e, todo dia, 3 estudantes ficavam encarregados de alimentar o peixinho mascote. Depois do curso, notou-se que, escolhendo 2 estudantes, eles alimentaram o peixinho juntos exatamente uma vez. Quantos dias o curso durou?
Solução: Temos que a quantidade de pares diferentes de estudantes é 
. Além disso, por dia 3 estudantes ficavam encarregados, ou seja, 
pares, vezes a quantidade de dias (d) que o curso durou, tem que ser igual a quantidade de pares total, já que todo par trabalhou junto uma vez. Ou seja:
= 
d
24.23/2=(3.2/2)d
276 = 3d
d=92 dias
No exemplo 1, contamos de duas maneiras a quantidade total de pares de estudantes.
Exemplo 2 (OBM): Em um torneio de xadrez, cada participante joga com cada um dos outros. Uma vitória vale 1 ponto, um empate vale 1/2 ponto e uma derrota vale 0 ponto. Cada jogador ganhou a mesma quantidade de pontos contra homens e contra mulheres. Prove que a quantidade de participantes do torneio é um quadrado perfeito.
Solução: Sendo m o número de mulheres e n o número de homens no torneio, temos que acontecem 
partidas entre as mulheres, 
partidas entre os homens e nm partidas entre homens e mulheres. Além disso, temos que independente de se há uma vitória e uma derrota ou se há um empate, a quantidade de pontos ganha pelo dois competidores juntos é a mesma (1 ponto).
Além disso, podemos traduzir a condição de que "Cada jogador ganhou a mesma quantidade de pontos contra homens e contra mulheres", para: "a soma dos pontos ganhos pelas mulheres quando jogam contra as mulheres e a soma dos pontos ganhos pelas mulheres quando jogam contra os homens é a mesma". Porém, a condição fica interessante pelo fato de que, a soma dos pontos das mulheres contras as mulheres é exatamente o número de partidas entre mulheres, , vezes o números de pontos que vale cada partida (1 ponto), ou seja 
.
Desse modo, ganhamos que a soma dos pontos ganhos pelas mulheres jogando contra homens é .
Analogamente, fazendo o mesmo raciocínio para os homens, a soma dos pontos ganhos por homens jogando contra mulheres é . Porém, vamos lembrar que, confirma havíamos contado, a soma dos pontos ganhos nos jogos de mulheres contra homens é nm. Assim, temos que nm= +.
Assim, calculando os binomiais:
nm= (n-1).n/2 + (m-1)m/2
2nm = (n-1).n + (m-1)m
2nm=
-n+
-m
n+m=
Ou seja, a quantidade de participantes (n+m) é quadrado perfeito.
Nesse último problema a contagem dupla foi na quantidade de pontos oriundos das partidas entre homens e mulheres.
Problemas
Problema 1: Qual o número máximo de subconjuntos que podem escolhidos de um conjunto de 20 membros tão que:
(I) Todo subconjunto tem no mínimo um membro;
(II) Todo par de subconjuntos desse grupo tem no máximo dois membros em comum;
Problema 2: Temos n estudantes em uma determinada escola, e sabemos das seguintes afirmações:
(a) Todo estudante tem 10 ou 11 amigos;
(b) Escolhendo aleatoriamente dois estudantes, eles têm 5 amigos em comum;
Encontre todos os n que satisfaçam as condições.
Problema 3 (China 1993): Um grupo de dez pessoas foi para a livraria. Sabemos que:
(I) Todo mundo comprou exatamente 3 livros;
(II) Para qualquer par de pessoas, elas compraram pelo menos um livro em comum;
Qual o menor número de pessoas que pode ter comprado o livro que fora mais comprado?
Problema 4 (Russia 1996): Na assembleia legislativa da Russia, existem 1600 delegados, que forma 16000 comitês de 80 pessoas cada. Prove que é possível achar dois comitês que tem no mínimo quatro membros em comum.
Problema 5 (IMC 2002): Duzentos estudantes participaram de um prova de matemática. Eles têm seis problemas para resolver. Sabemos que cada problema foi resolvido corretamente por no mínimo 120 participantes. Prove que existem dois participantes tal que todos os problemas foram resolvidos por no mínimo um desses estudantes.
Problema 6 (Rússia 1990): Existem 30 senadores no senado. Para cada par de senadores, ou eles são ambos amigos um do outro ou ambos inimigos. Cada senador tem exatamente 6 inimigos. Sabendo que um comitê é formado por três senadores, ache o número total de comitês nos quais todos os membros são amigos uns dos outros ou todos os membros são inimigos uns dos outros.
Problema 7 (China TST 1992): 16 estudantes participaram de uma olimpíada de matemática na qual cada problema era de múltipla escolha com quatro opções. Depois do teste, foi descoberto que todo par de estudantes tinha ao menos uma resposta em comum. Determine o número máximo de questões.
Problema 8 (CMO 2006): Existem 2n+1 times em um torneio de matemática, no qual cada time joga contra com cada um dos outros times exatamente uma vez, sem empates. Nos dizemos que os times X, Y e Z são trigêmeos quando forma um ciclo trigêmeo: X ganha de Y, Y ganha de Z e Z ganha de X. Determine o número máximo possível de ciclos trigêmeos.
Problema 9 (USA TST 2005): Seja n um inteiro maior do que 1. Para um inteiro positivo m, seja Sm={1,2,3,4,...,mn}. Suponha que existe um conjunto T com 2n elementos tal que:
(I) Cada elemento de T é um subconjunto de m elementos de Sm;
(II) Cada par de elementos de T compartilha no máximo um elemento em comum;
(III) Cada elemento de Sm está contido em exatamente dois elementos de T;
Determine o máximo valor possível de m em função de n.
Referências
[1] Art of Problem Solving