\documentclass[12pt]{article}
\usepackage{amsmath,amsthm,amsfonts,amssymb,amscd,amsbsy}
\usepackage{graphics}
\usepackage[latin1]{inputenc}

\headsep=-1.5truecm
\oddsidemargin=0pt
\evensidemargin=0pt
\textwidth=17truecm
\textheight=23truecm
\renewcommand{\baselinestretch}{1.5}
\newcommand{\CC}{\mathbb C}
\newcommand{\FF}{\mathbb F}
\newcommand{\QQ}{\mathbb Q}
\newcommand{\RR}{\mathbb R}
\newcommand{\ZZ}{\mathbb Z}
\newcommand{\NN}{\mathbb N}
\newcommand{\4}{\vspace{.6cm}}
\newcommand{\2}{\vspace{.2cm}}
\newcommand{\1}{\vspace{.1cm}}
\newcommand{\7}{\hspace{-.7cm}}

\begin{document}

\vglue .9in

\renewcommand{\thepage}

\centerline{\LARGE\bf V  Bienal da SBM}

\vskip .4in

\centerline{\large João Pessoa -- 18 a 22 de outubro  de 2010}

\vskip .9in

\centerline{\LARGE\bf Alguns Belos Problemas de Matemática Discreta}



\vskip .9in

\centerline{\LARGE Algumas partes do texto ainda não estão finalizadas }

\vskip .2in

\centerline{\LARGE e outros problemas serão acrescentados}



\vskip .9in

\centerline{\Large\bf Rogério Ricardo Steffenon~$^1$}



\vskip .3in

\centerline{ UNISINOS -- Universidade do Vale do Rio dos Sinos}

\vskip .1in

\centerline{ Avenida Unisinos, 950, São Leopoldo -- RS}

\vskip .1in

\centerline{ CEP 93.022-000 - Brasil}

\footnotetext {$^1$  Doutor em Matemática -- UFRGS. Professor  da UNISINOS. e-mail: rogerios@unisinos.br}

\newpage

\centerline{{\Large\bf Apresentação}}

\vskip .5in

\7 Neste minicurso serão apresentados e resolvidos alguns belos problemas, cuja solução utiliza argumentos elementares e relativamente simples de Matemática Discreta. Entre os tópicos abordados podemos citar os seguintes: Indução Matemática, Sequência de Fibonacci, Recorrência, Combinatória, Divisibilidade, Sistemas de Numeração, Princípio da Casa dos Pombos e Probabilidade. 
A ideia deste minicurso se assemelha com aquele ministrado na III Bienal da SBM em Goiânia, no ano de 2006. Muitos dos problemas abordados surgem em olimpíadas de matemática e podem ser uma boa fonte para os professores incentivarem os alunos em aprender Matemática.

\2\7 A distribuição das aulas será a seguinte:

\2\7 {\bf 1ª Aula}: Nesta aula serão abordados problemas que envolvem a Indução Matemática e Sistema Binário: Torres de Hanói, Pesagem de Moedas numa balança de dois pratos, quantidade de jogos necessários para definir um vencedor num torneio do tipo mata-mata. A partir dos problemas resolvidos vamos deduzir que todo número natural pode ser escrito de modo único como soma de potências de 2 e também apresentar os cartões binários mágicos.

\2\7 {\bf 2ª Aula}: Apresentaremos vários problemas cuja solução envolve o Princípio da Casa dos Pombos. Também abordaremos o Paradoxo Gêmeo (problema dos aniversários) e o problema dos Dois Bodes.

\2\7 {\bf 3ª Aula}: Nesta aula abordaremos problemas que envolvem a sequência de Fibonacci e divisi-

\7 bilidade. Vamos provar que todo número natural pode ser escrito de modo único como soma de termos não consecutivos da sequência de Fibonacci e com isso apresentamos uma mágica com ``cartões de Fibonacci''.

\2\7 {\bf 4ª Aula}: Apresentaremos os conceitos básicos de contagem, utilizando permutações (simples e circulares) e combinações (simples e completas). Algumas fórmulas interessantes  de Combinatória envolvendo somas serão deduzidas nesta aula.

\2\7 {\bf 5ª Aula}: Serão resolvidos problemas diversos envolvendo alguns tópicos das aulas anteriores.
 
\2\7 {\bf Pré-requisito: nenhum.}

\newpage

{\bf Bibliografia}

\4\2\7 {\bf 1.} ANDREESCU, T. et. al. 102 Combinatorial Problems. Birkhäuser Boston, 2002.

\2\7 {\bf 2.} COUTINHO, S. C. Números Inteiros e Criptografia RSA. Rio de Janeiro: IMPA, 2007.

\2\7 {\bf 3.} GRIMALDI, R. P. Discrete and Combinatorial Mathematics: An Applied Introduction. 

\1 Addison Wesley, 2004.

\2\7 {\bf 4.} HEFEZ, A. Elementos de Aritmética. Rio de Janeiro: SBM, 2005.

\2\7 {\bf 5.} HOLANDA, B. et al. Treinamento Cone Sul 2007. Fortaleza: Realce, 2007.

\2\7 {\bf 6.} KOSHY, T. Fibonacci and Lucas Numbers with Applications. John Wiley & Sons, 2001.

\2\7 {\bf 7.} LIMA, E. L. A Matemática do Ensino Médio  Volume 2. Rio de Janeiro: SBM, 2006.

\2\7 {\bf 8.} LOVÁSZ, L. et. al. Matemática Discreta. Rio de Janeiro: SBM, 2006.

\2\7 {\bf 9.} MOREIRA, C. G. T. de A. et al. Olimpíadas Brasileiras de Matemática $\bullet$ 9ª  a 16ª, 

\1 Problemas e Soluções. Rio de Janeiro: SBM/OBM, 2003.

\2\7 {\bf 10.} MORGADO, A. C. et. al. Análise Combinatória e Probabilidade. Rio de Janeiro: SBM, 

\1 2006.

\2\7 {\bf 11.} ROSEN, K. Elementary Number Theory and its applications. Addison Wesley, 2005.

\2\7 {\bf 12.} ROSEN, K. Matemática Discreta e Suas Aplicações. São Paulo: McGraw-Hill, 2009. 

\2\7 {\bf 13.} SANTOS, A. L. Problemas Selecionados de Matemática. Rio de Janeiro: Ciência Moderna, 

\1~ 2006.

\2\7 {\bf 14.} SANTOS, J. P. O. et. al. Introdução à Análise Combinatória. Rio de Janeiro: Ciência 

\1~ Moderna, 2007.

\2\7 {\bf 15.} http://www.mat.ufg.br/bienal/2006/mini/misturini.steffenon.pdf  

\1~ Uma Grosa de Problemas de Matemática -- III Bienal da SBM

\newpage

\renewcommand{\thepage}{\arabic{page}}

\setcounter{page}{1}

\4\7 {\bf Problema 1.} 

\2\7  Os objetivos deste exercício são:

\2\7 (i) Provar o resultado $1+2+2^2+\cdots+2^n=2^{n+1}-1$, para todo $n\geq 1$.

\2\7 (ii) Fazer a mágica com os Cartões Mágicos Binários.

\2\7 (iii) Deduzir o seguinte resultado: Todo número inteiro positivo pode ser escrito de modo único 

\1~ como a soma de diferentes potências de 2. 

\2\7 (a) Num torneio de tênis individual há $2^{n+1}$ participantes.  Sabendo que a disputa é do tipo 

\1~ {\it mata-mata}* , quantos jogos são realizados para se definir o vencedor?

\2\7 *Os jogadores são divididos em grupos de 2, ao acaso, e jogadores de um mesmo  grupo jogam entre si. Os perdedores são eliminados e os vencedores são divididos novamente em grupos de 2 e assim por diante até restar um jogador, que é proclamado campeão.

\4\7 (b) Em um programa de televis\~{a}o, um candidato deve responder 21 perguntas. A primeira per-

\1 gunta vale 1 ponto, a segunda 2 pontos, a terceira 4 pontos, e, assim, sucessivamente, do-


\1 brando sempre. O candidato responde a todas as perguntas e ganha os pontos correspon-

\1 dentes \`{a}s respostas que acertou, mesmo que erre algumas.

 \2\7 (b.1) Qual o n\'{u}mero de pontos que o candidato far\'{a} se acertar todas as perguntas?

\2\7 (b.2) Quantas e quais as perguntas o candidato acertou se o n\'{u}mero de pontos obtidos for igual 

\1~~ a 571113?

\4\7 {\bf Problema 2.} 

\2\7  Numa biblioteca há dez estantes com muitos livros em cada uma delas. Além disso, dispomos de uma balança eletrônica(como as que existem em farmácias). Resolva cada uma das situações abaixo:

\2\7  (a) Sabemos que, em nove delas, cada livro pesa 1 kg e que, em uma delas, cada livro pesa 

\1 1,01 kg. Como descobrir, com uma pesagem apenas, qual a  estante dos livros de 1,01 kg e, 

\1 em consequência, quais são as estantes com os livros de 1kg?

\2\7 (b) Sabemos que, em algumas estantes, cada livro pesa 1 kg e nas outras, cada livro pesa 1,01 
	
\1 kg, podendo inclusive haver apenas livros de um dos tipos. Como descobrir, com uma 
	
\1    pesagem apenas, quais as estantes dos livros de 1kg? 

\2\7 (c) Sabemos que, em algumas estantes, cada livro pesa 1 kg, em outras cada livro pesa 1,01 kg 

\1 e nas outras cada livro pesa 1,02 kg, podendo inclusive haver apenas livros de um dos tipos. 

\1 Como descobrir, com uma pesagem, quais as estantes dos livros de 1kg, de 1,01 kg ? 


\2\4\7 {\bf Princípio Fundamental da Enumeração ou Princípio Multiplicativo}

\2\7 Se uma decisão $d_1$ pode ser tomada de $x_1$ maneiras e se, uma vez tomada a decisão $d_1$, a decisão $d_2$ puder ser tomada de $x_2$ maneiras, então o número de maneiras de se
tomarem as decisões $d_1$ e $d_2$ é $x_1\cdot x_2$. Mais geralmente, suponha que tenhamos que tomar $n$ decisões sucessivas $d_1, d_2,\ldots, d_n$ e se a decião $d_i$ puder ser tomada de $x_i$ maneiras, então o número de maneiras de tomarmos as decisões $d_1, d_2,\ldots, d_n$ é $x_1\cdot x_2\cdot \ldots \cdot x_n$.

\4\7 {\bf Teorema Fundamental da Aritmética -- TFA}

\2\7 Todo número natural $n\geq 2$ pode ser escrito de modo único na forma $n=p_1^{e_1}\cdot p_2^{e_2} \cdot \ldots \cdot p_t^{e_t}$, 

\1\7 onde $p_1<p_2<\ldots <p_t$ são números primos e os
expoentes $e_i$ são inteiros positivos. 

\2\7 Uma forma alternativa para o TFA: 

\1\7 Todo número natural $n\geq 1$ pode ser escrito de modo único na forma $n=2^k(2m+1)$, onde 

\1\7 $k, m$ são inteiros não negativos.

\2\7 Uma consequência importante do TFA e do Princípio Multiplicativo: 

\1\7 Se $n=p_1^{e_1}\cdot p_2^{e_2} \cdot \ldots \cdot p_t^{e_t}$, então
 $n$ possui $(e_1+1)\cdot(e_2+1)\cdot \ldots \cdot (e_t+1)$ divisores positivos.

\4\7 {\bf Problema 3.} 

\2\7  Numa escola há um corredor com 2010 armários numerados de 1 a 2010 , inicialmente todos fechados. 2010 alunos numerados de 1 a 2010, passam pelo corredor. O aluno de número $k$ reverte o estado de todos os armários cujos números são múltiplos de $k$. Por exemplo, o aluno de número 4 mexe nos armários de números 4, 8, 12,..., abrindo os que encontra fechados e fechando os que encontra abertos. Ao final, depois da passagem do 2010º aluno, quais armários ficarão abertos?

\4\7 {\bf Princípio de Indução Matemática}

\2\7 Um conjunto $A$ de números inteiros que contém o inteiro 1, e tem a propriedade que $k\in A$, 

\1\7 implica que $k+1\in A$, então $A=\NN=\{1,2,\ldots\}$.

\2\7 {\bf Problema 4. ~(As Torres de Hanói)}  

\2\7 O jogo consiste em uma base onde estão firmadas três hastes verticais que denominamos {\bf A}, {\bf B} e {\bf C} e um certo número de discos,  de diâmetros diferentes, furados no centro. No começo do jogo os 
   discos estão todos enfiados na haste  {\bf A}, em ordem decrescente de tamanho, com o disco menor acima dos demais. 
  
\1\7 O objetivo é mover todos os discos, de {\bf A} para {\bf
  C}, obedecendo às seguintes regras:

\2\7 (1) Só é permitido mover um disco de cada vez.

\2\7 (2) Um disco maior nunca pode ser posto sobre um disco menor.

\2\7 É fácil ver que é necessário usar a haste {\bf B} como
  intermediária. O problema consite no seguinte:

\2\7 {\it Qual o número mínimo de movimentos que precisaremos fazer para alcançar o objetivo?}

\2\7  \underline{Sugestão}: Verifique quantos movimento são necessários
  quando temos 1 disco, 2, 3, 4 discos e tente encontrar alguma regularidade. Existem vários sites que tratam do assunto.
 
\2\7  Para jogar veja, por exemplo:   http://www.prof2000.pt/users/pjca/Jogos\_ficheiros/hanoi/Torre%20de%20Hanoi.html 
		
\2\7 {\bf Observação}: {\it The Reve's Puzzle}:~ Uma questão interessante é considerar o mesmo problema com 4 hastes {\bf A}, {\bf B} , {\bf C} e {\bf D}.  Inicialmente há $n$ discos de diâmetros diferentes, fincados inicialmente na haste $A$, nas condições acima. O objetivo, seguindo as duas regras acima, é passá-las para a haste {bf D}. Nesse caso as hastes {\bf B} e {\bf C} fucionam	como intermediárias. Até o momento não se conhece o número mínimo de movimentos para resolver o problema com $n$ discos. Há uma conjecuta, com cerca de 70 anos, de que o número mínimo de movimentos necessários é igual ao número de movimentos usados por um algoritmo criado por Frame e Stewart (Conjectura de Frame-Stewart).

\2\7 {\bf Problema 5.} 

\2\7 Seja $k\in \NN, k\geq 2$. Suponha que você possua $k$ moedas de um real, uma das quais  é falsa e pesa menos do que uma verdadeira. Você tem uma balança de dois pratos mas não tem pesos.
 A única forma de pesagem consiste em por algumas moedas em cada prato e verificar se a balança está equilibrada.

\2\7 (a) Faça uma tabela com duas colunas. Na primeira coluna escreva valores de $k$($k=2,3,4,...$)
 
~e na segunda coloque a quantidade  mínima de pesagens para descobrir a moeda falsa.

\2\7 (b) O que acontece para os seguintes valores de $k: 3,4,9,10,27,28$?

\2\7 (c) Mostre, por indução em $n$, que se $k=3^n$, então $n$ pesagens são suficientes para  achar a 

~moeda adulterada.
   
\4\7 {\bf Problema 6.} 

\2\7   Suponha que você possua 12 moedas de um real, uma das quais  é falsa e tem peso diferente de uma verdadeira(não sabemos se a falsa pesa mais ou menos que uma verdadeira). Você tem uma balança de dois pratos mas não tem pesos. A única forma de pesagem consiste em pôr algumas moedas em cada prato e verificar se a balança está equilibrada. 
 
\2\7 (a) Mostre que 3 pesagens são suficientes para  achar a moeda adulterada. 
 
\2\7 (b) Consegues resolver o mesmo problema com 13 moedas?  E com 14 moedas?

\4\7 {\bf Princípio das Gavetas de Dirichlet ou Princ\'{i}pio da Casa dos Pombos (PCP)}

\2\7 Se $n+1$ pombos são colocados em $n$ casas, então pelo menos uma casa conter\'{a} dois ou mais pombos.

\4\7 {\bf Problema 7.}

\2\7 Em João Pessoa há pelo menos duas pessoas com a mesma quantidade de fios de cabelo na cabeça.

\2\7 {\bf Solução}: Observações científicas indicam que ninguém tema mais de 500.000 fios de cabelo na cabeça. 
Com isso a quantidade de cabelos que uma pessoa pode ter é $ 0,1,\ldots, 500.000$ (essas são as casas!). 
A população de João Pessoa é superior a 700.000 (esses são os pombos!).  O resultado segue pelo PCP.

\4\7 {\bf Problema 8.} Prove que se escolhermos mais do que $n$ números do conjunto $\{1, 2, \ldots, 2n\}$, então dois desses números são primos entre si.

\2\7 {\bf Solução}: Considere os $n$ pares de números: 1 e 2, 3 e 4, ..., $2n-1$ e $2n$. Como são escolhidos mais do que $n$ números, pelo PCP, há pelo menos dois pertencentes ao mesmo par.  Como dois números do mesmo par são consecutivos, eles são primos entre si. 

\4\7  {\bf Problema 9.}

\2\7 Seja $a\neq 0$ um algarismo no sistema decimal. Prove que todo número natural $n$ tem um múltiplo que se escreve apenas com os algarismos $0$ e $a$.

\2\7 {\bf Solução}: Consideramos os $n+1$ n\'{u}meros $a, aa, aaa, aaaa, ...,\underbrace{aa...aa}_{n+1}$ (esses são os pombos!). Sabemos que os possíveis restos na divisão por $0, 1, 2, \ldots, n-1$ (essas são as casas!). Pelo PCP segue que pelo menos dois dos $n+1$ n\'{u}meros acima devem ter o mesmo resto na divisão por $n$, digamos que $M=aa\ldots aa$ ($p$ algarismos)  e $N=aa\ldots aa$ ($q$ algarismos), com $p>q$. Então  $M-N$ é um número formado apenas por ZEROS e $a$´S.

\4\7 {\bf Problema 10.} (Primeira Questão da Terceira Fase da OBM de 2008)

\2\7 Vamos chamar de {\it garboso} o número que possui um múltiplo cujas quatro primeiras casas de sua representação decimal são 2008. Por exemplo, 7 é garboso pois 200858 é múltiplo de 7 e começa com 2008. Observe que $200858=28694\times 7$. 

\1\7 Mostre que todos os inteiros positivos são garbosos.
 
\4\7 {\bf Problema 11.}

\2\7 Sejam $A=\{n\in \mathbb{N} : \mbox{mdc}(n,10)=1\}$ e $a_{1}a_{2}\ldots a_{k}$ um n\'{u}mero com $k$ algarismos. Agora considere o
 conjunto $B=\{a_{1}a_{2}\ldots a_{k},\ a_{1}a_{2}\ldots a_{k}a_{1}a_{2}\ldots a_{k},\ a_{1}a_{2}\ldots a_{k}a_{1}a_{2}\ldots a_{k}a_{1}a_{2}\ldots a_{k},\ \ldots\}$.

\1\7 Dado $n\in \mathbb{N}$, seja $M(n)$ o conjunto dos m\'{u}ltiplos de $n$.

\1\7  Mostre que se $x\in A$, então $M(x)\cap B$ \'{e} infinito.

\4\7  {\bf Problema 12.}

\2\7 De 1${}^{\text{o}}$ de janeiro at\'{e} 31 de outubro de 2009, uma pequena livraria de João Pessoa, que abre todos os dias, vendeu no m\'{i}nimo um livro por dia e um total de 463 livros. Mostre que existiu um per\'{i}odo de dias consecutivos em que foram vendidos exatamente 144 livros.

\2\7 {\bf Solução}: Seja $a_{i}$ a quantidade de livros vendidos at\'{e} $0$ dia $i$, para $1\leq i\leq 304$. Então $1\leq a_{1}<a_{2}<\ldots<a_{304}=463$. Considere a sequencia
$ b_{i}=a_{i}+144$. Assim segue que $145\leq b_{1}<b_{2}<\ldots<b_{304}=607$. Logo $a_{i},\ b_{j}\in\{1,\ \ldots$, 607 $\}$, para todo $i,\ j\in\{1,\ \ldots$, 304 $\}$.
 Pelo Princ\'{i}pio da Casa dos Pombos, existem $i,\ j$ tais que $a_{i}=b_{j}$. Portanto $a_{i}-a_{j}=144$.

\4\7 {\bf Problema 13.}

\2\7 Dados CINCO n\'{u}meros reais arbitr\'{a}rios, mostre que existem dois deles, digamos $x$ e $y$, tais que $0\displaystyle \leq\frac{x-y}{1+xy}\leq 1$.

\2\7 {\bf Solução}: Observe que a expressão $\frac{x-y}{1+xy}$ nos faz lembrar da f\'{o}rmula $\displaystyle \tan(a-b)=\frac{\tan a-\tan b}{1+\tan a\tan b}$~. 

\2\7 Sejam $x_{1},\ x_{2},\ x_{3},\ x_{4},\ x_{5}$ os CINCO n\'{u}meros reais arbitr\'{a}rios. 

\2\7 Como a função tangente \'{e} uma bijeção do intervalo $(-\displaystyle \frac{\pi}{2},\ \frac{\pi}{2})$ e $\RR$, logo para cada $x_{i}$, existe um $a_{i}\displaystyle \in(-\frac{\pi}{2},\ \frac{\pi}{2})$, tal que $\tan a_{i}=x_{i}$. 

\2\7 Dividimos os intervalo $(-\displaystyle \frac{\pi}{2},\ \frac{\pi}{2})$ em quatro subintervalos de comprimento $\displaystyle \frac{\pi}{4}$. Pelo PCP, que existem $a_{i},\ a_{j}$ tais que $0\displaystyle \leq a_{i}-a_{j}\leq\frac{\pi}{4}$.

\2\7 Usando o fato de que a função tangente \'{e} crescente em $(-\displaystyle \frac{\pi}{2},\ \frac{\pi}{2}),\ \mathrm{e}$ a fórmula acima temos que:

\2\7 $\displaystyle \tan 0\leq\tan(a_{i}-a_{j})\leq\tan\frac{\pi}{4}$~ e~ $ 0\displaystyle \leq\frac{\tan a_{i}-\tan a_{j}}{1+\tan a_{i}\tan a_{j}}\leq 1$, ~ou seja, ~$0\displaystyle \leq\frac{x_{i}-x_{j}}{1+x_{i}x_{j}}\leq 1$.

\4\7 {\bf Problema 14.}

\2\7 Guilherme teve os olhos vendados e com uma caneta fez 50 pontos numa cartolina quadrada com lado igual a 70 cm. Mostre que existem dois pontos cuja distância \'{e} inferior a 15 cm.

\4\7 {\bf Problema 15.} Prove que se escolhermos mais do que $n$ números do conjunto $\{1, 2, \ldots, 2n\}$, então um deles será múltiplo do outro. 

\2\7 {\bf Solução}: Dado $m$ um inteiro positivo, vimos que uma consequ~encia do TFA nos diz que ele pode ser escrityo de modo único na forma $m=2^kb$, onde $k\geq 0$ e $b$ é ímpar. Denominamos $b$ a parte ímpar de $m$.

\1\7 No conjunto $\{1,2,\ldots,2n\}$ só podem existir $n$ possíveis partes ímpares diferentes: $1, 3, \ldots, 2n-1$.
Se escolhermso mais do que $n$ números nesse conjunto segue, pelo PCP, que existem dois números $r, s\in \{1,2,\ldots,2n\}$ que têm a mesma parte ímpar, ou seja, $r=2^kb$ e $s=2^tb$. O maior desses números será múltiplo do menor.

\4\7 {\bf Problema 16.} {\bf Paradoxo Gêmeo ou Problema dos Aniversários} 

\2\7  Você está assistindo um jogo de futebol e lá pelas tantas surge a seguinte questão:
 
\2\7 - ``Qual é a probabilidade de que pelo menos dois dos 22 jogadores em campo façam aniversário no mesmo dia(dia e mês)?'' (*)

\1\7 * É muito provável que você nunca tenha pensado nisso durante uma partida de futebol...

\4\7 {\bf Problema 17.} {\bf Problema dos Dois Bodes}

\2\7  Este problema é inspirado  num programa de TV americano conhecido como {\it Let's make a deal} (Vamos fazer um negócio). Nesse show, dá-se ao concorrente finalista a chance de escolher uma entre três portas. Atrás de exatamente uma das portas, está um prêmio interessante (um carro, por exemplo); as outras duas portas ocultam prêmios de valor bem inferior (um bode atrás de cada porta, por exemplo). Pede-se ao concorrente que escolha uma porta. 
A esta altura, o apresentador do show, Monty Hall, que sabe o que tem atrás de cada porta, mostra ao concorrente um dos prêmios de menor  valor atrás de uma das portas não escolhidas. Além disso, oferece ao concorrente a oportunidade de optar pela outra porta fechada. A questão é a seguinte: é vantajoso optar pela outra porta ou tanto faz? 

\4\7 {\bf Problema 18.} {\bf Problema dos Dois Bodes com apresentador Preguiçoso}

\2\7 Uma variante do problema anterior é o caso em que o concorrente escolhe inicialmente a porta em que está o prêmio maior. Nesse caso o apresentador, que sabe o que tem por trás das portas e que sempre mostra um bode, pode escolher uma entre duas portas para abrir. Nesse caso como ficam as chances do candidato, sabendo que o apresentador é preguiçoso, ou seja, que ele abrirá a porta que estiver mais próxima dele?

\4\7 {\bf Problema 19.} 

\2\7 Imagine que um prédio de quatro andares deva ser pintado
usando-se uma cor para cada andar. Sabendo que as cores utilizadas podem ser verde  e
amarelo e que andares consecutivos não poderão ser pintados de amarelo, de quantas maneiras é possível fazer a
pintura deste prédio? E se o prédio tiver $n$ andares?

\4\7 {\bf Problema 20.} 

\2\7 Uma escada tem 5 degraus. De quantas
maneiras podemos chegar ao topo, subindo um ou dois degraus de cada vez? E se a escada tiver $n$ degraus?

\4\7 Consideremos a seguinte variação da sequência de Fibonacci $F_1=1, F_2=2$ e $F_{n}=F_{n-1}+F_{n-2}$,

\1\7 para $n\geq 3$.

\4\7 {\bf Problema 21.} {\bf Sequência de Fibonacci e o Número de Ouro}

\2\7  Os objetivos deste exercício são:

\2\7 (i) Provar os seguintes resultados para a sequência definida acima:

\1 $F_1+F_3+\cdots+F_{2n-1}=F_{2n}-1$. 

\1 $F_2+F_4+\cdots+F_{2n}=F_{2n+1}-1$.

\2\7 (iii) Deduzir o seguinte resultado: Mostre que todo número inteiro positivo pode ser escrito de 

\1~ modo único como soma de termos não consecutivos da sequência $F_n$.

\2\7 (iii) Fazer a mágica com os Cartões Mágicos de Fibonacci.

\4\7 {\bf Problema 22.}

\2\7 Um conjunto de números positivos tem a propriedade do triângulo, se tiver três elementos distintos que são os comprimentos dos lados de um tringle cuja área é positivo. Considere conjuntos $\{4,5,6 ,..., n\}$ de inteiros positivos consecutivos, em que todos os subgrupos de dez elementos têm a propriedade de triângulo. Qual é o maior valor possível de $n$?

\4\7 {\bf Problema 23.} {\bf Sequência de Padovan-Perrin e o Número de Plástico}

\2\7 Um carteiro entrega cartas para dezenove casas, numeradas de 1 a 19, numa certa rua de Campina Grande. Até hoje em nenhum dia ele entregou cartas para casas consecutivas, mas dadas duas casas consecutivas, sempre havia carta para uma delas. De quantas maneiras diferentes isso pode ocorrer?


\2\7 {\bf Problema das permutações simples:} De quantos modos podemos ordenar em fila $n$ objetos?

\2\7 \underline{Resposta}: O número de permutações simples de $n$ objetos distintos, ou seja, o número de ordens em que podemos colocar $n$ objetos é $P_n=n!$.

\2\7 {\bf Problema das combinações simples:} De quantos modos podemos selecionar $k$ objetos distintos entre $n$ objetos distintos dados?

\2\7 \underline{Resposta}: O número de combinações simples de $n$ tomados $k$ a $k$, ou seja, o número de subconjuntos com $k$ elementos de um conjunto de $n$ elementos é igual a

\[C_n^k={n\choose k}=\frac{n!}{k!(n-k)!},~0\leq k\leq n~.\]

\2\7 {\bf Observação}: Seja $A=\{a_1,a_2,\ldots,a_n\}$ um conjunto com $n$ elementos. É fácil ver que a cada subconjunto de $A$ com $k$ elementos, ($0\leq k\leq n$), correponde um subconjunto com $n-k$ elementos. Portanto segue que:

\[{n\choose k}={n\choose n-k},~~\mbox{para todo}~~0\leq k\leq n~.\]


\4\7 {\bf Combinações Completas}: O número de soluções inteiras não negativas da equação 

\2\7 $x_1+x_2+\cdots +x_n=p$ é dado por $CR_n^p=C_{n+p-1}^{n-1}=C_{n+p-1}^{p}$.

\2\7 {\bf Definição}:({\it segundo dicionário Aurélio})~ {\bf Anagrama} é uma palavra ou frase formada pela transposição das letras de outra palavra ou frase.

\2\7 Anagrama: do grego ana = "voltar" ou "repetir" + graphein = "escrever".

\2\7 Um exemplo conhecido é o nome da personagem Iracema, anagrama de América, no romance de José de Alencar.



\4\7 {\bf Problema 24.} 

\2\7 Um número é dito {\it peroba} se possui pelo
menos dois dígitos vizinhos com a mesma paridade.

\2\7 Quantos números {\it perobas} de cinco dígitos existem?


\4\7 {\bf Problema 25.} 

\2\7 Dizemos que uma palavra $Q$ é {\it quase-anagrama} de outra palavra $P$ quando $Q$ pode ser obtida retirando-se uma letra de $P$ e trocando a ordem das letras
restantes, resultando em uma palavra com uma letra a menos do que $P$. Um quase-anagrama pode ter sentido em
algum idioma ou não. Por exemplo, RARO, RACR e ARCO são quase-anagramas de CARRO. Quantos são os
quase-anagramas da palavra PALAVRA que começam com A?


\4\7 {\bf Problema 26.}

\2\7 De quantas maneiras podemos colocar, em cada
espaço abaixo, um entre os algarismos 4, 5, 6, 7, 8, 9, de modo que todos os seis algarismos apareçam e
formem, em cada membro, números de dois algarismos que satisfazem a dupla desigualdade?

\2~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
{\LARGE $\underline{~~}~\underline{~~}
> \underline{~~}~\underline{~~} >\underline{~~}~\underline{~~} ~. $}

\4\7 {\bf Problema 27.} 

\2\7 No campeonato interplanetário de futebol, cada vitória vale três pontos, cada empate vale  um ponto e cada derrota vale zero ponto. Um {\it resultado} é uma
vitória, empate ou derrota. Sabe-se que o Lanoicanretni não sofreu nenhuma derrota e tem 16 pontos, mas não se sabe
quantas partidas esse time  jogou. 

\2\7 Quantas sequências ordenadas de resultados o Lanoicanretni poderia ter
obtido? Representando vitória por V, empate por E e derrota por D, duas possibilidades por exemplo, são
(V,E,E,V,E,V,V,E) e  (E,V,V,V,V,V).

\4\7 {\bf Problema 28.} 

\2\7 Esmeralda, a digitadora, tentou digitar um
número de seis algarismos, mas os dois algarismos não apareceram (a tecla devia estar com defeito). O que
apareceu foi 20046. 

\2\7 Quantos são os números de sete algarismos que ela pode ter tentado digitar?

\4\7 {\bf Problema 29.} 

\2\7 Quantos são os anagramas da palavra PERIGOSA
em que as quatro vogais aparecem em ordem alfabética? 

\1\7 (Obs.: As quatro vogais não precisam ficar em
posições consecutivas.)


\4\7 {\bf Problema 30.} 

\2\7 Cinco amigos, Arnaldo, Bernaldo, Cernaldo,
Dernaldo e Ernaldo, devem formar uma fila com outras 30 pessoas. 

\2\7 De quantas maneiras podemos formar esta
fila de modo que Arnaldo fique na frente de seus 4 amigos?  (Os amigos não precisam ficar em
posições consecutivas.)


\4\7 {\bf Problema 31.}

\2\7 A fábrica {\it Sehr Gut} produz 5 tipos de
trufas: Avelã (A), Brigadeiro (B), Chocolate(C), 

\1\7 Morango(M) e Passas (P). Essas trufas são vendidas em caixas
com 12 unidades.

\2\7 (a) Sabendo que seja possível encontrar caixas com um único
sabor ou sortido, quantas caixas 

\1 diferentes existem?

\2\7 (b) Sabendo que em cada caixa haja pelo menos uma trufa de cada
tipo, quantas caixas 

\1~ diferentes existem?

\2\7 (c) Sabendo que em cada caixa haja pelo menos três trufas de
chocolate, quantas caixas 

\1~ diferentes existem? (Não é necessário que haja todos os tipos nas caixas)

\2\7 (d) Sabendo que em cada caixa haja pelo menos três e no máximo
cinco trufas de chocolate, 

\1~ quantas caixas diferentes existem? (Não é necessário que haja todos os
tipos nas caixas)

\4\7 {\bf Problema 32.} (Oitava Questão da OBM Sênior de 1992) 

 \2\7   Em um torneio de xadrez cada jogador disputou uma partida com cada um dos demais participantes. A cada partida, havendo o empate, cada jogador ganhou 1/2 ponto; caso contrário, o vencedor ganhou 1 ponto e o perdedor  0 pontos. Participaram homens e mulheres e cada participante conquistou o mesmo número de pontos contra  homens que contra mulheres. Mostre que o número total de  participantes é um quadrado perfeito.

\2\7 {\bf Solução}: Seja $h$ o número de homens e $m$ o número de mulheres no torneio. Como em cada jogo é disputado 1 ponto, nos jogos entre h omens forma disputados ${h\choose 2}$
pontos e nos jogos entre mulheres foram disputados ${m\choose 2}$ pontos. Sejam $a$ e $b$ os pontos conquistados por homens e mulheres, respectivamente.

\2\7 Das condições do enunciado, $a={h\choose 2}$ e $b={m\choose 2}$. Como o total de jogos do torneio é ${h+m\choose 2}$,

\2\7 temos $2\left({h\choose 2}+{m\choose 2}\right)={h+m\choose 2}\Longleftrightarrow h+m=(h-m)^2$, ou seja, o total de participantes, $h+m$,

\2\7 é quadrado perfeito.

\4\7 {\bf Problema 33.} 

\2\7 O objetivo desta quest\~ao \'e provar de duas maneiras
diferentes a identidade 

\begin{equation}
\sum_{k=0}^{n} {n\choose k}={n\choose0}+{n\choose1}+{n\choose2}+
\cdots+{n\choose n}=2^n\,.
\end{equation}

\2\7 {\bf (a)}\, Aplique o Bin\^omio de Newton para a expressão
$\bigl(1+x\bigr)^n$. Faça $x=1$.

\2\7 {\bf (b)}\, Considere...

\4\7 {\bf Problema 34.} 

\2\7 O objetivo desta quest\~ao \'e provar a identidade de Lagrange

\begin{equation}
\sum_{k=0}^{n} {n\choose k}^2={n\choose0}^2+{n\choose1}^2+{n\choose2}^2+
\cdots+{n\choose n}^2={2n\choose n}\,.
\end{equation}

\2\7{\bf (a)}\, Basta mostrar que
\begin{equation}
\sum_{k=0}^{n} {n\choose k}{n\choose n-k}={n\choose0}{n\choose n}+{n\choose1}{n\choose n-1}+
{n\choose2}{n\choose n-2}+
\cdots+{n\choose n}{n\choose0}={2n\choose n}\,.
\end{equation}

\2\7 {\bf (b)}\, Considere o problema de
formar comiss\~oes de $n$ pessoas a partir de um grupo de $n$ homens e $n$
mulheres. Conte essas comiss\~oes de duas maneiras diferentes:
$^{\rm\underline{a}}$ diretamente, 2$^{\rm\underline{a}}$ dividindo em casos, conforme o n\'umero de mulheres que a comiss\~ao cont\'em.
Comparando os resultados, obtenha  nova demonstra\c{c}\~ao de (3).

\2\7 {\bf (c)}\, Aplique o Bin\^omio de Newton a
ambos os lados da igualdade
$\bigl(1+x\bigr)^{2n}=\bigl(1+x\bigr)^n\bigl(1+x\bigr)^n$.  Comparando a
express\~ao do coeficiente de $x^n$ de ambos os lados, obtenha a
identidade (3).  (usar diagramas de ruas?)

\4\7 {\bf Problema 35.} 

\2\7 O objetivo deste exerc\'{i}cio \'{e} dar duas demonstrações diferentes para a identidade
$$
\sum_{k=1}^{n}k {n\choose k}=n2^{n-1}.
$$

\2\7 {\bf (a)} {\it Demonstração combinat\'{o}ria}: Considere o conjunto de todas as poss\'{i}veis comissões tendo uma  pessoa designada para presidente, que se pode formar a partir de uma conjunto de $n$ pessoas (uma  comissão pode ter um n\'{u}mero qualquer de pessoas, de 1 a $n$). Conte este conjunto de comissões  de duas maneiras diferentes e compare os resultados. 

\2\7 {\bf Sugestão}: Um m\'{e}todo \'{e}, depois de escolhida a comissão, escolher o presidente entre seus membros.  Outro m\'{e}todo \'{e} escolher primeiro uma pessoa para ser o presidente e depois escolher o restante da  comissão. Use o fato acima: se $|B|=m$, então  $B$ possui $\displaystyle \sum_{k=0}^{m} {m\choose k}=2^{m}$ subconjuntos.

\2\7 {\bf (b)} Tome a expressão
$$
(1+x)^{n}=\sum_{k=0}^{n} {n\choose k} x^{k}
$$ que se obt\'{e}m aplicando o bin\^{o}mio de Newton, derive em relação a $x$ e substitua $x=1$.

\4\4\4\4\7 {\bf Problema 36.} 

\2\7 O objetivo deste exerc\'{i}cio \'{e} dar duas demonstrações diferentes para a identidade
$$
\sum_{k=1}^{n}k^2 {n\choose k}=n(n+1)2^{n-2}.
$$

\2\7 {\bf (a)} {\it Demonstração combinat\'{o}ria}: Considere o conjunto de todas as poss\'{i}veis comissões tendo uma  pessoa designada para presidente e uma para secretário, podendo a mesma pessoa acumular os dois cargos, que se pode formar a partir de uma conjunto de $n$ pessoas (uma  comissão pode ter um n\'{u}mero qualquer de pessoas, de 1 a $n$). Conte este conjunto de comissões  de duas maneiras diferentes e compare os resultados. 

\2\7 {\bf Sugestão}: Um m\'{e}todo \'{e}, depois de escolhida a comissão, escolher o presidente e o secretário entre seus membros.  Outro m\'{e}todo \'{e} escolher primeiro uma pessoa para ser o presidente, uma pessoa para secretário e depois escolher o restante da  comissão. Use o fato acima: se $|B|=m$, então  $B$ possui $\displaystyle \sum_{k=0}^{m} {m\choose k}=2^{m}$ subconjuntos.

\2\7 {\bf (b)} Tome a expressão
$$
(1+x)^{n}=\sum_{k=0}^{n} {n\choose k} x^{k}
$$ que se obt\'{e}m aplicando o bin\^{o}mio de Newton, derive em relação a $x$, depois multiplique a expressão obtida por $x$, derive mais uma vez em relação a $x$ e substitua $x=1$.


 \4\7 {\bf Problema 37.} 

\2\7 O objetivo deste exerc\'{i}cio \'{e} dar duas demonstrações diferentes para a identidade
$$
\sum_{k=2}^{n}k(k-1) {n\choose k}=n(n-1)2^{n-2}.
$$

\2\7 {\bf (a)} \emph{Demonstra\c{c}\~ao combinat\'oria:}
Considere o conjunto de todas as poss\'{\i}veis comiss\~oes tendo
uma  pessoa designada para presidente e outra para vice-presidente,
que se pode formar a partir de $n$  pessoas (portanto as
comiss\~oes v\~ao conter ao menos 2 pessoas). Conte essas
comiss\~oes de 2 maneiras  diferentes e compare os resultados. 

\2\7 {\bf
Sugest\~ao:} Um m\'etodo \'e, depois de escolhida a comiss\~ao, escolher o presidente e o vice-presidente  entre seus membros. Outro m\'etodo \'e escolher primeiro  uma pessoa para ser o
presidente e outra   para vice-presidente e escolher depois o
restante da  comiss\~ao. Use o fato acima: se $|B|=m$, então  $B$ possui $\displaystyle \sum_{k=0}^{m} {m\choose k}=2^{m}$ subconjuntos e a mesma ideia da quest\~ao anterior.


\2\7 {\bf (b)} Tome a express\~ao
\[
(1+x)^n=\displaystyle \sum_{k=0}^n {n \choose k} \, x^k
\]
que se obt\'em aplicando o bin\^omio de Newton, derive duas vezes
em rela\c{c}\~ao a $x$ e depois fa\c{c}a a substitu\c{c}\~ao
$x=1$.

 \4\7 {\bf Problema 38.} 

\2\7 Prove a identidade
\[
n{2n-1\choose n-1}=\sum_{k=1}^nk{n\choose k}^2 .
\]

\2\7 {\bf (a)} \emph{Demonstra\c{c}\~ao combinat\'oria:}
Dados um conjunto de $n$ homens e $n$ mulheres conte de duas
maneiras diferentes todas as comiss\~oes de $n$ pessoas com um
homem escolhido para ser o l\'{\i}der dos homens.


\2\7 {\bf (b)} \emph{Demonstra\c{c}\~ao utilizando o
bin\^omio de Newton:} Considere
\[
(1+x)^n(1+y)^n=\Bigg(\sum_{k=0}^n\binom{n}{k}x^k\Bigg) \cdot
\Bigg(\sum_{j=0}^n\binom{n}{j}y^j\Bigg)
\]

\1 derive em rela\c{c}\~ao a $x$, substitua $y=x$ e finalmente
identifique o coeficiente de $x^{n-1}$ dos dois lados da
igualdade.

\4\7 {\bf Problema 39.} ({ Olimpíada Chinesa -- 1994}) 

\2\7 O objetivo desta quest\~ao \'e provar a identidade 

\begin{equation}
{2n+1\choose n}=\sum_{k=0}^{n} 2^k {n\choose k}{n-k\choose\left\lfloor \left(n-k\right)/2\right\rfloor}.
\end{equation}

\2\7 {\it Demonstração combinat\'{o}ria}: Consideremos uma turma com $2n$ alunos, $n$ meninos e $n$ meninas, e sua professora $T$.  
Denotemos as meninas por  $a_1, a_2, ..., a_n$ e os meninos por $b_1, b_2, ..., b_n$. Para $1\leq i \leq n$, consideremos os pares de alunos $(a_i,b_i)$.
A turma tem $n$ ingressos para um jogo de futebol entre Brasil e Argentina. Consideremos o número de maneiras de encontrar $n$ pessoas entre as $2n+1$ da classe para ir para o jogo.
A resposta óbvia é ${2n+1\choose n}$. Por outro lado, nós também podemos calcular esse número da seguinte maneira...


 \4\7 {\bf Problema 40.} 

\2\7 O objetivo desta quest\~ao \'e dar tr\^es demonstra\c{c}\~oes diferentes para o fato de que
sempre que $n \geq r$  e $m \geq r$, vale a seguinte identidade
(Convolu\c{c}\~ao de Vandermonde) .

\vspace{0.3cm}

\centerline{$\displaystyle {n+m \choose r}= {n \choose 0} {m
\choose r}+{n \choose 1} {m \choose r-1}+ {n \choose 2} {m \choose
r-2}+\cdots \cdots + {n \choose r} {m \choose 0}$ }

\vspace{0.3cm}

\2\7 {\bf (a)} \emph{Demonstra\c{c}\~ao combinat\'oria:}
Sejam $A$ e $B$ dois conjuntos disjuntos com $\mid A \mid =n$ e
$\mid B\mid =m$. Considere a cole\c{c}\~ao

\centerline{$\mathcal{F}=\{C\subseteq A\cup B\mid \ \ \mid C\mid
=r \ \}$}

\vspace{0.1cm}

\noindent Conte os elementos de $\mathcal{F}$ dividindo em casos,
de acordo com quantos elementos eles t\^em em comum com $A$.

\vspace{0.2cm}

\2\7 {\bf (b)} \emph{Demonstra\c{c}\~ao utilizando o
Bin\^omio de Newton:} Considere
\[
(1+x)^{n+m}=(1+x)^n \, (1+x)^m,
\]
expanda os 3 bin\^omios, e compare o coeficiente de $x^r$ nos dois
lados da igualdade.

\vspace{0.5cm}

\2\7 {\bf (c)} O objetivo deste item \'e mostrar uma maneira
diferente de provar a mesma identidade acima: \emph{usando um
diagrama de ruas e quadras.} Para simplificar, s\'o se pede que
voc\^e fa\c{c}a um caso particular.

\vspace{0.2cm}

No diagrama de quadras e ruas abaixo, considere todos os caminhos
(de m\'{\i}nima dist\^ancia) de $O$ para $A$ (na figura, caminhos
indo sempre para cima a para a direita) e conte-os dividindo em
casos, de acordo com o ponto onde cruzam a diagonal com os pontos
marcados com quadrados, correspondendo \`as esquinas cuja
dist\^ancia de $O$ \'e 8 quadras. Considerando todos os casos
poss\'{\i}veis, obtenha um caso particular da identidade da
quest\~ao anterior.

\vspace{0.5cm}

\2\7 {\bf (d)} Novamente, dividindo todos os caminhos (de
m\'{\i}nima dist\^ancia) de $O$ para $A$ em casos, de acordo com o
ponto em que cruzam  a diagonal de pontos circulados, obtenha uma
igualdade similar \`a obtida na  parte (a).


\begin{minipage}{6.cm}

\hspace{0.2cm}
\begin{picture}(220,250)

\put(10,10){\line (1,0){120}}

\put(10,30){\line (1,0){120}}

\put(10,50){\line (1,0){120}}

\put(10,70){\line (1,0){120}}

\put(10,90){\line (1,0){120}}

\put(10,110){\line (1,0){120}}

\put(10,130){\line (1,0){120}}

\put(10,150){\line (1,0){120}}

\put(10,170){\line (1,0){120}}

\put(10,190){\line (1,0){120}}

\put(10,210){\line (1,0){120}}

\put(10,230){\line (1,0){120}}

\put(10,10){\line (0,1){220}}

\put(30,10){\line (0,1){220}}

\put(50,10){\line (0,1){220}}

\put(70,10){\line (0,1){220}}

\put(90,10){\line (0,1){220}}

\put(110,10){\line (0,1){220}}

\put(130,10){\line (0,1){220}}


\put(10,10){\circle*{5}}

\put(130,230){\circle*{5}}

\put(10,90){\circle{6}}

\put(30,70){\circle{6}}

\put(50,50){\circle{6}}

\put(70,30){\circle{6}}

\put(90,10){\circle{6}}


\put(67.5,107.5){\line (1,0){5}}

\put(67.5,107.5){\line (0,1){5}}

\put(72.5,112.5){\line (-1,0){5}}

\put(72.5,112.5){\line (0,-1){5}}


\put(87.5,87.5){\line (1,0){5}}

\put(87.5,87.5){\line (0,1){5}}

\put(92.5,92.5){\line (-1,0){5}}

\put(92.5,92.5){\line (0,-1){5}}


\put(107.5,67.5){\line (1,0){5}}

\put(107.5,67.5){\line (0,1){5}}

\put(112.5,72.5){\line (-1,0){5}}

\put(112.5,72.5){\line (0,-1){5}}


\put(127.5,47.5){\line (1,0){5}}

\put(127.5,47.5){\line (0,1){5}}

\put(132.5,52.5){\line (-1,0){5}}

\put(132.5,52.5){\line (0,-1){5}}


\put(47.5,127.5){\line (1,0){5}}

\put(47.5,127.5){\line (0,1){5}}

\put(52.5,132.5){\line (-1,0){5}}

\put(52.5,132.5){\line (0,-1){5}}


\put(27.5,147.5){\line (1,0){5}}

\put(27.5,147.5){\line (0,1){5}}

\put(32.5,152.5){\line (-1,0){5}}

\put(32.5,152.5){\line (0,-1){5}}


\put(7.5,167.5){\line (1,0){5}}

\put(7.5,167.5){\line (0,1){5}}

\put(12.5,172.5){\line (-1,0){5}}

\put(12.5,172.5){\line (0,-1){5}}


\put(3,3){\makebox(0,0){O}}

\put(140,235){\makebox(0,0){A}}

\end{picture}

\end{minipage}


 \4\7 {\bf Problema 41.} 

 \2\7  Para $k,n\ge1$ fixados, considere a pergunta: de quantas maneiras pode-se expressar

\vspace{-.5cm}

\[
x_1+x_2+x_3+\cdots+x_k=n,~~\mbox{onde os}~~ x_i~~\mbox{s\~ao inteiros n\~ao negativos?}\]



\noindent Por exemplo, de quantas maneiras pode-se escrever
$x_1+x_2+x_3=4$? Algumas possibilidades s\~ao: 1+3+0=4, 0+1+3=4,
1+2+1=4, etc.

\vspace{0.2cm}

\noindent Al\'em do m\'etodo visto em aula, \'e poss\'{\i}vel usar
um diagrama de ruas e quadras para resolver este problema. Cada
maneira de escrever $x_1+x_2+x_3+\cdots+x_k=n\,$ pode ser
visualizada como uma trajet\'oria, cada $x_i$ representando
n\'umero de passos para cima. Por exemplo,

\hspace{2.cm} \
\begin{picture}(150,150)

\put(10,10){\line (1,0){60}}

\put(10,40){\line (1,0){60}}

\put(10,70){\line (1,0){60}}

\put(10,100){\line (1,0){60}}

\put(10,130){\line (1,0){60}}

\put(10,10){\line (0,1){120}}

\put(40,10){\line (0,1){120}}

\put(70,10){\line (0,1){120}}

\thicklines

\put(9.5,10){\line (0,1){30}}

\put(10.5,10){\line (0,1){30}}

\put(10,40.5){\line (1,0){30}}

\put(10,39.5){\line (1,0){30}}

\put(39.5,40){\line (0,1){60}}

\put(40.5,40){\line (0,1){60}}

\put(40,100.5){\line (1,0){30}}

\put(40,99.5){\line (1,0){30}}

\put(69.5,100){\line (0,1){30}}

\put(70.5,100){\line (0,1){30}}

\put(10,10){\circle*{4}}

\put(70,130){\circle*{4}}

\put(1,8){\makebox(0,0){O}}

\put(79,136){\makebox(0,0){A}}

\put(110,80){\makebox(0,0){$x_1=1$}}

\put(110,60){\makebox(0,0){$x_2=2$}}

\put(110,40){\makebox(0,0){$x_3=1$}}

\put(10,-5){\makebox(0,0){$1$}}

\put(40,-5){\makebox(0,0){$2$}}

\put(70,-5){\makebox(0,0){$1$}}

\put(25,-5){\makebox(0,0){$+$}}

\put(55,-5){\makebox(0,0){$+$}}

\put(85,-5){\makebox(0,0){$=$}}

\put(100,-5){\makebox(0,0){$4$}}

\end{picture}
\ \ \ \ \ \hspace{1.cm} \
\begin{picture}(150,150)

\put(10,10){\line (1,0){60}}

\put(10,40){\line (1,0){60}}

\put(10,70){\line (1,0){60}}

\put(10,100){\line (1,0){60}}

\put(10,130){\line (1,0){60}}

\put(10,10){\line (0,1){120}}

\put(40,10){\line (0,1){120}}

\put(70,10){\line (0,1){120}}

\thicklines

\put(9.5,10){\line (0,1){30}}

\put(10.5,10){\line (0,1){30}}

\put(10,40.5){\line (1,0){30}}

\put(10,39.5){\line (1,0){30}}

\put(39.5,40){\line (0,1){90}}

\put(40.5,40){\line (0,1){90}}

\put(40,130.5){\line (1,0){30}}

\put(40,129.5){\line (1,0){30}}

\put(10,10){\circle*{4}}

\put(70,130){\circle*{4}}

\put(1,8){\makebox(0,0){O}}

\put(79,136){\makebox(0,0){A}}

\put(110,80){\makebox(0,0){$x_1=1$}}

\put(110,60){\makebox(0,0){$x_2=3$}}

\put(110,40){\makebox(0,0){$x_3=0$}}

\put(10,-5){\makebox(0,0){$1$}}

\put(40,-5){\makebox(0,0){$3$}}

\put(70,-5){\makebox(0,0){$0$}}

\put(25,-5){\makebox(0,0){$+$}}

\put(55,-5){\makebox(0,0){$+$}}

\put(85,-5){\makebox(0,0){$=$}}

\put(100,-5){\makebox(0,0){$4$}}

\end{picture}

\vspace{0.8cm}

\noindent {\bf (a)} Conte desta maneira o n\'umero de diferentes
solu\c{c}\~oes da equa\c{c}\~ao

\vspace{-.5cm}

\[x_1+x_2+x_3+x_4=7~~\mbox{onde cada}~~x_i~~\mbox{\'e inteiro com}~~x_i\geq 0?\]


\noindent {\bf (b)} Quantas diferentes combina\c{c}\~oes de moedas
de 1, 5, 10, 25 e 50 centavos pode um cofrinho conter, sabendo que
ao todo ele cont\'em 20 moedas?


 \4\7 {\bf Problema 42.} 

\2\7 Considere o lançamento de um dado $n$ vezes e seja $S$ a soma dos valores obtidos nos
lançamentos.
Seja $x_i$ o resultado obtido no $i$-ésimo lançamento.
Então o número de soluções da equação 

\vspace{-.5cm}

\[x_1 + x_2 +\cdots + x_n = S ,~~\mbox{com}~~1\leq x_i\leq 6,~~\mbox{ é igual a}~~\sum_{k=0}^{\left\lfloor \frac{S-n}{6}\right\rfloor} (-1)^k {n\choose k}{S-6k-1\choose n-1}~.\] 


\4\7 {\bf Problema 43.} 

 \2\7 Um fazendeiro que disp\~{o}e de R\$ 60.000,00
pretende gastar essa import\^{a}ncia na compra de cavalos e  bois. Sabendo cada cavalo custa R\$ 700,00 e
cada boi R\$ 650,00, obtenha uma equa\c{c}\~{a}o diofantina que 
 modele este problema.
 
 \2\7 (a) Quantas e quais são as solu\c{c}\~{o}es desse problema? 
 
 \2\7 (b) Qual o n\'{u}mero de bois e cavalos que ele deve comprar se quiser comprar a maior quantidade 

\1~ de animais?

\4\7 {\bf Problema 44.} 

\2\7 Sejam $a$ e $b$ inteiros positivos relativamente primos. Mostre que a equação $ax+by=c$ tem soluções inteiras não negativas para todo
$c>ab-a-b$. E se $c=ab-a-b$?

 \4\7 {\bf Problema 45.} 

 \2\7  (a) Um dado perfeito tem as faces marcadas com 1,1,2,2,3,3. O dado vai  ser lançado duas 

\1~ vezes. Qual a probabilidade de que a soma dos  resultados seja par?
 
 \2\7 (b) E se o dado for lançado $n$ vezes e $n$ começar a crescer, o que  acontece com esta probabilidade? 
 
 \2\7  \underline{Sugestão}: começar a calcular a  probabilidade nos casos $n=3, 4, 5$ e fazer uma conjectura.




  
  
 
  

\end{document}