Contagem

Dicas para Problemas de Contagem

• Seja muito cuidadoso e organizado com problemas de contagem. Um detalhe que você não prestar atenção pode mudar todo o seu raciocínio.
• Entenda bem os objetos que você está contando. Saiba quais são e quais as propriedades deles.
• Cada objeto deve ser contado uma e somente uma vez.
  • Veja se você não se esqueceu de contar alguém.
  • Veja se você contou algum objeto que não deveria.
  • Veja se você não contou algum objeto mais de uma vez.
• Procure começar pelas dificuldades. Se você deixá-las para depois, pode ser que elas fiquem piores.
• Quando mais de uma coisa pode acontecer e para cada uma delas existe um raciocínio diferente, divida em casos.
• Como problemas de combinatória exigem que você preste atenção em bastantes detalhes, se você tiver tempo, você pode escrever passo a passo cada expressão e justifique muito bem a sua solução. Isto pode ajudar você a não errar na contagem. Se você não tiver esse tempo, ao menos, procure explicar para você mesmo detalhadamente o porquê de você estar fazendo cada passo.
• Tome cuidado: às vezes você acha que está contando apenas um objeto, mas está contando vários de uma vez.
• Imagine a contagem já feita. Quais características ela terá no final? Essas características podem lhe ajudar a resolver o problema?
• Seja cuidadoso ao entender o enunciado: às vezes uma coisa que você entende errado do enunciado, faz com que você resolva incorretamente o exercício.
• Fique atento às restrições.
• Quer ter mais confiança se a sua contagem está certa? Se forem poucos objetos, dá para fazer cada uma das possibilidades. Já se forem $n$ objetos, dá para fazer pequenos casos e ver se o resultado coincide com o que você encontrou para este valor específico de $n$. E lembre-se: os casos pequenos não irão provar nada, porém podem ajudar a identificar algum erro do seu raciocínio, caso houver.
• Depois de feita a contagem, procure ver se existem dois (ou mais) objetos que podem considerados os mesmos.
• Você tentou resolver o problema focando em certos objetos e não de certo? Talvez focar em outros tipos de objetos pode facilitar a sua vida.
• Quanto melhor você entender o processo que está usando para fazer a contagem e quais são as passagens, menos chance você possui de errar.
• Sempre tome cuidado em saber se a ordem importa ou não.
• Se tiver muitos objetos, faça casos particulares.
• Entenda bem cada método de contagem que você está usando (e quando usar) para não se confundir na hora de usá-los.
• Preste atenção se os objetos que você está contando são iguais ou diferentes.
• Faça uma contagem de cada vez.

O grande professor Augusto César Morgado também tinha umas dicas muito úteis e famosas:

• Se imagine no papel da pessoa que está fazendo a coisa pedida pelo problema.
• Nunca tenha pressa em resolver. Não queira fazer tudo de uma vez só. Procure dividir as decisões tomadas em várias decisões mais simples.

Exemplo

Em um alfabeto de $26$ letras, quantas palavras de $4$ letras existem?

Solução: Podemos escolher a primeira letra de $26$ maneiras. O mesmo vale para a segunda, a terceira e a quarta. Por isso, a quantidade de palavras é $26\times 26\times 26\times 26=26^{4}$.

Exemplo

Quantos números de três algarismos existem?

Solução: Observe que o algarismo das centenas não pode ser igual a zero. Desta forma, existem $9$ possibilidades para ele. Além disso, existem $10$ maneiras de escolhermos as dezenas e $10$ as unidades. Por isso, pelo Princípio Multiplicativo, existem $9\cdot 10\cdot 10=900$ números de três algarismos.

Exemplo

Quantos números de três algarismos distintos existem?

Solução: Como o algarismo das cententas não pode ser igual a zero, existem $9$ possibilidades para ele. Já para as dezenas, lembre-se: ela pode ser igual a zero, porém não pode ser igual ao algarismo que já usamos nas centenas, ou seja, também existem nove possibilidades aqui. Finalmente, existem $8$ possibilidades para a unidade (pois o algarismo usado deve diferente do das unidades e do das dezenas). Com isso, pelo Princípio Multiplicativo, existem $9\cdot 9\cdot 8=648$ números.

Exemplo

Se $A$ possui $n$ elementos, prove que ele possui $2^n$ subconjuntos.

Solução: Pensaremos neste problema da seguinte maneira: de quantas maneiras podemos montar um subconjunto de $A$? Vamos ao primeiro elemento. Temos $2$ possibilidades: colocá-lo ou não colocá-lo. A mesma coisa vale para cada um dos outros $n-1$ elementos. Desta forma, o número de subconjuntos é

$\underbrace {2} _{\text{primeiro elemento}}\cdot \underbrace {2} _{\text{segundo elemento}}\cdots \underbrace {2} _{n{\text{-ésimo elemento}}}=2^{n}.$

Exemplo (OBM 2010 - 3ª Fase - Nível 2)

Dizemos que um número inteiro positivo $n$ é abestado se ao lermos da direita para esquerda obtivermos um inteiro maior que $n$. Por exemplo, $2009$ é abestado porque $9002$ é maior que $2009$, por outro lado, $2010$ não é abestado por $0102$, que é o número $102$, é menor que $2010$ e $3443$ não é abestado pois quando lido da direta para esquerda é exatamente igual ao original. Quantos inteiros positivos de quatro algarismos são abestados?

Solução: Vamos usar uma maneira de representar que nos ajude com as contas. Considere $ABCD$ um número de quatro algarismos. Quando ele será abestado? Se ele for menor que o número $DCBA$. Isto ocorre em dois casos:

• $A<D$;
• $A=D$ e $C>B$.

Vamos analisar cada um deles separadamente.

1º Caso: $A<D$.

Aqui $B$ e $C$ podem assumir quaisquer valores. Existem $10$ possibilidades para $B$ e $10$ para $C$, ou seja, $10.10=100$ maneiras de escolhermos os dois.

E quanto a $A$ e $D$? Se $A=1$, existem $8$ possibilidades para $D$: $2,3,4,5,6,7$ e $8$. Se $A=2$, existem $7$ possibilidades para $D$.

Ao usarmos o mesmo raciocínio para os outros valores de $A$, segue que o total de possibilidades para $A$ e $D$ é $8+7+6+5+4+3+2+1=36$.

Portanto, o total de possibilidades deste caso é $100\cdot 36=3600$.

2º Caso: $A=D$ e $C>B$.

Vamos analisando as possibilidades para $A$ e $D$. Existem $9$ possibilidades para $A$. E como $D$ deve ser igual à $A$, segue que existe $1$ possibilidade para $D$.

E quando a $B$ e $C$? Pelo mesmo raciocínio que fizemos no 1º Caso, existem $9+8+7+6+5+4+3+2+1=45$ possibilidades. Logo, neste caso existem $9\cdot 1\cdot 45=405$ maneiras de escolhermos os algarismos.

Portanto, o total de números abestados é

$\underbrace {3600} _{1^{\circ }{\text{ Caso}}}+\underbrace {405} _{2^{\circ }{\text{ Caso}}}=4005$.

Exemplo

Escrevemos todos os números de quatro dígitos que contêm apenas algarismos do conjunto $\{1,2,3,4\}$ em ordem crescente, como abaixo:

$1111,1112,1113,1114,1121,\ldots ,4443,4444$

a) Quantos números há na lista?

b) Em que posição da lista está o número $3141$?

Solução:

a) Como há quatro possibilidades para cada algarismo e há quatro algarismos, a quantidade de números na lista é $4\cdot 4\cdot 4\cdot 4=4^{4}$.

b) Se fixarmos o número 1 na esquerda, veremos que os números da forma $1\ \_\ \_\ \_$ que estão nessa lista totalizam $4\cdot 4\cdot 4=4^{3}=64$, o mesmo valendo para números começando em 2, 3 e 4. Isso significa que os números que começam com 1 estão entre as posições 1 e 64, os que começam com 2 estão entre as posições 65 e 128, enquanto os números que começam com 3 estão entre 129 e 192.

Por um raciocínio análogo, existem 16 números que começam com $3\ 1\ \_\ \_$, dos quais 4 começam com $3\ 1\ 1\ \_$, 4 começam com $3\ 1\ 2\ \_$, e 4 começam com $3\ 1\ 3\ \_$. O que significa que $3141$ está na posição $128+4+4+4+1=141$.

Exemplo (OBM 2017 - Níveis 1 e 2)

Na Terra dos Impas, somente os algarismos ímpares são utilizados para contar e escrever números. Assim, em vez dos números $1,2,3,4,5,6,7,8,9,10,11,12,\ldots$ os Impas tem os números correspondentes $1,3,5,7,9,11,13,15,17,19,31,33,\ldots$ (note que os numeros dos Impas têm somente algarismos ímpares). Por exemplo, se uma criança tem 11 anos, os Impas diriam que ela tem 31 anos.

a) Como os Impas escrevem nosso número 20?

b) Numa escola desse lugar, a professora escreveu no quadro negro a continha de multiplicar abaixo. Se você fosse um aluno Impa, o que escreveria como resultado?

c) Escreva, na linguagem dos Impas, o número que na nossa representação decimal é escrito como 2017.

Solução: Vale a pena escrevermos alguns números iniciais na linguagem dos Impas para treinar. Felizmente, o item a) pede que façamos justamente isso.

a) Pelo enunciado, o nosso número 12 corresponde a 33 na linguagem dos Impas, o que significa que $13,14,15,16,17,18,19,20$ correspondem a $35,37,39,51,53,55,57,59$, portanto, os Impas escrevem nosso 20 como 59.

b) O 13 dos impas corresponde ao nosso 7, e o 5 dos Impas corresponde ao nosso 3. O resultado da multiplicação, no nosso sistema, seria $7 \times 3 = 21$, no entanto, precisamos passar o resultado para a linguagem dos Impas, na qual 21 é escrito como 71.

c) Os Impas usam apenas algarismos ímpares, o que significa que existem $5$ números com apenas um dígito, $5^2$ com dois, $5^3$ números com três dígitos e, de modo mais geral, $5^n$ números com $\ n$ dígitos (porque há 5 possibilidades de algarismos para cada dígito). Como os Impas contam em ordem crescente, conseguimos determinar quantos dígitos tem o número 2017 de uma maneira bem rápida. O maior número, na nossa representação, que tem $\ n$ dígitos na linguagem dos Impas será $5+5^{2}+\ldots +5^{n}$, e será um número composto por $n$ 9s. Dessa forma, se calcularmos o valor dessa expressão aumentando $\ n$ de um em um, podemos encontrar a quantidade de dígitos de 2017:

• $5 = 5$
• $5+5^{2}=30$
• $5+5^{2}+5^{3}=155$
• $5+5^{2}+5^{3}+5^{4}=780$
• $5+5^{2}+5^{3}+5^{4}+5^{5}=3905$

Como 2017 está entre os dois últimos resultados, ele tem cinco dígitos, o que significa que ele está entre 11111 e 99999 na linguagem dos Impas, que correspondem a 781 e 3905, respectivamente. Mas ainda são muitos números a analisar: não queremos olhar os 3126 números um por um. E não precisamos.

Se fixarmos, por exemplo, o 1 na casa mais à esquerda num número de 5 dígitos, podemos concluir que há $5^4$ números Impas que têm cinco dígitos e começam com 1. Isso significa que os números Impas de cinco dígitos que têm um 1 à esquerda vão de $5+5^{2}+5^{3}+5^{4}+1=781$ até $5+5^{2}+5^{3}+5^{4}+(5^{4})=1405$.

Pelo mesmo raciocínio, os números Impas de cinco dígitos que têm um 3 à esquerda totalizam $5^4$ e vão de $5+5^{2}+5^{3}+5^{4}+(5^{4})+1=1406$ até $5+5^{2}+5^{3}+5^{4}+(5^{4}+5^{4})=2030$. Quase chegamos em 2017! Isso significa que ele tem um 3 à esquerda e está bem próximo de 39999, que corresponde a 2030.

Daí, podemos simplesmente contar em ordem decrescente simultaneamente no sistema decimal e na numeração Impa.

2030	2029	2028	2027	2026	2025	2024	2023	2022	2021	2020	2019	2018	2017
39999	39997	39995	39993	39991	39979	39977	39975	39973	39971	39959	39957	39955	39953

Dessa forma, concluímos que 2017 corresponde, na linguagem dos Impas, a $39953$.

Fatorial

Se $n$ é um número inteiro não negativo, podemos definir $n!$ (lê-se: "$n$ fatorial) como sendo

$n!=n\cdot (n-1)\dots \cdot 2\cdot 1$

Observe que $n!=n(n-1)!$ para $n>1$. Por convenção, $0! = 1$. Uma vantagem de considerarmos isto é que esta última fórmula será válida também para $n=1$.

Exemplos:

(1) $1! = 1$

(2) $2!=2\cdot 1=2$

(3) $3!=3\cdot 2\cdot 1=6$

(4) $4!=4\cdot 3\cdot 2\cdot 1=24$

(5) $5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120$

Exemplo

Vamos definir o fatorial duplo. Você não precisa dele para fazer problemas de olimpíadas, mas é legal brincar com eles.

Para $\ n$ par e positivo,

$n!!=n(n-2)(n-4)\cdots 6\cdot 4\cdot 2.$

Para $\ n$ ímpar e positivo,

$n!!=n(n-2)(n-4)\cdots 5\cdot 3\cdot 1.$

Por convenção $0!!=1$ e $(-1)!!=1$.

(a) Calcule $6!!$.

(b) Calcule $7!!$.

(c) Prove que $(2n)!!=2^{n}\cdot n!$.

(d) Prove que $(2n+1)!!={\frac {(2n+1)!}{2^{n}n!}}$.

(e) Prove que $n!=n!!(n-1)!!$.

Solução:

(a) $6!!=6\cdot 4\cdot 2=48$.

(b) $7!!=7\cdot 5\cdot 3\cdot 1=105$

(c) Vamos começar abrindo um dos lados da igualdade e chegar em outro. Parece valer mais a pena mexer no lado direito:

$(2n)!!=(2n)(2n-2)(2n-4)\cdots 6\cdot 4\cdot 2.$

Observe que no lado direito da igualdade aparece $2^n$, ou seja, uma multiplicação de $\ 2$ por ele mesmo (com ele aparecendo $\ n$ vezes). Ou seja, precisamos de alguma maneira de "separar" esses fatores $\ 2$. Repare que, podemos escrever na nossa igualdade anterior:

$(2n)!!=({\color {red}2}(n))({\color {red}2}(n-1))({\color {red}2}(n-2))\cdots ({\color {red}2}\cdot 3)\cdot ({\color {red}2}\cdot 2)\cdot ({\color {red}2}\cdot 1).$

Ao separarmos esses $\ n$ fatores $\ 2$ (em vermelho):

$(2n)!!=\underbrace {\color {red}2\cdot 2\cdots 2} _{n{\text{ vezes}}}\cdot n(n-1)(n-2)\cdots 3\cdot 2\cdot 1=2^{n}\cdot n!.$

(d) Vamos abrir um lado e chegar em outro. Observe que

$(2n+1)!!=(2n+1)(2n-1)\cdots 5\cdot 3\cdot 1.$

Aqui só temos os fatores ímpares. Só que no exemplo anterior aprendemos a lidar com fatores pares. Será que podemos usar isso? Sim. Seria legal se os fatores pares e ímpares aparecessem em uma mesma conta. Repare que

$(2n+1)!=(2n+1)(2n)(2n-1)(2n-2)\cdots 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=\underbrace {(2n+1)(2n-1)\cdots 5\cdot 3\cdot 1} _{\text{fatores ímpares}}\cdot \underbrace {(2n)(2n-2)\cdots 6\cdot 4\cdot 2} _{\text{fatores pares}}.$

Se usarmos o item anterior e que $(2n+1)!!=(2n+1)(2n-1)\cdots 5\cdot 3\cdot 1$,

$(2n+1)!=(2n+1)!!\cdot 2^{n}n!\Leftrightarrow (2n+1)!!={\frac {(2n+1)!}{2^{n}n!}}.$

(e) Como a definição de fatorial duplo depende da paridade de $\ n$, vamos dividir em casos:

(i) $\ n$ par

Vamos sair do lado direito e chegar no esquerdo:

$n!!=n(n-2)\cdots 4\cdot 2$

$(n-1)!!=(n-1)(n-3)\cdots 3\cdot 1$.

Ao multiplicarmos essas duas igualdades:

$n!!(n-1)!!=n(n-1)(n-2)(n-3)\cdots 4\cdot 3\cdot 2\cdot 1=n!$

(ii) $\ n$ ímpar

Análogo.

Permutações Simples

Fazemos uma permutação de objetos quando trocamos eles de lugar. A própria palavra permutar significa "trocar um pelo outro".

Uma permutação simples é uma permutação de objetos diferentes.

Por exemplo, considere as três bolas a seguir:

Podemos ter uma permutação trocando as bolas amarela e azul de lugar entre si:

Existem ainda outras permutações:

O número de permutações de $n$ objetos é $n!$. Este número, em alguns lugares, é representado por $P_n$.

Exemplo (OBM 2013 - 3ª Fase - Nível 2)

Arnaldo desenha um pentágono regular $ABCDE$ e, em seguida, desenha uma estrela de $5$ pontas $MNOPQ$. Depois disso, ele liga os segmentos $AM,BP,CN,DQ$ e $EO$. Na figura formada, dizemos que dois vértices são vizinhos se existe um segmento ligando os dois.

Bernaldo percebe que é possível colocar todos os $10$ subconjuntos de $2$ elementos do conjunto $\{1,2,3,4,5\}$ nos $10$ vértices da figura formada de tal forma que os subconjuntos colocados em dois vértices vizinhos tem interseção vazia. Uma tal associação é dita curiosa e um exemplo é dado abaixo:

(a) Dê mais um exemplo de associação curiosa.

(b) Determine a quantidade de associações curiosas existentes.

Solução:

(a)

(b) Primeiro analisamos as possibilidades para $A$. Depois analisamos os vizinhos de $A$, e assim por diante, até que uma vez escolhidos os vértices que já analisamos, o resto da estrela já esteja determinada. Observe que existem $10$ possibilidades para $A$ (pois existem $10$ subconjuntos de $\{1,2,3,4,5\}$ com $2$ elementos). Podemos supor sem perda de generalidade que $\{1,2\}$.

Desta forma, os subconjuntos dos vértices vizinhos de $A$ (ou seja, $B$, $M$ e $D$) não devem possuir $1$ e nem $2$. Assim, eles só podem ser $\{3, 4\}$, $\{3, 5\}$ e $\{4,5\}$, de onde segue que existem $3!=3\cdot 2\cdot 1=6$ maneiras de escolhermos $B$, $M$ e $D$. Podemos supor sem perda de generalidade que $B=\{3,4\}$, $M=\{3,5\}$ e $E=\{4,5\}$.

Analisemos $Q$. Como este é vizinho de $M=\{3,5\}$, segue que ele só pode ser igual a $\{1,4\}$, $\{2,4\}$ e $\{1,2\}$. Mas $\{1,2\}$ já o conjunto escolhido para $A$. Desta forma, existem duas possibilidades para $Q$. Sem perda de generalidade, podemos supor que $Q=\{1,4\}$.

A partir daí, todos os vértices já estão determinados. Provemos isto. Como $N$ é vizinho de $M=\{3,5\}$, segue que as possibilidades para ele são $\{1,2\}$, $\{1,4\}$ e $\{2,4\}$. Destas, a única que ainda não usamos é $\{2,4\}$. Analogamente, $C=\{1,5\}$, $D=\{2,3\}$, $P=\{2,5\}$.

Portanto, o total de maneiras de fazermos isto é

$\underbrace {10} _{{\text{Possibilidades para }}A}.\underbrace {6} _{{\text{Possibilidades para }}B,M{\text{ e }}E}.\underbrace {2} _{{\text{Possibilidades para }}Q}=120.$

Permutações com Repetição

Suponha que existam $n$ objetos, onde um deles se repete $a_1$ vezes, o outro $a_2$ e assim por diante até que o último se repita $a_k$ vezes, de forma que $a_{1}+a_{2}+\cdots +a_{k}=n$. O número de permutações destes objetos será

${\frac {n!}{a_{1}!a_{2}!\cdots a_{k}!}}.$

Em alguns lugares, este número é presentado por

$P_{n}^{a_{1},a_{2},\cdots ,a_{k}}$

ou

${n \choose a_{1},a_{2},\cdots ,a_{k}}.$

Anagramas

São permutações das letras de uma palavra ou expressão. Por exemplo, são anagramas da palavra CONTAR as palavras CANTOR, CONTRA e TRANCO. Também LAMINA é um anagrama da palavra ANIMAL. Os anagramas não precisam ser uma palavra com significado da língua portuguesa. Por exemplo, MATEMATACI é um anagragrama da palavra MATEMATICA.

Combinação

O número de maneiras de escolhermos $p$ objetos distintos dentre $n$ objetos distintos dados (e a ordem não importar) será

${n \choose p}={\frac {n!}{p!(n-p)!}}$.

Também podemos representar ${n \choose p}$ por $C_{n,p}$ ou $C_{n}^{p}$. Estes são chamados de números binomiais (ou coeficientes binomiais). Repare que esta definição acima só vale para $0\leq p\leq n$, já que fatorial só está definido para números não negativos.

Propriedades dos Coeficientes Binomiais

(i) ${n \choose n}=1$, ${n \choose 0} = 1$ e ${n \choose 1} = n$;

(ii) ${n \choose k}={n \choose n-k}$;

(iii) (Relação de Stifel) Para $k>0$, ${n \choose k}+{n \choose k-1}={n+1 \choose k}$;

Exemplo

Quantas diagonais possui um polígono de $n$ lados?

Solução: Para formamos uma diagonal devemos unir dois vértices do polígono e este segmento não pode ser um lado. Para escolhermos dois vértices do polígono existem ${n \choose 2}=\frac{n(n-1)}{2}$ maneiras. Mas devemos eliminar os $n$ casos em que esses segmentos formam lados. Assim a quantidade de diagonais será

${\frac {n(n-1)}{2}}-n={\frac {n(n-3)}{2}}.$

Exemplo

Para $n$ inteiro não negativo, calcule

${2n \choose 2}\cdot {2n-2 \choose 2}\cdot {2n-4 \choose 2}\cdots {4 \choose 2}\cdot {2 \choose 2}.$

Solução: Vamos "abrir" cada um dos fatores:

${\frac {(2n)!}{2!(2n-2)!}}\cdot {\frac {(2n-2)!}{2!(2n-4)!}}\cdot {\frac {(2n-4)!}{2!(2n-6)!}}\cdots {\frac {4!}{2!2!}}\cdot {\frac {2!}{2!0!}}={\frac {(2n)!}{\underbrace {2!\cdots 2!} _{n{\text{ fatores}}}}}={\frac {(2n)!}{2^{n}}}.$

Exemplo (OBM 2003 - 3ª Fase - Nível 2)

Num tabuleiro $2 \times 2$, ao lado, escrevemos números inteiros de $1$ a $9$ obedecendo à seguinte regra: $A > B$, $C>D$, $A > C$ e $B>D$.

(a) Quantos tabuleiros existem tais que $B=C$?

Dica:

Queremos que $A>B=C>D$. Basta escolhermos três números distintos. O maior deles deverá ser obrigatoriamente o $A$, o segundo maior será $B$ e $C$, enquanto o terceiro maior será $D$.

(b) Quantos tabuleiros diferente existem no total?

Dica:

Divida em casos: $B > C$ e $B<C$. Em ambos os casos, basta escolhermos quatro números e colocarmos em ordem.

Solução:

(a) Precisamos nos organizar bem. Será que conseguimos determinar o maior e o menor deles? Como $A > B$, $B$ não pode ser o maior de todos. Da mesma forma, como $A > C$ e $C>D$, segue que $C$ e $D$ não podem ocupar a posição de máximo. Logo, $A$ é o maior número de todos. Pelo mesmo raciocínio, $D$ é o menor dos números.

Assim, $A>B=C>D$. A estratégia será a seguinte: basta escolhermos os números e depois ordená-los. Precisamos escolher $3$ dentre os $9$ números (já que, se escolhemos o número $B$, então $C$ está escolhido).

Em um conjunto de $9$ elementos, de quantas maneiras podemos escolher $3$? De ${9 \choose 3}={\frac {9!}{3!(9-3)!}}=84$ maneiras.

Portanto, neste caso, existem $84$ tabuleiros diferentes.

(b) Já analisamos o caso em que $B=C$. Resta analisarmos os casos em que $B > C$ e $B<C$.

No em que $B > C$, teremos $A>B>C>D$. Assim, é necessário escolher $4$ dentre os $9$ números. Podemos fazer isto de ${9 \choose 4}={\frac {9!}{4!(9-4)!}}=126$ maneiras.

Analogamente, para o caso em que $B<C$ também teremos $126$ maneiras. Logo, o total de possibilidades é $84+126+126=336$.

Exemplo (OBM 2009 - 3ª Fase - Nível 2)

Um dominó é formado por $28$ peças diferentes. Cada peça tem duas metades, sendo que cada metade tem de zero a seis pontos:

Esmeralda coloca $4$ peças de dominó dentro de um estojo, respeitando as regras do jogo, isto é, peças vizinhas se tocam em metades com as mesmas quantidades de pontos. Caso seja possível guardar as quatro peças no estojo, dizemos que o conjunto de quatro peças é precioso.

Por exemplo, a figura acima mostra as maneiras de guardar o conjunto precioso formado pelas peças

(a) Mostre que um conjunto precioso não pode conter duas peças duplas.

A figura abaixo mostra as peças duplas.

(b) Quantos conjuntos preciosos contêm uma peça dupla?

(c) Determine a quantidade total de conjuntos preciosos.

Solução:

(a) Suponha, por absurdo, que seja possível um conjunto precioso com duas peças duplas. Observe que as peças duplas não podem estar juntas. De fato, isso só poderia acontecer se elas fossem iguais e só existe uma peça de cada tipo. Assim, a menos de uma rotação, o estojo é da forma:

Neste caso, teremos $X=A=C$ e $Y=B=D$, de onde segue que as peças $1$ e $2$ são iguais, o que não pode acontecer. Absurdo. Logo, não existem duas peças duplas em um conjunto precioso.

(b) Um conjunto precioso com peças duplas será da forma:

Para formarmos este conjunto, devemos fazer duas coisas:

• Escolhemos a peça dupla, ou seja, o $X$;
• Escolhemos $Y$ e $Z$ de tal modo que $X$,$Y$ e $Z$ sejam dois a dois distintos.

A primeira podemos fazer de $7$ maneiras e a segunda de ${6 \choose 2}$.

Desta forma, o número de peças duplas é $7.{6 \choose 2}=105$.

(c) Já sabemos que não existem conjuntos com mais de uma peça dupla e que existem $105$ com apenas uma peça dupla. Basta contarmos a quantidade de conjuntos preciosos sem peças duplas.

Precisamos que estas peças sejam duas a duas distintas e que elas não sejam duplas. Para que as peças não sejam duplas, é necessário que $X\neq W$, $W\neq Z$, $Z\neq Y$ e $Y \ne X$. Além disso, queremos comparar $X$ com $Z$ e $W$ com $Y$. Observe que $X\neq Z$, pois as peças $1$ e $2$ precisam ser distintas. Da mesma forma, $W\neq Y$, pois as peças $1$ e $4$ são diferentes. Portanto, os números $X$, $Y$, $Z$ e $W$ são dois a dois distintos.

Então, para formar um conjunto precioso, basta escolhermos quatro números de ${7 \choose 4}$ maneiras? Não, para cada conjunto quatro números escolhidos, podemos rotacionar as peças e formar $3$ conjuntos preciosos:

Logo, o total de conjuntos preciosos sem peças duplas será $3\cdot {7 \choose 4}=105$.

Portanto, o total de conjunto preciosos é $105+105=210$.

Exemplo (OBM 2019 - Nível 1)

Betinha tem 3 fichas brancas, 4 pretas e 3 cinzentas, todas de mesmo formato e diferentes apenas em relação à cor. Ela coloca fichas no tabuleiro a seguir, formado por quadradinhos iguais, no máximo uma ficha por quadradinho.

De quantas maneiras diferentes ela pode colocar no tabuleiro

a) exatamente três fichas, sendo uma ficha branca, uma preta e uma cinzenta somente na primeira linha horizontal?

b) exatamente três fichas pretas somente na segunda linha horizontal?

c) exatamente três fichas de cores diferentes?

d) todas as dez fichas, de modo que em dois quadradinhos com um lado comum não haja duas fichas pretas?

Solução:

a) Para isso, é necessário organizar 3 elementos distintos em uma fila, que totalizam um total de $3!=6$ possibilidades.

b) Aqui, devemos escolher o quadradinho em que não vamos colocar uma ficha. Como há 4 maneiras de se fazer isso, há 4 possibilidades.

c) Precisamos escolher 3 quadradinhos entre 10, importando a ordem. Isso nos dá $10\cdot 9\cdot 8=720$ possibilidades.

d) O maior desafio desse problema é encontrar todas as maneiras de colocar as fichas pretas. Vamos separar em vários casos.

Caso 1: O primeiro quadrado da segunda linha está desocupado.

Pelo Princípio das Casas dos Pombos, como há 4 fichas e apenas 3 linhas, existe uma linha com 2 fichas. Vamos separar em três casos (que, no fundo, são 2):

Caso 1a: A linha do meio é a que tem duas fichas. Isso faz com que exista apenas uma configuração possível, listada a seguir:

Caso 1b: A primeira linha tem duas fichas.

Se a segunda linha está vazia, há apenas uma possibilidade:

Se ela tem uma ficha, no entanto, há duas:

Totalizando 3 possibilidades para esse caso.

Caso 1c: A terceira linha tem duas fichas. Esse caso é simétrico ao anterior, portanto contabiliza 3 possibilidades também, exceto a que vale para os dois (há duas fichas na primeira e terceira linhas). Portanto, o caso 1 inteiro tem 1+3+2=6 possibilidades.

Caso 2: O primeiro quadradinho da segunda linha tem uma ficha.

Vamos separar esse caso em 3 sub-casos.

Caso 2a: O resto da segunda fileira está vazio.

Uma das fileiras restantes precisa ter duas fichas. Se for a primeira, a ficha restante tem 3 possibilidades de lugares. Se for a última, também, portanto esse caso nos dá 6 possibilidades.

Caso 2b: Há uma ficha no terceiro quadradinho da segunda fileira. Depois de colocarmos essa ficha, há apenas 4 quadradinhos disponíveis para fichas e nenhum deles é vizinho do outro, portanto há ${\dfrac {4\cdot 3}{2}}=6$ possibilidades para esse caso.

Caso 2c: Há uma ficha no quarto quadradinho da segunda fileira.

Devemos colocar uma ficha em cada fileira. Como há duas escolhas para cada fileira, há um total de $2 \cdot 2=4$ possibilidades.

Portanto, o número total de possibilidades para as fichas pretas é:

$1a+1b+1c+2a+2b+2c=1+3+(3-1)+6+6+4=22$

Colocadas as fichas pretas no tabuleiro, devemos escolher três quadradinhos dentre 6, sem importar a ordem, para as fichas brancas, ou seja, o número total e final de possibilidades é:

$22\cdot {\dfrac {6!}{3!\cdot 3!}}=22\cdot {\dfrac {6\cdot 5\cdot 4}{3!}}=22\cdot 20=440$

Contou Alguém Mais de Uma Vez?

Considere a seguinte situação. Alguém conta o número de pessoas em um lugar e consegue o número $60$. Algo porém aconteceu: cada pessoa foi contada $3$ vezes. Quantas pessoas de fato há neste lugar? A resposta é ${\frac {60}{3}}=20$.

Em geral, se, em uma contagem, cada objeto foi contado $n$ vezes, você pode corrigir isto dividindo o seu resultado por $n$.

Por isso que você deve tomar cuidado nos problemas de contagem. Sempre que terminar, pergunte-se: alguns objetos foram contados mais de uma vez? Quais objetos eu contei mais de uma vez? Quantas vezes contei cada um desses objetos?

Exemplo (OBM 2005 - 3ª Fase - Nível 2)

Num tabuleiro quadrado $5 \times 5$, 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?

Solução: Ao invés de considerarmos um tabuleiro quadrado, mexeremos com uma malha pontilhada, onde cada um dos pontos são centros de cada quadradinho.

A estratégia será a seguinte: contaremos a quantidade de hipotenusas e vemos quantos triângulos retângulos podemos formar a partir de cada uma delas.

Para facilitar a escrita, vamos nomear os $25$ pontos da figura. Os pontos da primeira linha de $1,2,3,4,5$, os da segunda $6,7,8,9,10$ e assim por diante. Em geral, o ponto da linha $x$ e da coluna $y$ será $5(x-1)+y$.

Consideremos uma hipotenusa com extremidades nos pontos $5K+a$ (linha $K+1$ e coluna $a$) e $5N+b$ (linha $N+1$ e coluna $b$). Observe que só podemos formar catetos paralelos às bordas do tabuleiro se $K$ for diferente de $N$ e $a$ diferente de $b$.

Nestas condições, quantos triângulos retângulos podemos com catetos paralelos às bordas do tabuleiro podemos formar? Apenas dois. Os possíveis valores para o vértice oposto à hipotenusa são $5N+a$ e $5K+b$. Logo, o número de triângulos retângulos é o dobro do de hipotenusas.

Para descobrirmos o número delas, vamos descobrir a quantidade de maneiras de descobrirmos cada uma das suas extremidades. O primeiro vértice pode ser escolhido de $25$ maneiras. E quanto ao segundo? Observe que ele não pode estar nem na mesma linha e nem na mesma coluna. Logo, existem $16$ maneiras para escolhermos ele.

Portanto, pelo Princípio Fundamental da Contagem, o número de maneiras de montarmos a hipotenusa é $25\cdot 16=400$, certo? Cuidado. Contamos duas vezes a mais cada uma das hipotenusas. De fato, para cada hipotenusa montada primeira pelo vértice $5K+a$ e depois pelo $5N+b$ pode ser montada de novo se escolhermos os vértices na ordem contrária. Logo, o número de hipotenusas deve ser $\frac{400}{2}=200$. Desta forma, o número de triângulos retângulos será $2\cdot 200=400$.

Exemplo (OBM 2000 - 3ª Fase - Nível 3)

Seja $C$ um cubo de madeira. Para cada um dos $28$ pares de vértices de $C$ cortamos o cubo $C$ pelo plano mediador dos dois vértices do par. Em quantos pedaços fica dividido o cubo?

Nota: Dados dois pontos $A$ e $B$ no espaço, o plano mediador de $A$ e $B$ é o conjunto dos pontos do espaço cujas distâncias a $A$ e $B$ são iguais. Em outras palavras: é o plano perpendicular ao segmento $AB$ passando pelo ponto médio de $AB$.

Solução: Em primeiro lugar, vamos entender quais são os planos mediadores. A partir daí teremos condições de ver quais figuras formamos para aí sabermos em quantos pedaços fica dividido o cubo.

Como saber quais são os planos mediadores? Precisamos de uma maneira de organizar o nosso raciocínio. Uma maneira interessante de fazermos isto é separarmos em tipos de plano. Observe que cada par de vértices nos dá um plano mediador. E existem alguns tipos de pares de vértices: os adjacentes (que estão unidos por uma aresta), os que estão opostos em uma mesma face e os que estão opostos, porém em faces diferentes. Vamos analisar cada caso.

Comecemos com o caso em que os vértices são adjacentes, ou seja, ligados por uma aresta. Observe que existem $12$ arestas e portanto $12$ pares de vértices adjacentes. Portanto existem $12$ planos mediadores deste tipo? Não! Observe a figura a seguir:

O plano destacada é mediador de $A$ e $B$, $C$ e $D$, $E$ e $F$, $G$ e $H$. Mais geralmente falando, cada plano mediador deste tipo é formado por quatro pares de vértices. Por isso, contamos cada um quatro vezes. Desta forma, o número de planos mediadores deste tipo é ${\frac {12}{3}}=4$.

Além disso, existem os planos mediadores de vértices opostos de uma mesma face.

E também os planos mediadores de vértices opostos e de faces diferentes.

Que figuras iremos ter? Vamos analisar alguns elementos da figura para descobrir. Se desenharmos todos planos e pegarmos apenas as partes deles que estão dentro do cubo, cada face terá exatamente esta figura desenhada nela:

Observe que a intersecção de todos os planos mediadores é o centro do cubo e todas as intersecções de segmentos da figura acima são de intersecções de planos mediadores. Assim os pedaços formados são várias pirâmides cujo vértice é o centro do cubo e as bases são triângulos que pertencem às faces do cubo. Para terminarmos, basta contarmos o número de triângulos.

Como existem $6$ faces e $16$ triângulos em cada face, existem $6\cdot 16=96$ regiões formadas pelos planos mediadores.

Permutações Circulares

Imagine que queiramos fazer uma permutação com objetos igualmente espaçados e que estão em um círculo.

Aqui, duas permutações são equivalentes se podemos girar uma delas e obter a outra.

O número de permutações circulares de $n$ objetos é $(n-1)!$.

Em certos lugares, o número de permutações circulares é denotado por $(PC)_{n}$.

Exemplo

Quantas palavras de três letras existem de forma que elas não se repitam e estejam em ordem alfabética.

Solução: Se escolhermos as letras, existe apenas uma maneira de montarmos a palavra: basta colocarmos em ordem alfabética. Ou seja, basta calcularmos a quantidade de maneiras de selecionarmos as letras para terminarmos o problema. Existem ${26 \choose 3}=2600$ maneiras de fazermos isto. Portanto, esta é a quantidade de palavras que satisfazem as condições do enunciado.

Exemplo (OBM 2006 - 3ª Fase - Nível 2)

Quantos subconjuntos $\{a,b,c\}$ de três elementos distintos de $\{1,2,3,\dots ,100\}$ são tais que $b$ é a média aritmética de $a$ e $c$ ($a < b < c$)?

Solução: Se escolhermos $a$ e $c$ de modo que ${\frac {a+c}{2}}$ seja inteiro, então o conjunto $\{a,b,c\}$ já está determinado. Mas quando ${\frac {a+c}{2}}$ é inteiro? Basta que $a + c$ seja par, o que equivale a dizer que $a$ e $c$ possuem mesma paridade.

De quantas maneiras podemos escolher $a$ e $c$? Existem $100$ possibilidades para $a$. Existirão outros $49$ números com a mesma paridade de $a$ (e diferentes dele) . Logo, existem $49$ possibilidades para $c$. Com isso, podemos escolher $a$ e $c$ de $100\cdot 49=4900$ maneiras? Não.

Metade dos casos $a>c$ e na outra metade $a < c$. Logo, o total de possibilidades será ${\frac {4900}{2}}=2450$.

Exemplo (OPM 2016 - 1ª Fase - Nível Beta)

Uma quantidade $2n$ de carros deve ser colocada nas extremidades de $2n$ segmentos de retas, $n$ deles verticais e $n$ horizontais. Segmentos na mesma direção estão igualmente espaçados, e têm a mesma medida. A seguir exibimos dois exemplos para $n = 6$:

Após os carros serem dispostos, eles se movem simultaneamente com a mesma velocidade constante em direção à outra extremidade do segmento correspondente. Dizemos uma disposição de carros é segura quando dois carros não passam pelo mesmo ponto simultaneamente. Por exemplo, na figura acima, a disposição à esquerda é segura e a disposição à direita não é segura, pois, por exemplo, os carros na sexta coluna e na primeira linha passam pelo mesmo ponto simultaneamente.

a) Suponha que o carro da primeira linha seja colocado à esquerda. Determine onde os carros da primeira coluna, da última coluna e da última linha devem ser colocados para que a disposição seja segura.

b) É possível que exista uma disposição segura para $n = 7$?

c) Quantas são as disposições seguras para $n = 6$?

Solução:

a) Para que o carro na primeira coluna não colida com ele, o carro da primeira coluna deve ser disposto em baixo. E, para que o carro da última coluna não colida com o primeiro, ele deve ser disposto em cima. Por fim, para que o carro da última linha não colida com esses dois anteriores, é necessário que ele seja disposto na direita.

b) Não. Para qualquer disposição dos carros, aqueles dispostos na terceira linha e na terceira coluna vão sempre colidir na interseção central de segmentos.

c) Vamos supor que colocamos o carro da $\ i\$-ésima linha na esquerda. Então:

• O carro da $\ i\$-ésima coluna não pode estar em cima, e portanto deve estar em baixo.
• O carro da $7-i$-ésima coluna não pode estar em baixo, portanto deve estar em cima.
• Para não colidir com os dois anteriores, o carro da $7-i$-ésima linha deve estar na direita.
• Nenhum dos outros carros restantes pode colidir com estes quatro já determinados.

Podemos notar que as posições desses três carros também seriam determinadas se o carro inicial estivesse na direita e não na esquerda. Isso significa que, se escolhermos as posições dos carros nas 3 primeiras linhas, determinaremos a disposição toda. Dessa forma como há 2 escolhas para cada linha, existem $2 \cdot 2 \cdot 2 = 8$ disposições seguras para $n = 6$.

Exemplo (OBM 2000 - 3ª Fase - Nível 3)

Seja $X$ o conjunto de todas as sequências $a=(a_{1},a_{2},\cdots ,a_{2000})$ tais que $a_{i}\in \{0,1,2\}$ se $1\leq i\leq 1000$ e $a_{i}\in \{0,1\}$ se $1001\leq i\leq 2000$. Dados $a$ e $b$ em $X$, definimos a distância $d(a,b)$ entre $a$ e $b$ como sendo o número de valores de $i$, $1\leq i\leq 2000$, tais que $a_i \neq b_i$. Determine o número de funções $f:X \to X$ que preservam distância, isto é, tais que $d(f(a),f(b))=d(a,b)$ para quaisquer $a$ e $b$ em $X$.

Solução: A ideia aqui é a seguinte: com apenas alguns elementos, conseguimos ter todas as informações da função $f$ que satisfaz as condições do enunciado. Veremos quais são estes elementos e de quantas maneiras podemos escolhê-los. Vamos supor aqui que $f$ preserva distância.

Começaremos vendo o seguinte: se soubermos quem é $f(0,0,0,\cdots ,0)$, $f(1,0,0\cdots ,0)$ e $f(2,0,0,\cdots ,0)$ já podemos falar sobre uma das coordenadas de $f(0,a_{2}',a_{3}',\cdots ,a_{2000}')$, $f(1,a_{2}',a_{3}',\cdots ,a_{2000}')$ e $f(3,a_{2}',a_{3}',\cdots ,a_{2000}')$ para $a_{2}',a_{3}',\cdots ,a_{2000}'$ quaisquer.

Para facilitar a nossa escrita, vamos considerar

$A=f(0,0,0,\cdots ,0)=(a_{1},a_{2},\cdots ,a_{2000}),$

$B=f(1,0,0\cdots ,0)=(b_{1},b_{2},\cdots ,b_{2000}),$

$C=f(2,0,0,\cdots ,0)=(c_{1},c_{2},\cdots ,c_{2000}).$

Vamos descobrir mais informações sobre o problema. Observemos que

$d(A,B)=d(f(0,0,0,\cdots ,0),f(1,0,0\cdots ,0))=d((0,0,0,\cdots ,0),(1,0,0\cdots ,0))=1,$

justamente pela definição da distância $d$. Analogamente, $d(B,C)=1$ e $d(C,A)=1$.

Como $d(A,B)=1$, pela definição de $d$, existe um único número natural $i_1$ com $1\leq i_{1}\leq 2000$ tal que $a_{i_{1}}\neq b_{i_{1}}$. Da mesma forma, existe um único $i_{1}'$ tal que $b_{i_{1}'}\neq c_{i_{1}'}$. E qual a relação entre $i_1$ e $i_{1}'$? Vejamos que eles são iguais.

Suponha, por absurdo, que eles sejam diferentes. Como $B$ e $C$ só tem a $i_{1}'$-ésima coordenada diferente, segue que $a_{i_{1}}\neq b_{i_{1}}=c_{i_{1}}$. Além disso, como $A$ e $B$ só possuem a $i_1$-ésima coordenada diferente, segue que $a_{i_{1}'}=b_{i_{1}'}\neq c_{i_{1}'}$. Ou seja, $A$ e $C$ são diferentes nas posições $i_1$ e $i_{1}'$. Isto nos daria que a distância entre $A$ e $C$ é pelo menos $2$. Contradição. Logo $i_{1}=i_{1}'$.

Observe que, para todo elemento de $X$, as $1000$ primeiras coordenadas possuem três valores ($0$, $1$ e $2$) enquanto as últimas $1000$ possuem apenas dois ($0$ e $1$). Vamos mostrar que $a_{i_{1}}$ e $b_{i_{1}}$ se diferenciam em alguma das $1000$ primeiras coordenadas, isto é, $i_{1}\leq 1000$.

Suponha, por absurdo, que $i_{1}>1000$. Então $a_{i_{1}},b_{i_{1}}$ $c_{i_{1}}$ são três números distintos. Mas, nas últimas $1000$ coordenadas, só podemos ter dois valores: $0$ ou $1$. Absurdo. Logo $i_{1}\leq 1000$.

E como falar sobre uma das coordenadas de $f(0,a_{2}',a_{3}',\cdots ,a_{2000}')$ (para $a_{2}',a_{3}',\cdots ,a_{2000}'$ quaisquer) conhecendo $A, B$ e $C$? O que acontece é o seguinte: se $i_1$ for a coordenada em que $A, B$ e $C$ são distintos e $x_{0}=f(0,a_{2}',a_{3}',\cdots ,a_{2000}')=(x_{1},x_{2},\cdots ,x_{n})$, então $x_{i_{1}}=a_{i_{1}}$. Vamos provar isto.

Suponha, por absurdo, que $x_{i_{1}}$ não seja igual a $a_{i_{1}}$. Observe que $a_{i_{1}},b_{i_{1}}$ e $c_{i_{1}}$ são, em alguma ordem, $0,1$ e $2$. Se $x_{i_{1}}$ não é igual a $a_{i_{1}}$, então ele é igual a $b_{i_{1}}$ ou $c_{i_{1}}$. Suponha, sem perda de generalidade, que $x_{i_{1}}=b_{i_{1}}$.

Considere $m=d(A,x_{0})$. Vejamos quanto vale $d(B,x_{0})$ em função de $m$. Observe que $A$ e $x_0$ se diferenciam em $m$ coordenadas. Já $A$ e $B$ só se diferenciam em uma: a $i_1$-ésima coordenada. Mas nesta posição, as coordenadas de $B$ e $x_0$ coincidem. Logo, $B$ e $x_0$ se diferenciam em $m - 1$ coordenadas, ou seja, $d(B,x_{0})=m-1$.

Vamos pensar em $d(B,x_{0})$ de outra forma. Observe que

$m=d(A,x_{0})=d(f(0,0,0,\cdots ,0),f(0,a_{2}',a_{3}',\cdots ,a_{2000}'))=d((0,0,0,\cdots ,0),(0,a_{2}',a_{3}',\cdots ,a_{2000}')).$

Isto significa que $m$ dos valores $a_{2}',a_{3}',\cdots ,a_{2000}'$ são diferentes de zero. Daí

$d(B,x_{0})=d(f(1,0,0\cdots ,0),f(0,a_{2}',a_{3}',\cdots ,a_{2000}'))=d((1,0,0\cdots ,0),(0,a_{2}',a_{3}',\cdots ,a_{2000}'))=$

$=m+1,$

pois $B$ e $x_0$ se diferenciam na primeira coordenada e em outras $m$. Contradição. Logo, $x_{i_{1}}=a_{i_{1}}$.

Analogamente, se $f(1,a_{2}',a_{3}',\cdots ,a_{2000}')=(y_{1},y_{2},\cdots ,y_{n})$, então $y_{i_{1}}=b_{i_{1}}$. E finalmente, se $f(1,a_{2}',a_{3}',\cdots ,a_{2000}')=(z_{1},z_{2},\cdots ,z_{n})$, então $z_{i_{1}}=c_{i_{1}}$.

Fizemos isto para a primeira coordenada. Será que vale para as outras? Sim! Vamos pensar nas $1000$ primeiras coordenadas e depois nas $1000$ últimas. Considere

$A_{t}=f(0,0,\cdots ,0)=(a_{1},a_{2},\cdots ,a_{2000}),$

$B_{t}=f(0,0,\cdots ,0,\underbrace {1} _{t{\text{-ésima coordenada}}},0,\cdots ,0)=(b_{1},b_{2},\cdots ,b_{2000}),$

$C_{t}=f(0,0,\cdots ,0,\underbrace {2} _{t{\text{-ésima coordenada}}},0,\cdots ,0)=(c_{1},c_{2},\cdots ,c_{2000}),$

onde $t\leq 1000$. Se $f(x_{1},x_{2},\cdots ,x_{2000})=(y_{1},y_{2},\cdots ,y_{2000})$ e $i_t$ é a posição onde $A, B$ e $C$ são distintos, então $y_{i_{t}}=a_{i_{t}}$ se $x_{t}=0$; $y_{i_{t}}=b_{i_{t}}$ se $x_{t}=1$ e $y_{i_{t}}=c_{i_{t}}$ se $x_{t}=2$ (*). A prova disso é análoga à anterior.

Observe além disso que $i_{1},i_{2},\cdots ,i_{1000}$ são todos distintos. De fato, suponha, por absurdo, que existam $m$ e $n$ distintos tais que $i_{m}=i_{n}$. Observe que $A_{m}=A_{n}$. Como $d(A_{m},B_{m})=1$, segue que eles só se diferenciam na $i_m$-ésima coordenada, ou seja, eles coincidem nas outras $1999$. Além disso, $d(A_{m},B_{n})=d(A_{n},B_{n})=1$ de onde segue que eles só se diferenciam na $i_m$ coordenada e coincidem nas outras $1999$. Daí $B_{m}$ e $B_n$ se coincidem em pelo menos $1999$ coordenadas, ou seja, a distância entre eles é no máximo $1$. Isto é um absurdo, pois $d(B_{m},B_{n})=2$. Logo, todos os valores $i_{1},i_{2},\cdots ,i_{2000}$ são distintos.

Desta forma $i_{1},i_{2},\cdots ,i_{2000}$ é uma permutação de $1,2,\cdots ,1000$. Observe que se escolhermos uma permutação dessas e os valores de $a_{i_{t}},b_{i_{t}}$ e $c_{i_t}$, teremos determinado as $1000$ primeiras coordenadas de todas as imagens da função.

E quanto as $1000$ últimas coordenadas? Vejamos que o processo é parecido. Lembre-se que estas coordenadas só podem ser iguais a $0$ ou $1$. Para $j>1000$, podemos definir

$A_{j}=f(0,0,\cdots ,0)=(a_{1},a_{2},\cdots ,a_{2000}),$

$B_{j}=f(0,0,\cdots ,0,\underbrace {1} _{j{\text{-ésima coordenada}}},0,\cdots ,0)=(b_{1},b_{2},\cdots ,b_{2000}).$

Observe que

$d(A_{j},B_{j})=d(f(0,0,\cdots ,0),f(0,0,\cdots ,0,\underbrace {1} _{j{\text{-ésima coordenada}}},0,\cdots ,0))=$

$=d((0,0,\cdots ,0),(0,0,\cdots ,0,\underbrace {1} _{j{\text{-ésima coordenada}}},0,\cdots ,0))=1.$

Assim existe um único $t$ tal que $a_t$ e $b_t$ são diferentes. Vejamos que este $t$ é maior do que $1000$. Com efeito, suponha, por absurdo, que $t\leq 1000$. Como $i_{1},i_{2},\cdots ,i_{2000}$ é uma permutação de $1,2,\cdots ,1000$, segue que existe $w$ tal que $i_{w}=t$. Seja $k$ o valor da $i_{w}$-ésima coordenada de $A_w$. Como $A_{j}=f(0,0,\cdots ,0)$ e a $w$-ésima coordenada de $(0,0,\cdots ,0)$ é $0$, por $(*)$

$a_{t}=a_{i_{w}}=k.$

Da mesma forma, como $B_{j}=f(0,0,\cdots ,0,\underbrace {1} _{j{\text{-ésima coordenada}}},0,\cdots ,0)$ e a $w$-ésima coordenada de $(0,0,\cdots ,0,\underbrace {1} _{j{\text{-ésima coordenada}}},0,\cdots ,0)$ é $0$ (pois $w\leq 1000$), segue que, por $(*)$

$b_{t}=b_{i_{w}}=k.$

Assim $a_{t}=b_{t}$. Absurdo. Logo, $t>1000$. Vamos chamar este $t$ de $i_{j}$ (já que ele está relacionado com $A_j$ e $B_j$). Podemos falar das últimas $1000$ coordenadas de $f(x_{1},x_{2},\cdots ,x_{2000})$ a partir destes valores.

De fato, se $f(x_{1},x_{2},\cdots ,x_{2000})=(y_{1},y_{2},\cdots ,y_{2000})$, então $y_{i_{j}}=a_{i_{j}}$ se $x_{j}=0$ e $y_{i_{j}}=b_{i_{j}}$ se $x_{j}=1$. Isto pode ser provado de forma semelhante à que já fizemos.

Daí, para determinarmos as $1000$ coordenadas de $f(x_{1},x_{2},\cdots ,x_{2000})$ para quaisquer $x_{1},x_{2},\cdots ,x_{2000}$ precisamos escolher uma permutação de $i_{1001},\cdots ,i_{2000}$ de $1001,\cdots ,2000$ e as permutações $a_j, b_j$ de $0,1$ para $1001\leq j\leq 2000$.

Desta forma, para construirmos a função do enunciado, precisamos das seguintes escolhas:

• escolher uma permutação $i_{1},\cdots ,i_{1000}$ de $1,\cdots ,1000$. Isto pode ser feito de $1000!$ maneiras;
• escolher uma permutação $i_{1001},\cdots ,i_{2000}$ de $1001,\cdots ,2000$. Isto pode ser feito de $1000!$ maneira
• escolher permutaçãoes $a_{j},b_{j},c_{j}$ de $0,1,2$ para $1\leq j\leq 1000$. Cada permutação pode ser feita de $3!=6$ maneiras. Como existem $1000$ permutação, o total de escolhas aqui é $6^{1000}$;
• escolher permutações $a_j, b_j$ de $0,1$ para $1001\leq j\leq 2000$. Cada permutação pode ser feita de $2! = 2$ maneiras. Como existem $1000$ permutação, o total de escolhas aqui é $2^{1000}$.

Desta forma, o total de funções que satisfazem as condições do enunciado será $1000!\cdot 1000!\cdot 6^{1000}\cdot 2^{1000}=(1000!)^{2}\cdot 12^{1000}$.

Exemplo

Se $|X|=m$ e $|Y|=n$ com $n \ge m$, prove a quantidade de funções injetivas $f: X \to Y$ é ${\frac {n!}{(n-m)!}}$.

Solução: Considere $X=\{x_{1},x_{2},\cdots ,x_{m}\}$. É suficiente encontrarmos de quantas maneiras podemos escolher $f(x_{1}),f(x_{2}),\cdots ,f(x_{n})$ pois estes valores determinam a função por completo.

Observe que existem $n$ maneiras de determinarmos $f(x_1)$, já que ele pode ser igual a qualquer elemento de $Y$. E quanto a $f(x_2)$? Como $f$ é injetiva, elementos diferentes se "transformam" em elementos diferentes, ou seja, $f(x_2)$ deve ser diferente de $f(x_1)$. Assim existem $n-1$ maneiras para determinarmos $f(x_2)$.

Pelo mesmo raciocínio existem $n-2$ maneiras de escolhermos $f(x_{3})$ e assim por diante até $n-m+1$ maneiras de escolhermos $f(x_{m})$.

Desta forma, pelo Princípio Multiplicativo, a quantidade de funções injetivas é

$n(n-1)(n-2)\cdots (n-m+1)={\frac {n!}{(n-m)!}}.$

Formalização da Combinatória

Para que a combinatória fique mais organizada e mais coerente, é útil usarmos conjuntos .

Aqui usaremos $|X|$ para representar a quantidade de elementos de um conjunto $X$.

Em textos mais comuns de combinatória, é comum considerarmos para $n$ inteiro positivo.

$[n]=\{1,2,\dots ,n\}.$

Princípio Aditivo (ou Princípio da Adição)

Se $A \cap B = \emptyset$, então

$|A\cup B|=|A|+|B|.$

Podemos generalizar esta regra para uma quantidade maior de conjuntos. De fato, se $A_1,A_2,\dots,A_n$ são dois a dois disjuntos, então

$|A_1 \cup A_2 \cup \dots \cup A_n| = |A_1|+|A_2|+\dots+|A_n|.$

Princípio Fundamental da Contagem (ou Princípio Multiplicativo ou Princípio da Multiplicação ou Princípio Fundamental da Enumeração)

Se $A\times B=\{(a,b):a\in A{\text{ e }}b\in B\}$, então

$|A\times B|=|A||B|.$

Podemos generalizar esta regra para uma quantidade maior de conjuntos. De fato,

$|A_{1}\times A_{2}\times \dots \times A_{n}|=|A_{1}||A_{2}|\dots |A_{n}|.$

Permutações

O número de permutações de $[n]$ é $n!$.

Combinações

Se um conjunto possui $n$ elementos, então a quantidade de subconjuntos dele que possuem $k$ elementos é ${n \choose k}$.

Onde Praticar?

Para saber Contagem é legal praticar bastante. Mas por onde?

• Para começar é legal a apostila "Métodos de Contagem e Probabilidade" do autor Paulo Cezar Pinto Carvalho que pode ser encontrada aqui. Existem vários exercícios resolvidos aqui.
• Se você terminou e quer praticar mais ainda, pode usar o livro "Análise Combinatória e Probabilidade" dos autores Augusto César Morgado, João Bosco Pitombeira de Carvalho, Paulo Cezar Pinto Carvalho e Pedro Fernandez. Também existem vários exercícios resolvidos.

Lugares Para Estudar

• Contagem I (POTI - Nível 2)
• A aula do POTI - Nível 2: Arquivo:Problemas Resolvidos - Contagem I.pdf
• Contagem II (POTI - Nível 2)
• A aula do POTI - Nível 2: Arquivo:Problemas Resolvidos - Contagem II.pdf
• Problemas Resolvidos: Contagens Elementares (POTI - Nível 2)
• A aula do POTI - Nível 3: Arquivo:Aula 01 - Contagem.pdf
• A aula da Semana Olímpica de 2001: Combinatória (Paulo José).
• A aula da Semana Olímpica de 2014: Contagens Elementares (Samuel Barbosa).
• A aula da Semana Olímpica de 2017: Contagens Elementares (Samuel Barbosa)
• A aula da Semana Olímpica de 2019: Princípio Multiplicativo (Kellem Santos)
• A aula da Semana Olímpica de 2019: Métodos em Contagens (Gustavo Empinotti)

Vídeos

• Contagem I (POTI - Nível 2)
• Contagem II (POTI - Nível 2)
• Permutações (POTI - Nível 2)
• Contagens Elementares: Princípio Aditivo e Multiplicativo (POTI - Nível 3)
• O Princípio Multiplicativo (POTI 2017)
• Permutações (POTI 2017)
• Permutações com Restrições (POTI 2017)
• Anagramas (POTI 2017)
• Aplicações do Princípio Multiplicativo I (POTI 2017)
• Aplicações do Princípio Multiplicativo II (POTI 2017)

Bibliografia

• E. Lozansky, C. Rousseau : Winning Solutions, Springer-Verlag, New York, 1996.
• MORGADO, Augusto César; CARVALHO, João Bosco Pitombeira de; CARVALHO, Paulo Cezar Pinto; FERNANDEZ, Pedro. Análise Combinatória e Probabilidade: com as soluções dos exercícios. Rio de Janeiro: SBM, 2006. 383 p. ISBN 978-85-85-85818-01-2.