Quantos são os números naturais pares que se escrevem (na base10) com três algarismos distintos?

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?

O 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

\begin{equation*} 15+18+14 = 47 \end{equation*}

maneiras de escolher um exercício.

(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.

(O Princípio Aditivo 2ª versão) Sejam \(A\) e \(B\) conjuntos finitos e disjuntos, então

\begin{equation*} \#(A\cup B)=\#A+ \#B \end{equation*}

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 é

\begin{equation*} \#(A\cup B)=\#A+ \#B. \end{equation*}

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{.}\)

Quantos números naturais de três algarismos distintos (na base 10) existem?

O procedimento de escolher um número satisfazendo estas hipóteses pode ser quebrado em três tarefas.

1. 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.

2. 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.

3. 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 é

\begin{equation*} 9\times 9\times 8 = 648\text{.} \end{equation*}

(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.

(Princípio Multiplicativo 2ª versão) Sejam \(A\) e \(B\) conjuntos finitos; então,

\begin{equation*} \#(A\times B) = \#A\times \#B. \end{equation*}

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

\begin{equation*} \#(A\times B) = \#A\times \#B. \end{equation*}

Abaixo, clique em "Evaluate (Sage)" para obter a lista com todos os elementos do produto cartesiano \(\{a, b, c\}\times\{1, 2, 3\}\text{.}\)

A placa dos automóveis eram formadas por 3 letras (K, Y e W inclusive) seguidas por quatro algarismos. Quantas placas podiam ser formadas?

Cada letra pode ser escolhida de 26 modos e cada algarismo de 10 modos distintos. A resposta é

\begin{equation*} 26\times26\times26\times 10\times10\times10\times10 = 26^3\times10^4 = 175760000. \end{equation*}

Sejam \(A\) e \(B\) dois conjuntos com \(\#A=m\) e \(\#B=n\text{.}\)

1. Quantas são as funções \(f:A\rightarrow B?\)
2. 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

\begin{equation*} \overbrace{n\times n \times n \cdots \times n}^{m \text{ termos}} = n^m. \end{equation*}

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 é

\begin{equation*} (n-0)\times(n-1)\times(n-2)\times \cdots \times(n-(m-1)) \end{equation*}

Quantos são os números naturais pares que se escrevem (na base 10) com três algarismos distintos?

Já sabemos que o número total de números naturais com três algarismos distintos é

\begin{equation*} 9\times 9\times 8 = 648. \end{equation*}

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 é

\begin{equation*} 648 - 5\times 8\times 8=328. \end{equation*}

Quantas palavras contendo 5 letras diferentes podem ser formadas com um alfabeto de 26 letras?

Quantos são os gabaritos possíveis de um teste de 25 questões de múltipla-escolha, com cinco alternativas por questão?

Quantos divisores naturais possui o número 600?

Em uma banca há 7 exemplares iguais da revista A, 4 exemplares iguais da revista B e 15 exemplares igauis da revista C. Quantas coleções não vazias de revistas dessa banca é possível formar?

Quantos números inteiros entre 1000 e 9999 são ímpares e possuem quatro dígitos distintos?

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?

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?

Dica

Separe os casos \(n\) faces azuis e \(6-n\) faces laranjas. Depois use o Princípio Aditivo.

Resposta

Considere um tabuleiro \(2015\times37\text{,}\) pintado como um tabuleiro de xadrez. Cada linha e coluna tem um botão que inverte a cor de cada casinha da linha ou coluna correspondente, num total de \(2015 + 37 = 2052\) botões. Quantas colorações diferentes do tabuleiro podem ser obtidas?

Dica

Note que o que determina a cor final da casinha é a paridade da soma da quantidade de vezes que os botões da sua linha ou da sua coluna são apertados. Note que apertar duas vezes o mesmo botão é o mesmo que não apertar o botão. A ordem em que os botões são apertados não importa. As casas nas interseções das linhas e colunas, com botão apertado, não mudam de cor.

Resposta

(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,

a) quantas palavras de comprimento menor do que \(6\) podem ser formadas?

b) 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{?}\)

Resposta

a) \(62~~~~\) b) \(19\text{.}\)

Solução

item a) O número de palavras de comprimento menor que 6 é

\begin{equation*} 2^1 + 2^2 + 2^3 + 2^4 + 2^5 = \frac{2\times(2^5-1)}{2-1} =2\times 32 = 62. \end{equation*}

item b) Precisamos descovrir o menor valor de \(n\) para que

\begin{equation*} 2^1 + 2^2 + \cdots + 2^n > 1.000.000. \end{equation*}

Usando a fórmula da soma da PG, temos

\begin{equation*} \frac{2\times(2^n-1)}{2-1} > 1.000.000 \Leftrightarrow 2^n> 500.001. \end{equation*}

Como \(2^{18} = 262144\) e \(2^{19} = 524288\) concluímos que o menor valor de \(n\) é \(19\text{.}\)