Pular para o conteúdo principal

Equações lineares com coeficientes unitários

Consideremos o seguinte problema: de quantos modos podemos distribuir 5 bombons idênticos em 2 caixas diferentes? Para responder a essa pergunta, vamos conhecer mais uma aplicação da análise combinatória: as equações lineares com coeficientes unitários.



Quando falamos desse tipo de equação, estamos nos referindo a equações do tipo x1 + x2 + ... + xr = m, com m > 0. Em nosso caso, estamos interessados em encontrar o número de soluções inteiras positivas para essa equação.


No caso de nosso exemplo, onde temos cinco bombons para serem distribuídos em duas caixas diferentes, podemos simbolizar a primeira caixa por x1 e a segunda por x2 formando, assim, a equação linear x1 + x2 = 5. Conforme podemos ver na tabela abaixo, no conjunto dos números inteiros, essa equação possui infinitas soluções:
































x1...-10123456...
x2...6543210-1...

Perceba que a soma de cada valor da primeira linha com seu respectivo valor da segunda linha (aquele que está em baixo) resulta em exatamente 5. Se, no entanto, formos transpor esse modelo para o mundo material - como o caso dos bombons - apenas as soluções com números inteiros positivos vão nos servir (pois não há como alguém colocar -2 bombons em uma caixa). Neste caso, é fácil perceber que o número de soluções passa a ser finito: se x1 vale 0, x2 vale 5; x1 vale 1, x2 vale 4 e assim por diante. No caso desta equação, as soluções inteiras positivas são pares ordenados que somam 11 (se tivéssemos um x3 seriam triplas ordenadas).


Mas como podemos contar o número de soluções inteiras positivas que a equação possui, já que seu número é finito?


Vamos começar olhando para o resultado da equação, a saber: 5. Obviamente, podemos escrever esse 5 como a soma de cinco números 1:


1 + 1 + 1 + 1 + 1 = 5


O que queremos fazer é separar esse 5 na soma de duas parcelas positivas. Para isso, podemos introduzir algum símbolo, como uma barra vertical, entre os 1's da solução acima:


1 + 1  | + 1 + 1 + 1 = 5


1 + 1 + 1 + 1 | + 1 = 5


E assim por diante. Perceba que cada maneira diferente que escolhemos onde colocar a barra nos fornecerá uma solução para a equação x1 + x2 = 5. Nos exemplos acima, a primeira solução equivale a x1 = 2 e x2 = 3 e a segunda corresponde a x1 = 4 e x2 = 1 . Perceba que o número de barras que introduzimos é uma unidade menor do que o número de soluções que procuramos: se estivéssemos procurando por três soluções, introduziríamos duas barras pois, assim, a soma de 1's teria três "divisões".


Para valores pequenos, como os mostrados acima, pode ser até fácil e divertido ficar colocando barras em vários lugares e contando o total, mas para equações que exijam um número muito grande de soluções - ou cujo resultado não seja tão fácil de escrever como soma de 1's como 5 -, é necessário procurar por um método mais eficiente.


Felizmente, graças a um teorema da Análise combinatória, sabemos que o número de soluções de uma equação da forma x1 + x2 + ... + xr = m, com m > 0. pode ser calculado por Cm-1r-1. A demonstração segue a ideia de escrevermos o resultado r como uma soma de 1's, onde o valor de x1 corresponde ao número de 1's que antecedem a primeira barra, o valor de x2 ao de 1's que antecede a segunda barra e assim por diante, até o valor de xr que corresponde à quantidade de números 1's à direita da barra r-1. Como cada distribuição possível corresponde a uma única solução, basta contarmos de quantas formas podemos fazê-lo, o que pode ser calculado a partir da fórmula enunciada.


Assim, o número de soluções inteiras para a equação que motivou este artigo é C41 = 4, que confere com a tabela anterior.


Note que as soluções calculadas acima desconsideram o 0, que a rigor não é considerado um número positivo nem negativo. Mas e se quisermos contar as soluções que contém 0? Neste caso teremos de nos utilizar de um artifício o qual veremos no próximo artigo.

Comentários

  1. muito bom esse material. relevante o suficiente para suprimir algumas dúvidas. obrigado!!!!!

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Como acessar configurações avançadas no Sagemcom F@st 2704N

NOVO TUTORIAL: GUIA DEFINITIVO DAS CONFIGURAÇÕES AVANÇADAS DO SAGEMCOM F@ST 2704N!
Atualização 23/01/2015: Alguns problemas apontados e descobertos nesse modem:
1. Alguns usuários relatam dificuldade em salvar alterações na configuração ADSL;
2. Não sei como acessar os logs do modem; mesmo habilitando, eles não aparecem;
3. Se você trocar o DNS do modem, ele voltará ao da Oi ao ser reiniciado;
4. Estou enfrentando alguns problemas sérios de lentidão. Não sei se isso é relacionado ao modem ou a algum dispositivo na minha rede interna.
-----
Os modens da marca Sagemcom estão se tornando muito populares no Brasil, não, quiçá, por sua qualidade, mas porque eles são os atuais queridinhos das operadoras: quando você assina um plano ADSL, geralmente a operadora envia um modem wireless para sua casa a fim de que você possa navegar sem precisar ter gastos extras com esse equipamento. É claro que os equipamentos fornecidos pelas operadoras são básicos, mas saciam as necessidades dos usuários comuns - …

O Guia Definitivo das configurações avançadas no Sagemcom F@st 2704N

Há alguns meses, eu contei minha experiência com o Sagemcom F@st 2704N e tenho recebido diversos comentários sobre suas configurações avançadas. Agora que minhas aulas na faculdade estão acabando, resolvi reservar um tempinho para explorar melhor esse modem que, diga-se de passagem, é muito bom.