Dados de Deus: Solução do 5° desafio

segunda-feira, 21 de março de 2011

Solução do 5° desafio

Consideremos a versão generalizada do problema, em que [;n;]

[;n;]

é o número de marinheiros, $[;a_{k};]$ é a quantidade de moedas surrupiadas pelo k-ésimo homem, [;m;]

[;m;]

é a quantia de moedas que sobram a cada roubo, [;a;]

[;a;]

corresponde à quantidade de moedas na última divisão e [;N;]

[;N;]

é o total no início.

Podemos escrever as seguintes equações para cada um dos marinheiros:

$[;N=na_{1}+m;]$

$[;N-a_{1}-m=na_{2}+m;]$

$[;N-a_{2}-m=na_{3}+m;]$

.

.

.

$[;N-a_{n-1}-m=na_{n}+m;]$

$[;N-a_{n}-m=na_{a}+m;]$

O que é equivalente a:

$[;N=na_{1}+m;]$

$[;(n-1)a_{1}=na_{2}+m;]$

$[;(n-1)a_{2}=na_{3}+m;]$

.

.

.

$[;(n-1)a_{n-1}=na_{n}+m;]$

$[;(n-1)a_{n}=na+m;]$

Esse sistema possui n+1 equações e n+2 incógnitas, o que significa que N ficará em função de um parâmetro, digamos [;a;]

[;a;]

. Para resolvermos, multiplicamos a k-ésima equação por $[;(\frac{n}{n-1})^k;]$ , da seguinte forma:

$[;N=na_{1}+m;]$

$[;(n-1)a_{1}=na_{2}+m;]$ $[;(\frac{n}{n-1});]$

$[;(n-1)a_{2}=na_{3}+m;]$ $[;(\frac{n}{n-1})^2;]$

.

.

.

$[;(n-1)a_{n-1}=na_{n}+m;]$ $[;(\frac{n}{n-1})^n;]$

$[;(n-1)a_{n}=na+m;]$ $[;(\frac{n}{n-1})^{n+1};]$

Somando todas as equações acima, obtemos:

$[;N=\frac{n^{n+2}}{(n-1)^{n+1}}a\ +\ m(1+\frac{n}{n-1}+\ ...\ +(\frac{n}{n-1})^{n+1});]$

Aplicando a fórmula da P.G.:

$[;N=\frac{n^{n+2}}{(n-1)^{n+1}}(a+m)\ -\ m(n-1);]$

Para o caso particular em que [;n=5;]

[;n=5;]

e

[;m=1;]

:

$[;N=(a+1)\frac{5^7}{4^6}\ -\ 4;]$

Logo:

[;15625|(N+4);]

O menor número divisível por 15625 é o próprio 15625. Com isso,

[;N=15621;]

Nenhum comentário:

Postar um comentário

Assinar: Postar comentários (Atom)