IME / ITA ⇒ Análise Combinatória: Combinações Completas Tópico resolvido

[ALDRINMOD]

Um feiticeiro vai comprar os ingredientes que sua esposa bruxa precisa para preparar uma poção mágica. Ele tem cem reais para fazer as compras numa loja de artigos estranhos. A loja vende rabo de morcego por cinco reais o pedaço, unhas de lagartixa por cinco reais o pedaço, olhos de salamandra por cinco reais a unidade e sangue de novilho por vinte reais o litro. Calcular o número de maneiras distintas que a compra poderá ser feita com os cem reais do feiticeiro. Divida o resultado por [tex3]13[/tex3].
Obs.: Os ingredientes não podem ser subdivididos.

Resposta:

---

[tex3]41[/tex3]

[Karl Weierstrass]

Sejam [tex3]x,\,y,\,z[/tex3] e [tex3]w[/tex3], respectivamente, o número de pedaços de rabo de morcego, o número pedaços de unha de largatixa, o número de olhos de salamandra e o número de litros de sangue de novilho.

O número de maneiras de fazer a compra é dado pelo número de soluções inteiras não negativas da equação

[tex3]\hspace{70pt}5x\,+\,5y\,+\,5z\,+\,20w\,=\,100[/tex3]

Simplificando, obtemos

[tex3]\hspace{70pt}x\,+\,y\,+\,z\,+\,4w\,=\,20[/tex3]

Fazendo [tex3]t\, =\,4w[/tex3], vem

[tex3]\hspace{70pt}x\,+\,y\,+\,z\,+\,t\,=\,20[/tex3]

Como [tex3]w \in \{0,\,1,\,2,\,3,\,4,\,5\},[/tex3] [tex3]t \in \{0,\,4,\,8,\,12,\,16,\,20\}[/tex3].

Assim, o resultado procurado é a soma do número de soluções inteiras não negativas das equações:

[tex3]\hspace{70pt}x\,+\,y\,+\,z\,=\,20\\

\hspace{70pt}x\,+\,y\,+\,z\,=\,16\\

\hspace{70pt}x\,+\,y\,+\,z\,=\,12\\

\hspace{70pt}x\,+\,y\,+\,z\,=\,8\\

\hspace{70pt}x\,+\,y\,+\,z\,=\,4\\

\hspace{70pt}x\,+\,y\,+\,z\,=\,0\\[/tex3]

Sabendo que o número de soluções inteiras não negativas de uma equação da forma

[tex3]\hspace{70pt}x_1\,+\,x_2\,+\,\cdots\,+\,x_n\,=\,p,[/tex3]

é dado por [tex3]CR_{n,\,p}\,=\,C_{n+p-1,\,p},[/tex3] concluímos que existem [tex3]536[/tex3] maneiras de efetuar a compra dos ingredientes. Logo, [tex3]\frac{536}{13}\,\approx\,41.[/tex3]

Obs.: [tex3]CR_{n,p}\,=\,C_{n+p-1,\,p},[/tex3] é o número de combinações completas de [tex3]n[/tex3] objetos de classe [tex3]p[/tex3].