05/06/2013
INSTITUTO DE APLICAÇÃO
FERNANDO RODRIGUES DA SILVEIRA
2ª SÉRIE DO ENSINO MÉDIO
Prof. Ilydio Pereira de Sá
www.magiadamatematica.com
MATEMÁTICA COMBINATÓRIA:
INTRODUÇÃO
Princípio Fundamental da Contagem
(PFC) ou Princípio Multiplicativo
O princípio fundamental da contagem diz
que se há x modos de tomar uma
decisão D1 e, tomada a decisão D1, há y
modos de tomar a decisão D2, então o
número
de
modos
de
tomar
sucessivamente ou simultaneamente as
decisões D1 e D2 é xy.
1
05/06/2013
Exemplo 1: Com 5 homens e 5 mulheres, de
quantos modos se pode formar um casal?
SOLUÇÃO: Formar um casal equivale a tomar
as decisões:
D1 : Escolha do homem (5 modos).
D2 : Escolha da mulher (5 modos).
Há 5 × 5 = 25 modos de formar um casal.
O princípio fundamental da contagem
pode ser generalizado para um número
qualquer de decisões, ou seja, se um
problema de contagem pode ser
subdividido
em
decisões
(etapas)
sucessivas ou consecutivas, o número de
possibilidades existentes para essas
escolhas será igual ao PRODUTO das
possibilidades
para
as
etapas
intermediárias.
Exemplo 2: Uma bandeira é formada por 7 listras
que devem ser coloridas usando-se apenas as
cores verde, azul e cinza. Se cada listra deve ter
apenas uma cor e não podem ser usadas cores
iguais em listras adjacentes, de quantos modos se
pode colorir a bandeira?
Solução: Colorir a bandeira equivale a escolher a
cor de cada listra. Há 3 modos de escolher a cor da
primeira listra e, a partir daí, 2 modos de escolher a
cor de cada uma das outras 6 listras. A resposta é
3 × 26 = 192 modos.
2
05/06/2013
Exemplo 3: Quantos são os números de três dígitos
distintos?
Solução: O primeiro dígito pode ser escolhido de 9
modos, pois não pode ser igual a 0. O segundo
dígito pode ser escolhido de 9 modos, pois não
pode ser igual ao primeiro dígito. O terceiro dígito
pode ser escolhido de 8 modos, pois não pode ser
igual nem ao primeiro nem ao segundo dígitos.
A resposta é 9 × 9 × 8 = 648 números.
Exemplo 4: Qual o número máximo de veículos
que podem ser emplacados no Brasil, com o atual
sistema de três letras e quatro algarismos?
Solução: Como o alfabeto utilizado tem 26 letras
e o nosso sistema de algarismos é decimal (10
símbolos), teremos:
263 x 104 = 175 760 000 veículos
Exemplo 5: Quantos divisores inteiros e positivos
possui o número 360?
Solução: 360 = 23 × 32 × 51. Os divisores inteiros e
positivos de 360 são os números da forma
2x × 3y × 5z, com x ∈ {0, 1, 2, 3} (4 possibilidades);
y ∈ {0, 1, 2} (3 possibilidades) e z ∈ {0, 1}
(2 possibilidades). Há 4 × 3 × 2 = 24 maneiras de
escolher os expoentes x, y e z. Há, portanto, 24
divisores positivos.
3
05/06/2013
IMPORTANTE !
Você já deve ter percebido nesses exemplos qual é a estratégia
para resolver problemas de Combinatória:
1) Postura: Devemos sempre nos colocar no papel da pessoa
que deve fazer a ação solicitada pelo problema e ver que
decisões devemos tomar. No Exemplo 3, nós nos colocamos
no papel da pessoa que deveria escrever o número de três
dígitos; no Exemplo 2, nós nos colocamos no papel da
pessoa que deveria colorir a bandeira; no Exemplo 1, nós nos
colocamos no papel da pessoa que deveria formar o casal.
2) Divisão: Devemos, sempre que possível, dividir as decisões
a serem tomadas em decisões mais simples. Formar um
casal foi dividido em escolher o homem e escolher a mulher;
colorir a bandeira foi dividido em colorir cada listra; etc.
Mas será que recaímos sempre em
multiplicação ? Ou existem outros casos?
Observe o próximo exemplo:
Usando as frutas Maçã (M), Banana (B), Abacaxi (A) e Pêra
(P), quantos tipos distintos de saladas de frutas, com três
dessas frutas, podem ser formadas?
Agora temos uma novidade, que não ocorria nos casos
anteriores. É que se escolhermos uma opção (B, A, M), por
exemplo, e mexermos nessa ordem (A, B, M), não teremos
uma salada de frutas diferente, será exatamente a mesma. A
ordem de escolha das frutas não influi no resultado final.
Como faremos nesses casos?
Vamos escrever todas as opções, como se fossem distintas
ao mudarmos a ordem das frutas:
A B M
A M B
B A M
B M A
M A B
M B A
A B P
A P B
B A
P
B P
A
P A
B
P B
A
A M P
A P M
M A
P
M P
A
P A
M
P M
A
B P M
B M P
P B M
P M B
M B P
M P B
A resposta do problema está representada em apenas um
dos grupos acima (4 tipos de saladas de frutas). Se
calculássemos como nos casos anteriores, teríamos um
total de 4 x 3 x 2 x 1 = 24 tipos (que estão representados
acima). Como a resposta se repetiu 6 vezes, é claro que o
resultado teve que ser dividido por 6. Por que será? Como
podemos generalizar esse fato?
4
05/06/2013
Vejamos um outro exemplo:
Uma famosa sorveteria anuncia 31 diferentes sabores de
sorvete. O número possível de casquinhas com três bolas
sem nenhuma repetição de sabor é, portanto, 31 x 30 x 29 =
26 970; qualquer um dos 31 sabores pode vir em cima,
qualquer um dos 30 restantes no meio, e qualquer um dos 29
que sobraram embaixo. Se não estamos interessados no
modo como os sabores são dispostos na casquinha, mas
simplesmente em quantas casquinhas com três sabores há,
teremos que dividir 26 970 por 6, obtendo então 4 495
casquinhas. Por que será que, novamente, dividimos por 6?
A razão por que dividimos por 6 é que há 6 = 3 x 2 x 1=3!
diferentes maneiras de dispor os sabores escolhidos numa
casquinha. Vamos supor que os sabores escolhidos seja:
morango-baunilha-chocolate.
Teríamos
as
seguintes
ordenações possíveis: MBC, MCB; BMC; BCM, CBM e CMB.
Uma vez que o mesmo se aplica a cada casquinha com três
sabores, o número dessas casquinhas é (31x30x29) / (3x2x1)
= 4 495 casquinhas com 3 sabores, escolhidos dentre os 31
oferecidos (sem importar a ordem de colocação desses 3
sabores na casquinha).
Um exemplo menos “engordativo” é fornecido pelas muitas
loterias existentes em nosso país. A mega-sena, por exemplo
cujo jogo mínimo consiste na escolha de 6 dezenas, dentre as
60 disponíveis. Caso a ordem de escolha dos números fosse
importante na escolha do apostador, teríamos 60 x 59 x 58 x
57 x 56 x 55 jogos distintos, com seis dezenas.
Mas como sabemos que a ordem de escolha desses números
não é importante, temos que dividir esse resultado por
6x5x4x3x2x1 = 720, já que qualquer uma das seqüências de
seis números pode ser decomposta em 720 outras apostas
iguais. Teremos, portanto 50 063 860 possibilidades de
escolha das 6 dezenas, dentre as 60 disponíveis na Megasena.
5
05/06/2013
Observe que a forma do número obtido é a mesma nesses 3
últimos exemplos:
• (4 x 3 x 2 x 1) / (3 x 2 x 1) diferentes tipos de salada de
frutas.
• (31 x 30 x 29) /(3 x 2 x1) diferentes casquinhas com três
sabores.
• (60 x 59 x 58 x 57 x 56 x 55) / (6 x 5 x 4 x 3 x 2 x 1)
maneiras de escolher seis números entre os sessenta da
mega-sena.
Números obtidos desta forma são chamados coeficientes
combinatórios ou combinações. Eles surgem quando
estamos interessados no número de maneiras de escolher R
elementos a partir de N elementos e não estamos
interessados na ordem em que os R elementos são
escolhidos.
Tente resolver:
Durante a Copa do Mundo, que foi disputada por 24
países, as tampinhas de Coca-Cola traziam sempre
palpites sobre os países que se classificariam nos três
primeiros lugares (por exemplo: 1º lugar, Brasil; 2º lugar,
Nigéria; 3º lugar, Holanda). Se, em cada tampinha, os
três países são distintos, quantas tampinhas diferentes
poderiam existir?
6
05/06/2013
SOLUÇÃO:
24 x 23 x 22 = 12 144 tampinhas distintas, já que a ordem
de colocação dos nomes dos países é importante (define a
sua classificação na copa)
Outra para você tentar resolver
2) Quantos são os triângulos que podem ser construídos a
partir de 10 pontos marcados sobre uma circunferência?
A
B
C
SOLUÇÃO:
Neste caso, a ordem de disposição dos elementos de cada
coleção não importa ao problema, isto é, o triângulo ABC é o
mesmo do triângulo ACB, por exemplo. Logo, como na
questão da Mega-Sena, teremos que a quantidade de
triângulos será dada por:
DESAFIO
(OBMEP – 2009) Com exatamente dois segmentos de
reta, podemos fazer figuras diferentes unindo os vértices
de um pentágono. Cinco dessas figuras estão ilustradas a
seguir.
Incluindo essas cinco, quantas figuras diferentes podemos
fazer desse modo?
7
05/06/2013
SOLUÇÃO
Percebemos que essas figuras são sempre formadas
pelos dois segmentos, escolhidos entre os lados e as
diagonais de um pentágono. Como o pentágono possui 5
lados e 5 diagonais, são 10 os segmentos disponíveis para
a escolha dos 2 que formarão a figura.
Podemos usar o princípio multiplicativo, lembrando que
esse é um daqueles casos mostrados anteriormente, que
envolvem multiplicação e divisão, pois a figura formada
pelos segmentos AB e CD será a mesma formada pelos
segmentos CD e AB, ou seja a ORDEM desses segmentos
não influi na figura resultante, logo, teremos:
10. 9
= 45figuras
2. 1
8