Contagem

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

Princípio Aditivo

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)

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

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

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$

Permutações

O número de permutações de $n$ objetos é $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.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.$

Combinação

O número de maneiras de escolhermos $p$ dentre $n$ objetos (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_{p}^{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$ ?

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

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.{7 \choose 4}=105$ .

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

Contou Duas Vezes a Mais? Divida por 2

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.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 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.49=4900$ maneiras? Não.