MATEMÁTICA DISCRETA
COMBINATÓRIA (4/4)
Carlos Luz
EST Setúbal / IPS
25 – 31 Março 2012
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
1/8
Princípio da Distribuição
O princípio da distribuição (de Dirichelet) (conhecido por
pigeonhole principle ou princípio da gaiola dos pombos numa
tradução livre), segue uma …loso…a diferente dos príncipios de
contagem examinados nas secções anteriores.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
2/8
Princípio da Distribuição
O princípio da distribuição (de Dirichelet) (conhecido por
pigeonhole principle ou princípio da gaiola dos pombos numa
tradução livre), segue uma …loso…a diferente dos príncipios de
contagem examinados nas secções anteriores.
Enquanto que estes últimos permitem contar precisamente o número
de objectos que satisfazem determinadas condições, o princípio da
distribuição permite deduzir a existência de um determinado tipo de
objectos com uma certa propriedade.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
2/8
Princípio da Distribuição
O princípio da distribuição (de Dirichelet) (conhecido por
pigeonhole principle ou princípio da gaiola dos pombos numa
tradução livre), segue uma …loso…a diferente dos príncipios de
contagem examinados nas secções anteriores.
Enquanto que estes últimos permitem contar precisamente o número
de objectos que satisfazem determinadas condições, o princípio da
distribuição permite deduzir a existência de um determinado tipo de
objectos com uma certa propriedade.
Por exemplo, suponhamos que dispomos de 3 pombos para distribuir
por duas gaiolas A e B. Os pombos podem ser distribuídos de acordo
com uma das seguintes formas: 3 na gaiola A e 0 na gaiola B, 2 em A
e 1 em B, 1 em A e 2 em B, ou 0 em A e 3 em B. Observe-se que, em
qualquer caso, uma das gaiolas A ou B conterá pelo menos 2 pombos.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
2/8
Princípio da Distribuição
O princípio da distribuição (de Dirichelet) (conhecido por
pigeonhole principle ou princípio da gaiola dos pombos numa
tradução livre), segue uma …loso…a diferente dos príncipios de
contagem examinados nas secções anteriores.
Enquanto que estes últimos permitem contar precisamente o número
de objectos que satisfazem determinadas condições, o princípio da
distribuição permite deduzir a existência de um determinado tipo de
objectos com uma certa propriedade.
Por exemplo, suponhamos que dispomos de 3 pombos para distribuir
por duas gaiolas A e B. Os pombos podem ser distribuídos de acordo
com uma das seguintes formas: 3 na gaiola A e 0 na gaiola B, 2 em A
e 1 em B, 1 em A e 2 em B, ou 0 em A e 3 em B. Observe-se que, em
qualquer caso, uma das gaiolas A ou B conterá pelo menos 2 pombos.
Esta conclusão poderia ter sido obtida imediatamente por aplicação
da chamada forma fraca do princípio da distribuição.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
2/8
Teorema (Princípio da Distribuição – forma fraca)
Sejam m e n números naturais. Se m n + 1 objectos são distribuídos
por n caixas, então uma das caixas terá pelo menos dois objectos.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
3/8
Teorema (Princípio da Distribuição – forma fraca)
Sejam m e n números naturais. Se m n + 1 objectos são distribuídos
por n caixas, então uma das caixas terá pelo menos dois objectos.
Demonstração
Suponhamos por absurdo que nenhuma das n caixas contém mais do que
1 objecto. Então cada caixa conterá quando muito 1 objecto, pelo que o
número total de objectos nas n caixas é igual a n. Mas isto é absurdo, pois
foram distribuídos m n + 1 objectos pelas n caixas.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
3/8
Teorema (Princípio da Distribuição – forma fraca)
Sejam m e n números naturais. Se m n + 1 objectos são distribuídos
por n caixas, então uma das caixas terá pelo menos dois objectos.
Demonstração
Suponhamos por absurdo que nenhuma das n caixas contém mais do que
1 objecto. Então cada caixa conterá quando muito 1 objecto, pelo que o
número total de objectos nas n caixas é igual a n. Mas isto é absurdo, pois
foram distribuídos m n + 1 objectos pelas n caixas.
Observação
Uma demonstração alternativa do princípio da distribuição na forma fraca
é a seguinte: seja f : Nm ! Nn a função que associa a cada objecto a
caixa correspondente; atendendo ao teorema 2.1, f não pode ser injectiva
pois m > n; logo, existem objectos distintos x e y tais que f (x ) = f (y ),
isto é, pelo menos dois objectos estão na mesma caixa.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
3/8
Exemplo
Suponha-se que numa gaveta estão 10 meias pretas e 12 meias azuis. Se
uma meia for retirada de cada vez, sem reposição, quantas terão que ser
retiradas para garantir um par da mesma cor?
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
4/8
Exemplo
Suponha-se que numa gaveta estão 10 meias pretas e 12 meias azuis. Se
uma meia for retirada de cada vez, sem reposição, quantas terão que ser
retiradas para garantir um par da mesma cor?
Resolução: Podemos imaginar que as meias retiradas são “objectos” a distribuir
por 2 “caixas”, correspondentes respectivamente às cores “preto” e “azul”.
Então, pelo princípio da distribuição, para garantir duas meias da mesma cor (ou
equivalentemente, uma caixa com 2 objectos) basta efectuar a distribuição de no
mínimo 3 meias pelas 2 caixas (isto é, basta retirar da gaveta 3 meias).
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
4/8
Exemplo
Suponha-se que numa gaveta estão 10 meias pretas e 12 meias azuis. Se
uma meia for retirada de cada vez, sem reposição, quantas terão que ser
retiradas para garantir um par da mesma cor?
Resolução: Podemos imaginar que as meias retiradas são “objectos” a distribuir
por 2 “caixas”, correspondentes respectivamente às cores “preto” e “azul”.
Então, pelo princípio da distribuição, para garantir duas meias da mesma cor (ou
equivalentemente, uma caixa com 2 objectos) basta efectuar a distribuição de no
mínimo 3 meias pelas 2 caixas (isto é, basta retirar da gaveta 3 meias).
Exemplo
Nas mesmas condições do problema anterior, quantas terão que ser
retiradas para garantir um par azul?
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
4/8
Exemplo
Suponha-se que numa gaveta estão 10 meias pretas e 12 meias azuis. Se
uma meia for retirada de cada vez, sem reposição, quantas terão que ser
retiradas para garantir um par da mesma cor?
Resolução: Podemos imaginar que as meias retiradas são “objectos” a distribuir
por 2 “caixas”, correspondentes respectivamente às cores “preto” e “azul”.
Então, pelo princípio da distribuição, para garantir duas meias da mesma cor (ou
equivalentemente, uma caixa com 2 objectos) basta efectuar a distribuição de no
mínimo 3 meias pelas 2 caixas (isto é, basta retirar da gaveta 3 meias).
Exemplo
Nas mesmas condições do problema anterior, quantas terão que ser
retiradas para garantir um par azul?
Resolução: No pior caso, os elementos da caixa que não corresponde à cor
pretendida são seleccionados primeiro. Assim, sendo retiradas primeiro as 10
meias pretas, …ca garantido pelo princípio da distribuição que no …nal das duas
tiragens seguintes existirá um par azul na respectiva caixa. À 12a tiragem …ca
pois garantido um par de meias azul.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
4/8
Exemplo
Mostrar que, dados quaisquer quatro números inteiros, existem dois deles
cuja diferença é divisível por 3.
Resolução: Vamos tomar para “objectos” os 4 inteiros e consideramos as
seguintes 3 “caixas”: a caixa 0 para os inteiros divisíveis por 3, a caixa 1 para os
inteiros que divididos por 3 dão resto 1 e a caixa 2 para os inteiros que divididos
por 3 dão resto 2. Pelo princípio da distribuição, ao efectuar a distribuição dos 4
inteiros pelas três caixas, obtém-se uma caixa com dois inteiros. Se os dois
inteiros estão na caixa i , com 0
i 2, podemos representá-los por 3x + i e
3y + i, onde x e y são inteiros. Então, 3 divide a diferença dos dois inteiros pois
esta é igual a (3x + i ) (3y + i ) = 3(x y ).
Caixa 0
Carlos Luz (EST Setúbal / IPS)
Caixa 1
Caixa 2
Combinatória (4/4)
25 – 31 Março 2012
5/8
Exemplo (“teorema da festa”)
Mostrar que numa festa com n 2 pessoas, existem pelo menos duas que
têm o mesmo número de conhecidos na festa.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
6/8
Exemplo (“teorema da festa”)
Mostrar que numa festa com n 2 pessoas, existem pelo menos duas que
têm o mesmo número de conhecidos na festa.
Resolução:
Seja f a função que associa a cada uma das pessoas o número de
conhecidos presentes na festa; então 0
f (x ) n 1, para qualquer
x 2 Nn , pelo que f (Nn ) f0, . . . , n 1g .
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
6/8
Exemplo (“teorema da festa”)
Mostrar que numa festa com n 2 pessoas, existem pelo menos duas que
têm o mesmo número de conhecidos na festa.
Resolução:
Seja f a função que associa a cada uma das pessoas o número de
conhecidos presentes na festa; então 0
f (x ) n 1, para qualquer
x 2 Nn , pelo que f (Nn ) f0, . . . , n 1g .
Ora, dados dois quaisquer convidados diferentes x e y , não se pode ter
f (x ) = 0 e f (y ) = n 1 pois neste caso x não conheceria ninguém e y
conheceria toda a gente, incluindo x .
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
6/8
Exemplo (“teorema da festa”)
Mostrar que numa festa com n 2 pessoas, existem pelo menos duas que
têm o mesmo número de conhecidos na festa.
Resolução:
Seja f a função que associa a cada uma das pessoas o número de
conhecidos presentes na festa; então 0
f (x ) n 1, para qualquer
x 2 Nn , pelo que f (Nn ) f0, . . . , n 1g .
Ora, dados dois quaisquer convidados diferentes x e y , não se pode ter
f (x ) = 0 e f (y ) = n 1 pois neste caso x não conheceria ninguém e y
conheceria toda a gente, incluindo x .
Assim, f (Nn ) é um subconjunto de f0, . . . , n 1g com, no máximo,
n 1 elementos.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
6/8
Exemplo (“teorema da festa”)
Mostrar que numa festa com n 2 pessoas, existem pelo menos duas que
têm o mesmo número de conhecidos na festa.
Resolução:
Seja f a função que associa a cada uma das pessoas o número de
conhecidos presentes na festa; então 0
f (x ) n 1, para qualquer
x 2 Nn , pelo que f (Nn ) f0, . . . , n 1g .
Ora, dados dois quaisquer convidados diferentes x e y , não se pode ter
f (x ) = 0 e f (y ) = n 1 pois neste caso x não conheceria ninguém e y
conheceria toda a gente, incluindo x .
Assim, f (Nn ) é um subconjunto de f0, . . . , n 1g com, no máximo,
n 1 elementos.
Podemos agora pensar na distribuição dos n “objectos”
f (1), f (2), . . . , f (n) pelas n 1 “caixas”, cada uma delas correspondente
a um elemento de f (Nn ).
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
6/8
Exemplo (“teorema da festa”)
Mostrar que numa festa com n 2 pessoas, existem pelo menos duas que
têm o mesmo número de conhecidos na festa.
Resolução:
Seja f a função que associa a cada uma das pessoas o número de
conhecidos presentes na festa; então 0
f (x ) n 1, para qualquer
x 2 Nn , pelo que f (Nn ) f0, . . . , n 1g .
Ora, dados dois quaisquer convidados diferentes x e y , não se pode ter
f (x ) = 0 e f (y ) = n 1 pois neste caso x não conheceria ninguém e y
conheceria toda a gente, incluindo x .
Assim, f (Nn ) é um subconjunto de f0, . . . , n 1g com, no máximo,
n 1 elementos.
Podemos agora pensar na distribuição dos n “objectos”
f (1), f (2), . . . , f (n) pelas n 1 “caixas”, cada uma delas correspondente
a um elemento de f (Nn ).
Pelo princípio da distribuição, dois daqueles objectos, digamos f (i ) e f (j ),
estarão na mesma caixa sendo portanto iguais. Isto é, f (i ) = f (j ), pelo
que os convidados i e j têm o mesmo número de conhecidos na festa.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
6/8
Teorema (Princípio da Distribuição – forma forte)
Sejam m, n e k números naturais. Se m nk + 1 objectos são
distribuídos por n caixas, uma das caixas terá pelo menos k + 1 objectos.
A desigualdade não pode ser enfraquecida.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
7/8
Teorema (Princípio da Distribuição – forma forte)
Sejam m, n e k números naturais. Se m nk + 1 objectos são
distribuídos por n caixas, uma das caixas terá pelo menos k + 1 objectos.
A desigualdade não pode ser enfraquecida.
Demonstração
Suponha-se que existem, no máximo, k objectos em cada caixa; então
existem no máximo nk objectos no total, o que contraria a hipótese de
terem sido distribuídos m nk + 1 objectos pelas n caixas. Por outro
lado, dados m objectos tais que m nk, é sempre possível distribuí-los
por n caixas, cada uma com k objectos no máximo; isto mostra que a
desigualdade não pode ser enfraquecida.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
7/8
Teorema (Princípio da Distribuição – forma forte)
Sejam m, n e k números naturais. Se m nk + 1 objectos são
distribuídos por n caixas, uma das caixas terá pelo menos k + 1 objectos.
A desigualdade não pode ser enfraquecida.
Demonstração
Suponha-se que existem, no máximo, k objectos em cada caixa; então
existem no máximo nk objectos no total, o que contraria a hipótese de
terem sido distribuídos m nk + 1 objectos pelas n caixas. Por outro
lado, dados m objectos tais que m nk, é sempre possível distribuí-los
por n caixas, cada uma com k objectos no máximo; isto mostra que a
desigualdade não pode ser enfraquecida.
Observação
A forma fraca do princípio é implicada pela forma forte pois, dados m
objectos e n caixas, se m n + 1, considerando k = 1, tem-se
m n k + 1, donde, pela forma forte, uma das caixas terá pelo menos
k + 1 = 2 objectos.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
7/8
Problema
Dado um baralho com 52 cartas, retirando, sem reposição, uma carta de
cada vez, quantas é necessário retirar para garantir que se tenham três
cartas do mesmo naipe?
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
8/8
Problema
Dado um baralho com 52 cartas, retirando, sem reposição, uma carta de
cada vez, quantas é necessário retirar para garantir que se tenham três
cartas do mesmo naipe?
Resolução: Tratemos as cartas como “objectos” e consideremos que, ao serem
retiradas do baralho, as cartas são distribuídas por n = 4 “caixas”, cada uma
correspondendo a cada naipe. A forma forte garante então que uma das caixas
terá pelo menos k + 1 = 3 objectos (isto é, 3 cartas do mesmo naipe) desde que
sejam retiradas do baralho m
nk + 1 = 4 2 + 1 = 9 cartas.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
8/8
Problema
Dado um baralho com 52 cartas, retirando, sem reposição, uma carta de
cada vez, quantas é necessário retirar para garantir que se tenham três
cartas do mesmo naipe?
Resolução: Tratemos as cartas como “objectos” e consideremos que, ao serem
retiradas do baralho, as cartas são distribuídas por n = 4 “caixas”, cada uma
correspondendo a cada naipe. A forma forte garante então que uma das caixas
terá pelo menos k + 1 = 3 objectos (isto é, 3 cartas do mesmo naipe) desde que
sejam retiradas do baralho m
nk + 1 = 4 2 + 1 = 9 cartas.
Exemplo
Qual o número mínimo de empregados que uma empresa deve ter para
assegurar que haja três empregados que fazem anos no mesmo dia?
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
8/8
Problema
Dado um baralho com 52 cartas, retirando, sem reposição, uma carta de
cada vez, quantas é necessário retirar para garantir que se tenham três
cartas do mesmo naipe?
Resolução: Tratemos as cartas como “objectos” e consideremos que, ao serem
retiradas do baralho, as cartas são distribuídas por n = 4 “caixas”, cada uma
correspondendo a cada naipe. A forma forte garante então que uma das caixas
terá pelo menos k + 1 = 3 objectos (isto é, 3 cartas do mesmo naipe) desde que
sejam retiradas do baralho m
nk + 1 = 4 2 + 1 = 9 cartas.
Exemplo
Qual o número mínimo de empregados que uma empresa deve ter para
assegurar que haja três empregados que fazem anos no mesmo dia?
Resolução: Teremos de distribuir m empregados por n = 365 dias de maneira
que um dos dias tenha pelo menos k + 1 = 3 empregados. Pela forma forte do
princípio da distribuição, a ocorrência desta situação …ca garantida desde que
m nk + 1 = 365 2 + 1 = 731, isto é, se a empresa tiver no mínimo 731
empregados.
Carlos Luz (EST Setúbal / IPS)
Combinatória (4/4)
25 – 31 Março 2012
8/8