\documentclass[a4paper,12pt,brazil,landscape]{article}
\newcommand{\ultimamodificacao}{28 de agosto de 2007}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{epsfig,graphicx,color,latexsym,alltt,calc,ifthen,slides,hyperref} 

\begin{document}

\setbackgroundcolor{white}
\settextcolor{blue}
\setslidetitlecolor{red}
\setbordercolor{darkblue}

\setedition{slides.sty}
\newincluder{fulledition}
\setincluder{fulledition}{true}

\sffamily 
\bfseries 
\mathversion{bold}
\Hugesize 
%\Hugefont

\hypertarget{inicio}{}
\title{O Princ\'{\i}pio da Casa de Pombos \\ Baseado em Santos, Mello e Murari (2002), Cap. 7}
\author{Newton José Vieira}
\lhead{Matemática Discreta}
\rhead{Casa de Pombos}
\lfoot{UFMG}
%\rfoot{rsb}
\organization{UFMG}
\cfoot{\hyperlink{inicio}{\threebigotimes}~~~\hyperlink{sumario}{\threebigoplus}}
\date{\ultimamodificacao}
\titlepage

%\newslide{SUMÁRIO}
\hypertarget{sumario}{}
%\begin{twoblocks}
%\begin{itemize}
%\item \hyperlink{teoria-conjuntos-1}{Teoria dos Conjuntos}
%\item \hyperlink{relacoes-funcoes-1}{Relações e Funções}
%\item \hyperlink{fundamentos-logica-1}{Fundamentos de Lógica}
%\item \hyperlink{tecnicas-prova-1}{Técnicas Elementares de Prova}
%\end{itemize}
%\centralbar{13cm}
%\begin{itemize}
%\item \hyperlink{comandos}{Comandos Especiais}
%\end{itemize}
%\end{twoblocks}

\pagenumbering{arabic}

%-----------------------------------------------------------------------------
%\setskiplink{preliminares}

\newslide{A vers\~ao mais simples}

\begin{itemize}
	\item \textcolor{black}{Teorema}: Se h\'a $n$ casas e mais de $n$ pombos s\~ao
	      distribu\'{\i}dos entre elas, ent\~ao alguma casa conter\'a pelo menos dois pombos.
\end{itemize}
	     
%----------------------------------------------------------------------------------------------

\newslide{A vers\~ao mais simples}

\begin{itemize}
	\item \textcolor{black}{Teorema}: Se h\'a $n$ casas e mais de $n$ pombos s\~ao
	      distribu\'{\i}dos entre elas, ent\~ao alguma casa conter\'a pelo menos dois pombos.
	\item \textcolor{black}{Demonstra\c{c}\~ao}: Se cada uma das $n$ casas contiver no m\'aximo
	      um pombo, ent\~ao ter\~ao sido distribu\'{\i}dos no m\'aximo $n$ pombos, o
	      que contradiz o fato de que s\~ao distribu\'{\i}dos mais de $n$ pombos.
\end{itemize}
	     
%----------------------------------------------------------------------------------------------

\newslide{A vers\~ao mais simples}

\begin{itemize}
	\item \textcolor{black}{Teorema}: Se h\'a $n$ casas e mais de $n$ pombos s\~ao
	      distribu\'{\i}dos entre elas, ent\~ao alguma casa conter\'a pelo menos dois pombos.
	\item \textcolor{black}{Demonstra\c{c}\~ao}: Se cada uma das $n$ casas contiver no m\'aximo
	      um pombo, ent\~ao ter\~ao sido distribu\'{\i}dos no m\'aximo $n$ pombos, o
	      que contradiz o fato de que s\~ao distribu\'{\i}dos mais de $n$ pombos.
 \item \textcolor{black}{Princ\'{\i}pio das gavetas de Dirichlet:}
	     \begin{quote}
	      Se colocarmos $n$ objetos em $r$ gavetas, sendo $n>r$, ent\~ao alguma gaveta
	      conter\'a pelo menos dois objetos.
	     \end{quote}
\end{itemize}
	     
%----------------------------------------------------------------------------------------------
	     
\newslide{Exemplos simples}


       \begin{itemize}
	      \item Em uma festa com mais de 12 crian\c{c}as, h\'a pelo menos duas que nasceram
	            no mesmo m\^es.

\vspace*{3mm}
	      \item Em uma festa com mais de 7 crian\c{c}as, h\'a pelo menos duas que nasceram
	            no mesmo dia da semana.

\vspace*{3mm}
	      \item Em uma festa com mais de 366 crian\c{c}as, h\'a pelo menos duas que
	            aniversariam no mesmo dia.
       \end{itemize}


%--------------------------------------------------------------------------------------------

	     
\newslide{Mais um exemplo}

\begin{itemize}
 \item Qualquer subconjunto de $\{1,2,3,\ldots,12\}$ de 7 elementos possui dois
       subconjuntos cuja soma dos elementos \'e a mesma.
       \begin{itemize}
        \item Subconjunto com a menor soma: $\{1\}$. Soma: 1.
        \item Subconjunto com a maior soma: $\{6,7,8,9,10,11,12\}$. Soma: 63.
        \item N\'umero de subconjuntos (exceto $\emptyset$) de um conjunto de
              7 elementos: $2^7-1$.
       \end{itemize}
\end{itemize}

%--------------------------------------------------------------------------------------------
	     
\newslide{Mais um exemplo}

\begin{itemize}
 \item Qualquer subconjunto de $\{1,2,3,\ldots,2n\}$ de $n+1$ elementos possui um
       par de elementos primos entre si.
       \begin{itemize}
        \item Subconjuntos sem n\'umeros consecutivos: $\{1,3,5,\ldots, 2n-1\}$ e $\{2,4,6,\ldots, 2n\}$.
        \item Cada um dos subconjuntos acima cont\'em $n$ elementos.
        \item Um subconjunto com $n+1$ elementos cont\'em dois elementos consecutivos (primos entre si).
       \end{itemize}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{Uma generaliza\c{c}\~ao}

\begin{itemize}
 \item \textcolor{black}{Teorema}: Se h\'a $n$ casas e mais de $nk$ pombos s\~ao
	     distribu\'{\i}dos entre elas, ent\~ao alguma casa cont\'em pelo menos $k+1$ pombos.
 \item \textcolor{black}{Demonstra\c{c}\~ao}: Se cada uma das $n$ casas contiver no m\'aximo
       $k$ pombos, ent\~ao ter\~ao sido distribu\'{\i}dos no m\'aximo $nk$ pombos, o
       que contradiz o fato de que s\~ao distribu\'{\i}dos mais de $nk$ pombos.
\end{itemize}
	     
%----------------------------------------------------------------------------------------------
	     
\newslide{Uma generaliza\c{c}\~ao}

\begin{itemize}
 \item \textcolor{black}{Teorema}: Se h\'a $n$ casas e mais de $nk$ pombos s\~ao
	     distribu\'{\i}dos entre elas, ent\~ao alguma casa cont\'em pelo menos $k+1$ pombos.
 \item \textcolor{black}{Demonstra\c{c}\~ao}: Se cada uma das $n$ casas contiver no m\'aximo
       $k$ pombos, ent\~ao ter\~ao sido distribu\'{\i}dos no m\'aximo $nk$ pombos, o
       que contradiz o fato de que s\~ao distribu\'{\i}dos mais de $nk$ pombos.

\vspace*{3mm}
 \item Exemplo: Em uma festa de anivers\'ario com 37 crian\c{c}as, pelo menos 4 nasceram no
       mesmo m\^es, pois $37=12.3+1$.
 \item Exemplo: Em um grupo de 20 pessoas, pelo menos 3 nasceram no mesmo dia da semana,
       pois $20=7.2+6$.
\end{itemize}
	     
%----------------------------------------------------------------------------------------------
	     
\newslide{Exemplo}

\begin{itemize}
 \item Se uma urna cont\'em 4 bolas vermelhas, 7 verdes, 9 azuis e 6 amarelas,
       qual \'e o menor n\'umero de bolas que devemos retirar (sem olhar) para
       que possamos ter certeza de termos tirado pelo menos 3 bolas da mesma
       cor?
       \begin{itemize}
        \item Casas: as 4 cores.
        \item Pombos: bolas que devemos retirar.
        \item A resposta \'e $4.2+1=9$.
       \end{itemize}
\end{itemize}


%--------------------------------------------------------------------------------------------
	     
\newslide{Exemplo}

\begin{itemize}
 \item Sejam 6 pontos no espa\c{c}o, n\~ao havendo tr\^es alinhados. Cada par de pontos
       \'e ligado por um segmento de reta e cada um desses 15 segmentos \'e pintado de
       azul ou de vermelho. Prove que existe um tri\^angulo com os tr\^es lados da mesma
       cor. 
       \begin{itemize}
        \item Um ponto $x$ est\'a ligado a 5 outros (as 5 retas s\~ao os pombos).
        \item H\'a duas cores para pintar (as cores s\~ao as casas).
        \item Logo, tr\^es dos 5 segmentos de reta t\^em a mesma cor:
        
              \begin{picture}(300,150)
               \put(100,10){\makebox(0,0){$x$}}
               \put(100,110){\makebox(0,0){$1$}}
               \put(300,110){\makebox(0,0){$2$}}
               \put(300,10){\makebox(0,0){$3$}}
               
               \put(100,25){\line(0,1){70}}
               \put(110,20){\line(2,1){180}}
               \put(120,10){\line(1,0){160}}
              \end{picture}
        \item Considere o tri\^angulo 123 \ldots
       \end{itemize}
\end{itemize}


%--------------------------------------------------------------------------------------------


\lastpage 

%--------------------------------------------------------------------------------------------

%\defskiptarget{preliminares}

\end{document}
