FANDOM


O método das bolas e divisórias (também conhecido como método pau-bola) é um método que permite calcular o número de soluções da equação $ x_1+x_2+...+x_n=p $ , onde $ n $ e $ p $ são inteiros positivos fixados e devemos ter $ x_1, x_2,..., x_n $ inteiros não-negativos.

Por meio de uma contagem dupla, acha-se que o número de soluções inteiras não-negativas de $ x_1+x_2+...+x_n=p $ é igual ao número de combinações completas de $ n $ tomados $ p $ a $ p $, que é $ {n+p-1\choose p} $.

Já o número de soluções positivas dessa mesma equação será $ {p-1\choose n-1} $.

Exemplo (OBM 2012 - 3ª Fase - Nível 2) Editar

Muitas pessoas conhecem a famosa sequência de Fibonacci, mas o que muita gente não sabe é que na mesma época um matemático brasileiro criou as sequências de Somanacci. Essas sequências são geradas a partir de três termos inicias inteiros positivos menores que $ 2012 $. Diferente do que acontece na sequência de Fibonacci, cada termo de uma sequência de Somanacci é a soma de todos os termos anteiores. Quantas sequência de Somanacci distintas possuem o número $ 2012 $ em alguma posição?

Solução: Sejam $ a_1,a_2,a_3,\dots $ os termos desta sequência. Seja $ p $ um número tal que $ a_p=2012 $. Como $ a_1, a_2 $ e $ a_3 $ são menores que $ 2012 $, segue que $ p \geq 4 $. Conseguimos relacionar $ a_p $ com termos menores?

Para isto, uma maneira de começarmos é procurarmos alguma maneira de relacionarmos um termo com o anterior? Observe que, pela definição da sequência:

$ a_n=a_{n-1}+a_{n-2}+\dots+a_2+a_1 (*) $

$ a_{n-1}=a_{n-2}+\dots+a_2+a_1 (**) $.

Se substituirmos $ (**) $ em $ (*) $:

$ a_n=2a_{n-1} $.

Assim,

$ a_n=2a_{n-1}=2^2a_{n-2}=\dots=2^{n-4}a_4 $.

(Não continuamos até o $ a_1 $, pois esta sequência é gerada pelos três termos anteriores).

Observe que para $ n $ grande, a fatoração em primos de $ a_n $ possui o $ 2 $ com um expoente grande. Então $ a_p $ não pode ser tão grande assim. Observe que $ 2012=2^2.503 $. Então

$ a_p=2012 \Leftrightarrow 2^{p-4}.a_4 =2^2.503 $,

de onde segue que $ p-4 \leq 2 $, ou seja, $ p \leq 6 $. Com isso, os possíveis valores de $ p $ são $ 4,5 $ e $ 6 $. Vamos analisar cada um dos casos.

(i) $ p=4 $

Aqui,

$ a_4=2012 \Leftrightarrow a_1+a_2+a_3=2012 $.

Os números $ a_1,a_2 $ e $ a_3 $ podem ser escolhidos livremente. O número de maneiras de escolhermos-os é

$ {2012-1\choose 3-1}={2011\choose 2}=\frac{2011.2010}{2}=2021055 $.

(ii) $ p=5 $

Observe que

$ a_5=2a_4=2(a_1+a_2+a_3) \Leftrightarrow a_1+a_2+a_3=\frac{2012}{2}=1006 $.

O número de soluções deste caso é $ {1006-1\choose 3-1}=\frac{1005.1004}{2}=504510 $.

(iii) $ p=6 $

Neste caso

$ a_6=4a_4=4(a_1+a_2+a_3) \Leftrightarrow a_1+a_2+a_3=\frac{2012}{4}=503 $.

O número de soluções deste caso é $ {503-1\choose 3-1}=\frac{502.501}{2}=125751 $.

Portanto, o total de sequências é $ 2021055+504510+125751=2651316 $.