Problemas Teoremas

Setembro 19, 2010

Um problema de juros compostos de uma série não uniforme da Universidade de Purdue

Filed under: Cálculo financeiro,Matemática,Problem,Problemas,Purdue University,Séries,Sucessões — Américo Tavares @ 11:49 pm
Tags: , ,

Esta é a tradução do problema Problem No. 2 (Fall 2010 Series) e da minha resolução aceite pela Universidade de Purdue.

« Qual é o montante mais pequeno que deverá investir-se à taxa de juro de i\%, composta anualmente, de maneira a poder levantar-se 1^{2},2^{2}, 3^{2},\ldots dólares no final do ano 1,2,3,\ldots , perpetuamente? (Para i=10, a resposta é 2310 dólares.) »

Transcrição do original

“ What is the smallest amount that may be invested at interest rate i\%, compounded annually, in order that we may withdraw 1^{2},2^{2}, 3^{2},\ldots dollars at the end of the 1st, 2nd, 3rd, … year, in perpetuity? (For i=10, the answer is 2310 dollars.) “

Resolução: O principal resultado que usaremos é o cálculo da soma da série \displaystyle\sum_{n=1}^{\infty }n^{2}x^{n}.

Proposição: se -1<x<1, a série \displaystyle\sum_{n=1}^{\infty }n^{2}x^{n} converge para \dfrac{x\left( 1+x\right) }{\left( 1-x\right) ^{3}}.

Demonstração: Tomemos a seguinte série geométrica, que é convergente para |x|<1:

\displaystyle\sum_{n=1}^{\infty }x^{n}=\dfrac{x}{1-x}\qquad (1)

e diferenciemos ambos os membros \displaystyle\sum_{n=1}^{\infty }nx^{n-1}=\left( 1-x\right) ^{-2}. Agora multipliquemo-los por x: x\displaystyle \sum_{n=1}^{\infty}nx^{n-1}=\sum_{n=1}^{\infty }nx^{n}=x\left( 1-x\right) ^{-2}. Diferenciando novamente, obtemos \displaystyle\sum_{n=1}^{\infty }n^{2}x^{n-1}=\left( 1+x\right) \left( 1-x\right) ^{-3}. Multipliquemos ambos os membros por x e completaremos a demonstração da Proposição:

x\displaystyle\sum_{n=1}^{\infty }n^{2}x^{n-1} =\displaystyle\sum_{n=1}^{\infty}n^{2}x^{n}=\dfrac{x\left( 1+x\right) }{\left( 1-x\right) ^{3}}\qquad (2)

Pondo x=1/c obtemos na forma alternativa, válida para |c|>1,

x\displaystyle\sum_{n=1}^{\infty }\dfrac{n^2}{c^n} =\dfrac{c(c+1)}{(c-1)^{3}}\qquad (3)

Designemos por P o valor actual total da série de levantamentos 1^{2},2^{2}, 3^{2},\ldots dólares, no fim do ano 1, 2, 3,\ldots . O levantamento n^{2} no final do ano n contribui para P no valor de n^{2}/(1+i/100)^{n}, em que i é a taxa de juro (em percentagem) composta anualmente. Sumando todas as contribuições desde n=1 a \infty dá P (no princípio do ano 1),  que é o montante A mais pequeno que é necessário investir-se para equilibrar (A-P=0) os levantamentos como enunciado no problema: P=\sum_{n=1}^{\infty}n^{2}/\left( 1+i/100\right) ^{n}.

Usando (3) com c=1+i/100>1 obtemos o valor actual P(i)=A(i), em dólares, em função da taxa de juro i em percentagem:

A(i)=P(i)=\dfrac{\left( 1+i/100\right) (2+i/100)}{(i/100)^{3}}\qquad (4)

Para i=10, confirmamos que A(10)=P(10)=2310.

Cópia do Texto original

[Correcção gramatical: "alternative form" em vez de "alternatively form"]

* * *

Comentário: Ao iniciar este problema não fazia a mínima ideia de como o iria resolver na prática. De repente consegui associar dois conceitos diferentes: um proveniente da Cálculo financeiro e o outro das Séries, que consegui concretizar na resolução apresentada.

Dezembro 6, 2009

Minha resolução do POW12 da Universidade de Purdue. Maximização e restrição a várias variáveis reais e uma inteira

Filed under: Cálculo,Matemática,Problem,Problemas,Purdue University — Américo Tavares @ 9:59 am
Tags: ,

Tradução da entrada anterior.

A minha  resolução do POW12 foi aceite. [Nota de 19-12-2009: apenas se afirma que foi "completa ou parcialmente resolvida"]

« Problema. Determine, demonstrando, o valor máximo de \displaystyle\prod\limits_{j=1}^{k}x_{j}, em que x_{j}\geq 0,\displaystyle\sum\limits_{j=1}^{k}x_{j}=100, e k é variável. Em particular, a sua resposta deve ser maior ou igual a todos os valores que se obtêm escolhendo outros valores de k. »

Original:

“ Problem. Find, with proof, the maximum value of \displaystyle\prod\limits_{j=1}^{k}x_{j} where x_{j}\geq 0,\displaystyle\sum\limits_{j=1}^{k}x_{j}=100, and k is variable. In particular, your answer must be greater than or equal to all values obtained from other choices of k. “

Eis a resolução submetida.

Resolução:

Sejam \left( x_{1},x_{2},\ldots ,x_{k}\right) \in\mathbb{R}^{k}, f\left( x_{1},x_{2},\ldots ,x_{k}\right) =\displaystyle\prod\limits_{j=1}^{k}x_{j}\in\mathbb{R}, c\left( x_{1},x_{2},\ldots ,x_{k}\right) =\displaystyle\sum_{j=1}^{k}x_{j}-100 \in\mathbb{R} e \lambda\in\mathbb{R}. Para um dado k\in\mathbb{Z}, com k\geq 1, sabemos pelo método dos multiplicadores de  Lagrange que f\left( x_{1}^{\ast },x_{2}^{\ast },\ldots ,x_{k}^{\ast }\right) é um extremo local, se para x^{\ast }=\left( x_{1}^{\ast },x_{2}^{\ast },\ldots,x_{k}^{\ast }\right)

\nabla f\left( x^{\ast }\right) -\nabla c\left( x^{\ast }\right) \lambda^{\ast }=0\quad \quad k\text{ equa\c{c}\~{o}es}

c\left( x^{\ast }\right) =0\quad \quad 1\text{ equa\c{c}\~{a}o}

em que \lambda ^{\ast } é o valor do multiplicador \lambda que é solução destas k+1 equaçoes. Assim temos respectivamente

\displaystyle\prod\limits_{j\neq i}^{k}x_{j}^{\ast }-\lambda ^{\ast }=0\quad\quad 1\leq i\leq k

e

\displaystyle\sum\limits_{j=1}^{k}x_{j}^{\ast}-100=0\text{. }

Resolvendo este sistema de equações achamos

x_{1}^{\ast }=x_{2}^{\ast }=\cdots =x_{i}^{\ast }\cdots =x_{k}^{\ast}=\lambda ^{\ast }=\dfrac{100}{k}

e

\displaystyle\prod\limits_{j=1}^{k}x_{j}^{\ast}=\left( \dfrac{100}{k}\right) ^{k},

sendo este último um extremo local de f\left( x_{1},x_{2},\ldots ,x_{k}\right) , fixado k. Transformámos o problema inicial de maximização em k variáveis contínuas e uma discreta, a variável  k no da maximização de \left( 100/k\right) ^{k}. Agora introduzimos a função seguinte

u\left( t\right) =\left( \dfrac{100}{t}\right) ^{t}\quad\text{com }t\in\mathbb{R}\text{.}

A função u\left( t\right) tem um máximo no mesmo ponto t do da função

v\left( t\right) =\ln u\left( t\right) =t\ln 100-t\ln t\text{.}

Mas v^{\prime }\left( t\right) =0 para t^{\ast }=e^{\ln100-1}\simeq 36.788,v^{\prime }\left( t\right) >0 para t<t^{\ast } e v^{\prime }\left( t\right) <0 para t>t^{\ast }. Assim

u\left( t^{\ast }\right) =\left( \dfrac{100}{t^{\ast }}\right) ^{t^{\ast }}

é um máximo de u\left( t\right) . Dado que u\left( 37\right) >u\left( 36\right) , o máximo ocorre para k=37. Assim, para \sum_{j=1}^{k}x_{j}=\sum_{j=1}^{37}x_{j}=100 tem-se

\max\displaystyle\prod\limits_{j=1}^{k}x_{j}=\displaystyle\prod\limits_{j=1}^{37}x_{j}=\left( \dfrac{100}{37}\right) ^{37}\text{.}

Actualização de 19-12-2009: corrigidos alguns erros assinalados pelo leitor Rod Carvalho.

Dezembro 5, 2009

My Solution of The Purdue University Problem Of The Week No. 12

Filed under: Calculus,Cálculo,Matemática,Math,Problem,Problemas,Purdue University — Américo Tavares @ 7:56 am
Tags: ,

My solution of POW12 was accepted. [Remark of December 19, 2009: it is only stated that it was "completely or partially proved"]

(Tradução aqui)

“ Problem. Find, with proof, the maximum value of \displaystyle\prod\limits_{j=1}^{k}x_{j} where x_{j}\geq 0,\displaystyle\sum\limits_{j=1}^{k}x_{j}=100, and k is variable. In particular, your answer must be greater than or equal to all values obtained from other choices of k. “

Here is the solution I submited.

Solution.

Let \left( x_{1},x_{2},\ldots ,x_{k}\right) \in\mathbb{R}^{k}, f\left( x_{1},x_{2},\ldots ,x_{k}\right) =\displaystyle\prod\limits_{j=1}^{k}x_{j}\in\mathbb{R}, c\left( x_{1},x_{2},\ldots ,x_{k}\right) =\displaystyle\sum_{j=1}^{k}x_{j}-100 \in\mathbb{R} and \lambda\in\mathbb{R}. For a given k\in\mathbb{Z}, with k\geq 1, we know by the Lagrange multipliers method that f\left( x_{1}^{\ast },x_{2}^{\ast },\ldots ,x_{k}^{\ast }\right) is a local extremum if for x^{\ast }=\left( x_{1}^{\ast },x_{2}^{\ast },\ldots,x_{k}^{\ast }\right)

\nabla f\left( x^{\ast }\right) -\nabla c\left( x^{\ast }\right) \lambda^{\ast }=0\quad \quad k\text{ equations}

c\left( x^{\ast }\right) =0\quad \quad 1\text{ equation}

where \lambda ^{\ast } is the value of the multiplier \lambda that is a solution of these k+1 equations. Hence we have respectively

\displaystyle\prod\limits_{j\neq i}^{k}x_{j}^{\ast }-\lambda ^{\ast }=0\quad\quad 1\leq i\leq k

and

\displaystyle\sum\limits_{j=1}^{k}x_{j}^{\ast}-100=0\text{. }

Solving this system of equations we find

x_{1}^{\ast }=x_{2}^{\ast }=\cdots =x_{i}^{\ast }\cdots =x_{k}^{\ast}=\lambda ^{\ast }=\dfrac{100}{k}

and

\displaystyle\prod\limits_{j=1}^{k}x_{j}^{\ast}=\left( \dfrac{100}{k}\right) ^{k},

the latter being a local extremum of f\left( x_{1},x_{2},\ldots ,x_{k}\right) , for a fixed k. We transformed the initial maximizing problem in k continuous variables and the discrete variable k into the maximizing of \left( 100/k\right) ^{k}. Now we introduce the following function

u\left( t\right) =\left( \dfrac{100}{t}\right) ^{t}\quad\text{with }t\in\mathbb{R}\text{.}

The function u\left( t\right) has a maximum at the same point t than the function

v\left( t\right) =\ln u\left( t\right) =t\ln 100-t\ln t\text{.}

On the other hand v^{\prime }\left( t\right) =0 for t^{\ast }=e^{\ln100-1}\simeq 36.788,v^{\prime }\left( t\right) >0 for t<t^{\ast } and v^{\prime }\left( t\right) <0 for t>t^{\ast }. Therefore

u\left( t^{\ast }\right) =\left( \dfrac{100}{t^{\ast }}\right) ^{t^{\ast }}

is a maximum of u\left( t\right) . Since u\left( 37\right) >u\left( 36\right) , the maximum occurs at k=37. Thus, for \sum_{j=1}^{k}x_{j}=\sum_{j=1}^{37}x_{j}=100 we have

\max\displaystyle\prod\limits_{j=1}^{k}x_{j}=\displaystyle\prod\limits_{j=1}^{37}x_{j}=\left( \dfrac{100}{37}\right) ^{37}\text{.}

Update (Dec., 19,2009): some errors (identified by Rod Carvalho here) corrected.

Maio 29, 2009

Congruências e divisibilidade — Um Problema da Purdue University

Filed under: Caderno,Congruências,Matemática,Problem,Problemas,Purdue University,Teoria dos Números — Américo Tavares @ 10:15 am
Tags: , ,

pdf: ver caderno

Versão portuguesa da entrada “Congruences and Divisibility– A Purdue University Problem“

Tradução do enunciado do Problema original [PROBLEM OF THE WEEK, Problem No. 12 (Spring 2009 Series)]:

« Para quantos inteiros positivos x\leq 10000 é que  2^{x}-x^{2} não é divisível por 7?

Justifique a sua resposta sem utilizar o computador. »

“For how many positive integers x\leq 10,000 is 2^{x}-x^{2} not divisible by 7?

Justify your answer without the use of computers.”

Eis a tradução da  minha resolução (aceite):

Se a\equiv b\quad \left( \text{mod }m\right) , então a^{n}\equiv b^{n}\quad\left( \text{mod }m\right) . Esta propriedade aplicada a 2^{n} dá em geral, para n=3k+s,1\leq s\leq 3,0\leq k

2^{n}\equiv 2^{s}\quad\left( \text{mod }7\right) ,\quad (1)

o que significa que os restos da divisão de  2^{n} por 7 formam uma sucessão periódica de comprimento 3 com início em n=1

\overset{\text{per\'{\i}odo}}{\overbrace{2,4,1}},\overset{3\text{ termos}}{\overbrace{2,4,1}},\ldots .

Quanto a n^{2}, dado que: a) se a\equiv b\quad \left( \text{mod }m\right) e c\equiv d\quad \left( \text{mod }m\right) , então a+c\equiv b+d\quad \left( \text{mod }m\right) e b) se a\equiv b\quad \left( \text{mod }m\right) , então a^{2}\equiv b^{2}\quad \left( \text{mod }m\right) , temos em geral, para n=7j+r,1\leq r\leq 7,0\leq j

n^{2}\equiv r^{2}\quad\left( \text{mod }7\right)\quad (2)

o que quer dizer que os restos da divisão de n^{2} por 7 formam uma sucessão  periódica  de comprimento 7 que começa em n=1

\overset{\text{per\'{\i}odo}}{\overbrace{1,4,2,2,4,1,0}},\overset{7\text{ termos}}{\overbrace{1,4,2,2,4,1,0}},\ldots .

Se a\equiv b\quad \left( \text{mod }m\right) e c\equiv d\quad \left( \text{mod }m\right) , então a-c\equiv b-d\quad \left( \text{mod }m\right) . Seja u_{n}=2^{n}-n^{2}. Em consequência de (1) e (2) obtemos

u_{n}\equiv 2^{s}-r^{2}\quad \left( \text{mod }7\right) .\quad (3)

Os restos da divisão de  u_{n} por 7 formam outra sucessão periódica de comprimento 21=\text{mmc}(3,7) que se inicia também em n=1. Apresentamos abaixo quatro exemplos da determinação destes restos.

Para 1\leq n\leq 21 os seguintes 15 termos não são divisíveis por 7:

u_{1},u_{3},u_{7},u_{8},u_{9},u_{11},u_{12},u_{13},u_{14},u_{16},u_{17},u_{18},u_{19},u_{20},u_{21}.

Assim para 1\leq n\leq 9996=21\times \left\lfloor \dfrac{10000}{21}\right\rfloor , há 15\times\left\lfloor \dfrac{10000}{21}\right\rfloor =7140 termos que não são divisíveis por 7.

Dos restantes 4 termos u_{9997} e u_{9999}  não são divisíveis por 7, o que dá um total de 7140+2=7142 números u_{n}=2^{n}-n^{2} não divisíveis por 7.

Quatro exemplos do cálculo dos restos:

u_{9}=2^{9}-9^{2}

(9=3\times 2+3,s=3,9=7\times 1+2,r=2)

2^{9}\equiv 2^{3}\quad\left(\text{mod }7\right) \equiv 1\quad\left(\text{mod }7\right)

9^{2}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

u_{9}\equiv 2^{3}-2^{2}\quad\left(\text{mod }7\right) \equiv -3\quad\left(\text{mod }7\right)

u_{10}=2^{10}-10^{2}

(10=3\times 3+1,s=1,10=7\times 1+3,r=3)

2^{10}\equiv 2^{1}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

10^{2}\equiv 3^{2}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

u_{10}\equiv 2^{1}-3^{2}\quad\left( \text{mod }7\right)\equiv 0\quad\left( \text{mod }7\right)

u_{9997}=2^{9997}-9997^{2}

(9997=3\times 3332+1,s=1,9997=7\times 1428+1,r=1)

2^{9997}\equiv 2^{1}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

9997^{2}\equiv 1^{2}\quad\left(\text{mod }7\right) \equiv 1\quad\left(\text{mod }7\right)

u_{9997} \equiv 2^{9997}-9997^{2}\quad \left( \text{mod}7\right) \equiv 1\quad \left( \text{mod }7\right)

u_{9998}=2^{9998}-9998^{2}

(9998=3\times 3332+2,s=2,9998=7\times 1428+2,r=2)

2^{9998}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

9998^{2}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

u_{9998} \equiv 2^{9998}-9998^{2}\quad \left( \text{mod}7\right) \equiv 0\quad \left( \text{mod }7\right)

Abril 24, 2009

Congruences and Divisibility — A Purdue University Problem

Filed under: Congruences,Math,Number Theory,Problem,Purdue University — Américo Tavares @ 12:59 pm
Tags: ,

pdf: ver caderno

Versão portuguesa aqui

PROBLEM OF THE WEEK, Problem No. 12 (Spring 2009 Series):

“ Problem. For how many positive integers x\leq 10,000 is 2^{x}-x^{2} not divisible by 7?

Justify your answer without the use of computers. ”

Here is my solution (accepted).

If a\equiv b\quad \left( \text{mod }m\right) , then a^{n}\equiv b^{n}\quad\left( \text{mod }m\right) . Applied to 2^{n} this property gives in general for n=3k+s,1\leq s\leq 3,0\leq k

2^{n}\equiv 2^{s}\quad\left( \text{mod }7\right) ,\quad (1)

which means that the remainders of the division of 2^{n} by 7 form a periodic sequence of length 3 starting at n=1

\overset{\text{period}}{\overbrace{2,4,1}},\overset{3\text{ terms}}{\overbrace{2,4,1}},\ldots .

As for n^{2} since (a) if a\equiv b\quad \left( \text{mod }m\right) and c\equiv d\quad \left( \text{mod }m\right) , then a+c\equiv b+d\quad \left( \text{mod }m\right) and (b) if a\equiv b\quad \left( \text{mod }m\right) , then a^{2}\equiv b^{2}\quad \left( \text{mod }m\right) , we have in general for n=7j+r,1\leq r\leq 7,0\leq j

n^{2}\equiv r^{2}\quad\left( \text{mod }7\right)\quad (2)

which means that the remainders of the division of n^{2} by 7 form a periodic sequence of length 7 starting at n=1

\overset{\text{period}}{\overbrace{1,4,2,2,4,1,0}},\overset{7\text{ terms}}{\overbrace{1,4,2,2,4,1,0}},\ldots .

If a\equiv b\quad \left( \text{mod }m\right) and c\equiv d\quad \left( \text{mod }m\right) , then a-c\equiv b-d\quad \left( \text{mod }m\right) . Let u_{n}=2^{n}-n^{2}. Therefore from (1) and (2) we have

u_{n}\equiv 2^{s}-r^{2}\quad \left( \text{mod}7\right) .\quad (3)

The remainders of the division of u_{n} by 7 form another periodic sequence of length 21=\text{lcm}(3,7) which starts also at n=1. Four examples of the evaluation of these remainders are presented below.

For 1\leq n\leq 21 the following 15 terms are not divisible by 7:

u_{1},u_{3},u_{7},u_{8},u_{9},u_{11},u_{12},u_{13},u_{14},u_{16},u_{17},u_{18},u_{19},u_{20},u_{21}.

Hence for 1\leq n\leq 9996=21\times \left\lfloor \dfrac{10000}{21}\right\rfloor , there are 15\times\left\lfloor \dfrac{10000}{21}\right\rfloor =7140 terms that are not divisible by 7.

From the remaining 4 terms u_{9997} and u_{9999}  are not divisible by 7, which gives a total of 7140+2=7142 numbers u_{n}=2^{n}-n^{2} not divisible by 7.

Four examples of the evaluation of the remainders:

u_{9}=2^{9}-9^{2}

(9=3\times 2+3,s=3,9=7\times 1+2,r=2)

2^{9}\equiv 2^{3}\quad\left(\text{mod }7\right) \equiv 1\quad\left(\text{mod }7\right)

9^{2}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

u_{9}\equiv 2^{3}-2^{2}\quad\left(\text{mod }7\right) \equiv -3\quad\left(\text{mod }7\right)

u_{10}=2^{10}-10^{2}

(10=3\times 3+1,s=1,10=7\times 1+3,r=3)

2^{10}\equiv 2^{1}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

10^{2}\equiv 3^{2}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

u_{10}\equiv 2^{1}-3^{2}\quad\left( \text{mod }7\right)\equiv 0\quad\left( \text{mod }7\right)

u_{9997}=2^{9997}-9997^{2}

(9997=3\times 3332+1,s=1,9997=7\times 1428+1,r=1)

2^{9997}\equiv 2^{1}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

9997^{2}\equiv 1^{2}\quad\left(\text{mod }7\right) \equiv 1\quad\left(\text{mod }7\right)

u_{9997} \equiv 2^{9997}-9997^{2}\quad \left( \text{mod}7\right) \equiv 1\quad \left( \text{mod }7\right)

u_{9998}=2^{9998}-9998^{2}

(9998=3\times 3332+2,s=2,9998=7\times 1428+2,r=2)

2^{9998}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

9998^{2}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

u_{9998} \equiv 2^{9998}-9998^{2}\quad \left( \text{mod}7\right) \equiv 0\quad \left( \text{mod }7\right)

Remark: typos corrected. [In the 2nd. last paragraph before the examples: "there are"  added]

Edited: May 29, 2009: Portuguese version removed and posted here

Tema: Rubric. Blog em WordPress.com.