FANDOM


Sim, nesta aula iremos aprender a contar! Eu sei o que você está pensando: “Ah, mas eu já sei contar: $ 1,2,3,\cdots $”. Mas o tipo de contagem que você faz é o seguinte: você olha para uma lista de coisas e conta cada um delas. Por exemplo, você tem as seguintes pessoas em uma fila: Ana, Beatriz, Carlos e Daniel. Você quer contar quantas pessoas tem, basta olhar para elas e dizer: $ 1 $, $ 2 $, $ 3 $ e $ 4 $.

Nesta aula iremos fazer coisas mais legais do que isso: iremos contar coisas sem precisar saber exatamente quem elas são! Como assim? Veja o seguinte exemplo.

ExemploEditar

Ranimilbus quer se vestir para ir passear. Ele tem que escolher entre três camisetas (azul, branca e cinza) e duas calças (verde e roxa). De quantas maneiras ele pode se vestir?

Solução: Já que ainda estamos começando com o assunto, vamos ver cada uma das possibilidades que ele pode se vestir. Que tal começar com uma tabela?

VerdeRoxa
AzulAzul e VerdeAzul e Roxa
BrancaBranca e VerdeBranca e Roxa
CinzaCinza e VerdeCinza e Roxa

Pela tabela, existem $ 6 $ maneiras de se vestir. Mas repare que poderíamos saber quantas maneiras ele tem de se vestir sem precisar saber quais são as roupas: bastaria termos multiplicado $ 3 $ por $ 2 $. É exatamente aí que estão as vantagens das técnicas de contagem: contar precisar saber exatamente quais são os objetos.

ObservaçãoEditar

Em geral, problemas de contagem são da forma: "de quantas maneiras podemos...".

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

Se tivermos

  • $ x $ maneiras de fazermos uma escolha $ 1 $
  • $ y $ modos de fazermos uma escolha $ 2 $,

então existem $ x+y $ possibilidades para escolhermos $ 1 $ ou $ 2 $.

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

Se tivermos

  • $ x $ maneiras de fazermos uma escolha $ 1 $
  • $ y $ modos de fazermos uma escolha $ 2 $,

então existem $ x\times y $ possibilidades para escolhermos $ 1 $ e $ 2 $.

Dicas para Problemas de Contagem Editar

  • 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.
  • Veja se você não se esqueceu de nenhum.
  • Veja se você contou algum objeto que não deveria.
  • 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.

ExemploEditar

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) Editar

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

Fatorial Editar

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

$ n!=n.(n-1)\dots.2.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 $

Permutações SimplesEditar

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:

Permutação

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

Permutação 1

Existem ainda outras permutações:

Permutação 2

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) Editar

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:

OBM2013q1n2

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

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

Solução:

(a)

OBM2013q1n21
(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.2.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. $

Anagramas Editar

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 Editar

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 $. 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 Editar

(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} $;

ExemploEditar

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}. $

ExemploEditar

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)Editar

Obm2003q1n2

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 $?

(b) Quantos tabuleiros diferente existem no total?

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) Editar

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

OBM2009q1n21

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.

OBM2009q1n22

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

OBM2009q1n23

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

A figura abaixo mostra as peças duplas.

OBM2009q1n24

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

OBM2009q1n25
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:

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

OBM2009q1n27-0

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 \neq 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:

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

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

Contou Alguém Mais de Uma Vez? Editar

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) Editar

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?
OBM2005q1n2

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.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.200=400 $.

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

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:

OBM2000q6n3

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.

OBM2000q6n31

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

OBM2000q6n32

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:

OBM2000q6n33

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.

Certas Características Determinam por Completo o Objeto que Você Deseja Contar Editar

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

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.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 (OBM 2000 - 3ª Fase - Nível 3)Editar

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} $.

Formalização da Combinatória Editar

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) Editar

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) Editar

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 Editar

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

CombinaçõesEditar

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

Onde Praticar? Editar

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.

Bibliografia Editar

  • 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.
O conteúdo da comunidade está disponível sob CC-BY-SA salvo indicação em contrário.