Seção 1.2 Princípios Combinatórios
Subseção 1.2.1 Princípio Aditivo
Exemplo 1.2.1.
Suponha que na disciplina de análise combinatória existem três listas de exercício. A 1ª contém 15 exercícios, a 2ª contém 18 exercícios e a 3ª contém 14 exercícios. De quantas maneiras um estudante pode escolher um exercício para resolver?
SoluçãoO estudante têm 15 opções para escolher um exercício da primeira lista, 18 opções para escolher um exercício da segunda lista e 14 opções para escolher um exercício da terceira lista. Portanto o estudante têm
maneiras de escolher um exercício.
Definição 1.2.2.
(O Princípio Aditivo 1ª versão) Se uma tarefa puder ser feita de \(n_1\) maneiras e uma segunda tarefa de \(n_2\) maneiras e se essas tarefas não puderem ser feitas ao mesmo tempo; então, existem \(n_1+n_2\) maneiras de fazer ambas as tarefas.
Teorema 1.2.3.
(O Princípio Aditivo 2ª versão) Sejam \(A\) e \(B\) conjuntos finitos e disjuntos, então
Demonstração.
Sejam \(T_a\) e \(T_b\) as tarefas de escolher um elemento em \(A\) e em \(B\text{,}\) respectivamente. Existem \(\#A\) maneiras de escolher um elemento em \(A\) e \(\#B\) maneiras de escolher um elemento em \(B\text{.}\) Pelo Princípio Aditivo 1ª versão, como as tarefas não podem ser feitas ao mesmo tempo, o número de maneiras de escolher um elemento em cada um dos conjuntos é
Tecnologia 1.2.4.
Abaixo, clique em "Evaluate (Sage)" para obter a lista com todos os elementos da união dos conjuntos \(\{a, b, c\}\) e \(\{1, 2, 3, 4\}\text{.}\)
O comando set(['a', 'b', 'c']) transforma a lista ['a', 'b', 'c'] em conjunto, ou seja, mesmo se tiverem elementos repetidos na lista, o método set remove as repetições e retorna um conjunto. Assim é possível usar métodos específicos para conjuntos, como união, interseção, diferença e diferença simétrica.
Subseção 1.2.2 Princípio Multiplicativo
Exemplo 1.2.5.
Quantos números naturais de três algarismos distintos (na base 10) existem?
SoluçãoO procedimento de escolher um número satisfazendo estas hipóteses pode ser quebrado em três tarefas.
A 1ª tarefa é escolher o primeiro dígito, (da esquerda para a direita) que pode ser feito de 9 maneiras, já que o zero não pode ser escolhido.
A 2ª tarefa é escolher o segundo dígito, que pode ser feito de 9 maneiras, pois não pode ser igual a escolha do primeiro dígito.
A 3ª tarefa é escolher o terceiro dígito, que pode ser feito de 8 maneiras, pois não pode ser igual aos dois primeiros dígitos.
A resposta é
Definição 1.2.6.
(O Princípio Multiplicativo 1ª versão) Suponha que um procedimento pode ser quebrado em duas tarefas. Se existem \(n_1\) maneiras de executar a primeira tarefa e \(n_2\) maneiras de executar a segunda tarefa, depois que a primeira tarefa estiver executada, então existem \(n_1\times n_2\) maneiras de executar o procedimento.
Teorema 1.2.7.
(Princípio Multiplicativo 2ª versão) Sejam \(A\) e \(B\) conjuntos finitos; então,
Demonstração.
Note que a tarefa de escolher um elemento no produto cartesiano \(A\times B\) pode ser feita escolhendo um elemento em \(A\) e um elemento em \(B\text{,}\) do Princípio Multiplicativo 1ª versão temos
Tecnologia 1.2.8.
Abaixo, clique em "Evaluate (Sage)" para obter a lista com todos os elementos do produto cartesiano \(\{a, b, c\}\times\{1, 2, 3\}\text{.}\)
Exemplo 1.2.9.
A placa dos automóveis eram formadas por 3 letras (K, Y e W inclusive) seguidas por quatro algarismos. Quantas placas podiam ser formadas?
SoluçãoCada letra pode ser escolhida de 26 modos e cada algarismo de 10 modos distintos. A resposta é
Exemplo 1.2.10.
Sejam \(A\) e \(B\) dois conjuntos com \(\#A=m\) e \(\#B=n\text{.}\)
- Quantas são as funções \(f:A\rightarrow B\) ?
- Quantas são as funções injetoras \(f:A\rightarrow B\) ?
Solução 1. Devemos escolher a imagem de cada elemento de \(A\text{.}\) Existem \(n\) modos de escolher a imagem do "primeiro" elemento de \(A\text{,}\) \(n\) modos de escolher a imagem do "segundo" elemento de \(A\) \(\ldots\) até \(n\) modos de escolher a imagem do "m-ésimo" elemento de \(A\text{.}\) Pelo princípio multiplicativo, temos
2. Primeiramente, para existir solução precisamos que \(n\geq m\text{,}\) pois a função precisa ser injetora. Neste caso, existem \(n\) modos de escolher a imagem do "primeiro" elemento de \(A\text{,}\) \(n-1\) modos de escolher a imagem do "segundo" elemento de \(A\) \(\ldots\) até \(n-m+1\) modos de escolher a imagem do "m-ésimo" elemento de \(A\text{.}\) A resposta é
Exemplo 1.2.11.
Quantos são os números naturais pares que se escrevem (na base 10) com três algarismos distintos?
SoluçãoJá sabemos que o número total de números naturais com três algarismos distintos é
Podemos contar dentre estes, os que são ímpares, a diferença será a resposta deste problema.
O último algarismo pode ser escolhido de 5 maneiras (1, 3, 5, 7 ou 9). O primeiro algarismo pode ser escolhido de 8 maneiras (não pode ser o zero, nem o que foi escolhido para o último algarismo) e o segundo algarismo pode ser escolhido de 8 maneiras (nem pode ser igual ao primeiro nem ao último). Portanto a resposta é
Subseção 1.2.3 Princípio da Bijeção
O princípio da bijeção é uma ferramenta muito poderosa em análise combinatória. Utilizamos este princípio para contar, de maneira indireta, o número de elementos de um conjunto.
Teorema 1.2.12. (Princípio da Bijeção).
Dados dois conjuntos finitos \(A\) e \(B\) e uma função bijetiva \(f:A \to B\text{,}\) então \(\#A=\#B\text{.}\)
Demonstração.
Suponha que \(A=\{a_1,a_2,\ldots,a_n\}\text{.}\) Como \(f\) é injetiva, temos que \(f(a_i) \not = f(a_j)\text{,}\) se \(i\not= j\text{,}\) ou seja, existem pelo menos \(n\) elementos distintos em \(B\text{.}\) Em termos de cardinalidade, \(\#A\leq \#B\text{.}\)
Por outro lado, se \(f\) é uma função sobrejetiva, então \(\forall b_i \in B\) existe um \(a_i\in A\) tal que \(f(a_i)=b_i\text{,}\) ou seja, existem pelo menos \(n\) elementos distintos em \(A\text{,}\) isto é, \(\#B\leq \#A\text{.}\) Logo \(\#A=\#B\text{.}\)
Observação 1.2.13.
O Princípio da Bijeção é usado da seguinte forma: é comum em análise combinatória encontrarmos um problema cuja solução passa por determinar a cardinalidade de um certo conjunto, o qual denotaremos por \(A\text{,}\) mas que não sabemos como calcular. Porém, conseguimos mostrar que os elementos desse conjunto estão em bijeção como os elementos de um outro conjunto \(B\text{,}\) do qual obtemos êxito em calcular a cardinalidade com destreza. Assim, pelo princípio da bijeção, basta calcularmos a cardinalidade de \(B\text{.}\) Portanto, o princípio da bijeção é um método de transformar um problema em que temos dificuldade de responder, em outro que possui solução mais simples.
Exercícios 1.2.4 Exercícios
1.
Quantas palavras contendo 5 letras diferentes podem ser formadas com um alfabeto de 26 letras?
26×25×24×23×22=7893600
Para formar uma palavra, temos 26 opções para a primeira letra, 25 opções para a segunda letra, 24 opções para a terceira letra, 23 opções para a quarta letra e 22 opções para quinta e última letra. Pelo Princípio Multiplicativo a resposta é
2.
Quantos são os gabaritos possíveis de um teste de 25 questões de múltipla-escolha, com cinco alternativas por questão?
3.
Quantos divisores naturais possui o número 600?
\(4\times 2\times 3=24\)
A fatoração em primos de número 600 é \(2^3\times 3\times 5^2.\) Os divisores naturais de 600 são os números da forma:
Portanto, temos quatro opções para o valor de \(a\text{,}\) duas opções para o valor de \(b\) e três opções para o valor de \(c\text{.}\) Logo, a resposta é
4.
Em uma banca há 7 exemplares iguais da revista A, 4 exemplares iguais da revista B e 15 exemplares iguais da revista C. Quantas coleções não vazias de revistas dessa banca é possível formar?
\(8\times 5\times 16 - 1=639\)
Vamos inicialmente contar de forma que seja possível obter uma coleção vazia, no final, essa possibilidade será excluída do total para obtermos a resposta.
Como exitem 7 exemplares da revista A, podemos escolher de 0 até 7 exemplares para incluir na coleção, totalizando 8 possibilidades. Como existem 4 exemplares da revista B, podemos escolher de 0 até 4 exemplares para incluir na coleção, totalizando 5 possibilidades. Por último, como existem 15 exemplares da revista C, podemos escolher de 0 até 15 exemplares para incluir na coleção, totalizando 16 possibilidades.
A única maneira de escolher os exemplares, de modo que a coleção fique vazia é escolhendo 0 exemplares de cada revista. Portanto a resposta é
5.
Quantos números inteiros entre 1000 e 9999 são ímpares e possuem quatro dígitos distintos?
\(5\times 8\times 8\times 7 = 2240\)
Vamos começar escolhendo o dígito das unidades. O dígito das unidades pode ser qualquer um dos elementos do conjunto: \(\{1, 3, 5, 7, 9\}\text{,}\) ou seja, temos 5 opções. Agora, vamos escolher o primeiro dígito, da esquerda para a direita. O primeiro dígito nem pode ser igual ao dígito das unidades, nem pode ser zero, portanto, temos 8 opções para escolhe-lo. Para escolher o segundo dígito, temos 8 opções, pois ele nem pode ser igual ao primeiro dígito, nem igual ao último. Finalmente, para escolher o terceiro dígito temos 7 opções, pois 3 dígitos já foram escolhidos. Pelo princípio multiplicativo, a resposta é
6.
Um restaurante apresenta um cardápio popular, onde o cliente escolhe uma salada (dentre salada verde, salada russa ou salpicão), um prato principal (bife com fritas, peixe com purê, frango com legumes ou lasanha) e uma sobremesa (salada de frutas, pudim ou doce de leite). Quantas são as possíveis refeições?
7.
(UPE Seriado 2013 corrigido) Para efetuar saques, pagamentos, transferências e outras movimentações, os clientes do Banco Money precisam digitar uma senha numérica de sete dígitos que corresponde a uma senha formada por quatro algarismos e, em seguida, um código de acesso, também numérico, formado por três algarismos. Os clientes são orientados a não criar senhas iniciadas com zero nem códigos de acesso com algarismos repetidos, como no exemplo a seguir:
Dessa forma, quantas senhas numéricas distintas podem ser criadas pelos clientes do Banco Money?
a) 1,64 milhões b) 3,62 milhões c) 5,16 milhões d) 6,48 milhões e) 9,80 milhões
d)
O primeiro algarismo da Senha pode ser escolhido de 9 maneiras, o segundo, o terceiro e o quarto, podem ser escolhidos de 10 maneiras cada um.
O primeiro algarismo do Código de Acesso pode ser escolhido de 10 maneiras, o segundo de 9 maneiras e o terceiro de 8 maneiras. Portanto a resposta é:
8.
(PROFMAT 2015) De um baralho comum de 52 cartas são retiradas, em sequência e sem reposição, duas cartas. De quantos modos isso pode ser feito de maneira que a primeira carta seja de ouros e a segunda carta não seja uma dama? Informação: Um baralho de 52 cartas tem 4 naipes: copas, espadas, ouros e paus. Cada naipe possui 13 cartas: A(ás), 2, 3, 4, 5, 6, 7, 8, 9, 10, J(valete), Q(dama) e K(rei). Portanto há 4 reis, 4 damas, 4 valetes, 4 ases, etc.
a) 611 \(~~~\) b) 612 \(~~~\) c) 624 \(~~~\) d) 625 \(~~~\) e) 637
b)
Vamos separar em dois casos.
1º caso: a primeira carta é uma dama de ouros. Nesse caso, a primeira carta já está determinada. Para a segunda carta sobraram 51 opções, mas não queremos que ela seja uma dama, como ainda retam 3 damas o total de opções é \(51-3 = 48\text{.}\)
2º caso: a primeira carta não é uma dama de ouros. Nesse caso, temos 12 opções para a primeira carta, pois ela precisa ser de ouros, sem ser dama. Para a segunda carta sobraram 51 opções, mas não queremos que seja uma dama, o total de opções é \(51-4 = 47\text{.}\)
Pelos princípios aditivo e multiplicativo a resposta é
9.
(POTI - Nível 2)Escrevem-se todos os inteiros de \(1\) a \(9999\text{.}\) Quantos números têm pelo menos um zero?
\(2619\)
Vamos contar quantos não tem nenhum dı́gito zero e depois subtraimos este valor do total.
- De \(1\) a \(9\) temos \(9\) algarismos sem nenhum dı́gito \(0\text{.}\)
- De \(10\) a \(99\text{,}\) temos \(9 \times 9 = 81\) números sem nenhum zero.
- De \(100\) a \(999\) temos \(9 \times 9 \times 9 = 729\) números sem nenhum \(0\text{.}\)
- De \(1000\) a \(9999\) temos \(9^4 = 6561\) números sem nenhum zero.
Logo, entre \(1\) e \(9999\) temos \(9 + 81 + 729 + 6561 = 7380\) números sem nenhum zero. Portanto, há \(9999 - 7380 = 2619\) números com pelo menos um zero.
10.
(POTI - Nível 2)Quantos são os números de quatro algarismos que possuem pelo menos um dı́gito repetido?
11.
(POTI - Nível 2)Quantos são os números de quatro dı́gitos distintos que não possuem dois algarismos consecutivos com a mesma paridade?
\(720\)
Considere o número de representação decimal \(abcd\text{.}\) Então, inicialmente temos \(9\) opções para \(a\text{.}\) Escolhido \(a\text{,}\) sabemos que \(b\) deve ter paridade diferente e então tem \(5\) opções. O dı́gito \(c\) deve ter a mesma paridade que a e nao pode ser igual a ele, portanto só temos \(4\) opções para ele. Já o digito \(d\) deve ter a mesma paridade que \(c\) e deve ser diferente dele, portanto temos \(4\) opções para ele.
A quantidade total de números satisfazendo as condições do enunciado é \(9 \times 5 \times 4 \times 4 = 720\text{.}\)
12.
(POTI - Nível 2)De quantas maneiras podemos colocar um rei preto e um rei branco em um tabuleiro de xadrez \((8 \times 8)\) sem que nenhum deles ataque o outro?
\(3612\)
Podemos dividir o tabuleiro em três regiões: A primeira é formada pelas \(4\) casas nos cantos do tabuleiro; a segunda pelas \(24\) casas da borda (que não estão nos cantos); e a terceira pelo tabuleiro \(6 \times 6\) no interior do tabuleiro.
Se o primeiro rei for posto na primeira região, temos \(60\) maneiras de colocar o segundo rei; se ele for posto na segunda, temos \(58\) maneiras; e se for posto na terceira, temos \(55\) maneiras. Logo, temos um total de
modos diferentes de colocar os dois reis.
13.
(OBM 2004 - 2ª fase do nível 1)De quantos modos podemos sombrear quatro casas do tabuleiro \(4\times4\) de modo que em cada linha e em cada coluna exista uma única casa sombreada?
\(24\)
Para a primeira linha, temos 4 opções. Para a segunda linha, temos 3 opções, pois não podemos sombrear na mesma coluna que já foi sombrado na linha 1. Na terceira linha, temos 2 opções, e finalmente, na última linha temos apenas uma opções. A resposta é
14.
(OBM 2005)Num relógio digital, as horas são exibidas por meio de quatro algarismos. O relógio varia das 00:00 às 23:00 horas. Quantas vezes por dia os quatro algarismos mostrados são todos pares?
\(7\times 3 \times 5 = 105\text{.}\)
Neste problema existe uma restrição nos dı́gitos que marcam as horas e no primeiro dı́gito que marca os minutos.
Dessa forma, em vez de pensar em cada dı́gito separadamente, vamos pensar em três blocos. O primeiro, que é formado pelos dois primeiros dígitos, pode assumir 7 valores diferentes (00, 02, 04, 06, 08, 20 ou 22). O segundo é formado apenas pelo terceiro dı́gito e pode assumir 3 valores (0,2 ou 4). O último dı́gito pode assumir 5 valores (0,2,4,6 ou 8). Logo, o total de vezes em que todos aparecem pares é \(7 \times 3 \times 5 = 105\text{.}\)
15.
(OBM 2005)Num tabuleiro quadrado \(5 \times 5\text{,}\) serão colocados três botões idênticos, cada um no centro de uma casa, determinando um triângulo. De quantas maneiras podemos colocar os botões formando um triângulo retângulo com catetos paralelos às bordas do tabuleiro?
\(400\text{.}\)
Temos 25 maneiras de escolher a posição do vértice oposto a hipotenusa. Uma vez feita essa escolha, precisamos escolher uma posição na mesma coluna e outra posição na mesma linha, que o vértice oposto a hipotenusa, para colocar os outros vértices do triângulo retângulo. Portanto, o número total de maneiras é
16.
(Maio 2006)Um calendário digital exibe a data: dia, mês e ano, com 2 dı́gitos para o dia, 2 dı́gitos para o mês e 2 dı́gitos para o ano. Por exemplo, 01-01-01 corresponde a primeiro de janairo de 2001 e 25-05-23 corresponde a 25 de maio de 2023. Em frente ao calendário há um espelho. Os dı́gitos do calendário são como os da figura abaixo.
Se 0, 1, 2, 5 e 8 se reflentem, respectivamente, em 0, 1, 5, 2 e 8, e os outros dı́gitos perdem sentido ao se refletirem, determine quantos dias do século, ao se refletirem no espelho, correspondem também a uma data.
\(588\text{.}\)
Só podemos usar os dígitos: 0, 1, 2, 5 e 8. Os únicos valores possı́veis para os dois primeiros dı́gitos (os que marcam o dia e que o reflexo devem corresponder a um ano) são: 01, 02, 05, 08, 10, 11, 12, 15, 18, 20, 21, 22, 25, 28.
Para os dois dı́gitos do meio temos as seguintes possibilidades: 01, 02, 05, 08, 10, 11, 12. Porém, apenas os pares 01, 10 e 11 também correspondem a um mês quando são refletidos.
Para os dois últimos as possibilidades são: 10, 20, 50, 80, 01, 11, 21, 51, 81, 02, 12, 22, 52, 82. Pois seus reflexos devem corresponder a um dia. Logo, o total de datas pedidas é \(14 \times 3 \times 14 = 588.\)
17.
(Rússia)Um número natural n é dito elegante se pode ser escrito como soma de cubo com um quadrado (\(n = a^3 + b^2\text{,}\) onde \(a, b\in \mathbb{N}\)). Entre 1 e 1000000 existem mais números que são elegantes ou que não são?
Entre \(1\) e \(1000000\) existem mais números que não são elegantes.
A quantidade de números elegantes deve ser menor ou igual ao número de soluções da inequação \(a^3 + b^2 ≤ 10^6\text{.}\) Note que \(0\leq a \leq 10^2\) e \(0 \leq b \leq 10^3\text{.}\) Então, temos \((10^2 + 1)\) possibilidades para o valor de \(a\) e \((10^3 + 1)\) possibilidades para o valor de \(b\text{.}\) Portanto, analisando as possibilidades para \(a\) e \(b\) observamos que \((10^2 + 1)(10^3 + 1) = 101101 \lt 5 \cdot 10^5\text{.}\) Logo, a quantidade de números elegantes é menor do que a metade da quantidade de números entre \(1\) e \(1000000\text{.}\) Isto é, existem mais números que não são elegantes.
18.
(OBM 2005 - 2ª fase do nível 1)Lara tem cubos iguais e quer pintá-los de maneiras diferentes, utilizando as cores laranja ou azul para colorir cada uma de suas faces. Para que dois cubos não se confundam, não deve ser possível girar um deles de forma que fique idêntico ao outro. Por exemplo, há uma única maneira de pintar o cubo com uma face laranja e cinco azuis. Quantos cubos pintados de modos diferentes ela consegue obter?
\(10\)
Para 0 faces azuis e 6 laranjas, Lara só tem uma maneira de pintar os cubos.
Para 1 face azul e 5 laranjas, Lara só tem uma maneira de pintar os cubos.
Para 2 faces azuis e 4 laranjas, Lara tem duas maneiras de pintar os cubos, duas faces azuis opostas, ou duas adjacentes.
Para 3 faces azuis e 3 laranjas, Lara tem duas maneiras de pintar os cubos, três faces azuis com um vértice em comum, ou três faces azuis com uma aresta em comum, duas a duas.
Para 4 faces azuis e 2 laranjas, Lara tem duas maneiras de pintar os cubos, duas faces laranjas opostas, ou duas adjacentes.
Para 5 faces azuis e 1 laranja, Lara só tem uma maneira de pintar os cubos.
Para 6 faces azuis e 0 laranjas, Lara só tem uma maneira de pintar os cubos.
Pelo princípio aditivo, a resposta é
19.
(FUVEST 2015 - 2ª fase) Um “alfabeto minimalista” é constituído por apenas dois símbolos, representados por \(*\) e \(\#\text{.}\) Uma palavra de comprimento \(n, n \geq 1\text{,}\) é formada por \(n\) escolhas sucessivas de um desses dois símbolos. Por exemplo, \(\#\) é uma palavra de comprimento \(1\) e \(\#**\#\) é uma palavra de comprimento \(4\text{.}\) Usando esse alfabeto minimalista,
- quantas palavras de comprimento menor do que \(6\) podem ser formadas?
- qual é o menor valor de \(n\) para o qual é possível formar \(1.000.000\) de palavras de tamanho menor ou igual a \(n\text{?}\)
a) \(62~~~~\) b) \(19\text{.}\)
item a) O número de palavras de comprimento menor que 6 é
item b) Precisamos descobrir o menor valor de \(n\) para que
Usando a fórmula da soma da PG, temos
Como \(2^{18} = 262144\) e \(2^{19} = 524288\) concluímos que o menor valor de \(n\) é \(19\text{.}\)
20.
(OMU 2024 - Prova Individual - Item a) Andrês decidiu visitar um museu com \(n\) exposições. De quantas maneiras Andrês pode visitar uma quantidade ímpar de exposições?
\(2^{n-1}\)
Supondo que Andrês vai visitar uma quantidade ímpar de exposições, e que as exposições estão numeradas de \(1\) até \(n\text{.}\) Andrês pode decidir visitar as qualquer uma das \(n - 1\) primeiras exposições. Depois disso, se a quantidade de exposições visitadas foi um número par, Andrês precisa visitar a \(n\)-ésima exposição. Caso a quantidade se exposições visitadas foi um número ímpar, Andrês não pode visitar a \(n\) ésima exposição.
Portanto, o número ímpar de visitas nas \(n\) exposições está em bijeção com o número qualquer de visitas nas \(n-1\) primeiras exposições. Este número é \(2^{n-1}\text{.}\) Pois, em cada umas das \(n-1\) primeiras exposições, Andrês só precisa descidir se entra ou não.