%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 04 Jul 2018 12:54:49pm -03 by yoshi on korujinha.local>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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\mdc{\mathop{\rm mdc}\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\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}
\let\sim=\thicksim

\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*.}
\newcommand\nlabelS{\bf\upshape S\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 feitos em sala
}  

\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}

\begin{enumerate}[label=\nlabelS]
  
\item (7/3/2018) Dois conjuntos~$A$ e~$B$ são \textit{comparáveis}
  se~$A\subset B$ ou~$B\subset A$.  Seja~$X$ um conjunto finito
  com~$n$ elementos.  Suponha que~$A_1,\dots,A_{n+2}$ sejam~$n+2$
  subconjuntos de~$X$ distintos.  Prove que existem~$i$ e~$j$
  com~$1\leq i\leq n+2$ e~$1\leq j\leq n+2$ tais que~$A_i$ e~$A_j$ não
  são comparáveis.  \observacao{Se você preferir, você pode se
    restringir ao caso concreto em que~$n=8$.}
  
\item (14/3/2018) Encontre uma fórmula~$\phi$ que tenha a seguinte
  tabela-verdade:
  \begin{center}
    \def\v{$V$}\def\f{$F$}
    \begin{tabular}{cccc}
      $p$ & $q$ & $r$ & $\phi$\\
      \hline			
      \v &  \v &  \v &  \v \\
      \v &  \v &  \f &  \v \\
      \v &  \f &  \v &  \v \\
      \v &  \f &  \f &  \f \\
      \f &  \v &  \v &  \v \\
      \f &  \v &  \f &  \v \\
      \f &  \f &  \v &  \f \\
      \f &  \f &  \f &  \v \\
    \end{tabular}    
  \end{center}

\item (21/3/2018) Prove que não existe um inteiro~$x$ tal que~$x^2$ é
  da forma~$3k+2$ com~$k$ inteiro.

\item (4/4/2018) Prove que a equação 
  \begin{equation}
    \label{eq:1}
    x^{10}+2mx+2n=0
  \end{equation}
  não tem soluções racionais se~$m$ e~$n$ são ímpares. 

\item (11/4/2018) Prove que, para todo~$n\geq1$, vale que 
  \begin{equation}
    \label{eq:2}
    \sum_{1\leq k\leq n}{1\over k^2}
    =1+{1\over2^2}+{1\over3^2}+\dots+{1\over n^2}
    \leq2-{1\over n}.
  \end{equation}
  \observacao{De fato, Euler~(1735) provou que a soma em~\eqref{eq:2}
    converge para~$\pi^2/6=1.6449\dots$.  Veja, por exemplo,
    \url{http://math.cmu.edu/~bwsulliv/MathGradTalkZeta2.pdf}.}

\item (9/5/2018) Neste exercício, queremos comparar~$\lfloor
  nx\rfloor$ e~$n\lfloor x\rfloor$ para~$n\in\NN$ e~$x\in\RR$.
  \begin{enumerate}[label=\rmlabel]
  \item Calcule~$\lfloor nx\rfloor$, $n\lfloor x\rfloor$ e~$\{x\}$ nos
    seguintes dois casos: 
    \begin{enumerate}[label=\alabel]
    \item $n=5$ e $x=\pi$,
    \item $n=5$ e~$x=-\pi$.
    \end{enumerate}
  \item Prove que, para todo~$n\in\NN$ e~$x\in\RR$, temos que
    $\lfloor nx\rfloor=n\lfloor x\rfloor$ se e só se~$n\{x\}<1$.
  \end{enumerate}

\item (16/5/2018) Seja~$n\in\NN$.  Suponha que~$n$ não seja primo e
  que~$n>4$.  Prove que~$n\mid(n-1)!$.

\item (23/5/2018) Sejam~$m$ e~$n$ inteiros.  Prove
  que~$\mdc(m+1,n+1)\mid mn-1$.  \hint{Você pode preferir provar o
    seguinte fato, que implica o resultado que queremos: se~$c\in\ZZ$
    divide ambos~$m+1$ e~$n+1$, então $c\mid mn-1$.}

\item (6/6/2018) Suponha que $a\equiv b\pmod m$ e
  que~$a\equiv b\pmod n$, onde~$a$ e~$b$ são inteiros e~$m$ e~$n$ são
  naturais positivos com~$\mdc(m,n)=1$.  Prove
  que~$a\equiv b\pmod{mn}$.  \hint{Lembre-se do lema de Gauss:
    se~$a\mid bc$ e~$\mdc(a,b)=1$, então~$a\mid c$.}

\item (13/6/2018) Seja~$p$ um primo ímpar.  Prove que
  $p\mid(p-3)!-(p-1)/2$.  \NB{Devido ao trancaço promovido pelo
    SINTUSP, não houve entrega desse exercício.}

\item (27/6/2018) Sejam~$a$ e~$b$ naturais positivos.  Prove que
  existe um natural~$d$ que satisfaz as seguintes duas propriedades:
  \begin{enumerate}[label=\rmlabel]
  \item $d\mid a$ e~$d\mid b$ e
  \item se~$c$ é um natural tal que~$c\mid a$ e~$c\mid b$,
    então~$c\mid d$.
  \end{enumerate}
  Ademais, suponha que~$d'$ seja um natural tal que
  \begin{enumerate}[label=\rmlabel]
  \item[(\textit{i}$'$)] $d'\mid a$ e~$d'\mid b$ e
  \item[(\textit{ii}$'$)] se~$c$ é um natural tal que~$c\mid a$
    e~$c\mid b$, então~$c\mid d'$.
  \end{enumerate}
  Prove que~$d'=d$.

\item (4/7/2018) 
  \begin{enumerate}[label=\rmlabel]
  \item\label{item:S12.i} Seja~$X$ um conjunto e~$\cF\subset\cP(X)$
    uma família de subconjuntos de~$X$.  A família~$\cF$ admite uma
    relação de ordem parcial natural dada pela relação~``$\subset$'',
    a saber, 
    \begin{equation}
      \label{eq:3}
      \{(A,B)\in\cF\times\cF\:A\subset B\}.      
    \end{equation}
    O que significa dizer que~$F\subset X$ é um elemento minimal de~$\cF$
    em relação a essa ordem?

  \item Continuando com~\ref{item:S12.i}, prove que se~$\cF$ é finito e
    não-vazio (isto é, $\cF$ tem um número finito de elementos
    e~$\cF\neq\emptyset$), então~$\cF$ tem um elemento minimal.

  \item Tomemos agora~$X=\NN$ e
    \begin{equation}
      \label{eq:4}
      \cF=\{F\subset X\:F\text{ é infinito}\}.
    \end{equation}
    Assim, $\cF$~é o conjunto dos conjuntos infinitos de naturais.  Decida
    se~$\cF$ tem um elemento minimal em relação à ordem dada
    por~``$\subset$''.  Justifique sua resposta.  \NB{Um conjunto é
      \textit{finito} se ele tem um número finito de elementos
      \texttt{:-)}.  Um conjunto é \textit{infinito} se ele não é finito
      \texttt{:-D}.}

  \end{enumerate}




\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:
