%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 27 Jun 2018 07:06:05pm -03 by yoshi on pokopon>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno,a4paper]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
%\usepackage[latin1]{inputenc}
%----------------------------

%right pdf-output for special characters
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage{aecompl}

%\usepackage{lmodern}
\usepackage{amssymb}

\usepackage{xcolor}
\usepackage[backref]{hyperref}
\hypersetup{
    colorlinks,
    linkcolor={red!60!black},
    citecolor={green!60!black},
    urlcolor={blue!60!black}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%  Page Layout
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{bbm}
\footskip28pt
\usepackage{fancyhdr}
\pagestyle{fancy}

\lhead{}
\chead{}
\rhead{}
%\lfoot{}
\cfoot{}
%\rfoot{\today, \currenttime}
\fancyfoot[RO,LE]{\thepage}
\fancyfoot[LO,RE]{{\footnotesize\today, \currenttime}}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%------------------ disjoint union with dot -------------------------------%
\makeatletter
\def\moverlay{\mathpalette\mov@rlay}
\def\mov@rlay#1#2{\leavevmode\vtop{%
   \baselineskip\z@skip \lineskiplimit-\maxdimen
   \ialign{\hfil$\m@th#1##$\hfil\cr#2\crcr}}}
\newcommand{\charfusion}[3][\mathord]{
    #1{\ifx#1\mathop\vphantom{#2}\fi
        \mathpalette\mov@rlay{#2\cr#3}
      }
    \ifx#1\mathop\expandafter\displaylimits\fi}
\makeatother

\newcommand{\dcup}{\charfusion[\mathbin]{\cup}{\cdot}}
\newcommand{\bigdcup}{\charfusion[\mathop]{\bigcup}{\cdot}}
%------------------ disjoint union with dot -------------------------------%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{datetime}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{lineno}
\newcommand*\patchAmsMathEnvironmentForLineno[1]{%
\expandafter\let\csname old#1\expandafter\endcsname\csname #1\endcsname
\expandafter\let\csname oldend#1\expandafter\endcsname\csname end#1\endcsname
\renewenvironment{#1}%
{\linenomath\csname old#1\endcsname}%
{\csname oldend#1\endcsname\endlinenomath}}% 
\newcommand*\patchBothAmsMathEnvironmentsForLineno[1]{%
\patchAmsMathEnvironmentForLineno{#1}%
\patchAmsMathEnvironmentForLineno{#1*}}%
\AtBeginDocument{%
\patchBothAmsMathEnvironmentsForLineno{equation}%
\patchBothAmsMathEnvironmentsForLineno{align}%
\patchBothAmsMathEnvironmentsForLineno{flalign}%
\patchBothAmsMathEnvironmentsForLineno{alignat}%
\patchBothAmsMathEnvironmentsForLineno{gather}%
\patchBothAmsMathEnvironmentsForLineno{multline}%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\let\rho=\varrho
\def\e{{\rm e}}
\def\Div{\mathop{\rm Div}\nolimits}
\def\mdc{\mathop{\rm mdc}\nolimits}
\def\occ{\mathop{\rm occ}\nolimits}
\def\dist{\mathop{\rm dist}\nolimits}
\def\dim{\mathop{\rm dim}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\im{\mathop{\rm im}\nolimits}
\def\prof{\mathop{\rm prof}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\One{{\ensuremath{\mathbbm{1}}}}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
\def\llfloor{\left\lfloor}
\def\rrfloor{\right\rfloor}  
\def\llceil{\left\lceil}
\def\rrceil{\right\rceil)}  
\let\sim=\thicksim
\def\qand{\quad\text{e}\quad}
\def\qqand{\qquad\text{e}\qquad}

\def\inR{\mathrel{\in_{\text R}}} 
\def\inU{\mathrel{\in_{\text U}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cE{\mathcal E}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cK{\mathcal K}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cZ{\mathcal Z}

\def\tG{\widetilde G}
\def\tcG{\widetilde\cG}

\def\barp{{\bar p}}

\def\Ave{\mathop{{\rm Ave}}}
\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}
\def\diam{\mathop{{\rm diam}}\nolimits}
\def\PG{\mathop{{\rm PG}}\nolimits}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfa{\textbf{a}}
\def\bfb{\textbf{b}}
\def\bfd{\textbf{d}}
\def\bff{\textbf{f}}
\def\bfp{\textbf{p}}
\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}
\def\bfX{\textbf{X}}
\def\bfdelta{\boldsymbol\delta}

\def\ldens{\underline\bfd}
\def\udens{\overline\bfd}
\def\lldens{\underline\bfdelta}
\def\uldens{\overline\bfdelta}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother
\usepackage{enumitem}
\newcommand\rmlabel{\upshape({\itshape\roman*\,\/})}
\newcommand\RMlabel{\upshape(\Roman*)}
\newcommand\alabel{\upshape({\itshape\alph*\,\/})}
\newcommand\Alabel{\upshape({\itshape\Alph*\,\/})}
\newcommand\nlabel{\upshape({\itshape\arabic*\,\/})}
\newcommand\nlabelp{\upshape(P\arabic*)}
\newcommand\nlabelE{\bf\upshape E\arabic*}

\def\datedue#1{{\bf$\boldsymbol\{$\textsl{Data de entrega}: #1$\boldsymbol\}$}}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\let\hint\sugestao
\def\observacao#1{[\textit{Observação.} #1]}
\let\NB\observacao

\begin{document}
\title[MAC105 Fundamentos de Matemática]%
{Fundamentos de Matemática para a Computação\\
  \bigskip\bigskip{\bf\textit{1{\tiny o.} Semestre de 2018}}\\
  \bigskip\bigskip Exercícios
}  

\shortdate
\yyyymmdddate
\def\today{\number\year/\number\month/\number\day}
\settimeformat{ampmtime}
\date{Versão de \today, \currenttime}
%\date{Versão de \today}

\maketitle

\linenumbers 
\onehalfspace
%\pagestyle{plain}
\pagestyle{fancy}

\noindent\textbf{Entrega.}
Entregue suas soluções no Paca.  Soluções entregues fora de prazo
valerão menos.

\medskip

\noindent\textbf{Política de colaboração e uso de fontes.}
Todo trabalho entregue por você deve ser seu.  Você é encorajado a
discutir com seus colegas o material visto em sala e os enunciados dos
exercícios, mas tome cuidado para não compartilhar seu trabalho além
do permitido.  Nos \textit{exercícios individuais}, você não pode
compartilhar suas soluções ou mesmo ideias de soluções.  Nos
\textit{exercícios em grupo}, você só pode compartilhar suas ideias e
soluções com membros de seu grupo.  Nos exercícios em grupo,
\textit{cada membro do grupo deve escrever uma solução própria}---esta
disciplina tem como um de seus objetivos estudar como escrever
matemática e portanto o processo de escrita será enfatizado, mesmo nos
exercícios em grupo.  Ao entregar um exercício feito em grupo, não
esqueça de escrever o nome de todos os membros do grupo em sua
solução. 

Você não deve procurar soluções de terceiros (como de amigos ou na
Web).  Caso você acidentalmente encontre a solução de algum exercício
em algum lugar, você deve citar esta fonte em sua solução.  Caso você
acidentalmente acabe colaborando com colegas na descoberta de uma
solução, você deve citar esta colaboração em sua solução.  Seu
desempenho nesta disciplina ficará prejudicado caso você viole essas
regras.

\medskip
\noindent\textbf{Fontes dos exercícios.}  Vários dos exercícios vêm de
nossa bibliografia.  Usamos as seguintes abreviaturas (outras
abreviaturas poderão ser adicionadas posteriormente). \textbf{MH:}
Michael Hutchings, \textit{Introduction to mathematical arguments};
\textbf{KH:} Kevin Houston, \textit{How to think like a mathematician}; 
\textbf{DJV:} Daniel J. Velleman, \textit{How to prove it}.

\medskip
\noindent\textbf{Exercícios para entrega.}  Os exercícios para entrega
estão marcados com uma data de entrega.  Nesses exercícios, há também
indicação se é um exercício individual ou se pode ser feito em grupo.
No caso de exercícios em grupo, o número máximo de alunos por grupo
está especificado.

\bigskip
\hfill* * * * *\hfill\null
\bigskip

\begin{enumerate}[label=\nlabelE]
  
\item Faça os exercícios de~1 a~7, p.~27, de \textbf{MH}.
  
\item Faça o Exercício~1.34 de \textbf{KH}.

  \def\sdiff{\bigtriangleup}
\item A \textit{diferença simétrica}~$A\sdiff B$ de dois conjuntos~$A$
  e~$B$ é o conjunto~$(A\cup B)\setminus(A\cap B)$.  Prove que a
  operação de diferença simétrica é associativa, isto é,
  que~$A\sdiff(B\sdiff C)=(A\sdiff B)\sdiff C$ para quaisquer
  conjuntos~$A$, $B$ e~$C$.  \datedue{14/3/2018; exercício individual}

\item Faça o Exercício~6.11(ii) de~\textbf{KH}.

\item Faça o Exercício~6.11(iv) de~\textbf{KH}.

\item Faça os exercícios de~1 a~17 da Seção~1.2 de~\textbf{DJV}.
  
\item Seja~$n$ um inteiro positivo.  Sejam~$x_1,\dots,x_n$ variáveis
  booleanas.  Dado~$S\subset[n]$, definimos as fórmulas~$\phi_S$, 
  $\psi_S$ e~$\gamma_S$ como segue:
  \begin{equation}
    \label{eq:1}
    \phi_S=\bigvee_{i\in S}x_i,\qquad
    \psi_S=\bigvee_{i\in[n]\setminus S}\neg x_i\qqand
    \gamma_S=\phi_S\vee\psi_S.
  \end{equation}
  Finalmente, seja
  \begin{equation}
    \label{eq:2}
    \Phi_n=\bigwedge_{S\subset[n]}\gamma_S.
  \end{equation}
  Por exemplo, se~$n=2$ e~$S=\{2\}$, temos~$\gamma_S=\neg x_1\vee x_2$.
  Ademais,
  \begin{equation}
    \label{eq:3}
    \Phi_2=(x_1\vee x_2)\wedge(x_1\vee\neg x_2)\wedge(\neg x_1\vee
    x_2)\wedge(\neg x_1\vee\neg x_2).
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Suponha que~$n=3$ e~$S=\{2,3\}$.  Diga o que é~$\phi_S$.
  \item Diga o que é~$\Phi_3$.
  \item Mostre que~$\Phi_n$ é insatisfatível para qualquer valor
    de~$n$.
  \end{enumerate}
  \observacao{Você pode ficar na dúvida o que são~$\phi_\emptyset$
    e~$\psi_{[n]}$.  Vale que~$\gamma_\emptyset=\bigvee_{i\in[n]}\neg
    x_i$ e~$\gamma_{[n]}=\bigvee_{i\in[n]}x_i$.}
  \datedue{21/3/2018; exercício individual}
  
\item Faça o Exercício~10.11 de~\textbf{KH}.

\item Faça os itens~(i) a~(iv) do Exercício~11.12 de~\textbf{KH}. 

\item Considere a afirmação~$p$ dada abaixo:
  \begin{equation}
    \label{eq:4}
    p=(\forall x,\,y\in\RR)\big(x<y\Rightarrow(\exists z\in\RR)(x<z<y)\big).
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Determine a negação~$\neg p$ de~$p$.
  \item Diga em palavras (``em linguagem humana'') o significado
    de~$p$ e de~$\neg p$.
  \item A afirmação~$p$ é verdadeira?  A afirmação~$\neg p$ é verdadeira?  Justifique.  
  \end{enumerate}
  \datedue{28/3/2018; exercício individual}

\item Considere a afirmação~$q$ dada abaixo:
  \begin{equation}
    \label{eq:5}
    q=(\forall x,\,y\in\NN)\big(x<y\Rightarrow(\exists z\in\NN)(x<z<y)\big).
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Determine a negação~$\neg q$ de~$q$.
  \item Diga em palavras (``em linguagem humana'') o significado
    de~$q$ e de~$\neg q$.
  \item A afirmação~$q$ é verdadeira?  A afirmação~$\neg q$ é verdadeira?  Justifique. 
  \end{enumerate}
  \datedue{28/3/2018; exercício individual}

\item Faça os itens~(i), (ii) e~(iii) do Exercício~20.14
  de~\textbf{KH}.  \observacao{No item~(i), basta encontrar o erro na
    demonstração proposta.}

\item Faça o maior número possível dos itens~(iv) a~(xi) do
  Exercício~20.14 de~\textbf{KH}.

\item Faça os item~(x) do Exercício~20.14 de~\textbf{KH}.
  \datedue{4/4/2018; exercício individual}

\item Prove que a hipótese de~$n$ ser ímpar no Exercício~20.14(x)
  de~\textbf{KH} é necessária.

\item Faça o maior número possível dos itens~(i) a~(ix) do
  Exercício~22.10 de~\textbf{KH}.

\item Fixe um inteiro~$d\geq1$.  Sabemos que, para todo inteiro~$n$,
  exitem inteiros~$q$ e~$r$ com~$0\leq r<d$ tais que~$n=dq+r$.
  Ademais, sabemos que tais~$q$ e~$r$ são únicos.  Para cada~$0\leq
  r<d$, seja
  \begin{equation}
    \label{eq:6}
    A_r=\{n\in\ZZ\:n=dq+r\text{ onde $q$ e~$r\in\ZZ$ e }0\leq r<d\}.
  \end{equation}
  Seja~$\cP=\{A_0,\dots,A_{d-1}\}$.  Prove que~$\cP$ é uma partição
  de~$\ZZ$. 

\item Para todo inteiro~$n\geq1$, seja
  \begin{equation}
    \label{eq:7}
    \cP_n=\big\{\{X,[n]\setminus X\}\:X\subset[n-1]\big\}.
  \end{equation}
  Assim, $\cP_1=\big\{\{\emptyset,\{1\}\}\big\}$
  e~$\cP_2=\big\{\{\emptyset,\{1,2\}\}, \{\{1\},\{2\}\}\big\}$.  
  \begin{enumerate}[label=\rmlabel]
  \item Diga o que é~$\cP_3$ explicitamente.
  \item Qual é a cardinalidade de~$\cP_n$?
  \item Prove que~$\cP_n$ é uma partição de~$\cP([n])$.
  \end{enumerate}

\item Seja~$X$ um conjunto e~$\cF\subset\cP(X)$.  Dizemos que~$\cF$ é
  \textit{intersectante} se, para quaisquer~$F$ e~$F'\in\cF$,
  temos~$F\cap F'\neq\emptyset$, isto é, quaisquer dois membros
  de~$\cF$ tem algum elemento em comum.  Suponha agora que~$X$ seja
  finito.  Seja~$n$ a cardinalidade~$|X|$ de~$X$ e suponha
  que~$\cF\subset\cP(X)$ seja tal que~$|\cF|>2^{n-1}$.  Prove
  que~$\cF$ não é intersectante.  \datedue{4/4/2018; exercício
    individual} 
  
\item Seja~$X$ um conjunto com~$n$ elementos.  Determine a média das
  cardinalidades~$|A\cap B|$ onde~$A$ e~$B$ variam sobre todos os
  subconjuntos de~$X$.  Isto é, determine
  \begin{equation}
    \label{eq:8}
    {1\over2^{2n}}\sum_{A\subset X}\sum_{B\subset X}|A\cap B|.
  \end{equation}
  \hint{Use funções indicadoras.} \datedue{11/4/2018; exercício
    indivi\-dual} 
  
\item Uma urna contém bolas azuis e vermelhas.  Seja~$a$ o número de
  bolas azuis e~$b$ o número de bolas vermelhas na urna.
  Seja~$n=a+b$.  Qual é o número médio de bolas azuis nos~$2^n$
  subconjuntos de bolas da urna?  Isto é, determine
  \begin{equation}
    \label{eq:9}
    {1\over2^n}\sum_{S\subset U}|S\cap A|, 
  \end{equation}
  onde~$U$ é conjunto das bolas na urna e~$A$ é o subconjunto das
  bolas azuis em~$U$.

\item Uma urna contém um total de~$3n$ bolas, das quais~$n$ são azuis
  e~$2n$ são vermelhas.  Seja~$k$ um inteiro com~$0\leq k\leq n$.
  Qual é o número médio de bolas azuis nos~${3n\choose3k}$
  subconjuntos de~$3k$ bolas da urna?  Esta pergunta pode também ser
  formulada da seguinte forma.  Seja~$U$ o conjunto das~$3n$ bolas na
  urna.  Determine
  \begin{equation}
    \label{eq:9b}
    {3n\choose3k}^{-1}\sum_S|S\cap A|, 
  \end{equation}
  onde a soma sobre~$S$ estende-se sobre todos os~$S\subset U$
  com~$|S|=3k$ e~$A=\{x\in U\:x\text{ é azul}\}$.

\item Faça o maior número possível dos itens~(i) a~(xiii) do
  Exercício~23.8 de~\textbf{KH}.

\item Prove que a equação~$x^{2018}-2x^3+24=0$ não tem raízes
  racionais.  \datedue{11/4/2018; exercício individual} 

\item Dado~$x\in\RR$, definimos~$|x|$, o \textit{módulo de~$x$}, como
  sendo~$-x$ se~$x<0$ e~$x$ se~$x\geq0$.  Prove que, para todo~$x$
  e~$y\in\RR$, temos
  \begin{equation}
    \label{eq:10}
    |x+y|\leq|x|+|y|.
  \end{equation}

\item Prove que, para todo~$x$ e~$y\in\RR$, temos
  \begin{equation}
    \label{eq:10b}
    \big||x|-|y|\big|\leq|x-y|.
  \end{equation}

\item Faça o maior número possível dos itens~(i) a~(xvi) do
  Exercício~24.10 de~\textbf{KH}.

\item Seja~$N$ um inteiro positivo.  O \textit{$N$-ésimo número
    Harmônico}~$H_N$ é o número
  \begin{equation}
    \label{eq:11}
    \sum_{1\leq k\leq
      N}{1\over k}=1+{1\over2}+\dots+{1\over N}.
  \end{equation}
  Prove que~$H_{2^n}\geq1+n/2$ para todo inteiro~$n\geq0$.
  \datedue{25/4/2018; exercício individual}

\item Neste exercício, consideramos \textit{torneios}: o resultado de
  campeonatos em que todos os jogadores jogam contra todos os outros
  jogadores, e tais que não há empates nos jogos.  Por exemplo, um
  torneio com~$n=4$ jogadores poderia ser tal que o jogador~$i$ venceu
  do jogador~$j$ se e só se o par ordenado~$(i,j)$ pertence ao
  conjunto
  \begin{equation}
    \label{eq:12}
    \{(3,1),(1,4),(4,2),(2,1),(2,3),(3,4)\}.
  \end{equation}
  Note que, no torneio acima, o jogador~$3$ venceu do jogadores~$1$
  e~$4$ e perdeu do jogador~$2$.  Você pode achar conveniente desenhar
  certos diagramas para representar torneios: represente cada jogador
  por um ponto e se o jogador~$i$ venceu do jogador~$j$, desenhe uma
  flecha de~$i$ para~$j$.  Desenhe um diagrama para representar o
  torneio dado acima.  

  Introduzimos agora uma definição: dizemos que um jogador~$i$ em um
  torneio é um \textit{rei} se, para todo jogador~$j$ diferente
  de~$i$, vale que~$i$ venceu de~$j$ ou~$i$ venceu de um jogador~$k$
  que venceu de~$j$.  Por exemplo, no exemplo acima, o jogador~$3$ é
  um rei.  Prove que todo torneio não-vazio tem um rei.  \hint{Tente
    fazer este exercício seriamente sem ler essa sugestão.  Se não
    sair, leia a sugestão \texttt{:-)}.  Use indução em~$n$, o número
    de jogadores no torneio.  Suponha que os jogadores
    são~$1,\dots,n$.  No passo de indução, aplique a hipótese de
    indução duas vezes: uma vez no torneio restrito aos
    jogadores~$1,\dots,n-1$ e outra vez em um outro torneio com~$n-1$
    jogadores.}  \datedue{25/4/2018; exercício individual}

\item Sejam~$A_1,\dots,A_n\subset X$ conjuntos.  Para~$x\in X$,
  seja~$\occ(x)$ o número de ocorrências de~$x$ nos~$A_i$, isto é,
  \begin{equation}
    \label{eq:13}
    \occ(x)=\sum_{1\leq k\leq n}I_{A_i}(x),
  \end{equation}
  onde~$I_{A_i}$ é a função característica de~$A_i$ ($1\leq i\leq
  n$).  Prove que
  \begin{equation}
    \label{eq:14}
    A_1\bigtriangleup A_2\bigtriangleup\dots\bigtriangleup A_n
    =\{x\in X\:\occ(x)\text{ é ímpar}\}.
  \end{equation}

\item Seja~$\pi(x)$ o número de números primos~$p$ com~$0<p\leq x$.
  Prove que, para todo inteiro positivo~$N$, temos
  \begin{equation}
    \label{eq:15}
    \pi(N)\geq{1\over2}\log_2N.
  \end{equation}
  \hint{Sejam~$p_1,\dots,p_r$ os primos menores ou iguais a~$N$.
    Assim, $r=\pi(N)$.  Usando decomposição em números primos, observe
    que todo inteiro positivo~$m\leq N$ pode ser escrito na
    forma~$n^2q$, onde~$n$ é um inteiro positivo e~$q$ é um produto
    dos~$p_i$ ($1\leq i\leq r$), com cada~$p_i$ ocorrendo no máximo
    uma vez em~$q$.  Quantos inteiros positivos~$m\leq N$ há?  Quantos
    inteiros positivos~$m\leq x$ podem ser escritos na forma acima?}

\item Faça o maior número possível dos itens~(i) a~(iii) do
  Exercício~25.7 de~\textbf{KH}.

\item Sejam~$A_1,\dots,A_n\subset[n]$ ($n\in\NN$) conjuntos
  com~$|A_i|\geq3$ para todo~$i$.  Prove que há~$i$, $j$ e~$k$
  com~$1\leq i<j<k\leq n$ tais que $A_i\cap A_j\cap A_k\neq\emptyset$.

\item Seja~$A(n)$ ($n\geq2$) a afirmação
  \begin{gather*}
    \text{para quaisquer }
    x_1,\dots,x_n\in\RR\text{ com~$x_i\geq0$ para todo~$i$,}
    \text{ vale que }\\{1\over n}(x_1+\dots+x_n)\geq\(x_1\dots
    x_n\)^{1/n}. 
  \end{gather*}
  A afirmação~$A(n)$ é conhecida como a desigualdade das médias
  aritmética e geométrica (desigualdade MAMG).
  \begin{enumerate}[label=\rmlabel]
  \item Prove~$A(2)$.
  \item Seja~$n\geq2$.  Prove que se~$A(2)$ e~$A(n)$ valem,
    então~$A(2n)$ também vale. 
  \item Seja~$n>2$.  Prove que se~$A(n)$ vale, então~$A(n-1)$ também
    vale.  \hint{Tome~$x_n=(x_1+\dots+x_{n-1})/(n-1)$.}
  \item Conclua que~$A(n)$ vale para todo~$n\geq2$.
  \end{enumerate}
  \noindent\datedue{2/5/2018; exercício individual}
  
\item 
  \begin{enumerate}[label=\rmlabel]
  \item Seja
    \begin{equation}
      \label{eq:16}
      X=\left\{n-{1\over m}\:n,\,m\in\NN\text{ com }n\geq1\text{ e
        }m\geq1\right\}. 
    \end{equation}
    Prove que~$X$ é bem ordenado, isto é, prove que todo~$Y\subset X$
    não-vazio tem um elemento mínimo: um elemento~$y\in Y$ tal que,
    para todo~$y'\in Y$, vale que~$y\leq y'$.
    
  \item Seja
    \begin{equation}
      \label{eq:16b}
      Z=\left\{n+{1\over m}\:n,\,m\in\NN\text{ com }n\geq1\text{ e
        }m\geq1\right\}. 
    \end{equation}
    Prove que~$Z$ \textit{não} é bem ordenado, isto é, prove que
    existe~$Y\subset Z$ não-vazio \textit{sem} elemento mínimo.
  \end{enumerate}
  \noindent\datedue{2/5/2018; exercício individual}

\item\label{E:floor} Para todo~$x\in\RR$, definimos~$\lfloor x\rfloor$
  como sendo o \textit{piso} de~$x$ (ou \textit{chão} de~$x$): o maior
  inteiro que não excede~$x$.  Por exemplo, $\lfloor\pi\rfloor=3$,
  $\lfloor e\rfloor=2$, $\lfloor-\pi\rfloor=-4$
  e~$\lfloor-e\rfloor=-3$.  Analogamente, definimos~$\lceil x\rceil$
  ($x\in\RR$) como sendo o \textit{teto} de~$x$: o menor inteiro maior
  ou igual a~$x$.
  \begin{enumerate}[label=\rmlabel]
  \item Desenhe o gráfico da função $f\:\RR\to\RR$ dada por
    $f(x)=\lfloor x\rfloor$ ($x\in\RR$).
  \item Prove que~$\lceil x\rceil=-\lfloor-x\rfloor$ para
    todo~$x\in\RR$.
  \item Prove ou dê contra-exemplo para as seguintes afirmações.
    \begin{enumerate}[label=\alabel]
    \item Para qualquer~$x\in\RR$, não existe~$k\in\ZZ$ tal que
      $\lfloor x\rfloor<k\leq x$.
    \item Se~$x$ e~$y$ são reais tais que $\lfloor
      x\rfloor<\lfloor y\rfloor$, então existe~$k\in\ZZ$ tal que
      $x<k\leq y$.
    \item Se~$n\in\NN$, então $n=\lfloor n/2\rfloor+\lceil n/2\rceil$.
    \item Para todo~$x$ real não-negativo, temos~$\lfloor\sqrt{\lfloor
        x\rfloor}\rfloor=\lfloor\sqrt x\,\rfloor$.
    \item Para todo~$x$ real não-negativo, temos~$\lceil\sqrt{\lfloor
        x\rfloor}\rceil=\lceil\sqrt x\,\rceil$.
    \item Para todo~$n\in\NN$, temos $\lfloor\lfloor\lfloor
      n/2\rfloor/2\rfloor/2\rfloor=\lfloor n/8\rfloor$.  \hint{Considere
        inicialmente a afirmação $\lfloor\lfloor
        x\rfloor/2\rfloor=\lfloor x/2\rfloor$.}
    \end{enumerate}
  \end{enumerate}

\item\label{E:floor2} Este exercício é uma continuação do
  Exercício~\ref{E:floor}.  Prove ou dê contra-exemplo para as
  seguintes afirmações.
  \begin{enumerate}[label=\rmlabel]
  \item Se~$n\in\NN$ e~$\alpha+\beta=1$, onde~$\alpha$ e~$\beta$ são
    reais não-negativos, então
    $n=\lfloor\alpha n\rfloor+\lceil\beta n\rceil$.
  \item Para todo~$x$ real não-negativo e todo inteiro~$k\geq1$, temos
    \begin{equation}
      \label{eq:18ab}
      \underbrace{\llfloor
        \sqrt{
          \llfloor
          \sqrt{\lfloor\,
            \dots
            \lfloor\sqrt{\lfloor x\rfloor}\rfloor
            \dots\rfloor
          }
          \rrfloor
        }\rrfloor
      }_{k\text{ vezes}}
      =\llfloor\sqrt[2^k]x\;\rrfloor
      =\llfloor x^{1/2^k}\rrfloor.
    \end{equation}
  \item Para todo~$n\in\NN$ e~$k\geq1$ ($k\in\NN$), temos
    \begin{equation}
      \label{eq:18b}
      \underbrace{\lfloor\lfloor\dots\lfloor\lfloor
      n/2\rfloor/2\rfloor\dots\rfloor/2\rfloor}_{k\text{ vezes}}
      =\lfloor n/2^k\rfloor.
    \end{equation}
  \end{enumerate}
  \noindent\datedue{9/5/2018; este exercício pode ser feito em
    grupos de~$\mathbf2$}

\item\label{E:base2} Para todo inteiro~$n$, sabemos como escrever~$n$
  na base~$2$.  Seja~$s(n)$ a cadeia de bits que representa~$n$ na
  base~$2$; aqui, por simplicidade, supomos~$n\geq0$.  Por exemplo,
  se~$n=22$, temos~$s(n)=10110$ e se~$n=2018$,
  então~$s(n)=11111100010$.  Seja~$\ell(n)$ o \textit{comprimento}
  de~$s(n)$, isto é, o número de bits em~$s(n)$.  Assim, $\ell(22)=5$
  e~$\ell(2018)=11$.
  \begin{enumerate}[label=\rmlabel]
  \item Monte uma tabela com~$n$, $s(n)$ e~$\ell(n)$ para~$1\leq n\leq
    15$.
  \item Prove por indução que se~$n\geq1$, então
    $\ell(n)=\lfloor\log_2n\rfloor+1$.
  \end{enumerate}

\item Dados inteiros positivos~$a$ e~$n$, queremos obter~$a^n$
  calculando apenas produtos.  Naturalmente, é possível obter~$a^n$
  calculando $a\times\dots\times a$ ($n-1$ produtos).  É possível
  calcular~$a^n$ com um número consideravelmente menor de produtos: de
  fato, (*)~\textsl{é possível calcular~$a^n$ fazendo, no máximo,
    $2\log_2n$ produtos}.  Por exemplo, é possível calcular~$a^{2018}$
  fazendo no máximo~$2\log_22018=2\times10.9\dots=21.9\dots$ produtos
  (o algoritmo óbvio faria~$2017$ produtos e a afirmação~(*) diz que
  basta fazer~$21$ produtos ou menos).
  \begin{enumerate}[label=\rmlabel]
  \item\label{item:E37i} Prove a afirmação~(*) acima.  \hint{Você pode
      achar mais conveniente demonstrar a seguinte afirmação por
      indução: \textsl{é possível calcular~$a^n$ fazendo no
        máximo~$2(\ell(n)-1)$ produtos}, onde~$\ell(n)$ é como
      definido no Exercício~\ref{E:base2}.  \textit{Dica}: note que,
      por exemplo, $a^5=(a^2)^2a$ e
      $a^{22}=\big(\big((a^2)^2\big)^2a^2a\big)^2$.}
  \item A sugestão do item~\ref{item:E37i} acima dá a
    cota~$2(\ell(n)-1)$ para o problema em questão.  Prove uma cota
    que é em geral \textit{melhor}, envolvendo a
    quantidade~$\ell_1(n)$, definido como sendo o número de bits~$1$
    na representação binária de~$n$ (por exemplo, $\ell_1(22)=3$
    e~$\ell_1(2018)=7$.)  \observacao{A motivação aqui são exemplos
      como~$a^{1024}$: esse número pode ser calculado com~$10$
      produtos, enquanto que a cota sugerida em~\ref{item:E37i}
      é~$2(\ell(n)-1)=20>10$.}
  \end{enumerate}
  \noindent\datedue{9/5/2018; este exercício pode ser feito em
    grupos de~$\mathbf2$}

\item Os matemáticos egípcios em 1800 A.C.\ expressavam frações
  racionais~$r$ entre~$0$ e~$1$ na forma $1/a_1+\dots+1/a_k$, com
  os~$a_i$ naturais distintos.  Por exemplo, uma forma para eles
  expressarem~$2/5$ era $1/3+1/15$, e uma forma de eles
  expressarem~$5/8$ era $1/2+1/8$.\footnote{Um uso da identidade
    $5/8=1/2+1/8$ é o seguinte: suponha que temos~$5$ pizzas para
    dividir entre~$8$ pessoas.  Uma forma simples seria dividir cada
    pizza em~$8$ pedaços e cada um ficar com~$5$ pedaços.  Uma forma
    alternativa melhor~(?) é dividir~$4$ pizzas em metades e uma pizza
    em~$8$ partes, e cada um ficar com uma metade e um pedaço de
    tamanho~$1/8$.}
  \begin{enumerate}[label=\rmlabel]
  \item\label{item:Eg.i} Escreva um programa que recebe como entrada
    um racional~$r$ com~$0<r<1$ e que tem como saída uma
    `representação egípcia' de~$r$.  Para escrever seu programa, use o
    seguinte processo indutivo, devido a Fibonacci (1202 D.C.):
    suponha~$r=m/n$ com~$m$ e~$n$ naturais não nulos.  Seja
    então~$q=\lceil n/m\rceil$ e use
    \begin{equation}
      \label{eq:17}
      {m\over n}={1\over q}+\(\text{representação de }{m\over n}-{1\over
        q}\).
    \end{equation}
  \item Use seu programa para obter uma representação egípcia
    de~$5/121$.
  \item Prove que seu programa de~\ref{item:Eg.i} funciona
    \texttt{:-)}.  Isto é, prove que ele \textit{termina} (não entra
    em um loop infinito) e que os denominadores que ele obtém para a
    representação egípcia são todos distintos.  \hint{Para provar que
      seu programa termina, prove que os `valores de~$m$' que ocorrem
      em seu programa decrescem estritamente.  Para provar que os
      denominadores são todos distintos, prove que os `valores de~$q$'
      são estritamente crescentes.}
  \end{enumerate}
  \noindent\datedue{16/5/2018; este exercício pode ser feito em
    grupos de~$\mathbf2$}

\item\label{Q:B_n} Em nossa análise da busca binária em listas
  ordenadas, ocorreram as árvores binárias~$B_n$ definidas a seguir.
  Para~$n=0$, a árvore~$B_n$ é uma árvore vazia (uma árvore com um
  único nó externo).  Suponha agora que~$n\geq1$ e que~$B_n$ já esteja
  definida para valores menores de~$n$.  Se~$n$ é ímpar, temos que
  $B_n=(r,B_{\lfloor n/2\rfloor},B_{\lfloor n/2\rfloor})$
  (naturalmente, supomos aqui que~$r$ é um nó novo, que não ocorre nas
  subárvores direita e esquerda de~$B_n$ e que essas subárvores não
  têm nós comuns).  Se~$n$ é par, temos
  que~$B_n=(r,B_{n/2},B_{n/2-1})$.  Desenhe as árvores~$B_n$
  para~$0\leq n\leq8$.

\item Lembre que, dada uma árvore binária~$T$, a
  \textit{profundidade}~$\prof(x)$ de um nó~$x$ de~$T$ é sua distância
  à raiz de~$T$.  Assim, a raiz de~$T$ tem profundidade~$0$ e se~$x$ é
  filho de~$p$, então $\prof(x)=\prof(p)+1$.  Definimos a
  altura~$h(T)$ de uma árvore~$T$ como sendo~$\max_x\prof(x)$, onde o
  máximo é tomado sobre todos os nós~$x$ de~$T$.  Seja~$h(n)=h(B_n)$,
  onde~$B_n$ é a árvore definida no Exercício~\ref{Q:B_n}.
  Determine~$h(n)$ para todo~$n\geq0$.  \observacao{Por exemplo,
    $h(0)=0$, $h(1)=1$ e~$h(2)=h(3)=2$.}

\item Lembre que, quando fazemos uma busca binária em uma lista
  ordenada e essa busca é sem sucesso, chegamos a um nó externo da
  árvore~$B_n$ (veja o Exercício~\ref{Q:B_n}), onde~$n$ é o número de
  elementos em nossa lista.  Fixe uma lista $x_0\leq\dots\leq x_{n-1}$
  e suponha, por simplicidade, que todos os~$x_i$ são distintos.
  Suponha que fazemos buscas sem sucesso nessa lista.  Cada busca
  sem sucesso~$b$ resulta em um certo número de perguntas do tipo
  ``$x\leq y\,?$'' sendo feitas.  Seja~$p(b)$ o número de tais
  perguntas feitas para realizar a busca~$b$.
  Sejam~$\alpha(n)=\min p(b)$ e $\beta(n)=\max p(b)$, onde o mínimo e
  o máximo são tomados sobre todas as buscas sem sucesso~$b$.  (Note
  que~$\beta(n)$ é o número de tais perguntas ``no pior caso'',
  e~$\alpha(n)$ é o número de perguntas ``no melhor caso''.)
  \begin{enumerate}[label=\rmlabel]
  \item Determine~$\alpha(n)$.
  \item Determine~$\beta(n)$.
  \item É verdade que~$\alpha(n)\leq\beta(n)\leq\alpha(n)+1$?
    Justifique sua resposta.
  \end{enumerate}
  \datedue{23/5/2018; exercício individual}

\item Lembre que, quando fazemos uma busca binária em uma lista
  ordenada e essa busca é com sucesso, chegamos a um nó interno da
  árvore~$B_n$ (veja o Exercício~\ref{Q:B_n}), onde~$n$ é o número de
  elementos em nossa lista.  Fixe uma lista $x_0\leq\dots\leq x_{n-1}$
  e suponha, por simplicidade, que todos os~$x_i$ são distintos.
  Suponha que fazemos buscas com sucesso nessa lista.  Cada busca com
  sucesso~$b$ resulta em um certo número de perguntas do tipo
  ``$x\leq y\,?$'' sendo feitas.  Seja~$p(b)$ o número de tais
  perguntas feitas para realizar a busca~$b$.  Note
  que~$p(b)=\prof(x_i)+1$ quando buscamos~$x$ na lista e~$x=x_i$.
  Seja~$\gamma(n)=\max p(b)$, onde o máximo é tomado sobre todas as
  buscas com sucesso~$b$.  (Note que~$\gamma(n)$ é o número de tais
  perguntas ``no pior caso''.)
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$\gamma(n)=\lfloor\log_2n\rfloor+1$.
  \item O \textit{nível}~$\ell$ de~$B_n$ é o conjunto dos nós
    internos~$y$ com~$\prof(y)=\ell$.  Por exemplo, no nível~$0$ temos
    somente a raiz de~$B_n$ se~$n>0$ (se~$n=0$, não há nós internos).
    Prove que o número de elementos no nível~$\ell$ de~$B_n$
    ($n\geq1$) é~$2^\ell$ se~$\ell\leq\lfloor\log_2n\rfloor-1$.
  \item Seja~$N_{1/2}$ o número de elementos~$x_i$ da lista
    $x_0\leq\dots\leq x_{n-1}$ tal que a busca com sucesso de~$x_i$ é
    tal que fazemos
    \begin{equation}
      \label{eq:18}
      \leq{1\over2}\gamma(n)
    \end{equation}
    perguntas ``$x<y\,?$''.  Isto é, para esses~$N_{1/2}$
    elementos~$x_i$, a busca com sucesso faz metade ou menos perguntas
    ``$x<y\,?$'' comparado com o pior caso.  
    \begin{enumerate}[label=\alabel]
    \item Prove que~$N_{1/2}<\sqrt{2n}$.  Assim, apenas para uma
      fração pequena dos~$x_i$ (que tende para~$0$
      conforme~$n\to\infty$) temos que a busca de~$x_i$ ``custa''
      $\leq\gamma(n)/2$ perguntas.
    \item O que ocorre se trocamos~$1/2$ em~\eqref{eq:18} por algo
      como~$3/4$ ou~$99/100$?  Sejam~$N_{3/4}$ e~$N_{99/100}$ os
      números de~$x_i$ correspondentes.  É ainda verdade que 
      \begin{equation}
        \label{eq:21}
        \lim_{n\to\infty}{N_{3/4}\over n}=0
      \end{equation}
      e
      \begin{equation}
        \label{eq:21b}
        \lim_{n\to\infty}{N_{99/100}\over n}=0?
      \end{equation}
      \NB{A conclusão é que, para a vasta maioria das buscas com
        sucesso, o número de perguntas que se faz não é
        significativamente diferente de~$\log_2n$.}
    \end{enumerate}
  \end{enumerate}

\item As seguintes árvores binárias~$M_n$ ($n\geq0$) ocorrem quando
  estuda-se o \textit{mergesort} (ordenação por
  intercalação).\footnote{Veja
    \url{https://introcs.cs.princeton.edu/python/42sort/} e
    \url{https://introcs.cs.princeton.edu/python/42sort/merge.py.html}.
    Para executar \texttt{merge.py}, você precisará de
    \url{https://introcs.cs.princeton.edu/python/code/stdio.py}
    e \url{https://introcs.cs.princeton.edu/python/code/stdarray.py}.} 
  Para~$n=0$, temos que~$M_n=(z)$ (isto é, $M_0$ tem um único nó
  externo).  Para~$n=1$, temos que~$M_n=(r,(z),(z'))$ (assim, $M_1$
  tem um nó interno e dois nós externos).  Para~$n\geq2$, temos
  que $M_n=(r,M_{\lfloor n/2\rfloor},M_{\lceil n/2\rceil})$.
  \begin{enumerate}[label=\rmlabel]
  \item Desenhe~$M_n$ para~$0\leq n\leq6$.
  \item Quantos nós internos tem~$M_n$?  Quantos nós externos
    tem~$M_n$? 
  \item Um nó interno é uma \textit{folha} se ele tem dois nós
    externos como filhos.  Quantas folhas tem~$M_n$?
  \item Seja~$h(M_n)$ a altura de~$M_n$.  
    \begin{enumerate}[label=\alabel]
    \item Prove que se~$r\leq s$, então $h(M_r)\leq h(M_s)$. 
    \item Prove que $h(M_n)=\lceil\log_2n\rceil+1$ para todo~$n\geq1$. 
    \end{enumerate}
  \end{enumerate}

\item Faça o maior número possível dos itens~(i) a~(xii) do
  Exercício~27.23 de~\textbf{KH}.

\item Sejam~$a$ e~$b$ números naturais, com~$b>0$.  Definimos
  sequências de naturais $p_1,\dots,p_t$ e $q_1,\dots,q_{t-2}$
  para um certo~$t\geq3$ da seguinte forma.  Pomos~$p_1=a$ e~$p_2=b$.
  Seja agora~$k\geq3$ e suponha que já definimos $p_3,\dots,p_{k-1}$ e
  $q_1,\dots,q_{k-3}$.  Se~$p_{k-1}=0$, então tomamos~$t=k-1$ e
  terminamos a definição de nossas sequências $p_1,\dots,p_t$ e
  $q_1,\dots,q_{t-2}$.  Por outro lado, se~$p_{k-1}\neq0$,
  definimos~$p_k$ e~$q_{k-2}$ pela divisão de~$p_{k-2}$ por~$p_{k-1}$:
  isto é, tomamos~$p_k$ e~$q_{k-2}$ como sendo os únicos naturais que
  satisfazem
  \begin{equation}
    \label{eq:19}
    p_{k-2}=q_{k-2}p_{k-1}+p_k,\qquad0\leq p_k<p_{k-1}.
  \end{equation}
  O procedimento acima define indutivamente a sequência dos~$p_k$ e
  a sequência dos~$q_k$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que
    \begin{equation}
      \label{eq:20}
      p_1p_2=\sum_{k=1}^{t-2}q_k^{\vphantom{2}}p_{k+1}^2.
    \end{equation}
  \item Faça um desenho que ilustra a identidade~\eqref{eq:20}.
    \hint{Considere um retângulo $p_1\times p_2$.}
  \end{enumerate}
  \datedue{23/5/2018; exercício individual}

\item Um prédio tem duas escadarias, uma delas com~$780$ degraus e
  outra com~$700$ degraus.  Sabendo que os degraus das duas escadas
  estão no mesmo nível exatamente quando conduzem a um mesmo andar,
  descubra quantos andares tem o prédio.

\item Para todo~$n\in\NN$, definimos o \textit{$n$-ésimo número de
    Fermat} com sendo~$F_n=2^{2^n}+1$.  Assim, $F_0=3$, $F_1=5$,
  $F_2=17$ etc.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que, para todo~$n\in\NN$, temos
    \begin{equation}
      \label{eq:24}
      \prod_{0\leq k\leq n}F_k=F_{n+1}-2.
    \end{equation}
  \item\label{item:F} Prove que se~$k$ e~$\ell$ são dois naturais
    distintos, então~$\mdc(F_k,F_\ell)=1$.
  \item É verdade que todo os~$F_n$ ($n\in\NN$) são primos?
  \item Deduza de~\ref{item:F} acima que há infinitos números primos.
    \NB{Essa é a prova de Goldbach para o fato de que há infinitos
      números primos.}
  \end{enumerate}
  \datedue{30/5/2018; exercício individual}  

\item Faça o maior número possível dos itens~(i) a~(xi) do
  Exercício~28.19 de~\textbf{KH}.

\item Sejam~$a$ e~$b$ inteiros com~$\mdc(a,b)=1$.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$\mdc(a+b,a-b)\leq2$.  \hint{Considere os
      números~$2a$ e~$2b$.}
  \item Prove que~$\mdc(a+b,a^2+b^2)\leq2$.  \hint{Considere os
      números~$2ab$, $ab-a^2$ e~$ab-b^2$.}
  \end{enumerate}
  \datedue{30/5/2018; exercício individual}  

\item Sejam~$x$ e~$y$ inteiros.  Professor~C (de ``cento e cinco'')
  resolveu chamar de \textit{divisores brilhantes de~$x$ e~$y$} os
  divisores comuns~$b\geq0$ de~$x$ e~$y$ que têm a seguinte
  propriedade: \textsl{se~$c$ divide ambos~$x$ e~$y$,
    então~$c\mid b$}.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que para quaisquer~$x$ e~$y\in\ZZ$,
    há no máximo um divisor brilhante para~$x$ e~$y$.
  \item Prove que, para quaisquer~$x$ e~$y\in\ZZ$, há um divisor
    brilhante para~$x$ e~$y$.
  \item Qual é o nome usual para esses divisores brilhantes?
  \end{enumerate}
  \datedue{6/6/2018; exercício individual}  
  
\item Sejam~$a$ e~$b$ inteiros.  Provamos em sala que existem
  inteiros~$k$ e~$\ell$ tais que~$ka+\ell b=\mdc(a,b)$.  A prova que
  vimos é indutiva: o caso~$b=0$ é claro e, se~$b\neq0$, então
  encontramos~$k'$ e~$\ell'$ para o par de inteiros~$b$ e~$r$, onde
  $a=bq+r$ e~$0\leq r<|b|$ ($q$ e~$r\in\ZZ$), e produzimos~$k$
  e~$\ell$ a partir de~$k'$ e~$\ell'$.  Implemente este algoritmo:
  escreva um programa que, dados~$a$ e~$b$, encontra~$k$, $\ell$
  e~$\mdc(a,b)$.  \NB{A parte principal de seu programa será uma
    função recursiva, que implementa o algoritmo dado nessa prova.}

\item Sejam~$a$ e~$b$ inteiros.  Queremos calcular~$\mdc(a,b)$ e
  também encontrar inteiros~$\alpha$ e~$\beta$ tais
  que~$\alpha a+\beta b=\mdc(a,b)$.  Considere o procedimento a
  seguir.  Construímos uma sequência de matrizes
  \begin{equation}
    \label{eq:26}
    M^{(0)},\dots,M^{(t)},
  \end{equation}
  para algum~$t\geq0$, da seguinte forma.  Tomamos
  \begin{equation}
    \label{eq:25}
    M^{(0)}=
    \begin{pmatrix}
      a &1 &0\\
      b &0 &1
    \end{pmatrix}.
  \end{equation}
  Suponha agora que~$k\geq1$ e que~$M^{(0)},\dots,M^{(k-1)}$ já
  estejam definidos.  Sejam~$m_{ij}$ as entradas
  de~$M^{(k-1)}$; isto é, suponha que
  $M^{(k-1)}=(m_{ij})_{0\leq i<2,\,0\leq j<3}$.
  Se~$m_{10}=0$, então tomamos~$t=k-1$ e terminamos a
  definição da sequência em~\eqref{eq:26}.  Caso contrário, suponha
  $m_{00}=m_{10}q+r$, onde~$q$ e~$r$ são inteiros e~$0\leq
  r<|m_{10}|$.  Seja
  \begin{equation}
    \label{eq:27}
    N=
    \begin{pmatrix}
      0 & 1\\
      1 &-q
    \end{pmatrix}, 
  \end{equation}
  e faça $M^{(k)}=NM^{(k-1)}$.  Isto define~$M^{(k)}$ e a sequência
  em~$\eqref{eq:26}$ fica definida por indução.  Suponha que última
  matriz~$M^{(t)}$ em~\eqref{eq:26} tenha a forma
  \begin{equation}
    \label{eq:28}
    M^{(t)}=
    \begin{pmatrix}
      m  &\alpha  &\beta\\
      m' &\alpha' &\beta'
    \end{pmatrix}.
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Prove que $m=\mdc(a,b)$.
  \item Prove que $\alpha a+\beta b=\mdc(a,b)$.  \hint{%
      Suponha que $m_{ij}^{(k)}$ sejam as entradas de~$M^{(k)}$
      ($1\leq k\leq t$); isto é,
      $M^{(k)}=(m_{ij}^{(k)})_{0\leq i<2,\,0\leq j<3}$.  Prove que,
      para todo~$k$, vale que
      $m_{i0}^{(k)}=m_{i1}^{(k)}a+m_{i2}^{(k)}b$ para ambos~$i=0$
      e~$i=1$.}
  \item Implemente este algoritmo.  Você obterá assim uma versão
    \textit{não-recursiva} do algoritmo de Euclides estendido
    \texttt{:-)}. 
  \end{enumerate}
  \datedue{6/6/2018; exercício individual}  

\item Dado um conjunto não-vazio de inteiros~$A$, seja
  \begin{equation}
    \label{eq:Div_def}
    \Div A=\{d\in\NN\:\text{ para todo~$a\in A$, vale que }d\mid a\}.
  \end{equation}
  Isto é, $\Div A$ é o conjunto dos divisores não-negativos comuns dos
  elementos em~$A$.  
  \begin{enumerate}[label=\rmlabel]
  \item Sejam~$a_1,\dots,a_n$ inteiros ($n\geq2$).  Prove que
    \begin{equation}
      \label{eq:23}
      \Div\{a_1,\dots,a_n\}=\Div\{a_1,\dots,a_{n-2},\mdc(a_{n-1},a_n)\}.
    \end{equation}
  \item Seja~$A$ um conjunto não-vazio de inteiros, e suponha que~$A$
    contenha um elemento não-nulo.  Definimos o \textit{máximo divisor
      comum}~$\mdc A$ de~$A$ como sendo o elemento máximo de~$\Div A$,
    isto é, $\mdc A=\max\Div A$.  Se~$A=\{0\}$, então
    pomos~$\mdc A=0$.  Escreva um programa que, dado um
    conjunto~$A\neq\emptyset$ de inteiros, calcula~$\mdc A$.
  \end{enumerate}

\item
  \begin{enumerate}[label=\rmlabel]
  \item Sejam~$A$ e~$B$ conjuntos não-vazios de inteiros, com~$A\subset
    B$.  Prove que~$\mdc A\geq\mdc B$.
  \item Seja~$A=\{a_1,a_2,\dots\}$ um conjunto infinito de inteiros.
    Prove que, para algum~$n\geq1$, vale que $\mdc
    A=\mdc\{a_1,\dots,a_n\}$. 
  \end{enumerate}

\item Seja~$A\neq\emptyset$ um conjunto de inteiros e seja~$d=\mdc
  A$.  Prove que~$d$ é uma combinação linear inteira de elementos
  de~$A$.  Isto é, prove que existem~$a_1,\dots,a_n\in A$
  e~$\alpha_1,\dots,\alpha_n\in\ZZ$ tais que
  \begin{equation}
    \label{eq:22}
    d=\sum_{1\leq i\leq n}\alpha_ia_i.
  \end{equation}

\item Seja~$A$ um conjunto não-vazio de inteiros.  Professor~C
  resolveu chamar de \textit{divisores brilhantes} de~$A$ os
  inteiros~$b\in\Div A$ com a seguinte propriedade:
  \textsl{se~$c\in\Div A$, então~$c\mid b$}.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que, para todo~$A\subset\ZZ$ com~$A\neq\emptyset$,
    há no máximo um divisor brilhante para~$A$.
  \item Prove que, para todo~$A\subset\ZZ$ com~$A\neq\emptyset$, há um
    divisor brilhante para~$A$.
  \item Qual é o nome usual para esses divisores brilhantes?
  \end{enumerate}
  
\item Faça o maior número possível dos itens~(i) a~(xiv) do
  Exercício~29.23 de~\textbf{KH}.

\item Faça os itens~(ii), (iii) e~(iv) do Exercício~31.25
  de~\textbf{KH}.

\item Seja~$p$ um primo com~$p\equiv1\pmod4$.
  \begin{enumerate}[label=\rmlabel]
  \item Sejam~$m$ e~$n$ naturais com~$m+n=p-1$.  Prove que
    $m!n!\equiv(-1)^{n+1}\pmod p$.  \hint{Observe
      que~$-1\equiv p-1\pmod p$, $-2\equiv p-2\pmod p$, etc e use o
      teorema de Wilson, que diz que $(p-1)!\equiv-1\pmod p$ para todo
      primo~$p$ (veremos a prova desse resultado na aula
      de~11/6/2018).}  \item Prove que
    \begin{equation}
      \label{eq:29}
      \(\(p-1\over2\)!\)^2\equiv-1\pmod p.
    \end{equation}
  \item Deduza que existe~$a$ inteiro com~$1\leq a\leq(p-1)/2$ tal
    que~$a^2\equiv-1\pmod p$.
  \item Considere a equação~$x^2=-1$.  Deduza que essa equação tem
    solução nos inteiros módulo~$p$ (isto é, existe~$a\in\ZZ_p$ tal
    que~$a^2=-1$).
  \item Tome agora~$p=11$, de forma que~$p\not\equiv1\pmod4$.
    Verifique que~$x^2=-1$ não tem solução em~$\ZZ_p=\ZZ_{11}$.
  \end{enumerate}
  \datedue{13/6/2018; exercício individual}

\item Sejam~$a$, $b$ e~$n$ inteiros com~$n>0$.  Considere a equação
  \begin{equation}
    \label{eq:30}
    ax\equiv b\pmod n.
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~\eqref{eq:30} tem solução em~$\ZZ$ se e só
    se~$\mdc(a,n)\mid b$.
  \item Seja
    \begin{equation}
      \label{eq:31}
      S=S_{a,b,n}=\{x\in\ZZ\:\quad ax\equiv b\pmod b\}
    \end{equation}
    o conjunto solução de~\eqref{eq:30}.  Suponha que~$x_0\in\ZZ$ seja
    uma solução de~\eqref{eq:30} e seja~$d=\mdc(a,n)$.  Prove que
    \begin{equation}
      \label{eq:32}
      S=\{x_0+tn/d\:t\in\ZZ\}.
    \end{equation}
  \end{enumerate}

\item Sejam~$p$ um primo e~$a$ um inteiro com~$p\nmid a$.
  Seja~$R\subset\ZZ$ um sistema completo de resíduos módulo~$p$.
  Prove que
  \begin{equation}
    \label{eq:33}
    aR=\{ar\:r\in R\}
  \end{equation}
  é também um sistema completo de resíduos módulo~$p$.
  \datedue{20/6/2018; exercício individual}  

\item Sejam~$p$ um primo e~$a$ um inteiro.  Prove que
  \begin{enumerate}[label=\rmlabel]
  \item $a^p+(p-1)!a\equiv0\pmod p$.
  \item $a+(p-1)!a^p\equiv0\pmod p$.
  \end{enumerate}

\item Seja~$p>3$ um primo.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$p!$ e~$(p-1)!-1$ são primos entre si.
  \item Suponha que~$n\equiv(p-1)!-1\pmod{p!}$.  Prove que os~$p$
    inteiros que sucedem~$n$ são compostos.  Prove que os~$p-2$
    inteiros que precedem~$n$ são compostos.
  \end{enumerate}

\item Seja~$p$ um primo ímpar.
  \begin{enumerate}[label=\rmlabel]
  \item Prove que $1^23^2\dots(p-2)^2\equiv2^24^2\dots(p-1)^2\pmod p$.
  \item Prove que se~$p\equiv1\pmod4$, então
    $2^24^2\dots(p-1)^2\equiv-1\pmod p$.
  \item Prove que se~$p\equiv3\pmod4$, então
    $2^24^2\dots(p-1)^2\equiv1\pmod p$.
  \end{enumerate}

\item Seja~$p$ um primo com~$p\equiv3\pmod4$.  Prove que
  \begin{equation}
    \label{eq:29b}
    \(\(p-1\over2\)!\)^2\equiv1\pmod p.
  \end{equation}

\item\label{E:L1mn} Sejam~$m$ e~$n$ naturais positivos
  com~$\mdc(m,n)=1$.  Sejam~$R_m$ e~$R_n$ sistemas completos de
  resíduos módulo~$m$ e~$n$, respectivamente.  Prove que
  \begin{equation}
    \label{eq:30b}
    R=\{rn+sm\:r\in R_m\text{ e }s\in R_n\}
  \end{equation}
  é um sistema completo de resíduos módulo~$mn$.
  \hint{Suponha~$nn'\equiv1\pmod m$ e~$mm'\equiv1\pmod n$.
    Dado~$a\in\ZZ$, tome~$r=an'$ e~$s=am'$.  Conclua que há~$t\in R$
    tal que~$t\equiv a\pmod{mn}$.  Por que tal~$t$ é único?  (Note que
    $|R|\leq mn$.)}.

\item\label{E:L2mn} Sejam~$m$ e~$n$ naturais positivos
  com~$\mdc(m,n)=1$.  Sejam~$R_m^*$ e~$R_n^*$ sistemas reduzidos
  completos de resíduos módulo~$m$ e~$n$, respectivamente.  Prove que
  \begin{equation}
    \label{eq:30c}
    R^*=\{rn+sm\:r\in R_m\text{ e }s\in R_n\}
  \end{equation}
  é um sistema reduzido completo de resíduos módulo~$mn$.  

\item Sejam~$m$ e~$n$ naturais positivos com~$\mdc(m,n)=1$.  Deduza
  de~\ref{E:L1mn} e~\ref{E:L2mn} que
  \begin{equation}
    \label{eq:34}
    \phi(mn)=\phi(m)\phi(n).
  \end{equation}

\item Seja~$n\geq2$ um natural.  Seja
  \begin{equation}
    \label{eq:35}
    P=P_n=\{[a]\:\mdc(a,n)=1\}\subset\ZZ_n.
  \end{equation}
  \begin{enumerate}[label=\rmlabel]
  \item Prove que se~$b\in[a]\in P$, então~$\mdc(b,n)=1$.  
  \item Sejam~$\alpha$ e~$\beta$ elementos de~$P$.  Prove
    que~$\alpha\beta\in P$.
  \item Seja~$\alpha$ um elemento de~$P$.  Prove que~$\alpha^{-1}\in
    P$.  
  \item Seja
    \begin{equation}
      \label{eq:36}
      P'=\{\alpha\in\ZZ_n\:\exists\beta\in\ZZ_n\text{ tal que
      }\alpha\beta=1\}. 
    \end{equation}
    Prove que~$P=P'$.
  \end{enumerate}

\item Fixe~$n\in\NN$ com~$n>0$.  Seja~$R^*$ um sistema reduzido
  completo de resíduos módulo~$n$ e seja~$a\in\ZZ$ com~$\mdc(a,n)=1$.
  \begin{enumerate}[label=\rmlabel]
  \item\label{item:aR*} Prove que
    \begin{equation}
      \label{eq:37}
      aR^*=\{ar\:r\in R^*\}
    \end{equation}
    é também um sistema reduzido completo de resíduos módulo~$n$. 
  \item Deduza o teorema de Euler de~\ref{item:aR*}.  \hint{Verifique
      que $\prod_{r\in R^*}r\equiv\prod_{r\in R^*}ar\pmod n$.}
  \end{enumerate}

\def\bfx{\mathbf{x}}
\def\bfy{\mathbf{y}}
\let\lesseq\preceq
\item\label{E:73} Seja dado um inteiro~$k\geq1$.
  Consideramos
  \begin{equation}
    \label{eq:38}
    \NN^k=\NN\times\dots\times\NN=\{(x_i)_{1\leq i\leq
      k}\:x_i\in\NN\text{ para todo }i\},
  \end{equation}
  o conjunto das $k$-uplas
  ordenadas~$(x_i)_{1\leq i\leq k}=(x_1,\dots,x_k)$ de naturais.  No
  que segue, quando conveniente, escrevemos~$\bfx,\bfy,\dots$ para
  elementos de~$\NN^k$.  Considere a relação~$L$ de~$\NN^k$
  para~$\NN^k$ (isto é, $L\subset\NN^k\times\NN^k$) dada por
  \begin{equation}
    \label{eq:39}
    L=\{((x_i)_{1\leq i\leq k},(y_i)_{1\leq i\leq
      k})\in\NN^k\times\NN^k\:x_i\leq y_i\text{ para todo }i\}.
  \end{equation}
  Se~$(\bfx,\bfy)\in L$ (isto é, $\bfx L\bfy$),
  escrevemos~$\bfx\lesseq\bfy$ (essa notação é mais intuitiva, devido
  à semelhança entre os símbolos~$\leq$ e~$\lesseq$).  Note que,
  para~$k=1$, a relação~$\lesseq$ nada mais é que a relação de
  ordem~$\leq$ em~$\NN$.  Seja~$P_k$ a seguinte propriedade:
  \begin{enumerate}
  \item[$(P_k)$] Se~$\bfx_1,\bfx_2,\bfx_3,\dots$ é uma sequência
    (infinita) de elementos de~$\NN^k$, então
    existem~$a<b$ tais que~$\bfx_a\lesseq\bfx_b$.  
%    ~$1\leq i_1<i_2<i_3<\dots$ (com infinitos~$i_j$) tais que
%    $\bfx_{i_1}\lesseq\bfx_{i_2}\lesseq\bfx_{i_3}\lesseq\dots$.
  \end{enumerate}
  \begin{enumerate}[label=\rmlabel]
  \item Prove que~$P_k$ é válida para~$k=1$.  \observacao{Você pode
      achar conveniente provar a seguinte afirmação: se
      $x_1,x_2,x_3,\dots$ é uma sequência (infinita) de naturais,
      então existem $i_1<i_2<\dots$ (com infinitos~$i_j$) tais que
      $x_{i_1}\leq x_{i_2}\leq x_{i_3}\leq\dots$.}
  \item Prove que~$P_k$ é válida para~$k=2$.
  \item Prove que~$P_k$ é válida para qualquer~$k\geq1$.
  \end{enumerate}
  \datedue{27/6/2018; exercício individual}  

\item Faça o maior número possível dos exercícios do Capítulo~4
  (Relações) de~\textbf{DJV}.

\item Faça o maior número possível dos itens~(i) a~(vii) do
  Exercício~30.28 de~\textbf{KH}.

\item Faça o maior número possível dos exercícios do Capítulo~5
  (Funções) de~\textbf{DJV}.

\item Faça o item~(viii) do Exercício~30.28 de~\textbf{KH}.

\item Estude o Capítulo~7 de~\textbf{DJV}.  Faça os exercícios daquele
  capítulo.

\item Sejam~$a$ e~$b$ naturais positivos.  Prove que
  existe um natural~$m$ que satisfaz as seguintes duas propriedades:
  \begin{enumerate}[label=\rmlabel]
  \item $a\mid m$ e~$b\mid m$ e
  \item se~$a\mid c$ e~$b\mid c$, então~$m\mid c$.
  \end{enumerate}
  Prove que existe no máximo um tal natural~$m$.  Tal~$m$ é, em certos
  contextos, denotado por~$a\vee b$.  Por qual nome  você
  conhece~$a\vee b$?

\def\bfz{\mathbf{z}}
\def\bfw{\mathbf{w}}
\item Seja dado um inteiro~$k\geq1$.  Consideramos
  \begin{equation}
    \label{eq:38b}
    \NN^k=\NN\times\dots\times\NN=\{(x_i)_{1\leq i\leq
      k}\:x_i\in\NN\text{ para todo }i\},
  \end{equation}
  o conjunto das $k$-uplas
  ordenadas~$(x_i)_{1\leq i\leq k}=(x_1,\dots,x_k)$ de naturais.  Como
  no exercício~\ref{E:73}, consideramos a relação~$L$ de~$\NN^k$
  para~$\NN^k$ (isto é, $L\subset\NN^k\times\NN^k$) dada por
  \begin{equation}
    \label{eq:80}
    L=\{((x_i)_{1\leq i\leq k},(y_i)_{1\leq i\leq
      k})\in\NN^k\times\NN^k\:x_i\leq y_i\text{ para todo }i\}.
  \end{equation}
  Como antes, escrevemos~$\bfx\lesseq\bfy$ quando $(\bfx,\bfy)\in L$.
  Sejam~$\bfx$ e~$\bfy$ elementos de~$\NN^k$.  Prove que
  existe~$\bfz\in\NN^k$ tal que
  \begin{enumerate}[label=\rmlabel]
  \item $\bfz\lesseq\bfx$ e~$\bfz\lesseq\bfy$ e
  \item se~$\bfw\in\NN^k$ é tal que~$\bfw\lesseq\bfx$ e~$\bfw\lesseq\bfy$,
    então~$\bfw\lesseq\bfz$.
  \end{enumerate}
  Ademais, suponha que~$\bfz'\in\NN^k$ seja tal que
  \begin{enumerate}[label=\rmlabel]
  \item[(\textit{i}$'$)] $\bfz'\lesseq\bfx$ e~$\bfz'\lesseq\bfy$ e
  \item[(\textit{ii}$'$)] se~$\bfw\in\NN^k$ é tal
    que~$\bfw\lesseq\bfx$ e~$\bfw\lesseq\bfy$,
    então~$\bfw\lesseq\bfz'$.
  \end{enumerate}
  Prove que~$\bfz'=\bfz$.  Como você pode resolver o exercício~S11
  (feito em sala) usando este exercício?  \datedue{4/7/2018; exercício
    individual}

\end{enumerate}

\endgroup
\end{document}

%%% Local Variables:
%%% mode: latex
%%% eval: (auto-fill-mode t)
%%% eval: (LaTeX-math-mode t)
%%% eval: (flyspell-mode t)
%%% TeX-master: t
%%% End:
