Gostaria de compartilhar uma questão interessante que achei por aí.
Suponha que em uma sacola você possa colocar [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?
Ensino Médio ⇒ Análise combinatória
Moderador: [ Moderadores TTB ]
-
- Mensagens: 847
- Registrado em: Sáb 18 Mar, 2017 17:30
- Última visita: 02-03-22
Jun 2017
11
14:03
Análise combinatória
Última edição: Andre13000 (Dom 11 Jun, 2017 14:03). Total de 1 vez.
“Study hard what interests you the most in the most undisciplined, irreverent and original manner possible.” -Richard Feynman
-
- Mensagens: 1483
- Registrado em: Dom 02 Ago, 2015 13:51
- Última visita: 30-09-22
Jun 2017
14
22:07
Re: Análise combinatória
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?
Ocupado com início do ano no ITA. Estarei fortemente inativo nesses primeiros meses do ano, então busquem outro moderador para ajudar caso possível.
-
- Mensagens: 847
- Registrado em: Sáb 18 Mar, 2017 17:30
- Última visita: 02-03-22
Jun 2017
18
15:25
Re: Análise combinatória
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]
Para maçãs: [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]
Para laranjas: [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] , 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.
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]
Para maçãs: [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]
Para laranjas: [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] , 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.
Última edição: Andre13000 (Dom 18 Jun, 2017 15:25). Total de 1 vez.
“Study hard what interests you the most in the most undisciplined, irreverent and original manner possible.” -Richard Feynman
-
- Mensagens: 1483
- Registrado em: Dom 02 Ago, 2015 13:51
- Última visita: 30-09-22
Jun 2017
18
16:34
Re: Análise combinatória
Eu conhecia o processso de contar as soluções de [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
Última edição: undefinied3 (Dom 18 Jun, 2017 16:34). Total de 1 vez.
Ocupado com início do ano no ITA. Estarei fortemente inativo nesses primeiros meses do ano, então busquem outro moderador para ajudar caso possível.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 1 Respostas
- 1904 Exibições
-
Última msg por csmarcelo
-
- 1 Respostas
- 2018 Exibições
-
Última msg por Leandro2112
-
- 2 Respostas
- 1510 Exibições
-
Última msg por nedved10
-
- 2 Respostas
- 1229 Exibições
-
Última msg por encucado
-
- 1 Respostas
- 1413 Exibições
-
Última msg por encucado