Instituto de Física
Universidade Federal Fluminense

Problemas de contagem sempre fascinam, tanto pela simplicidade com que podem ser enunciados quanto pela engenhosidade para resolvê-los. Em particular, exigem cuidado em contar corretamente. Nesta coluna, discutimos importante ‘estratégia’ nessa arte

Problemas de contagem são fascinantes, por serem tão simples de propor e, ao mesmo tempo… potencialmente difíceis de resolver, exigindo boa dose de criatividade. Além disso, frequentemente, são apresentados na forma de historinhas, do tipo: ‘João tem cinco camisas e três calças; de quantas maneiras…’ ou ‘em uma urna, temos bolinhas azuis, brancas e verdes; de quantos modos…’, o que dá a eles uma ‘concretude’ atraente.

Todo problema de contagem exige cuidado em não deixarmos algum elemento de fora e nem contarmos um elemento mais de uma vez. Por exemplo, se, em uma turma, contamos quantos estudantes gostam de maçã e quantos não gostam dessa fruta, a soma dos dois números tem que ser o total de estudantes da turma.

Mas, se perguntarmos quantos gostam de maçã e quantos gostam de banana… Pode ser que: i) deixemos de contar algum aluno que não gosta de nenhuma das duas frutas; ii) contemos estudantes que gostam das duas frutas mais de uma vez.

O chamado princípio da inclusão e exclusão é útil nessas situações. Vejamos um  exemplo. Quantos são os múltiplos de 2 ou 3 entre 1 e 100? Uma estratégia é, simplesmente, contar ‘na mão’ quantos são esses números. Mas isso pode ficar complicado rapidamente; podemos pular algum número, contar outro mais de uma vez…

Outra maneira é contar quantos são os múltiplos de 2 nesse intervalo: 2 x 1; 2 x 2; … 2 x 50, ou seja, temos 50 múltiplos de 2 entre 1 e 100. Podemos encontrar os múltiplos de 3 da mesma maneira: 3 x 1; 3 x 2; … 3 x 33. Total: 33 múltiplos.

Então, temos 50 + 33 = 83 múltiplos de 2 ou 3? Parece muito, não?

Aqui, aparece o problema da múltipla contagem: há números que são múltiplos de  2 e 3 (por exemplo, 6). Esses números foram contados duas vezes. Como corrigir essa redundância na contagem?

Pensemos assim: os múltiplos de 2 podem ser separados em dois conjuntos: {múltiplos de 2 que não são múltiplos de 3} e {múltiplos de 2 que são múltiplos de 3}. O mesmo pode ser feito para os múltiplos de 3: {múltiplos de 3 que não são múltiplos de 2} e {múltiplos de 3 que são múltiplos de 2}.

Vemos que, ao somar o número de múltiplos de 2 com o número de múltiplos de 3, o conjunto de múltiplos de 2 e 3 foi contado duas vezes. E quem são os múltiplos de 2 e 3? Justamente os… múltiplos de 6, pois, se um número é múltiplo de 2 e 3, então, é múltiplo de 2 x 3 = 6.

Entre 1 e 100, os múltiplos de 6 são 6 x 1; 6 x 2; … 6 x 16. Total: 16 números.

Portanto, o número de múltiplos de 2 ou 3 entre 1 e 100 é o seguinte: 50 (múltiplos de dois) + 33 (múltiplos de 3) – 16 (múltiplos de 2 e 3) = 67. Como, na primeira soma, incluímos os múltiplos de 2 ou 3 e na subtração excluímos os múltiplos de 2 e 3, fica explicado por que nosso princípio é chamado ‘inclusão e exclusão’.

Esse é um princípio útil que pode ser aplicado em vários problemas. O(a) leitor(a) ficou animado(a)? Que tal um desafio?

Quantos são os múltiplos de 2 ou 3 ou 5 entre 1 e 100? Dica: faça um ‘diagrama de Venn’ – aquele que usamos para representar conjuntos graficamente – para ajudar a entender quais números devem ser incluídos (somados) e excluídos (subtraídos).

Solução do desafio anterior

Usando o mesmo raciocínio que no caso de três sapos e três rãs, cada um dos M sapos terá que avançar N + 1 casas, e cada uma das N rãs terá que avançar M + 1 casas. Portanto, são M(N + 1) + N(M + 1) = 2MN + M + N avanços. Cada ‘deslizada’ é um avanço de uma casa; e cada pulo, um avanço de duas casas. Como teremos MN pulos, que correspondem a avanços de duas casas, executaremos MN pulos e M + N deslizadas, totalizando, entre pulos e deslizadas, MN + M + N movimentos.

Outros conteúdos desta edição

725_480 att-76180
725_480 att-76091
725_480 att-76062
725_480 att-76000
725_480 att-76274
725_480 att-76014
725_480 att-75781
725_480 att-75970
725_480 att-76204
725_480 att-76480
725_480 att-75887
725_480 att-74188
725_480 att-76056
725_480 att-76516
614_256 att-76019

Outros conteúdos nesta categoria

725_480 att-91223
725_480 att-90720
725_480 att-90114
725_480 att-89242
725_480 att-88475
725_480 att-88214
725_480 att-87646
725_480 att-87202
725_480 att-86475
725_480 att-86019
725_480 att-85747
614_256 att-85214
725_480 att-84801
725_480 att-84371
725_480 att-83992