Análise Combinatória – Princípio Fundamental da Contagem (PFC)

PRINCÍPIO ADITIVO

Considere a seguinte situação:

João interessou-se em assistir a 3 filmes e 2 peças de teatro que estão em cartaz, no entanto, só tem condições de custear um único evento. De quantas maneiras João poderá escolher um programa para fazer?

Resolução:

Se ele tem dinheiro para assistir apenas a um evento, então ou ele assiste ao Filme 1, ou ao Filme 2, ou ao Filme 3, ou à Peça 1, ou à Peça 2. Ao todo, serão cinco programas distintos.

O que nós acabamos de usar é um princípio muito importante nos métodos de contagem, chamado de Princípio Aditivo. De uma maneira geral, podemos enunciar o princípio aditivo da seguinte forma:

• Princípio aditivo: se A e B são dois conjuntos disjuntos (A ∩ B = ø) com, respectivamente, p e q elementos, então A ∪ B possui:

p + q elementos

No exemplo anterior podemos identificar os conjuntos:

• A = {x | x é um filme} = {F¹, F², F³}

• B = {y | y é uma peça de teatro} = {P¹, P²}

• A ∪ B = {z | tal que z é um filme ou uma peça}

PRINCÍPIO MULTIPLICATIVO

Considere a seguinte situação:

João interessou-se em assistir a 3 filmes e 2 peças de teatro que estão em cartaz, tendo condições de custear um filme e uma peça de teatro. De quantas maneiras João poderá fazer uma programação, escolhendo um filme e uma peça para assistir?

Resolução:

Vamos enumerar as possibilidades:

Filme 1 e Peça 1
Filme 1 e Peça 2
Filme 2 e Peça 1
Filme 2 e Peça 2
Filme 3 e Peça 1
Filme 3 e Peça 2

Portanto, João poderá escolher dentre 6 programas diferentes, se optar por assistir a um filme e a uma peça.

Note que, para cada filme escolhido, existem duas possibilidades de escolha para a peça de teatro. Como são três possibilidades de filme, temos um total de 3 · 2 = 6 maneiras de fazer uma programação.

O que nós acabamos de usar é um princípio muito importante nos métodos de contagem, chamado de Princípio Multiplicativo. De um modo geral, podemos enunciar o princípio multiplicativo da seguinte forma:

• Princípio multiplicativo: se um evento A pode ocorrer de m maneiras diferentes e, se, para cada uma dessas m
maneiras possíveis de A ocorrer, um outro evento B pode ocorrer de n maneiras diferentes, então o número de
maneiras de ocorrer o evento A seguido do evento B é m . n.

O PRINCÍPIO DA EXCLUSÃO

Considere o seguinte exemplo:

(UFRJ) Quantos números de 4 algarismos podemos formar nos quais o algarismo 2 aparece ao menos uma vez?

Resolução:

Resolver esse problema de forma direta seria muito trabalhoso. Pois pensar que o algarismo 2 deve aparecer pelo menos uma vez, significa que ele pode aparecer uma vez, duas vezes, três vezes ou quatro vezes. Logo teríamos que calcular todos esses casos, o que seria muito trabalhoso. Note que, se queremos que o algarismo 2 apareça pelo menos uma vez, a única situação que não queremos é o caso onde ele não aparece. E é trabalhando com essa ideia que resolveremos o problema de forma mais simples. Calcularemos o total de casos que existem e excluímos os casos que não nos interessam. Daí ficamos apenas com os casos que nos interessam. Primeiramente vamos calcular quantos números de 4 algarismos existem (com ou sem o algarismo 2).

9 . 10 . 10 . 10 = 9.000

Vamos agora calcular quantos números de 4 algarismos existem onde não aparece o algarismo 2.

8 . 9 . 9 . 9 = 5.832

Agora fazemos a diferença.

9.000 – 5.832 = 3.168

Logo, existem 3.168 números de quatro algarismos onde o algarismo 2 aparece pelo menos uma vez.

Esse método onde calculamos o total de casos possíveis e excluímos os casos que não nos interessa, é chamado de princípio da exclusão.

O PRINCÍPIO DAS GAVETAS DE DIRICHLET

Considere o seguinte exemplo:

Qual é o número mínimo de pessoas que devemos reunir para que tenhamos certeza de que entre elas há duas que fazem aniversário no mesmo mês?

Resolução:

A resposta é 13. Se houvesse apenas 12 pessoas, seria possível que cada uma delas fizesse aniversário em um mês diferente, já que o ano possui 12 meses. Com 13 pessoas, há, necessariamente, pelo menos um mês com mais de um aniversariante (se houvesse, no máximo, um aniversário por mês, o número de pessoas presentes seria, no máximo, 12).

O argumento empregado acima é conhecido como Princípio das Gavetas de Dirichlet ou Princípio das Casas do Pombos.

Um possível enunciado para este princípio é o seguinte:

Se n objetos forem colocados em, no máximo, (n – 1) gavetas, então pelo menos uma delas conterá, pelo menos, dois objetos.

EXERCÍCIO RESOLVIDO 

01. (ENEM) O código de barras, contido na maior parte dos produtos industrializados, consiste num conjunto de várias barras que podem estar preenchidas com cor escura ou não. Quando um leitor óptico passa sobre essas barras, a leitura de uma barra clara é convertida no número 0 e a de uma barra escura, no número 1. Observe a seguir um exemplo simplificado de um código em um sistema de código com 20 barras.

Se o leitor óptico for passado da esquerda para a direita irá ler: 01011010111010110001
Se o leitor óptico for passado da direita para a esquerda irá ler: 10001101011101011010

No sistema de código de barras, para se organizar o processo de leitura óptica de cada código, deve-se levar em consideração que alguns códigos podem ter leitura da esquerda para a direita igual à da direita para a esquerda, como o código 00000000111100000000, no sistema descrito acima.

Em um sistema de códigos que utilize apenas cinco barras, a quantidade de códigos com leitura da esquerda para a direita igual à da direita para a esquerda, desconsiderando-se todas as barras claras ou todas as escuras, é

a) 14.

b) 12.

c) 8.

d) 6.

e) 4.

Resolução.

A figura acima representa a resolução da questão, cujo gabarito é D.