Análise Combinatória e Probabilidade: Com Aplicações no SageMath

Sejam \(A_k\text{,}\) \(k = 8, 12, 18\text{,}\) os conjuntos dos vértices dos polígonos com 8, 12 e 18 lados, respectivamente. Queremos calcular \(\#(A_8\cup A_{12}\cup A_{18})\text{.}\) Pelo Princípio da Inclusão-Exclusão, temos

Como \(\#A_k = k\text{,}\) para concluir o cálculo, precisamos descobrir a cardinalidade de cada interseção.

Usando a figura abaixo como referência, se expandirmos os polígonos até a circunferência, estaremos de acordo com o enunciado. O vértice em comum aos três polígonos foi desenhado no ponto extremo superior, sem perda de generalidade, pois independente de onde ele esteja, os polígonos podem ser girados para ficarem desta forma.

Considere os semicírculos que partem do extremo superior no sentido horário, até o vértice seguinte de \(A_k\) e assim sucessivamente, de um vértice de \(A_k\) até o seguinte. Desta forma cada conjunto \(A_k\) define \(k\) semicírculos. Teremos a interseção de dois ou três vértices quando a respectiva quantidade de extremidades dos semicírculos coincidirem. Portanto, usaremos o máximo divisor comum para calcular a quantidade de interseções dos vértices. Assim, \(\#(A_i\cap A_j) = \text{mdc}(i, j)\text{,}\) para \(i, j \in \{8, 12, 18\}\text{,}\) com \(i\neq j\) e \(\#(A_8\cap A_{12} \cap A_{18}) = \text{mdc}(8, 12, 18)\text{.}\) Logo,

Na figura abaixo, podemos imaginar que os polígonos foram "cortados" e esticados para podermos visualizar as interseções dos vértices de acordo com os valores dos mdcs.

item a) Temos 3 opções para o primeiro dígito, 3 opções para o segundo dígito e assim sucessivamente, até o \(n\)-ésimo dígito que também temos 3 opções. Portanto a resposta é \(\underbrace{3\times \cdots \times 3}_{n\text{ parcelas}} = 3^n\text{.}\)

item b) Agora precisamos subtrair de \(3^n\) a quantidade de números de \(n\) dígitos, na qual, nem todos os três dígitos disponíveis aparecem. Defina \(A_1\) como o subconjunto dos números de \(n\) dígitos formados pelos dígitos \(1, 2\) e \(3\) tal que o dígito \(1\) não aparece. De maneira análoga defina os subconjuntos \(A_2\) e \(A_3\text{.}\) Desta forma, queremos calcular

Pelo Princípio da Inclusão-Exclusão, sabemos que

\(A_1\) possui \(2^n\) elementos, pois o dígito \(1\) não pode figurar no número de \(n\) dígitos, sobrando apenas os dígitos \(2\) e \(3\text{.}\) Desta forma, temos duas opções para o primeiro dígito, 2 opções para o segundo dígito e assim sucessivamente. Observe que os conjuntos \(A_2\) e \(A_3\) possuem a mesma quantidade de elementos.

\(A_1\cap A_2\) possui apenas \(1\) elemento, pois os dígitos \(1\) e \(2\) não podem figurar, sobrando apenas o dígito 3. Desta forma temos apenas uma opções para o primeiro dígito, uma opção para o segundo dígito e assim sucessivamente. De maneira análoga observamos que \(A_1\cap A_2\) e \(A_2\cap A_3\) também possuem apenas um elemento.

Finalmente, \(A_1\cap A_2\cap A_3\) não possui elementos, pois nenhum dos três dígitos podem figurar. Portanto a resposta é

Considere que as exposições do museu estão numeradas de \(1\) até \(n\text{.}\) Podemos representar cada maneira de visitar o museu com uma \(n\)-úpla. Usando \(A, M\) e \(N\) como entradas da \(n\)-úpla, para indicar que Andrês, Marcelo e Nenhum deles, respectivamente, visitou a \(i\)-ésima exposição.

Podemos formar um total de \(3^n\) \(n\)-úplas dessa maneira. Depois, precisamos excluir as que não possuem o símbolo \(A\) ou que não possuem o símbolo \(M\text{.}\) Note que podem ser formadas \(2^n\) \(n\)-úplas com apenas os símbolos \(M\) e \(N\) (sem o símbolo A) e também podem ser formadas \(2^n\) \(n\)-úplas com apenas os símbolos \(A\) e \(N\) (sem o símbolo M). E pode ser formada somente 1 \(n\)-úpla com apenas o símbolo \(N\text{.}\)

Portanto, o número de maneiras de visitar o museu é \(3^n - 2^{n+1} + 1\text{.}\)

Inicialmente, temos 10! possibilidades de colocarmos esses 10 veículos na posição de largada. Dessas permutações, vamos excluir aquelas que possuem uma equipe com dois carros lado a lado. Para isso, existem \(C_5^1\) maneiras de escolhermos essa equipe que poderá ser colocada em uma das 5 filas na largada \((1^{a}, 2^{a}, 3^{a}, 4^{a} \ ou \ 5^{a})\text{.}\) Devemos, ainda, permutar os carros de uma mesma equipe 2! e os demais 8 carros podem ser organizados de 8!. Assim, temos \(C_5^1\times 5\times 2!\times 8!\) formas distintas de organizarmos esses carros.

Algumas dessas maneiras de organizar os carros apresentam mais de uma equipe com seus carros emparelhados.

Agora, calcularemos em quantos casos teremos ao menos 2 equipes com seus carros emparelhados. Primeiramente, temos \(C_5^2\) formas de escolhermos essas 2 equipes e podemos colocá-las de \(5\times4\) maneiras diferentes nas 5 filas da largada (a primeira equipe pode entrar em qualquer uma das 5 filas e a segunda em uma das outras 4 que restaram). Mas, ainda, devemos permutar os carros das duas equipes lado a lado \(2!\times2\) e das demais \(6\) equipes \(6!\text{.}\)

Seguindo essa linha de raciocínio, pelo Princípio da Inclusão-Exclusão temos

item a) Como \(C\subset B\text{,}\) temos \(B\cap C = C\text{,}\) logo \(\#(B\cap C) = \#C\) e \(\#(B\setminus C) = \#B - \#C\text{.}\) Logo

Ou seja,

Usando que \((\#C, \#A, \#B)\) é uma P.G., podemos escrever \(\#C=a_0r^0, \#A=a_0r^1\) e \(\#B=a_0r^2\text{.}\) Logo,

Portanto,

Por hipótese, \(3\times\#(B\cap C) = 6\times\#(A\cap B)\text{,}\) mas \(\#(B\cap C) = \#C\text{,}\) assim

Finalmente, usando as igualdades (2.1.3), (2.1.4), (2.1.5) e o Princípio da Inclusão-Exclusão (Teorema 2.1.1), obtemos

Efetuando o cálculo, \(\#C = 4\text{.}\)

item b) Como \(\#(B\setminus C) = 3\times \#C = 12\text{,}\) temos