\documentclass{amsart} 
\linespread{1.2}
\usepackage{amssymb}
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\setlength{\textwidth}{17.5cm}
\setlength{\textheight}{55pc}
\setlength{\baselineskip}{1pc}
\setlength{\parindent}{2mm}
\setlength{\parskip}{0.4pc}
\setlength{\oddsidemargin}{-0.52cm}
\setlength{\evensidemargin}{-0.52cm}
\setlength{\topmargin}{-2pc}
\setlength{\topskip}{3pc}
\setlength{\unitlength}{.3cm}
\newcommand{\ih}{\'{\i}}
\newcommand{\ao}{\~ao}
\newcommand{\cao}{\c{c}\~ao}
\newcommand{\coes}{\c{c}\~oes}
\newcommand{\oes}{\~oes}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\Q}{{\mathbb Q}}
\begin{document}
\begin{center}

{\sc MAT0450  - Semin\'ario de Resolu\c{c}\~ao\ de Problemas
\\  IME-USP, 1$^\circ$ Semestre de 2013\\ Quarta Lista}
\end{center}
\vskip.8cm


\vskip.3cm

\noindent ({\bf 1}) Mostre que, se $n$ \'e um natural maior que $1$, ent\ao\ $n^4+4$ n\ao\ \'e primo. 


\vskip.3cm

\noindent ({\bf 1'}) Mostre que, se $n$ \'e um natural e se $k$ \'e um \'impar maior que $1$, ent\ao\ $n^4+4^k$ n\ao\ \'e primo. 

\vskip.3cm

\noindent ({\bf 2}) Sejam n e m naturais tais que 13 n\ao\ divide 5n+3m. Mostre que 13 n\ao\ divide 4n+5m. 

\vskip.3cm

\noindent ({\bf 2'}) Dados n e m naturais, mostre que 13 divide 2n+7m se, e somente se, 13 divide n+10m. 

\vskip.3cm

\noindent ({\bf 3}) Mostre que, para todo natural n$>$1, 1+1/2+1/3+...+1/n n\ao\ \'e inteiro.
\vskip.3cm

\noindent ({\bf 4}) Mostre que, se $a$ \'e um real positivo e se $n$ \'e um natural, ent\ao\ vale a desigualdade
\[
a^n+\frac{1}{a^n}-2\geq n^2\left(a+\frac{1}{a}-2\right)
\]

\noindent ({\bf 5}) Calcule o valor da soma 1!1+2!2+3!3+...+n!n para alguns valores de n. Descubra a f\'ormula geral para n arbitr\'ario e demonstre que ela \'e v\'alida.
 
\vskip.3cm

\noindent ({\bf 6}) Determine um n\'umero natural cuja divis\ao\ por 2 tem resto 1, cuja divis\ao\ por 3 tem resto 2, cuja divis\ao\ por 4 tem resto 3, cuja divis\ao\ por 5 tem resto 4 e cuja divis\ao\ por 6 tem resto 5, cuja divis\ao\ por 7 tem resto 0.

\vskip.3cm

\noindent ({\bf 6'}) Dado um primo n maior que 1, mostre que existem infinitos inteiros k tais que, para cada inteiro m maior que 1 e menor que n, o resto da divis\ao\ de k por m \'e m-1 e, al\'em disso, k \'e m\'ultiplo de n. 

\vskip.3cm

\noindent ({\bf 7}) Seja f:$\,\{1,2,3,...\}\to\{1,2,3,...\}$ fun\cao\ tal que $f(n+1)>f(f(n))$ para todo $n$. Mostre que $f(n)=n$ para todo $n$. 

\vskip.3cm

\noindent ({\bf 8}) \'E dada uma lista com os inteiros de 0 a 100 numa ordem qualquer. Mostre que \'e poss\'ivel riscar 90 n\'umeros da lista de modo que os demais fiquem em ordem crescente ou decrescente. 

\vskip.3cm

\noindent ({\bf 9}) Os n\'umeros inteiros de 1 a 1.000 est\ao\ dispostos em ordem em volta de um c\'irculo (isto \'e, o n\'umero 1 est\'a entre 1.000 e 2, 
o n\'umero 1.000 est\'a entre 999 e 1 e, se n \'e maior que 1 e menor que 1.000, ent\ao\ n est\'a entre n-1 e n+1). A partir de 1, risca-se todo 
14$^\circ$ n\'umero (1, 15, 29, 43,...). S\'o se p\'ara de riscar n\'umeros quando se atinge um n\'umero j\'a riscado. Quando n\'umeros restar\ao\ sem serem riscados? 

\vskip.3cm

\noindent ({\bf 10}) Descubra onde est\'a o erro da seguinte ``demonstra\cao". {\tt Seja $a$ um real positivo. A i\-gual\-da\-de $a^{n-1}=1$ \'e v\'alida para $n=1$. Suponhamos que $n$ \'e tal que $a^{k-1}=1$ para todo $k\leq n$. Ent\ao\ temos
\[
a^{(n+1)-1}=a^n=\frac{a^{n-1}\cdot a^{n-1}}{a^{n-2}}=\frac{1\cdot1}{1}=1.
\]
Segue portanto do Princ\'ipio de Indu\cao\ que $a^{n-1}=1$ para todo natural $n$.  }

\newpage

\begin{center}

{\sc Algumas Solu\coes}
\end{center}
\vskip.2cm

\noindent
({\bf 3}) Em vez de simplesmente demonstrar o que se pede, vou usar este caso para exemplificar uma estrat\'egia de resolu\cao. Talvez minha hist\'oria  n\ao\ pare\c{c}a t\ao\ plaus\'ivel quanto os casos de Polya, mas este \'e aproximadamente o relato dos passos que eu segui para resolver o problema. Fica para o leitor a tarefa de escrever uma solu\cao\ enxuta, que v\'a direto ao ponto.

Nosso plano \'e supor que 
\begin{equation}
\label{soma}
1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}=S_n
\end{equation}
\'e inteiro e usar propriedades de divisibilidade ou fatora\cao\ para chegar a um absurdo.

Para transformar (\ref{soma}) em uma equa\cao\ envolvendo apenas n\'umeros inteiros, multipliquemo-la por $n!$:
\begin{equation}
\label{soma2}
n!+\frac{n!}{2}+\frac{n!}{3}+\cdots+\frac{n!}{n}=n!S_n
\end{equation}
Para cada $k$ entre $1$ e $n$, $n!/k$ \'e o produto de todos os inteiros de $1$ a $n$, exceto $k$. Claro que todo $k$ que satisfa\c{c}a $1\leq k\leq n$ divide todas as parcelas dos dois membros de (\ref{soma2}), exceto, possivelmente, $n!/k$. No caso em que $n$ \'e primo, $n$ n\ao\ divide $n!/n$, pois $n$ n\ao\ divide nenhum dos termos do produto $2.3.\cdots.(n-1)$ e para um primo dividir um produto de inteiros ele tem de necessariamente dividir algum dos fatores. Assim chegamos, no caso em que $n$ \'e primo, ao seguinte absurdo: o lado direito da equa\cao\
\[
\frac{n!}{n}=n!S_n-n!-\frac{n!}{2}-\frac{n!}{3}-\cdots-\frac{n!}{n-1}
\]
\'e divis\'ivel por $n$, mas o lado esquerdo n\ao\ \'e. Isto demonstra o que quer\'iamos no caso em que $n$ \'e primo.

Uma maneira natural de tentar adaptar este argumento para o caso geral \'e discutir a divisibilidade das diversas parcelas de (\ref{soma2}) por algum primo $p$; por exemplo, para o maior primo menor ou igual a $n$. Percebe-se ent\ao\ a poss\'ivel utilidade um resultado c\'elebre da Teoria dos N\'umeros, conhecido como o Postulado de Bertrand, ou mais precisamente, como o Teorema de Bertrand-Chebyshev: dado um inteiro $n>1$, existe um primo $p$ satisfazendo $n< p< 2n$. Uma demontra\cao\ elementar (``elementar"\ n\ao\ significa ``f\'acil", significa que s\'o usa conceitos e t\'ecnicas b\'asicas) deste teorema pode ser encontrada no Ap\^endice C do livro de Jos\'e Pl\'inio de Oliveira Santos {\em Introdu\cao\ \`a Teoria dos N\'umeros}, volume da s\'erie Cole\cao\ Matem\'atica Universit\'aria, publicada pelo IMPA. Segue do Postulado de Bertrand que, se $n$ \'e um inteiro maior que $2$ e se $p$ \'e o maior primo menor que $n$, ent\ao\ $p$ n\ao\ divide $n$. De fato, se $n$ \'e primo, ent\ao\ $p$ n\ao\ divide $n$ por defini\cao. Se $n$ n\ao\ \'e primo e se $p$ divide $n$, ent\ao\ $n=p\cdot m$, onde $m\geq 2$. Pelo postulado de Bertrand, existe um primo $q$ satisfazendo $p<q<2p\leq n$; ou seja, $p$ n\ao\ \'e o maior primo menor que $n$.

Voltemos agora ao problema de mostrar que $S_n$ definido em (\ref{soma}) n\ao\ \'e inteiro se $n>2$. Seja $p$ o maior primo menor que $n$ e consideremos a igualdade
\begin{equation}
\label{somap}
\frac{n!}{p}=n!S_n-n!-\frac{n!}{2}-\frac{n!}{3}-\cdots-\frac{n!}{p-1}-\frac{n!}{p+1}-\cdots\frac{n!}{n-1}-\frac{n!}{n}
\end{equation}
Todas as parcelas do segundo membro desta igualdade t\^em o fator $p$; logo o inteiro do lado direito de (\ref{somap}) \'e divis\'ivel por $p$. Se $1\leq k<p$, ent\ao\ $p$ n\ao\ divide $k$ porque \'e maior que $k$; se $p<k\leq n$, ent\ao\ $p$ \'e o maior primo menor do que $k$, logo n\ao\ divide $k$, pela consequ\^encia do Postulado de Bertrand mencionada no par\'agrafo anterior. Sendo $p$ primo, $p$ tamb\'em n\ao\ divide $n!/p$, que \'e igual ao produtos de todos os inteiros $k$ satisfazendo $1\leq k<p$ ou $p<k\leq n$. Logo, $p$ n\ao\ divide o lado esquerdo de (\ref{somap}), embora divida o lado direito. Absurdo!

Reflitamos agora sobre a solu\cao\ que acabamos de encontrar, com o intuito descobrir uma solu\cao\ que n\ao\ use o Postulado de Bertrand. Percebemos que 
t\'inhamos chegamos a um absurdo quando conclu\'imos que a pot\^encia de $p$ na fatora\cao\ do inteiro do lado esquerdo de (\ref{somap}) \'e zero e a pot\^encia de $p$ em cada parcela do lado direito \'e maior ou igual a $1$. 

Troquemos o primo $p$ por um inteiro $m$, $1\leq m\leq n$, em (\ref{somap}):
\begin{equation}
\label{somam}
\frac{n!}{m}=n!S_n-n!-\frac{n!}{2}-\frac{n!}{3}-\cdots-\frac{n!}{m-1}-\frac{n!}{m+1}-\cdots\frac{n!}{n-1}-\frac{n!}{n}
\end{equation}
Chegaremos a um absurdo se encontrarmos um primo $p$ que apare\c{c}a na fatora\cao\ do inteiro do lado esquerdo de (\ref{somam}) com um expoente $N$ e na fatora\cao\ da soma do lado direito com expoente maior que $N$. Isso violaria a unicidade da fatora\cao\ em primos de um inteiro, pois seriam diferentes os expoentes de $p$ na fatora\cao\ dos dois lados de (\ref{somam}). Usando o Postulado de Bertrand, n\'os vimos que, se tomarmos $p$ como sendo o maior primo menor que $n$ e $m=p$, ent\ao, com $N=0$ chegamos ao absurdo procurado. Nossa tarefa agora \'e achar um primo $p$ e um inteiro $m$ que fa\c{c}a o esquema funcionar sem ser preciso usar o Postulado de Bertrand. 

A seguinte observa\cao\ \'e muito simples de verificar: se um primo $p$ aparece com expoente maior que $N$ na fatora\cao\ de um certo n\'umero de parcelas, ent\ao\ aparece com expoente tamb\'em maior que $N$ na soma dessas parcelas. \'E por isso que a meta de provar que a pot\^encia de $p$ no segundo membro de (\ref{somam}) \'e maior (e n\ao\ menor) do que no primeiro membro parece mais vi\'avel. Para isto, basta provar que o expoente de $p$ em cada parcela do segundo membro \'e maior que o expoente de $p$ na fatora\cao\ de $n!/m$.

Seja $M$ o expoente de um primo $p$ (que ainda vai ser escolhido) na fatora\cao\ de $n!$. Ent\ao\ o expoente de $p$ na fatora\cao\ de $n!S_n$ \'e maior ou igual a $M$. As demais parcelas de (\ref{somam}) s\ao\ todas da forma $n!/k$, para algum $k$ tal que $1\leq k\leq n$. Se $l_k\geq 0$ \'e o expoente de $p$ na fatora\cao\ de $k$, ent\ao\ o expoente de $p$ na fatora\cao\ de $n!/k$ ser\'a $N-l_k\leq N$. Vemos ent\ao\ que o problema estar\'a resolvido se encontrarmos um primo $p$ tal que o maior expoente de $p$ na fatora\cao\ de todos os inteiros $k$ de $1$ at\'e $n$ ocorra em um \'unico inteiro $m$ (digamos que $l_0$ seja o maior expoente de $p$, que ocorre apenas em $m$; ent\ao\ o expoente de $p$ na fatora\cao\ de $n!/m$ ser\'a $M-l_0$ e o expoente de $p$ na soma do segundo membro de (\ref{somam}) ser\'a maior do que $M-l_0$). 

J\'a vimos que este \'e o caso se $p$ for o maior primo menor ou igual a $n$, mas isto depende um resultado muito profundo e dif\'icil de provar, o Postulado de Bertrand. Al\'em disso, \'e bem simples verificar, por exemplo, que se $n$ \'e uma pot\^encia de um primo $p$, ent\ao\ $m=n$ \'e o inteiro procurado (isto generaliza nosso primeiro resultado, que $S_n$ n\ao\ \'e inteiro se $n$ \'e primo). Podemos tamb\'em tentar tomar como $p$ o maior primo que divide $n$ e ingenuamente desejar que d\^e certo tomar $m=p^l$, com $l$ denotando o expoente de $p$ na fatora\cao\ de $n$. Mas a\'i a gente percebe qual \'e a dificuldade: $n$ pode ser maior do que, digamos, $2p^l$ e portanto haver\'a um outro inteiro menor que $n$ com $p^l$ aparecendo em sua fatora\cao. O problema \'e que pode haver espa\c{c}o demais entre $p^l$ e $n$. Parece ser uma boa ideia portanto tentar primos pequenos, e por que n\ao\ tomar logo o menor deles, dois?

Qual inteiro $m$ ter\'a a propriedade de o expoente de $2$ na fatora\cao\ de $k$, $1\leq k\leq n$, atingir seu m\'aximo precisamente quando $k=m$? Resposta: ser\'a a maior pot\^encia de $2$ que seja menor ou igual a $n$. De fato, se $l$ \'e o \'unico inteiro positivo tal que $2^l\leq n< 2^{l+1}$, 
ent\ao\ $m=2^l$ \'e o \'unico inteiro entre $1$ e $k$ que tem $2^l$ em sua fatora\cao, porque todo $k\neq m$ satisfazendo $1\leq k\leq n$ tem em sua 
fatora\cao\ uma pot\^encia de dois com expoente $l_k$ satisfazendo $0\leq l_k<l$. De fato, se um inteiro $J$ \'e diferente de $m$ e tem em sua fatora\cao\ uma pot\^encia de $2$ com expoente maior ou igual a $l$, ent\ao\ $J=2^lK$, com $K\geq 2$; logo $J\geq 2^{l+1}>n$. \'E aqui que se v\^e direitinho que este argumento s\'o funciona para o primo $2$: por exemplo, a maior pot\^encia de $3$ menor que $20$ \'e $9$, entretanto $18$ \'e um outro inteiro menor que $20$ que tem $3$ com expoente $2$ em sua fatora\cao. 

Em resumo, se $l$ \'e o \'unico inteiro positivo tal que $2^l\leq n< 2^{l+1}$, $m=2^l$ e $M$ \'e o expoente de $2$ na fatora\cao\ de $n!$, ent\ao\ o expoente de $2$ na fatora\cao\ do primeiro membro de (\ref{somam}) \'e $M-l$ e na fatora\cao\ do segundo membro \'e maior que $M-l$. Absurdo! 

({\bf 7}) Roteiro: mostraremos primeiro, por indu\cao, que $f(n)\geq n$ para todo $n$; da\'i concluiremos que $f$ \'e crescente, donde seguir\'a o que queremos mostrar.

Demonstremos por indu\cao\ sobre $k$ que, para todo $k\geq 1$, 
\begin{equation}
\label{ind}
f(n)\geq k\ \ \mbox{para todo}\ \  n\geq k
\end{equation}
(em particular, teremos ent\ao\ que $f(n)\geq n$ para todo $n$). 
\footnote{O ponto mais ``tricky"\ desta solu\cao\ talvez seja formular como em (\ref{ind}) a hip\'otese de indu\cao. Por que n\ao, por exemplo, usar como  passo de indu\cao\ a afirma\cao\ (\ref{inda}) abaixo em vez de (\ref{ind})?
\begin{equation}
\label{inda} 
\mbox{Para cada}\ \  k\geq 1,\ \  f(n)\geq n \ \ \mbox{para todo}\ \  1\leq n\leq k. 
\end{equation}
Logicamente falando, claro que seria poss\'ivel fazer assim, mas, tentando fazer, a gente v\^e que n\ao\ sai f\'acil desse jeito. Uma maneira de chegar a (\ref{ind}) \'e observar primeiro que $f(1)\geq 1$, depois supor por absurdo que $f(2)<2$ e ver que n\ao\ pode; depois supor por absurdo que $f(3)<3$, etc. A gente acaba percebendo que, em cada passo, \'e preciso avan\c{c}ar al\'em do $k$ em 
quest\ao, e que, portanto, (\ref{ind}) \'e uma hip\'otese de indu\cao\ mais ``pr\'atica"\ do que (\ref{inda}).}
A afirma\cao\ (\ref{ind}) \'e trivialmente verdadeira para $k=1$, pois o contradom\'inio de $f$ s\ao\ os inteiros positivos. Suponha  que (\ref{ind}) \'e verdadeira para $k$. Tome $n\geq k+1$. Usando a hip\'otese de indu\cao\ para $n-1$ (que \'e maior ou igual a $k$) vem que $f(n-1)\geq k$ e portanto que tamb\'em $f(f(n-1))\geq k$. Usando a desigualdade que $f$ satisfaz por hip\'otese, temos $f(n)>f(f(n-1))\geq k$; logo $f(n)\geq k+1$, como quer\'iamos.

Mostremos agora que $f$ \'e crescente, isto \'e, que $f(n)<f(m)$ sempre que $1\leq n<m$. Claro que basta mostrar que $f(n)<f(n+1)$ para todo $n\geq 1$. Se isto fosse falso, existiria $n_0\geq 1$ tal que $f(f(n_0))<f(n_0+1)\leq f(n_0)$. Logo $k_0=f(n_0)$ n\ao\ satisfaria a desigualdade $f(n)\geq n$, que j\'a sabemos ser v\'alida para todo $n\geq 1$.

Sendo $f$ crescente, \'e tamb\'em verdade que $f(n)<f(m)$ s\'o se $n<m$ (raciocine por contradi\cao\ para ver isto). Da\'i, para cada $n$, como $f(f(n))<f(n+1)$, temos que $f(n)<n+1$. Mas j\'a sab\'iamos que $f(n)\geq n$. Logo, $f(n)=n$.




\end{document}
