Ensino Médio ⇒ Análise combinatória

[Andre13000]

Gostaria de compartilhar uma questão interessante que achei por aí.

Suponha que em uma sacola você possa colocar [tex3]n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n[/tex3]

frutas. Você dispõe de 4 tipos de fruta - banana, maçã, laranja e uva - dos quais:

1. o número de bananas na sacola deve ser um múltiplo de 5;
2. o número de maçãs na sacola deve ser par;
3. o número de uvas na sacola deve ser de no máximo 4; e
4. o número de laranja na sacola deve ser de no máximo 1.

De quantos modos diferentes as frutas podem ocupar a sacola?

[undefinied3]

Cara, tentei montar uma equação de recorrência e não consegui, tentar achar um padrão que desse pra formular uma hipótese sobre a fórmula em função de n e não consegui, tentei encontrar um equivalente de uma fruta em outra mas a laranja sempre me ferrava a vida, isso quando não era a uva. Você tem a solução?

[Andre13000]

O caminho é usar funções geradoras.

Considere por exemplo, que temos 1 banana. A quantidade de modos diferentes que podemos organizá-la na sacola é zero, pois não pode ter apenas uma banana. Mas agora tome 5 bananas. Tem um jeito de organizá-las. E o mesmo vale para todos os múltiplos de 5. E não esquecendo que se você tiver 0 bananas, tem um jeito ajeitá-las por convenção (pelo mesmo motivo que 0 fatorial é um).

A função geradora para bananas: [tex3]1+x^5+x^{10}+\dots=\frac{1}{1-x^5}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]1+x^5+x^{10}+\dots=\frac{1}{1-x^5}[/tex3]

Para maçãs: [tex3]1+x^2+x^4+\dots=\frac{1}{1-x^2}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]1+x^2+x^4+\dots=\frac{1}{1-x^2}[/tex3]

Para uvas: [tex3]1+x+x^2+x^3+x^4=\frac{1-x^5}{1-x}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]1+x+x^2+x^3+x^4=\frac{1-x^5}{1-x}[/tex3]

Para laranjas: [tex3]1+x=1+x[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]1+x=1+x[/tex3]

Se multiplicar as quatro séries, você obtém que [tex3]f(x)=1+2x+3x^2+~\dots[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]f(x)=1+2x+3x^2+~\dots[/tex3]

, ou seja, podemos organizar as frutas de n+1 modos.
Aqui tem mais informações: https://ocw.mit.edu/courses/electrical- ... s/ln11.pdf

Esse truque de multiplicar as séries é sustentada por uma tal lei de convolução, que para mim, não faz muito sentido.

[undefinied3]

Eu conhecia o processso de contar as soluções de [tex3]a_1x_1+a_2x_2+...+a_nx_n=p[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]a_1x_1+a_2x_2+...+a_nx_n=p[/tex3]

por solução geradora, mas a maneira de restringir o caso da uva e da laranja eu não sabia. Em vez de definir uma função infinita, vamos apenas até o expoente máximo, faz todo sentido. Não tinha pensado nisso