Mauro Munsignatti Jr.
Colégio técnico de Campinas - cotuca

A Análise Combinatória é um dos assuntos que mais dificuldades apresentam para os alunos no ensino médio. Saber apenas fórmulas de arranjo, combinação, etc. não é suficiente. O principal no estudo desse assunto é o raciocínio.

Dentre os variados problemas que envolvem a Análise Combinatória, há um grupo que pouquíssimos livros didáticos do ensino médio costumam abordar, mas que tem aparecido nos principais vestibulares do país: são problemas que exigem calcular o número de soluções inteiras não negativas de determinada equação.

Vejamos um exemplo: calcular o número de soluções inteiras e não negativas da equação x1 + x2 + x3 = 4. Para resolver, podemos listar todas as soluções e contar quantas são. A tabela mostra que a equação possui 15 soluções inteiras e não negativas.

Porém, se tivéssemos que contar “na mão” o resultado para a equação x1 + x2 + x3 + x4 = 8, por exemplo, com certeza o processo seria trabalhoso demais. Assim, uma maneira prática para resolver esse tipo de problema é o que mostramos a seguir, considerando novamente a equação x1 + x2 + x3 = 4. Podemos representar cada uma das soluções anteriores como na tabela. Note que cada sinal “+” tem a função de separar as quantidades relativas para x1, x2 e x3. Também é possível observar o seguinte: todas as soluçõesrepresentadas são anagramas da “palavra”····++, ou seja, uma palavra de 6 letras, sendo 4 do tipo “·” e 2 do tipo “+”. Assim, o número de anagramas dessa palavra é igual a = 15, que confere com a listagem que fizemos. Nooutro exemplo acima: “qual o número de soluções inteiras e não negativas da equação x1 + x2 + x3 + x4 = 8?”, temos que o número de soluções será igual ao número de anagramas da palavra ········+++, que é igual a: = = 165.

Podemos generalizar o seguinte resultado: o número de soluções inteiras e não negativas da equação x1 + x2 + ... + xn = p é igual a , pois será o número de anagramas da “palavra”

Assim, esse tipo de problema, aplicado em diferentes situações, pode ser resolvido usando a ideia de anagramas, que é uma aplicação de permutação com repetição.

O problema a seguir envolve o mesmo raciocínio, mas com uma pequena diferença.

Problema 1 (UEL-2004)

Numa competição internacional, um país obteve, no total, 10 medalhas dentre as de ouro, prata e bronze. Sabendo-se que esse país recebeu pelo menos uma medalha de ouro, uma de prata e uma de bronze, quantas são aspossibilidades de composição do quadro de medalhas do país?

a) 10       b)       30       c) 36       d) 120       e) 132

Resolução

Sendo x o número de medalhas de ouro, y o de prata e z o de bronze, temos que contar quantas são as soluções da equação x + y + z = 10, porém, não a quantidade de soluções inteiras e não negativas, e sim, soluções inteiras e positivas, pois sabe-se que esse país recebeu pelo menos uma medalha de cada tipo, ou seja, x 1, y 1 e z 1. Assim, podemos resolver o problema da seguinte forma: seja x = x’ + 1, y = y’ + 1 e z = z’ + 1, onde x’, y’ e 'z’ são números inteiros que podem assumir valores positivos ou também ovalor zero. Isso nos garante que cada uma das incógnitas x, y e z será um valor positivo. Fazendo essa troca de variável, temos:

x + y + z = 10
Þ x’ + 1 + y’ + 1 + z’ + 1 = 10
Þ x’ + y’ + z’ = 7.

A solução do problema será, agora sim, o número de soluções inteiras e não negativas da equação x’ + y’ + z’ = 7, que é igual ao número de anagramas da palavra ·······++, que é igual a: = 36.

O próximo problema é interessante pelas suas duas soluções com raciocínios bem diferentes.

Problema 2 (UFRJ-2000)

Uma estante de biblioteca tem 16 livros: 11 exemplares do livro Combinatória é fácil e 5 exemplares de Combinatória não é difícil. Considere que os livros com mesmo título sejam indistinguíveis. Determine de quantas maneiras diferentes podemos dispor os 16 livros na estante de modo que dois exemplares de Combinatória não é difícil nunca estejam juntos.

Resolução

Quando fui apresentado a esse problema pela primeira vez, resolvi da seguinte forma: colocarei, primeiro, os 11 exemplares do livro Combinatória é fácil na estante. Para que dois exemplares de Combinatória não é difícil nunca estejam juntos, devo escolher 5 lugares dentre os 12 espaços que surgem na estante representados pelo símbolo , após ter colocado os 11 livros iniciais. Veja o esquema abaixo: livro: Combinatória é fácil

Assim, a resposta seria: C12,5 = = 792 maneiras.

Porém, depois de um tempo, passei esse exercício a um amigo meu, Luiz Roberto Rosa, e ele apresentou a seguinte resolução, que achei bastante interessante: colocamos, inicialmente, os 5 exemplares de Combinatória não é difícil na estante. Fazendo isso, surgem na estante 6 lugares, também representadospelo símbolo :

Assim, para satisfazer o problema, devemos distribuir os 11 exemplares do livro Combinatória é fácil nos 6 espaços que surgem (é claro, cada espaço pode receber mais de 1 livro), com a condição de que os 4 espaços centraisrecebam pelo menos 1 livro. Isso pode ser traduzido em: qual é o número de soluções não negativas da equação x1 + x2 + x3 + x4 + x5 + x6 = 11, porém com x2 1, x3 1, x4 1 e x5 1 (pois sem essa restrição não garantiríamos que 2 exemplares de Combinatória não é difícil não fi carão juntos). Fazendo a troca das variáveis: x2 = x2’ + 1, x3 = x3’ + 1, x4 = x4’ + 1, x5 = x5’ + 1, obtemos:

x1 + x2 + x3 + x4 + x5 + x6 = 11

Þ x1 + x2’ + 1 + x3’ + 1 + x4’ + 1 + x5’ + 1 + x6 = 11

Þ x1 + x2’ + x3’ + x4’ + x5’ + x6 = 7

Assim, a resposta do problema proposto é igual ao número de soluções inteiras e não negativas da equação acima, que é igual ao número de anagramas da palavra ·······+++++ = = 792, conferindo com o resultado obtido na 1 maneira.

Para terminar, deixo para o leitor mais alguns problemas desse tipo com suas respostas.

Problema 3 (IBMEC - SP - 2003)

Um empresário precisa comprar um total de 12 automóveis para sua empresa. Os modelos selecionados: Honda Civic, Astra, Toyota Corolla e Santana. Sabendo-se que podem ser comprados de zero a 12 veículos de cada marca, de quantas maneiras o empresário poderá adquirir os 12 automóveis?

Problema 4 (UNICAMP - 1998)

a) De quantas maneiras é possível distribuir 20 bolas iguais entre 3 crianças de modo que cada uma delas receba, pelo menos, 5 bolas?

b) Supondo que essa distribuição seja aleatória, qual a probabilidade de uma delas receber      exatamente 9 bolas?

Problema 5 (UNICAMP - 2005)

Com as letras x, y, z e w podemos formar monômios de grau k, isto é, expressões do tipo xp yq zr ws, sendo p, q, r e s inteiros não negativos com p + q + r + s = k. Quando um ou mais desses expoentes são iguais a zero, dizemos que o monômio é formado pelas demais letras. Por exemplo, y3 z4 éum monômio de grau 7 formado pelas letras y e z (nesse caso, p = s = 0).

a) Quantos monômios de grau 4 podem ser formados com, no máximo, quatro letras?

b) Escolhendo-se ao acaso um desses monômios do item a), qual a probabilidade de ele ser      formado por exatamente duas das quatro letras?

Problema 6 (FUVEST - 2010)

Seja n um inteiro, n 0.

a) Calcule de quantas maneiras distintas n bolas idênticas podem ser distribuídas entre Luís e      Antônio.

b) Calcule de quantas maneiras distintas n bolas idênticas podem ser distribuídas entre Pedro,  Luís e Antônio.

c) Considere, agora, um número natural k tal que 0 k n. Supondo que cada uma das distribuições do item b) tenha a mesma chance de ocorrer, determine a probabilidade de que, após uma dada distribuição, Pedro receba uma quantidade de bolas maior ou igual a k.

Obs.: Nos itens a) e b), consideram-se válidas as distribuições nas quais uma ou mais pessoas não recebam bola alguma.

Respostas dos problemas de 3 a 6:

3) 455     4) a) 21     b) 2/7     5) a) 35     b) 18/35
6) a) n + 1      b) (n + 2)(n + 1)/2      c) (n – k +2)(n – k +1)/(n +1)(n + 2)