De quantos modos podemos nos vestir? Quantos números menores que 1000 possuem todos os algarismos pares?
Contar coisas é algo tão antigo quanto a própria humanidade. Porém, ao longo do tempo as ideias evoluíram e novas técnicas surgiram. Existem várias formas de contar coisas, a mais simples delas é a contagem caso a caso. Este é o processo que mais usamos em nosso cotidiano. Mas, é uma forma primitiva de resolver os problemas.
Vamos aprender uma técnica mais prática pensando no seguinte exemplo:
Seção1.1.2Exemplos Resolvidos
Exemplo1.1.1.
Uma porta só é aberta quando usamos simultaneamente a chave e o cartão corretos. Se você possui duas chaves e três cartões, quantos testes devemos fazer para garantir que a porta irá abrir?
Podemos montar um diagrama para auxiliar na solução do problema. No diagrama, podemos ver todas as combinações possíveis de uma chave com um cartão. Assim, a solução é visual e igual a 6.
Figura1.1.2.
Por outro lado, poderíamos ter resolvido o problema da seguinte forma: Note que para cada escolha de chave existem três maneiras para escolher o cartão. Como temos duas chaves, o total de combinações é \(2 \times 3 = 6\text{.}\) Nesse caso, seriam necessários 6 testes para achar a combinação correta.
Assim, se houvesse 30 chaves e 5 cartões não seria necessário fazer um diagrama para contar as combinações uma por uma, o resultado seria simplesmente \(30 \times 5 = 150\text{.}\) O método que acabamos de usar é conhecido como princípio multiplicativo. Nos próximos problemas vamos usá-lo de uma forma mais geral.
Exemplo1.1.3.
Teddy possui 5 blusas, 3 calções e 2 pares de sapatos. De quantas maneiras diferentes ele pode se vestir?
Vamos primeiro contar o número de maneiras que Teddy pode escolher a blusa e a calça. Bem, para cada calça que Teddy escolhe, ele tem ainda cinco maneiras de escolher a blusa. Como ele possui três calças, o número total de modos de escolher o par (calça e blusa) é \(5 \times 3 = 15\text{.}\) Agora, para cada maneira de escolher esse par, ele ainda tem duas maneiras de escolher os sapatos. Daí, é fácil concluir que Teddy pode se vestir de \(5 \times 3 \times 2 = 30\) maneiras diferentes.
Exemplo1.1.4.
De quantos modos podemos pintar um tabuleiro \(1 \times 4\) usando apenas três cores, sem pintar casas vizinhas da mesma cor?
Podemos pintar a primeira casa de três maneiras diferentes, a segunda de duas maneiras (não podemos usar a cor da primeira casa), a terceira casa pode ser pintada de duas maneiras (não podemos usar a cor da segunda casa), o mesmo ocorre com a quarta casa. Assim, o total de maneiras de pintar o tabuleiro é \(3 \times 2 \times 2 \times 2 = 24\text{.}\)
Suponha que Carlos, Felipe, Marina e Ana estejam em uma fila. Se trocarmos a posição de alguns deles dizemos que fizemos uma permutação. A pergunta é: Quantas permutações podemos ter usando quatro pessoas?
Antes de resolver o problema vamos introduzir uma notação muito usada em problemas de contagem por simplificar algumas contas.
Definição1.1.5.Notação Fatorial.
Dado um número natural \(n\text{,}\) seja \(n!\) (leia \(n\) fatorial) o produto \(1 \cdot 2 \cdot 3 \cdots (n-1) \cdot n\text{.}\)
Observe que o conceito de fatorial está fortemente ligado à noção de permutação. Para fixar essa notação, resolva alguns exercícios simples:
Exemplo1.1.6.
Calcule \(4!\text{,}\)\(5!\) e \(6!\)
Calcule \(\frac{100!}{98!}\) e \(\frac{47!}{44!3!}\)
Podemos escolher o primeiro da fila de quatro maneiras, a segunda de três, a terceira de duas e a última de apenas uma maneira (a pessoa que sobrar). Desse modo temos \(4 \cdot 3 \cdot 2 \cdot 1 = 4!\) permutações.
Exemplo1.1.8.
(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?
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 de algarismos. O primeiro, que é formado pelos dois primeiros algarismos, 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); e 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{.}\)
Agora vamos nos preocupar com alguns problemas mais "clássicos". Apesar de serem problemas bem conhecidos por todos, vamos abordá-los aqui, pois empregam ideias que são constantemente usadas em vários problemas.
Exemplo1.1.9.Quantidade de Subconjuntos.
Quantos subconjuntos possui o conjunto \(M = \{1, 2, 3, ..., 10\}\text{?}\)
A cada subconjunto de \(M\) vamos associar uma sequência de 10 dígitos que podem ser 0 ou 1. Essa associação será dada através da seguinte regra: O primeiro termo dessa sequência será 1 se o elemento 1 estiver no subconjunto e 0 caso contrário; O segundo termo dessa sequência será 1 se o elemento 2 estiver no subconjunto e 0 caso contrário; O terceiro termo dessa sequência será 1 se o elemento 3 estiver no subconjunto e 0 caso contrário; e assim por diante.
Por exemplo, o subconjunto \(\{1, 2, 5, 8, 10\}\) está associado à sequência 1100100101, o subconjunto \(\{2, 3, 5, 8\}\) está associado à sequência 0110100100, enquanto o subconjunto vazio \(\emptyset\) é representado por 0000000000. Note que a quantidade de subconjuntos de \(M\) é igual à quantidade destas sequências. Por outro lado, podemos escolher cada dígito de duas formas e, consequentemente, temos \(2^{10}\) sequências (que é a mesma quantidade de subconjuntos).
Exemplo1.1.10.Quantidade de Divisores.
Seja \(n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}\) um número natural na sua forma fatorada. Então, \(n\) possui exatamente \((\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1)\) divisores inteiros positivos. Incluindo 1 e \(n\text{.}\)
Note que cada divisor positivo de \(n\) é da forma \(d = p_1^{\beta_1} \cdot p_2^{\beta_2} \cdots p_k^{\beta_k}\) onde cada expoente \(\beta_i\) é um número entre \(0\) e \(\alpha_i\) (inclusive). Dessa forma, temos \((\alpha_1 + 1)\) maneiras de escolher o expoente de \(p_1\text{;}\)\((\alpha_2 + 1)\) maneiras de escolher o expoente de \(p_2\text{;}\) e assim por diante. Logo, segue o resultado do princípio multiplicativo.
Exercícios1.1.3Problemas Propostos
1.
Cada casa de um tabuleiro \(2 \times 2\) pode ser pintado de verde ou amarelo. De quantas maneiras podemos pintar o tabuleiro todo?
O tabuleiro tem 4 casas ao todo e cada uma pode ser pintada de duas maneiras. O número de maneiras de pintar é \(2^4 = 16\text{.}\) (Obs.: Se considerarmos as rotações do tabuleiro a resposta é 4).
2.
(OBM 2004) De quantos modos diferentes podemos pintar (usando apenas uma cor) as casas de um tabuleiro \(4 \times 4\) de modo que cada linha e cada coluna possua exatamente uma casa pintada?
Para a primeira linha temos 4 casas disponíveis, na segunda linha só temos 3 já que não podemos ocupar a mesma coluna da casa pintada anteriormente. Para a 3ª linha temos 2 possibilidades e para a 4ª linha só há 1 possibilidade. Logo, a resposta é \(4! = 24\text{.}\)
3.
Quantos números naturais de três algarismos distintos existem?
Seja \(abc\) esse número. Então \(a\) pode ser 1, 2, ..., 9 e \(b\text{,}\)\(c\) podem ser 0, 1, ..., 9. Inicialmente escolhendo \(a\) temos 9 opções. Para \(b\) também temos 9 já que ele não pode ser igual a \(a\) mas pode ser 0. Para \(c\) temos 8 possibilidades. A resposta é \(9 \cdot 9 \cdot 8 = 648\text{.}\)
4.
De quantos modos podemos pôr três torres de três cores diferentes em um tabuleiro \(8 \times 8\) de modo que nenhuma delas ataque a outra?
Temos 64 maneiras de escolher a posição da primeira torre, 49 para a segunda e 36 para a terceira. Total de maneiras é \(64 \cdot 49 \cdot 36 = 112896\text{.}\)
5.
Uma embarcação deve ser tripulada por oito homens, dois dos quais só remam do lado direito e um apenas do lado esquerdo. Determine de quantos modos esta tripulação pode ser formada, se de cada lado deve haver quatro homens. Obs: A ordem dos homens deve ser considerada.
Do lado direito já estão definidos 2 homens e do lado esquerdo já está definido 1 homem. Sobraram 5 homens. Desses, devemos escolher 2 para o lado direito e o resto vai para o esquerdo. Temos \(\frac{5 \cdot 4}{2!} = \frac{5!}{3! \cdot 2!}\) maneiras de escolher esses homens sem se preocupar, por enquanto, com a ordem (dividimos por \(2!\) para retirar a ordenação). Uma vez definido quem vai ficar do lado direito e esquerdo, temos \(4!\) maneiras de permutá-los em cada lado. Portanto a resposta é \(\frac{5!}{3! \cdot 2!} \cdot 4! \cdot 4! = 5 \cdot 4 \cdot 4 \cdot 3 \cdot 4! = 5760\text{.}\)
6.
De quantas maneiras podemos ir de A até B sobre uma grade sem passar duas vezes pelo mesmo local e sem mover-se para a esquerda? A figura abaixo mostra um caminho possı́vel.
A formiga deve ir para a direita exatamente 5 vezes. Ao escolhermos esses movimentos, o resto do caminho estará bem definido. Como podemos escolher cada um destes cinco movimentos de seis maneiras, o total de caminhos será \(6 \cdot 6 \cdot 6 \cdot 6 \cdot 6 = 6^5\text{.}\)
7.
Ache a quantidade de números de quatro dígitos tais que toda sequência de três algarismos consecutivos é formada por elementos distintos.
Considere o número com representação decimal \(abcd\text{.}\) As únicas sequências de algarismos consecutivos são \((a, b, c)\) e \((b, c, d)\text{.}\) Como \(a\) não pode ser 0 temos para ele 9 possíveis valores. Para \(b\) temos também 9 possíveis valores, já que pode ser igual a 0 mas não a \(a\text{.}\) Para \(c\) temos 8 possíveis valores, pois não pode ser igual a \(b\) nem a \(a\text{.}\) Agora, \(d\) não pode ser igual nem a \(c\) nem a \(b\text{.}\) Portanto tem 8 possíveis valores. A quantidade de números é \(9 \cdot 9 \cdot 8 \cdot 8 = 5184\text{.}\)
8.
(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?
Vamos primeiramente escolher o vértice oposto à hipotenusa do triângulo. Temos 25 maneiras de fazer isso. Escolhido o primeiro vértice devemos escolher uma casa na mesma coluna e outra na mesma linha, determinando o triângulo. Podemos fazer isso de \(4 \times 4 = 16\) maneiras. Logo, o número de triângulos é \(25 \times 16 = 400\text{.}\)
9.
Dizemos que a palavra algoritmo é um anagrama da palavra logaritmo pois é uma permutação das letras de logaritmo. Sabendo disso, calcule a quantidade de anagramas da palavra vetor.
Imagine que o anagrama seja da forma \(ABCDE\text{,}\) então só podemos ter \(E\) igual a e ou o. Além disso, todas as letras são diferentes. Temos 2 escolhas para \(E\text{,}\) sobram 4 escolhas para \(D\text{,}\) 3 para \(C\text{,}\) 2 para \(B\) e \(A\) fica determinado. A resposta é \(2 \times 4! = 48\text{.}\)
11.
De quantas maneiras é possível colocar em uma prateleira 5 livros de matemática, 3 de física e 2 de biologia, de modo que livros de um mesmo assunto permaneçam juntos?
Considere os três blocos formados por livros da mesma matéria. Podemos organizar esses blocos de \(3!\) maneiras. Agora, em cada bloco ainda podemos permutar seus livros. Assim, o número correto de maneiras é \(5! \cdot 3! \cdot 2! \cdot 3!\text{.}\)
12.
Quantos anagramas da palavra vetor possuem as vogais separadas?
A palavra vetor possui \(5! = 120\) anagramas. Usando a mesma ideia do problema 19 (separar em blocos), podemos achar que a quantidade destes anagramas com vogais juntas é \(2 \times 4! = 48\text{.}\) Logo, temos \(120 - 48 = 72\) anagramas com as vogais separadas.
13.
De quantas formas podemos colocar 4 bolas verdes e 4 bolas amarelas em um tabuleiro \(4 \times 4\) de modo que cada coluna e cada linha possua exatamente uma bola de cada cor?
Existem \(4!\) maneiras de colocar as bolas verdes. Depois disso, escolha uma das bolas verdes. Ponha uma bola amarela na sua linha e uma na sua coluna. Note que, ao fazermos isto, as posições das outras duas bolas amarelas estarão bem definidas. Dessa maneira, temos um total de \(4! \cdot 3 \cdot 3 = 216\) configurações.
Veja que \(3600 = 2^4 \cdot 3^2 \cdot 5^2\text{.}\) Seus divisores são da forma \(2^a 3^b 5^c\text{,}\) onde \(a = 0,1,2,3,4\text{,}\)\(b = 0,1,2\) e \(c = 0,1,2\text{.}\) Logo, temos 5 valores para \(a\) e 3 para \(b\) e \(c\text{.}\) Portanto, o número de divisores deve ser \(5 \cdot 3 \cdot 3 = 45\text{.}\)
Para que um divisor seja par não pode ocorrer \(a = 0\text{.}\) O número de possibilidades para \(a\) se reduz a 4. O número de divisores pares é \(4 \cdot 3 \cdot 3 = 36\text{.}\)
Para que um divisor seja quadrado perfeito, \(a\text{,}\)\(b\) e \(c\) devem ser pares. Logo, só poderão assumir os valores \(\{0,2,4\}\) para \(a\) e \(\{0,2\}\) para \(b\) e \(c\text{.}\) O número de divisores satisfazendo isso é \(3 \cdot 2 \cdot 2 = 12\text{.}\)
15.
(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 janeiro 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.
Figura1.1.12. Se 0, 1, 2, 5 e 8 se refletem, 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.
Como não podemos usar os dígitos 3, 4, 6, 7, 9 para formar uma data, os únicos valores possíveis para os dois primeiros dígitos (os que marcam o dia) são: 01, 02, 05, 08, 10, 11, 12, 15, 18, 20, 21, 22, 25, 28. Para os dois próximos dígitos temos as seguintes possibilidades: 01, 02, 05, 08, 10, 11, 12. Por outro lado, 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\text{.}\)
16.
(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?
A quantidade de números elegantes deve ser menor ou igual ao número de soluções da inequação \(a^3 + b^2 \le 10^6\text{.}\) Note que \(0 \le a \le 10^2\) e \(0 \le b \le 10^3\text{.}\) O número de soluções é menor do que \((10^2 + 1)(10^3 + 1) = 101101 < 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. Isto é, existem mais números que não são elegantes.
17.
Quantos são os números de cinco dígitos que são múltiplos de 3 e possuem 6 como um de seus dígitos?
